Team members: Lee, Yongzhong and Zhang, Lin
Tutor: Bae,kyle
Topic: Implementation of ODMRP protocol in Linux

Our project is about implementation of On-Demand Multicast Routing Protocol

( ODMRP ) for wireless ad-hoc network in Linux operating system. In this project report, ODMRP will be described inwith the comparison withof DVMRP (Distance Vector Multicast Routing Protocol), which is a popular multicast protocol widely used in wired network. The advantage of ODMRP in wireless environment will be emphasized. Also, some concerns, , which may lead to future work on ODMRP will be discussed. The second part will describebe the implementation of ODMRP in Llinux operating system. The general design idea will be discussed and the coding will be described at high level (abstractly). Test results will be discussed if we have it done by due date, 26, March. Lastly, what we have learned from this project will be summarized (?, "I" or "we").I will discuss briefly about the project, such as what I learned.

When a sender needs to transmit a packet to a group of receivers, multicasting becomes necessary. The reason is that when sending the same data to multiple receiivers, multicasting minimizes link bandwidth consumption, sender and receiver processing, and delivery delay. Wired network multicast routing protocols, such as DVMRP, MOSPF, PIM, CBT are all based on tree structures. The advantage of using tree structures is tha that it t the tree structure enables the efficient delivery of multicast packets by always taking the shortest pathdistance from a sender to a receiver, thus and avoiding flooding packets to the whole network. The tradeoff for this advantage gain is that the maintenance of this tree structure requires heavy storage, that is,: each node needs to maintain a routing table. This requires heavy storage. Moreover, when if the network topology changes with time, much bandwidth has to be consumed and heavy computation is needed to maintain the tree structure. Therefore, So these routing protocols perform well in environments with high bandwidth and densely distributed members, but suffer from scalability when applied in wireless environments, where the network topology changes constantly.

One multicast routing protocol, Distance Vector Multicast Routing Protocol (DVMRP), is widely used in wired networks. In this protocol, every node exchanges its routing table periodically with its neighboring nodes, and it updates its routing table based on the routing information it receivesgets from its neighbors. Therefore, tThe shortest path from itselftself to any node in the network is discovered (?by discover, you mean identify? might add "therefore" meaning by the way described in last sentence). For multicasting, oOne tree is created for oneevery multicast group and each receiver. Based on the tree structure, reverse path multicasting is performed with pruning and grafting mechanism. However, this protocol is very sensitive to mobility and suffers from scalability problem..

The wireless networks are very different from wired networks: they have their own features. First of all, wireless network has the broadcast nature of the channel, which is uncommon for the wired networks. Secondly, due to the mobility of nodes, the topology for wireless network is usually constantly changing, which makes those multicast routing protocols not feasible in wireless environment. Thirdly, wireless network has the constraints of power and bandwidth. Basing on these characteristics, multicast routing protocols for wireless network have to be robust to mobility, and with low channel and storage overhead, so that they can be scalable.

There are a couple of multicast routing protocols. One of them is On-Demand Multicast Routing Protocol (ODMRP), proposed at WAM (Wireless Adaptive Mobility) Lab in UCLA. This protocol has some very interesting features, which makes it suitable for ad-hoc wireless network. This routing protocol can be described is illustrated in Figure1 1. This protocol is independent of any unicast routing protocol and it doesn’t require any preexisting routing table. When a sender in a multicast group has data to send out, it periodically broadcasts a Join_request. This packet only contains the necessary information: hop count, multicast group IP, sender IP, sequence number and previous hop IP, which is the sender’s IP at this stage. The sender’s neighbor gets this join_request message and caches all information if the packet is not a duplicate, and forwards this join_request with some modification, mainly putting its own IP in the previous hop IP field in the join_request. On the other hand, if this neighbor is a receiver in this multicast group, it builds its so-called "join_table", and originates this join_table packet. The join_table contains the information: multicast group ID, sender IP and the next hop IP, which is the previous hop IP in the join_request packet receiver gets. If any node gets the join_table packet from its neighbor, it checks if any next hop IP matches its own IP. If there is one, this node set a forwarding flag for this multicast group and also builds its own join_table as if it was a receiver in this multicast group and broadcasts its own join_table packet and indeed this node becomes a member in the forwarding group. By this means, some nodes become to be the members for the multicast group and they are responsible for forwarding the data packets for this multicast group. As we see here, in this multicast group every receiver can be reached by every sender through one or more forwarding group members. Also, this protocol works in the case of multiple senders. 1.

