Performance Comparison of Different Multicast Routing Protocols in Mobile Ad-hoc Networks

Performance Comparison of Different Multicast Routing Protocols in Mobile Ad-hoc Networks

Performance Comparison of Different Multicast Routing Protocols in Mobile Ad-hoc Networks

Abstract

A Mobile Ad-Hoc Network(MANET) represents a system of wireless mobile nodes that can freely and dynamically self organize into arbitrary and temporary network topologies without the presence of any fixed infrastructure. Limited bandwidth and a high degree of mobility require that routing protocols for MANETs be robust, simple and energy conserving. In recent years, a number of new multicast protocols of different styles have been proposed for MANETs. In this paper we investigate the performance comparison of multicast routing protocols for MANETs. The protocols have been analyzed with network simulator. In this study we evaluate them in various network scenarios.

Key Words: Mobile ad-hoc network, Multicast routing, Packet delivery ratio, Delivery efficiency, Average latency, NS-2

1. Introduction

   A mobile ad-hoc network(MANET)[1] is an autonomous collection of mobile nodes that communicates over bandwidth constrained wireless links. This network is not supported by any fixed infrastructure or central administration. The nodes are self organized and can be deployed anywhere, any time to support a particular purpose. Typically application areas of it includes battle fields, rescue sites and data acquisition in remote areas. An ad-hoc network is also useful in conventions and classrooms where participants share information dynamically.

   In a typical ad hoc environment, network hosts work in groups to carryout a given task. Hence, multicast data transfer is more predominant than unicast data transfer. In military networks, multicast

   traffic dominates due to need of group communications. Multicasting involves the transmission of a datagram to a group of zero or more hosts identified by a single destination address, and is intended for group oriented computing. The use of multicasting within MANETs has many benefits. It can improve the efficiency of wireless channel while sending multiple copies of same data to different hosts. Instead of sending data via multiple unicast, multicasting minimizes channel consumption, sender and router processing, energy consumption and delivery delay.

   Multicast routing[13] in MANETs is much more complex than in wired networks and faces several challenges. Multicast group members move, which prevent the use of a fixed infrastructure multicast topology. Various multicast protocols have been proposed to perform multicasting in ad-hoc networks. In this paper we present a simulation based performance of the different multicast routing protocols in MANETs.We provide performance analysis of four protocols with different characteristics.

   This paper is organized as follows: Section 2 presents an overview of classification of multicast routing protocols in MANETs. Section 3 provides a review of multicast protocols which we simulate. Section 4 presents the simulation environment and metrics we used in comparing of protocol performance. Section 5 provides simulation results and concluding remarks in Section 6.