TIn this protocol has some interesting features: mesh topology, forwarding group, on-demand routing and soft state., Aa mesh topology instead of a tree structure is built for each multicasting group. ThisTheis mesh topology provides richer connectivity among multicast group members, and thisits infrastructure also reduces storage overhead. As we discussed above, this protocol It uses the concept of "Forwarding Group", which is comnprised of a set of nodes responsible for forwarding multicast data, to build a forwarding mesh for each multicast group. "On-demand" routing reduces avoids channel overhead and increases scalability, (?you need to explain "on-demand" and why it avoids.......), which makes this protocol robust to mobility. Therefore, all these features ensure ODMRP is scalable to large wireless network.. Another feature in this protocol(?incomplete, you need a more detailed description of this protocol).

Comparison between of ODMRP andwith DVMRP

• Some considerations about ODMRP
• Optimization of performance
• self-adjustable "Time out" parameters
• Reliable transmission
• ACK for data delivery
• Routing rediscovery
• with very high mobility routing may need maintained
• Receiver-advertising for join/leave group
• QoS

Since ODMRP uses "soft state" concept, no explicit message is required for a receiver to join or leave Multi-cast group. This is done by twoseveral "timer out" controls, suhch as MEM_TIMEOUT and FG_TIMEOUT(?is it necessary to explain hoe it’s done), where if the timers expires, the corresponding entries in member table for the receiver and FORWARDING_GROUP_FLAG for the forwarding group member are on longer valid.. The values of these "timers out" controls are important for performaence. As we understand, these values dependend not only on the topology of the wireless network ( e.g. the size of the network ), but also on the computing power and traffic load on each mobile node. Thus, these values need to be determinated experimentally. Ideally, they can be determined and be adjustedable at run time. Therefore,So it will become more robust to build in self-adjustable mechanism for these "time out" values.

TSince this multicast protocol is not dependent on any unicast routing protocols, it may stand alone, independent ofnot relying on any underneath unicast protocol. To make it more reliable the acknowledgente(ACK) concept can be applied at IP level. Also, this reliable transmission mechanism helps report routing failures during the data transmission.

Receiver-advertising for joining/leaving group

As we discussed previously, ODMRP applies "soft state" for a receiver to join or leave multiM-cast group. This requires receivers periodically broadcast their "join" messages. T and these messages propaogate inreverseely from receivers to senders to maintain this M-cast mesh topology. The consequence for itthat is consumption on a lot of bandwidth is consumed. It seems to me that in the situation of relatively low mobility, the above mesh topology maintenance can by done by recveiver-advertising mechanism.

In the case that dDuring the data transmission stage, the routing failure occurs. This can be caused by a member with relatively high mobility in the in the forwarding group moves away. The route needs to be reconstructed. One solution can be that the sender starts advertising over again. However, if the failing location is near the receiver, then receiver- advertising can be more efficient.

It is not unreasonable to believe that QoS is hard to realized in the ad-hoc wireless networks with high mobility. However, this question can be still attacked under some constrained conditions, such as low mobility. The similar mechanism used in ABR (?define) can be applied, such that the intermeidiate node appends its information, including hop counts, relaying delay and maybe mobility information, into the sender-advertising messages. By this means, QoS may be realized with relatively low cost.

We implemented our code in the Linux because that Linux(versions from 3.0 to 4.3) is full multicast compliant and it meets all requirements to send, receive and act as a mrouter for multicast datagrams. We got source code of mrouted(DVMRP)(version 3.8.1) from parcftp.xerox.com, file pub/net-research/ipmulti/mrouted 3.8.tar.Z, which was written by Steve Deering, The mrouted program is COPYRIGHT 1989 by The Board of Trustees of Leland Standford Junior University. We modified the source code of mrouted to implement ODMRP on the wireless networks.