2. Classification of Multicast Routing Protocols in MANETs

   1. Tree, Mesh multicast routing protocols

      Multicast routing protocols for MANETs can be classified based on how distribution paths are

      constructed among group members. According to this, existing multicast protocols for MANETs can be divided into tree based, mesh based and hybrid multicast protocols.

      Tree based protocols (e.g.,MAODV[14], ABAM[10], ADMR[8]) can be further divided into source rooted and shared tree based schemes according to the roots of the multicast trees.

      In a source rooted scheme, each source node creates a single multicast tree spanning all the members in a group. This requires a source to be aware of the topology information and addresses of all its receivers in the multicast group. In a shared tree based approach, only one multicast tree is created for a multicast group which includes all the source nodes. Each source uses this tree to initiate a multicast.

      Compared to source rooted approach, shared tree based approach is less efficient in multicast. Because in shared tree based the traffic is not evenly distributed through out the network and is aggregated on the shared tree which leads to low throughput. However in source rooted approach the traffic is evenly distributed through out the network which leads to better throughput but it has less scalability problem.

      Tree based multicast routing protocols provide high data forwarding efficiency at the expense of the low robustness.

      In a mesh based routing protocol(e.g., ODMRP[6],CAMP[15][16][17][11] a multicast

      mesh connecting a source to all receivers in the network is constructed. Route discovery and mesh building are accomplished by using broadcasting to discover routes or by using core or central points. There are multiple paths connecting the source and destination in the pair. These redundant paths provide more robustness and higher packet delivery but at the same time more overhead because of data packet duplication.

      Hybrid-based multicast routing protocols combine the advantages of both tree and mesh-based approaches. Hence, hybrid protocols address both efficiency and robustness. Using this scheme, it is possible to get multiple routing paths, and duplicate messages can reach a receiver through different

      paths. However, they may create non-optimal trees with nodes mobility.

      Figure 1: Classification of Multicast Routing Protocols

   2. Proactive and reactive multicast routing Protocols

      Another classification method is based on how routing information is acquired and maintained by mobile nodes. Using this method, multicast routing protocols can be divided into proactive routing and reactive routing.

      A proactive multicast routing protocol is called

      table-driven multicast routing protocol. In a network utilizing a proactive routing protocol, every node maintains one or more tables representing the entire topology of the network. These tables are updated regularly in order to maintain up-to-date routing information from each node to every other node. To maintain up-to-date routing information, topology information needs to be exchanged between the nodes on a regular basis, leading to relatively high overhead on the network. On the other hand, routes will always be available on request. There are some typical proactive multicast routing protocols, such as CAMP[15][16][17][11] and AMRIS[12].

      A reactive multicast routing protocol is also called on-demand multicast routing protocol. Reactive protocols seek to set up routes on-demand. If a node wants to initiate communication with a node to which it has no route, the routing protocol will try to establish such a route. Reactive multicast routing protocols have better scalability than proactive multicast routing protocols. However, when using reactive multicast routing protocols, source nodes may suffer from long delays for route searchig before they can forward data packets.

      ACMRP[3] and ABAM[10] are examples for reactive routing protocols for MANETs.

      Figure 2: Classification of Multicast Routing Protocols

   3. Source-Initiated Approach versus Receiver- Initiated Approach versus Hybrid Approach

   Based on how multicast connectivity is established and maintained, multicast routing protocols are classified into the following two approaches.

   1. The Source-Initiated approach(e.g.,ODMRP[6]), in which a multicast group is initiated and maintained by the source node (multicast group/source). The source constructs a multicast mesh or tree by flooding the network with a Join Request message. Any receiver node wishing to join a multicast group replies with a Join Reply message

   2. The Receiver-Initiated approach(e.g.,DDM[7]), in which any receiver node wishing to join a multicast group floods the network with a Join Request message searching for a route to a multicast group. The management of the membership of a multicast group is usually assigned to a core (rendezvous) node. All sources of the same multicast group share a single multicast connection.

   Some multicast protocols may not fall strictly into either of these two types of approach when they do not distinguish between source and receiver for initialization of the multicast group. Initialization is achieved either by the source or by the receiver. This type can be identified as a hybrid approach.

   Figure 3: Classification of Multicast Routing Protocols

3. Review of Multicast Routing Protocols

   1. Adhoc Multicast Routing (AMRoute)

      AMRoute [5] is a tree based protocol. It creates a multicast shared tree over mesh. It creates a bidirectional shared multicast tree using unicast tunnels to provide connections between multicast group members. Each group has at least one logical core that is responsible for member and tree maintenance. Initially, each group member declares itself as a core for its own group of size one. Each core periodically floods JOIN-REQS (using an expanding ring search) to discover other disjoint mesh segments for the group. When a member node receives a JOIN-REQ from a core of the same group but a different mesh segment, it replies with a JOIN- ACK and marks that node as a mesh neighbor. The node that receives a JOINACK also marks the sender of the packet as its mesh neighbor. After the mesh creation, each core periodically transmits TREECREATE packets to mesh neighbors in order to build a shared tree. When a member node receives a non-duplicate TREECREATE from one of its mesh links, it forwards the packet to all other mesh links. If a duplicate TREE-CREATE is received, a TREE-CREATE-NAK is sent back along the incoming link. The node receiving a TREE- CREATE-NAK marks the link s mesh link instead of tree link. The nodes wishing to leave the group send the JOIN-NAK to the neighbors and do not forward any data packets for the group.

      The key characteristic of AMRoute is its usage of virtual mesh links to establish the multicast tree. Therefore, as long as routes between tree members exist via mesh links, the tree need not be readjusted when network topology changes. Non members do not forward data packets and need not support any multicast protocol. Thus, only the member nodes that form the tree incurs processing and storage overhead. AMRoute relies on an underlying unicast protocol to maintain connectivity among member nodes and any unicast protocol can be used. The major disadvantage of the protocol is that it suffers from temporary loops and creates non-optimal trees when mobility is present.

      Table 1:Messages exchanged for AMRoute

      JOIN-REQS	To discover other disjoint mesh segments for group
      JOIN-ACK	Marks that node as a mesh neighbor
      TREE- CREATE	To build shared tree
      TREE- CREATE- NAK	If duplicate TREE-CREATE is received, a TREE-CREATE- NAK is sent back along the incoming link.
      JOIN-NAK	Nodes wishing to leave the group

   2. Adaptive Demand-Driven Multicast Routing Protocol (ADMR)

      ADMR [8] maintains a tree for every source- multicast pair. Each tree is maintained by a periodic flood of keep alive packets within the tree. The Multicast Routing state in ADMR is dynamically established and maintained only for active groups with at least one receiver and one active sender in the network. Each multicast data packet is forwarded from the sender to the receivers along the shortest delay path with the multicast forwarding state. Senders are not required to start or stop sending data to the group, or to join the group to which they wish to send. Furthermore, receivers dynamically adapt to the sending pattern of senders and mobility in the network. ADMR also detects when mobility in the network is too high to efficiently maintain the multicast routing state, and instead reverts to flooding for a short period of time if it determines that the high mobility has subsided. ADMR monitors the traffic pattern of the multicast source application, and, based on that, can detect link breaks in the tree, as well as sources that have become inactive and are no longer sending any data. In the former case, the protocol initiates local repair procedures and global repair if the local repair fails. A multicast state setup starts when a new multicast source node S starts sending to a multicast group G for which at least one receiver exists in the network, or when a receiver joins a multicast group for which there is at least one source in the network. The source node sends a multicast packet targeted at group when no routing state yet exists for this source and group. The routing layer on adds an

      ADMR header to the data packet and sends the data packet as a network flood. Each node in the network that receives this packet forwards it unless it has already forwarded a copy of it. In addition, the node records the MAC address of the node from which it received the packet in its Node Table, and the sequence number stored in the packet's ADMR header. This information will not only be used for duplicate detection but also for forwarding packets back to S. Furthermore, receivers for group G send a Receiver Join packet back toward . Every node that forwards this packet creates a forwarding entry in its Membership Table for source and group , indicating that it is a forwarder for this sender and this group. The collection of paths with forwarding state between S and the receivers for G produces the Forwarding Tree. Figure 4&5 illustrates the multicast state setup.

      Figure 4: Multicast tree construction in ADMR

      Figure 5: Multicast data forwarding in ADMR

      Table 2:Messages exchanged in ADMR

      Keep alive packet	To maintain tree
      Multicast data packet	Forwarded from sender to receiver along the shortest delay path
      ADMR header	Routing layer adds an ADMR header to the data packet
      Receiver Join	Indicating that it is a forwarder for this sender and this group

   3. Neighbor Supporting ad-hoc Multicast Routing Protocol (NSMP)

      NSMP [9] is a source-initiated multicast routing protocol, and is an extension to ODMRP [6]. A mesh is created by a source, which floods a request throughout the network. Intermediate nodes cache the upstream node information contained in the request and forward the packet after updating this field. When any receiver node receives the route discovery packets, it sends replies to its upstream nodes. Intermediate nodes receiving these replies make an entry in their routing tables and forward the replies upstream toward the source. In the case where the receiver receives multiple route discovery packets, it uses a relative weight metric (which depends on the number of forwarding and nonforwarding nodes on the path from the source to the receiver) for selecting one of the multiple routes. A path with the lowest value of relative weight is chosen. Figure 6&7 illustrates how a multicast mesh is built. In order to maintain the connectivity of the mesh, the source employs local route discoveries by periodically transmitting local requests, which are only relayed to mesh nodes and multicast neighbor nodes (nodes that are directly connected to at least one mesh node) to limit flooding, while keeping the most useful nodes informed. Any new receiver wanting to join the multicast group must wait for one of these local requests to join the desired multicast group. Replies are sent back to the source to repair broken links. Only nodes away from the source by two hops or less can join the mesh with a local request. Otherwise, they have to flood the member request.

      Figure 6: NSMP Mesh initialization

      Figure 7: NSMP Mesh creation.

      Table 3:Messages exchanged in NSMP

      Route discovery packet	Sent by sender to establish route
      Replies from receivers	The nodes which receives replies make an entry in routing tables
      Local route discoveries	To maintain connectivity of the mesh

   4. Adaptive Core Multicast Routing Protocol (ACMRP)

   ACMRP [3] is an on-demand core-based multicast routing protocol. A multicast mesh is shared by the sources of a group. A designated node, called a core, while not well known, adapts to the current network

   topology and group membership status. A multicast mesh is created and maintained by the periodic flooding of a Join Request packet which is performed by the adaptive core. When a node receives a fresh JREQ, it inserts the packet into its jreq cache and updates the route to the core. Then, it changes the upstream node address field in the packet to its own address and retransmits the packet. Group members (including multicast receivers as well as sources) send a Join Reply (JREP) packet to their upstream node on receipt of a nonduplicate JREQ packet. Upon receiving the JREP, the upstream node stores the group address, which will be used to forward multicast packets destined for the group in the future. This node is called a forwarding node. It inserts a (group address, source address) pair into the forwarding group table. Then, it sends a JREP to its own upstream node. Eventually, the JREP reaches the core. The backward propagations of JREPs construct multicast routes between group members and the core. Consequently, a multicast mesh is established. The adaptive core mechanism of ACMRP automatically handles any link failure, node failure, or network partition. Figure 8 shows an example of multicast mesh creation and packet delivery. Core broadcasts a JREQ, and group members ( , and ) send JREPs to their upstream nodes (resp., X, Core, Y, and Core). As a result, intermediate nodes (X and Y) and Core become forwarding nodes. As shown in Figure 9 a multicast mesh provides alternative multicast routes. Even if the link between and Core is broken, the packet is transferred to via.

   Figure 8: The propagation of JREP

   Figure 9: multicast packet deliveries from S1 to R1 and R2 on a link failure

   Table 4:Messages exchanged in ACMRP

   JREQ	Multicast mesh is created and maintained by sending JREQ
   JREP	Reply packet to JREQ

4. NS-2 simulator was used for performance simulation. NS-2 is originally developed by the University of California at Berkeley and the VINT project and extended to provide simulation support for ad hoc networks by the MONARCH project [18] at Carnegie Mellon University. Reference [19][4] gives a detailed description about physical layer, data link layer, and IEEE 802.11 MAC protocol used in the simulation. Recently VINT project[2] gives extensions to ns-2 simulator.

   1. Simulation environment

      Our simulation modeled a network of 50 mobile nodes that were placed randomly within 1000m x 1000m area. Radio propagation range for each node was 250 meters and channel capacity was 2 Mbits/sec. Nodes move according to the random way-point model which is characterized by a pause time. A pause time of 10 seconds was used in our simulation. Each movement scenario was made on the basis of the model. Member nodes were randomly selected. Each member node joins at the

      beginning of the simulation and remains as a member throughout the simulation. Each multicast source sends two 512-byte packets per second. We averaged 10 runs with different movement scenarios and each simulation executed for 300 seconds of simulation time.

      Table 5: Simulation Environment

      Number of Mobile nodes	50
      Area	1000 m x 1000 m
      Radio Propagation Range	250 m
      Channel capacity	2 Mbits/sec
      Pause time	10 sec

   2. We have used the following metrics in comparing protocol performance.

      Packet delivery ratio: The ratio of the number of data packets actually delivered to the destinations versus the number of data packets supposed to be received. This number presents the effectiveness of a protocol.

      Delivery efficiency : Number of data packets delivered per data packet transmitted. The term of transmitted includes transmitted by sources as well as retransmitted by intermediate nodes. The larger value indicates the smaller number of retransmission.

      Average latency : The average end-to-end delay from a transmission of the packet to a successful reception at a receiver.

5. 1. Number of source nodes

      In this experiment, the multicast group size is set constant at 10, node mobility speed is slow (1 m/s), and network traffic load is relatively light (10 pkt/sec). The number of multicast senders range in the set 5, 10, 15, 20 . Five sender represents a debate scenario, while at the other extreme, 20 senders model a video conference situation.

      Analysis:

      1. AMRoute performance was not affected by the number of senders because they use a shared tree for the multicast session.

      2. As the number of sources grows, ADMR maintain its packet delivery ratio consistently and average latency increases.

      3. NSMP shows robustness to the number of sources. In fact, performance even improves with the number of sources. Average latency increases with the number of source nodes.

      4. In ACMRP if number of source nodes increases then packet delivery ratio and delivery efficiency slightly decreases and average latency increases.

      Figure10: Packet delivery ratio vs No. of source nodes

      Figure 11: Average latency vs no. of source nodes

   2. Node speed

      Each node moved constantly with the predefined speed. Moving directions of each node were selected randomly, and when nodes reached the simulation terrain boundary,

      they bounced back and continued to move. The node movement speed was varied from 0 km/hr to 72

      km/hr. In the mobility experiment, 20 nodes are multicast members and 5 sources transmit packets at the rate of 2 pkt/sec each.

      Analysis:

      1. In AMRoute the delivery ratio steadily worsens as the mobility speed is increased. It has the highest number of transmissions because of loops.

      2. As the mobility speed increases, ADMR maintains slight increase in packet delivery ratio and consistency in delivery efficiency.

      3. NSMP shows steady packet delivery ratio and slight increase in data transmission with mobility speed i increased.

      4. In ACMRP , if the mobility speed increases then slight decrease in packet delivery ratio, Average latency and slight increase in Delivery efficiency are observed.

      Figure 12: Packet delivery ratio vs Mobility speed

      Figure 13:Delivery efficiency vs Mobility speed

      Table 6: Performance Evaluation of Protocols

      Parameters Metrics		Increase in Number of source nodes	Increase in mobility nodes
      Packet Delivery Ratio	AMRout e	Maintain Consistency	Decreases
      	ADMR	Maintain Consistency	Slightly Increases
      	NSMP	Slightly Increases	Maintain Consistency
      	ACMRP	Slightly decreases	Slightly decreases
      Delivery Efficienc y	AMRout e	Maintain Consistency	increases
      	ADMR	Maintain Consistency	Maintain Consistency
      	NSMP	Improves	Slightly Increases
      	ACMRP	Decreases	Slightly Increases
      Average Latency	AMRout e	Slightly Increases	Increases
      	ADMR	Increases	Slightly Increases
      	NSMP	Increases	Maintain Consistency
      	ACMRP	Increases	Slightly decreases

6. Conclusion

In this paper, we have conducted a performance evaluation of four multicast protocols that have been proposed for ad-hoc networks. In a mobile scenario, mesh based protocols outperformed tree based protocols.The availability of alternate routes provided robustness to mobility. AMRoute performed well under no mobility, but it suffered from loops and inefficient trees even for low mobility. ADMR shows good performance with increasing sources and shows consistency in case of high mobility. NSMP scales well with increasing group size and sources and does not show performance degradation in case of high mobility. ACMRP scales well with increasing sources and shows slight degradation in case of high mobility. We experimented with scenarios which we thought

were the most representation of ad-hoc wireless network applications. However, we did not cover every possible situation.

References:

1. Internet Engineering Task Force (IETF) Mobile AdHoc Networks (MANET) Working Group Charter.http://www.ietf.org/html.charters/manet- charter.html.

2. Kevin Fall, and Kannan Varadhan, editors, ns notes and documentation,The VINT Project, UC Berkeley, LBL, USC/ISI and Xerox PARC, Nov.2011. Available at http://www.isi.edu/nsnam/ns/ns- documentation

3. S. Park and D. Park, Adaptive core multicast routing protocol, Wireless Networks, vol. 10, no. 1, pp. 5360, 2004.

4. A Performance Comparison of On-Demand Multicast Routing Protocols for Ad Hoc Networks Jorjeta G. Jetcheva and David B. JohnsonDecember 15,2004CMU-CS-04-176 www.cs.cmu.edu/~jorjeta/Papers/CMU-CS-04- 176.pdf

5. J. Xie, R. R. Talpade, A. McAuley, and M. Liu, AMRoute: ad hoc multicast routing protocol, Mobile Networks and Applications, vol. 7, no. 6, pp. 429439, 2002.

6. S. J. Lee, W. Su, and M. Gerla, On-demand multicast routing protocol in multicast wireless mobile networks, ACM/Baltzer Mobile Networks and Applications, Vol. 7,2002, pp. 441-453

7. L. Ji and M. S. Corson, Differential destination multicast-a MANET multicast routing protocol for small groups, in Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '01), vol. 2, pp. 11921201, 2001.

8. J. G. Jetcheva and D. B. Johnson, Adaptive demand-driven multicast routing in multi-hop wireless ad hoc networks, in Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '01), pp. 3344, 2001.

1. C-K. Toh, G. Guichal, and S. Bunchua.

   ABAM: On-Demand Associativity-Based Multicast Routing for Ad Hoc Mobile Networks, IEEE Vehicular Technology Conference 2000. 52nd Volume: 3, pp. 987-993, 2000.

2. E. L. Madruga and J. J. Garcia-Luna-Aceves, Scalable multicasting: the core-asisted mesh protocol, ACM/Baltzer Mobile Networks and Applications, Vol. 6, 2000, pp.151-165

3. C. W. Wu, Y. C. Tay, and C.-K. Toh, Ad hoc Multicast Routing protocol utilizing Increasing id- numberS (AMRIS), draft-ietf-manet-amris-spec- 00.txt, 2000.

4. S. Lee, W. Su, and M. Gerla, Ad hoc wireless multicast with mobilityprediction, IEEE ICCCN 99, Boston, MA, Oct. 1999.

5. E. M. Royer, C. E. Perkins. Multicast Operation of the Ad-hoc On-Demand Distance Vector Routing Protocol, Proceeding of the fifth annual ACM/IEEE international conference on mobile computing and networking, pp. 207 -218, 1999.

6. J.J. Garcia-Luna-Aceves and E.L. Madruga,

   .The Core-Assisted MeshProtocol,. IEEE Journal on Selected Areas in Communications, vol. 17,no. 8, Aug. 1999, pp. 1380-1394.

7. J.J. Garcia-Luna-Aceves and E.L. Madruga, .A Multicast Routing Protocolfor Ad-Hoc Networks,. In Proceedings of IEEE INFOCOM'99, NewYork, NY, Mar. 1999, pp. 784-792.

8. E.L. Madruga and J.J. Garcia-Luna-Aceves,

   .Multicasting Along Meshesin Ad-Hoc Networks,. In Proceedings of IEEE ICC'99, Vancouver,Canada, Jun. 1999, pp. 314-318.

9. The CMU Monarch Projects wireless and mobility extensions to ns, The CMU Monarch Project, Aug. 1999. Available at http://www.monarch.cs.cmu.edu/.

10. J. Broch, D. A. Maltz, D. B. Johnson, Y. Hu, and J. Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the Fourth Annual ACM/IEEE InternationalConference

on Mobile Computing and Networking, ACM, Dallas, TX, Oct. 1998.