During the implementation there is a special multicast group, we defined in our mrouted, 224.0.0.16 for all the ODMRP routers ( Since we don't know which multicast address is still available, we just simply pick that address as our ODMRP routers address). All multicast ODMRP routers must join that group on all its multicast capable interfaces. When a multicast source has data packets to send, it periodically floods a member advertising packet. This packet is called Join_Request packet. Sender originates and sends Join_Request packets every MEM_REFRESH interval. Join_Request packet is not sent when a source does not have any multicast packets to send. When a receiver is interested in a multicast group, it gets the Join_Request packet, and reply it by its Join_Table packet. A multicast receiver originates and broadcasts a Join_Table packet every JT_REFRESH interval as long as there are any entries in its Member Table. The transmission of Join_Table is also triggered by the update of its Member Table. Each Sender IP Address and Next Hop IP Address pairs of a multicast group are contained in the Join_Table. Next Hop IP Address information can be obtained from the Message Cache entries.

In ODMRP multicast router, there are two important functions: accept_join_request() and accept_join_table().Function accept_join_request() which processes the join_request packet, when a node receives a Join_Request packet. we first check if it is a duplicate by comparing the combination of Source IP Address and Sequence Number with the entries in Message Cache. If it’s a duplicate, discard the packet. Otherwise, this node inserts an entry into message Cache with the information of the received packet (Multicast group IP Address, Sequence Number, Source IP Address, and Previous Hop IP Address). If the Hop Count field value isn't equal to or larger than TTL, the node sets the its IP address into previous Hop IP Address field and broadcasts the join_request. Also, if the node is a receiver for the multicast group, it inserts or updates the information into the Member Table, and originates a Join_Table packet and broadcasts it. The Hop Count field is increased by 1 each time a Join_Request packet passes through a node.

Function accept_join_request() processes the Join_Table. The node looks up the Next Hop IP address field of the received Join Table entries. If any entries match the node's IP address, it sets the FORWARDING_GROUP_FLAG and builds its own Join_Table. Next hop IP Address information can be obtained from the Message Cache entries. Then the node broadcasts the Join_Table packet. In Join Table packet, TTL may be set to TIME_TO_LIVE_VALUE which is not decreases by 1 each time a Join Request packet passes through a router, but should be adjusted based on network size and network diameter. Sequence number must be large enough to prevent wraparound ambiguity, and Hop count is initially set to zero.

Also, in the Multicast Data Packet Handling, nodes relay data packets only if the packets are not duplicates and the FORWARDING_GROUP_FLAG has not expired. It should be obvious that multicast traffic is handled at the transport layer with UDP, while TCP provides point-to-point connections, which is not feasible for multicast traffic. An application just needs to open a UDP socket and fill with a class D multicast address, the destination address where it wants to send data to. However, there are some operations that sending process must be able to control.

In our implementation, there are some configuration parameters which we defined in ODMRP, such as FG_TIMEOUT(480 milliseconds) which is time out interval for FORWARDING_GROUP_FLAG by each forwarding group members, JT_REFRESH(160 milliseconds) which is refresh period of sending Join Tables when there are entries in Member Table, MEM_REFRESH(400 milliseconds) which is refresh period of transmitting Join Request by a source, MEM_TIMEOUT(960 milliseconds) which is timeout interval for Member Table entries, RTE_TIMEOUT(960 milliseconds) which is timeout interval for Routing Table entries, RT_DISCV_TIMEOUT(50 seconds) which is timeout interval for discard routing table, TIME_TO_LIVE_VALUE(32 hops) which is time to live value for each packet. Some of the values should be adjusted to node's mobility speed and network size.

With ODMRP multicast, it is necessary to advise the kernel which multicast group we are interested in. That is, we have to ask kernel to join those multicast groups. Only those with a destination group previously registered via a join_Table are accepted. When a receiver is no longer interested in a multicast group, receiver just waits for time expired (there are no "Leave Group messages").

In ODMRP, a routing table is created on demand and is maintained by each node. There is no specific routing table format required by ODMRP. The routing table should include the next hop address for each destination maintained in the routing table. Therefore, we used original routing table for DVMRP.

As routed multicast datagrams can be received/sent across either physical interfaces or tunnels, a common abstraction for both is devised: VIFs, Virtual InterFaces. Mrouted passes vif structures to the kernel, indicating physical or tunnel interfaces to add to its routing tables.

Testing application:

Since there is no an application for ODMRP multicast. We just simply wrote an application to send and receive a data packer in ODMRP, which includes two programs: msender and mreceiver.

In msender, the sender first broadcasts a Join_Request Packet to its neighbours. The sender puts its IP address in the Source IP address and previous Hop IP Address field. After the sender receives Join_Table packets, it starts to broadcast a multicast data packet by UDP.

In mreceiver, Receiver is waiting for a join request packet or multicast data packet. If receiver receives a Join_Request packet, it replies with a Join_Table packet. If receiver receives a multicast data packet, it processes the data packet.

As a general principle, there is always tradeoff between the complete information about the whole network and the corresponding cost. The information about the whole network helps

3 M. Gerla, G. Pei, S. Lee and C. Chiang: On-Demand Multicast Routing Protocol (ODMRP) for Ad-Hoc Networks. Nov., 1998