ISSN ONLINE(2320-9801) PRINT (2320-9798)
1S. Rajarajeswari, 2P.Angaiyarkanni and 3A.Arockia Selvaraj |
Related article at Pubmed, Scholar Google |
Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering
Multicast routing is an effective way to establish the group communication when the same message or the same stream of data needs to be sent to numerous receivers. Multicast routing has concerned a lot of attention in group oriented computing due to supporting data transmission from a single source node to multiple destinations parallel. The benefit of multicast routing lies in its capability of reducing the communication cost and saving the network resources by sending only one copy of the message over the shared link leading to different destinations. In general, this survey classifies the multicast routing protocols into three categories based on the underlying routing structure: treeâ€Âbased, meshâ€Âbased and stateless multicast routing protocols. It summarizes the tree based , mesh based and stateless protocols in MANET and compares their objectives, performances, merit and demerits
Keywords |
Multicast routing, mobile ad hoc network, treeâÃâ¬ÃÂbased protocol, meshâÃâ¬ÃÂbased protocol,onâÃâ¬ÃÂdemand protocol, proactive protocol |
INTRODUCTION |
Multicasting is a technique for data routing in networks that allows the same message is forwarded to a group of destinations simultaneously. In mobile ad hoc networks (MANETs), the most challenging issue in multicast routing is to effectively handle the frequent and unpredictable topology changes caused by host mobility, link breakage and host failure. Multicasting is intended for groupâÃâ¬Ã oriented computing like audio/video conferencing, collaborative works, and etc. Multicasting is an essential technology to efficiently support oneâÃâ¬ÃÂtoâÃâ¬ÃÂmany or manyâÃâ¬ÃÂtoâÃâ¬ÃÂmany applications. Multicast routing has attracted a lot of attention in the past decade, due to it allows a source to send information to multiple destinations concurrently. Multicasting is the transmission of packets to a group of zero or more hosts called multicast group which is identified by a single destination address. multicast group is a set of network clients and servers interested in sharing a specific set of data. A typical example of multicast groups is a commander and his soldiers in a battlefield. There are other examples in which multicast groups need to be established. Typically, the membership of a host group is dynamic: that is, the hosts may join and leave groups at any time. There is no restriction on the location or number of members in a host group. A host may be a member of more than one group at a time. A host does not have to be a member of a group to send packets to it. A multicast protocol has the objective of connecting members of the multicast group in an optimal way, by reducing the amount of bandwidth necessary but also considering other issues such as communication delays and reliability [1]. |
Multicast routing plays a critical role in most of the new applications such as webâÃâ¬ÃÂbase learning, video conference, and interactive multimedia games. Multicast routing in mobile ad hoc networks poses several challenges due to inherent characteristics of the network such as node mobility, reliability, and scarce resources. The main difficulty in designing a routing protocol for mobile ad hoc networks is the dynamically changing topology, due to the random movement of mobile nodes. The multicast routing protocols designed for wireless mobile ad hoc networks are fundamentally different from those for conventional infrastructure based networks in that these are selfâÃâ¬ÃÂconfiguring and formed directly by a set of mobile nodes without relying on any established infrastructure. In such networks, the heterogeneity of the hosts makes it difficult to achieve bandwidth efficiency and service flexibility |
TREE BASED MULTICAST PROTOCOLS |
In a treeâÃâ¬ÃÂbased multicast routing algorithm, a treeâÃâ¬ÃÂlike data forwarding path is constructed which is rooted at the source of the multicast session. The multicast tree is composed of a unique path from the multicast source to each of the multicast receivers. TreeâÃâ¬ÃÂbased protocols are highly efficient (efficiency is defined as ratio of the total number of data packets received by the nodes to the total number of data packet transmissions in the network) due to the absence of multiple redundant paths to the multicast source node. The main advantage of a tree as the underlying forwarding structure is that the number of forwarding nodes tends to be reduced (although not optimized). However, multicast trees form a virtual backbone which is fragile in ad hoc networks where the mobile hosts move freely anywhere. This is due to the fact that in a multicast tree there is no alternative path between the source and destination to tolerate the frequent network topology changes. TreeâÃâ¬ÃÂbased protocols primarily focus on how to construct the tree with the minimum control overhead, and involving the minimum cost. The cost metric is generally assumed the average distance of the multicast members from the multicast source. The control overhead involved in treeâÃâ¬ÃÂbased protocols is low, and the performance in terms of packet delivery ratio of such protocols, decreases as the mobility increases. The major difference between the treeâÃâ¬ÃÂbased and meshâÃâ¬ÃÂbased multicast routing protocols lies in the manner in which a multicast message is relayed. In the treeâÃâ¬ÃÂbased multicast routing protocols, each intermediate node on the tree has a wellâÃâ¬ÃÂdefined list of the nextâÃâ¬ÃÂhop nodes for a specific multicast session. It will send a copy of the received multicast message to only the neighboring nodes on its nextâÃâ¬ÃÂhop list. Figure 1 shows a sample treeâÃâ¬ÃÂlike multicast route to connect the multicast source to the multicast receivers. Neighboring nodes on its nextâÃâ¬ÃÂhop list. Figure 1 shows a sample treeâÃâ¬ÃÂlike multicast route to connect the multicast source to the multicast receivers. |
Figure 1. A TreeâÃâ¬ÃÂbased multicast route |
TreeâÃâ¬ÃÂbased multicast routing protocols can be further subdivided into groupâÃâ¬ÃÂshared tree and sourceâÃâ¬ÃÂbased tree. In both cases, multicast trees are constructed to interconnect all the members of the multicast group. Data is delivered along the tree paths to reach all the group members. The sourceâÃâ¬ÃÂbased approach maintains, for each multicast source, an individual (minimal) tree towards all its multicast receivers. SourceâÃâ¬ÃÂbased tree is separately established and maintained for each multicast source node of a multicast group. The advantage of sourceâÃâ¬ÃÂbased tree is that each multicast packet is forwarded along the most efficient (shortest) path from the source node to each multicast group member. However, this method incurs a lot of control overhead and cannot quickly adapt to the movements of the nodes in a mobile ad hoc network. Since the construction of a minimum cost tree (for each source) spanning all the members of the multicast group is expensive, some of the treeâÃâ¬Ã based multicast routing schemes use a (coreâÃâ¬ÃÂbased) groupâÃâ¬ÃÂshared tree to distribute packets from all the sources. In the groupâÃâ¬ÃÂshared tree, a single tree is constructed for the whole group (e.g., regardless the sources location). Multicast packets are distributed along this shared tree to all members of the multicast group. Since the groupâÃâ¬ÃÂshared multicast tree only permits the multicast traffic to be sent out from the root to the multicast receivers, each source must forward its multicast traffic to the root. Multicast traffic of each source is then forwarded along the shared tree. The groupâÃâ¬ÃÂshared multicast tree is a wellâÃâ¬ÃÂknown treeâÃâ¬ÃÂbased approach adopted by core based trees (CBT) [7]. A groupâÃâ¬ÃÂshared tree is a shortestâÃâ¬ÃÂpath tree rooted at some core node. The core node is also referred to as a center node or a rendezvous point. Core nodes may be chosen from some preâÃâ¬ÃÂselected set of nodes or some heuristics may be employed to select core nodes. GroupâÃâ¬ÃÂshared multicast tree is a more scalable approach than the sourceâÃâ¬ÃÂbased approach in which instead of building multiple trees for each multicast group, a single shared tree is used for all multicast source nodes. Representative group shared multicast trees are built in MAODV [6] and AMRIS [3]. |
SourceâÃâ¬ÃÂbased or groupâÃâ¬ÃÂshared, the optimal multicast tree is defined as a Steiner tree, although in some multicast routing protocols, the minimum spanning tree problem (MST) is used to model the multicast routing problem. Constrained Steiner tree problem is shown to be NPâÃâ¬ÃÂcomplete, and so several heuristics have been proposed to solve the multicast tree problem. |
2.1 Source-Based Multicast Tree |
Distance Vector Multicast Routing Protocol (DVMRP) [8] is a multicast routing protocol initially designed for wired networks. Modified version of DVMRP can be also applied for multicasting in wireless adhoc networks. DVMRP builds and maintains sourceâÃâ¬ÃÂbased trees for sending multicast messages. The sourceâÃâ¬ÃÂbased tree is created by first flooding the whole network with the multicast traffic. After that the normal prune operations are conducted. In DVMRP, when a host receives a multicast packet, it sends the packet to all attached hosts and waits for a response. Hosts with no group members return a "prune" message, which eventually prevents further multicast messages for that group from reaching the host. The prune state is soft, that is, it will timeâÃâ¬ÃÂout within a set time interval. If after sending a prune and before the state can timeâÃâ¬ÃÂout, the host wants to join the group, it has to send a "graft" message upstream. DVMRP is inefficient when the number of receivers in the group is sparsely distributed. DVMRP builds its own routing table instead of reusing the existing unicast routing table for RPF, (short for reverse path forwarding) checking of incoming packets. A packet is assumed to have arrived on the RPF interface, if a host receives it on an interface that it uses to send unicast packets to the source. If the packet arrives on the RPF interface, then host forwards it out the interfaces that are present in the outgoing interface list of a multicast routing table entry. If it does not arrive on RPF interface, it is silently discarded to avoid loopâÃâ¬ÃÂbacks. The advantage of RPF is that it does not require the host to know about spanning trees. This way, multicast adapts automatically and only is sent where it is wanted [8]. |
Akbari Torkestani and Meybodi [22] proposed a link stabilityâÃâ¬ÃÂbased multicast routing protocol for wireless MANETs in which the multicast packets are forwarded along the Steiner tree links. The weight associated with a communication link is defined as its expected duration time which is assumed to be a random variable with unknown distribution. Expected link duration time is defined as the period of time during which the link is expected to be connected, and expected duration time of a multicast route is defined as the expected duration time of the weakest link. This protocol called LLMR aims at finding the most stable multicast route against the host mobility. LLMR is composed of a number of iterations and at each iteration a multicast route is constructed by finding a Steiner tree of the network topology graph. At each iteration, the selected multicast route is rewarded, if its expected duration time is longer than those seen so far and it is penalized otherwise. As the proposed algorithm proceeds, the choice probability of the most stable multicast route converges to one. Thyagarajan and Deering [9] proposed a hierarchical distanceâÃâ¬ÃÂvector multicast routing protocol. This approach involves partitioning the multicast backbone (MBone) into nonâÃâ¬ÃÂoverlapping regions, while using DVMRP as the interâÃâ¬ÃÂregion routing protocol. MBone is a virtual network developed to run on top of the physical Internet. IntraâÃâ¬ÃÂregion routing protocol may be accomplished by any of the multicast routing protocols. Jetcheva and Johnson [10] proposed an adaptive demandâÃâ¬ÃÂdriven multicast routing algorithm called ADMR that is able to adapt its behavior based on application sending pattern, to effectively detect the link breakage, and to terminate the routes that are no longer needed. ADMR creates and maintains sourceâÃâ¬ÃÂbased forwarding trees connecting each source with the receivers of the multicast group. The multicast forwarding state for a given multicast group and a source is conceptually represented as a loosely structured multicastâÃâ¬ÃÂforwarding tree routed at the source. The forwarding mechanism is based on the shortestâÃâ¬ÃÂdelay path through the tree to the receiver members of the multicast group. In this method, packet forwarding is based on two types of flooding: tree flood and network flood. Tree flood occurs among nodes of the multicast tree, while network flood is flooding among all the nodes in the network. ADMR can detect the network mobility characteristics without requiring any global positioning system or additional control traffic. Depending on the results of such a mobility detection process, ADMR multicast source switch to the flooding for a period of time when the mobility is high, and attempt to operate efficiently with multicast again in the case of low mobility. |
Group-Shared Multicast Tree |
Multicast Ad hoc onâÃâ¬ÃÂdemand Distance Vector Routing protocol soâÃâ¬ÃÂcalled MAODV proposed by Royer and Perkins [6] maintains a shared tree for each multicast group, consisting of only receivers and relays. MAODV results from the wellâÃâ¬ÃÂknown unicast routing algorithm called AODV proposed by the same authors [11]. MAODV is an onâÃâ¬ÃÂdemand routing protocol that discovers the route only when a node has data to send. It is a hard state protocol, i.e., if a member node of a multicast group desires to terminate its group membership, it must request for termination. When the core revokes its own group membership, it selects one of its tree neighbors to become the new core. If the new core is not a group member, one of its downstream tree neighbors is selected to become the new core. This core selection process is continued until a group member is found to become the new core. When a mobile node wants to join a multicast group or send a message but does not have a route to the group, a Route Request (RREQ) is originated. All the nodes that are members of a multicast group together with the nodes that are not members of the group but their position are very critical for forwarding the multicast information, compose the tree structure. Every multicast group is identified by a unique address and group sequence numbers for tracing the freshness of the group situation. In MAODV, a node maintains multicast routing table for the group tree structure. This table contains the multicast group address, the multicast group leader address, the multicast group sequence number, hop count to the multicast group leader, next hop information and the lifetime. Nodes in a tree structure are described as downstream and upstream nodes. A downstream node is a neighborhood node, which is further from the group leader (more hop counts from the group leader). An upstream node is a neighborhood node which is nearer to the group leader (less hop counts from the group leader). It is obvious that a group leader has only downstream nodes. Whenever a node leaves the multicast group, the tree structure is pruned. If an edge in the multicast tree is broken, the downstream node of the edge is responsible for finding a path to the core and reforming the multicast tree. If this node cannot find a path to the core within a certain time period, the network is assumed to be disconnected and the subtree rooted at this node becomes another multicast tree. If it is a group member, this node then becomes the core of the newly formed multicast tree; otherwise, the core selection process is used to find the core of the newly formed multicast tree. If the network becomes connected later, the multicast trees of the same group are merged into one whose core is the same as that of the multicast tree having the largest address. |
MESH-BASED MULTICAST ROUTING PROTOCOLS |
In a meshâÃâ¬ÃÂbased multicast routing protocol, multiple routes may exist between any pair of source and destination, which is intended to enrich the connectivity among group members for better resilience against topology changes. In a meshâÃâ¬ÃÂbased multicast routing protocol, packets are distributed along the mesh structures that are a set of interconnected nodes. Route discovery and mesh building are accomplished in two ways: by using broadcasting to discover routes or by using core or central points for mesh building. MeshâÃâ¬ÃÂbased protocols perform better in high mobility situation as they provide redundant paths from source to destinations while forwarding data packets. However, meshâÃâ¬ÃÂbased approaches sacrifice multicast efficiency in comparison to treeâÃâ¬ÃÂbased approach. MeshâÃâ¬ÃÂbased protocols have high packet delivery ratios compared to treeâÃâ¬ÃÂbased protocols, but incur more control overhead in route maintenance and redundant transmission. As noted before, the major difference between the treeâÃâ¬ÃÂbased and meshâÃâ¬ÃÂbased multicast routing protocols lies in the manner in which a multicast message is relayed. In most of the meshâÃâ¬ÃÂbased multicast routing protocols, however, relaying transmission takes a more redundant approach: each node on the mesh will rebroadcast the message upon its first reception of the message. |
Lee et al. [4] designed an onâÃâ¬ÃÂdemand multicast routing protocol called ODMRP for mobile ad hoc networks. ODMRP applies onâÃâ¬ÃÂdemand routing techniques to avoid channel overhead and improve scalability. It uses the concept of forwarding group [5], a set of nodes which is responsible for forwarding multicast data on the shortest paths between any member pairs to build a forwarding mesh for each multicast group. By maintaining and using a mesh, ODMRP avoids drawbacks of multicast trees in mobile wireless networks, such as intermittent connectivity, traffic concentration, frequent tree reconfiguration, nonâÃâ¬ÃÂshortest path in a shared tree. Indeed, ODMRP uses a forwarding mesh for data distribution. ODMRP is a reactive (onâÃâ¬ÃÂdemand) protocol that delivers packets to destination(s) on a mesh topology using scoped flooding of data within the mesh. As an onâÃâ¬ÃÂdemand routing mechanism, ODMRP reduces unnecessary channel overhead. On the other side, since routes are setup on demand, delay increases. The created mesh subâÃâ¬ÃÂnetwork provides richer connectivity among multicast members compared to trees. Hence, unlike trees, frequent reconfigurations are not required. ODMRP takes a softâÃâ¬ÃÂstate approach to maintain multicast group members. No explicit control message transmission is required to leave the group. ODMRP establishes and maintains group membership and multicast routes by the source on demand. The major strengths of ODMRP are its simplicity and scalability. |
PatchODMRP [12] is one of the first derivatives of ODMRP. It uses the same procedure to construct the initial forwarding mesh structure, but it differs from ODMRP in that it take local repairing approach on detection of mesh destruction (i.e. link breakage) to avoid frequent mesh reconstructions. PoolODMRP [13] enhances route repair cost of PatchODMRP using soâÃâ¬ÃÂcalled pool nodes. The pool nodes are defined as the neighbor nodes of forwarding nodes and they collect route information by overhearing data transmission. PoolODMRP reduces local route repair overhead by using the pool nodes. Cai et al. [13] improved the performance of PoolODMRP by using a passive acknowledge scheme so as to reduce the overhead more. The new scheme is called PDAODMRP, short for Passive Data Acknowledge ODMRP. It removes MAC layer BEACON signal and detects a route breakage by the passive acknowledge while data transmitting. Due to the use of the passive acknowledge scheme, PDAODMRP local route recovery is initiated by a upstream node whereas a downstream node starts a local recovery in previous two protocols. An enhanced version of ODMRP called EâÃâ¬ÃÂODMRP was proposed by Oh et al. [15]. The efficiency, simplicity, and robustness of ODMRP render it one of the most widely used MANET multicast protocols. The main reason for robustness of ODMRP is the periodic route refreshing. ODMRP rebuilds the data forwarding mesh on a fixed interval and thus the route refresh interval is a key parameter that has critical impact on the network performance. If the route refresh rate is too high, the network will undergo too much routing overhead, wasting valuable resources. If it is too low, ODMRP cannot keep up with network dynamics. EâÃâ¬ÃÂODMRP with the refresh rate dynamically adapted to the environment adjusts the refresh interval based on the route lifetime such that the forwarding mesh is refreshed before it breaks. The Performance Enhanced OnâÃâ¬ÃÂDemand Multicast Routing Protocol (PEODMRP) [16], and the OnâÃâ¬ÃÂDemand Multicast Routing Protocol with Multipoint Relay (ODMRPâÃâ¬ÃÂMPR) [17] are some other ODMRPâÃâ¬ÃÂbased multicast protocols. PEODMRP reduces control packet overhead via limiting the transmission area of Join Query flooding. If forwarders are set within a time, it responds with Join Reply without Join Query relay. PEODMRP has advantage when multiple sources exist in the same multicast group. ODMRPMPR minimizes the broadcasting overhead by reducing duplicated packetâÃâ¬ÃÂforwarding. Only designated one hop neighbor nodes relay packets while packet transmitting. It significant reduces duplicated packet transmission but packet delivery ratio decreases in high mobility network. |
CoreâÃâ¬ÃÂAssisted Mesh Protocol (CAMP) [18] is a proactive meshâÃâ¬ÃÂbased multicast routing protocol, which establishes a multicast mesh for each multicast group. CAMP avoids the need for networkâÃâ¬ÃÂwide floods (or global flooding) from each source to maintain multicast meshes by using one or more cores per multicast group. A receiverâÃâ¬ÃÂinitiated approach is used for receivers to join a multicast group by sending unicast join requests towards a core of the desired group. To join a multicast group, a node first checks if any of its neighbors already is a member of the multicast mesh. If that is the case, the node announces a membership request to its neighboring nodes. If there are no nodes to belong the mesh, node sends a join message to one of the core node. The core nodes are not necessarily needed. Because if there is no available core nodes, an expanded ring search is used to find at least one node to belong the mesh. The drawbacks of CAMP is that it needs the preâÃâ¬ÃÂassignment of cores to groups and a unicast routing protocol to maintain routing information about the cores, and this may incur considerable overhead in a large ad hoc network. Unlike CBT [7], in which all traffic flows through the core nodes, the core nodes in CAMP are used only to limit the control traffic when the receivers are joining multicast groups. |
STATELESS MULTICAST PROTOCOLS |
In the stateless multicast protocols, the forwarding states are included in packet header, and no protocol state is maintained at any nodes except for the multicast source node. From the information included in the packet headers, any intermediate node knows how to forward or duplicate the packet. Although packing routing information together with data traffic will enlarge data packet size, it reduces the total number of control packets generated by the protocol. Besides, when the group is idle, there is no control overhead. A recent shift toward the stateless multicasting is represented by DDM, LGT and RDG. All these protocols do not require maintenance of any routing structure at the forwarding nodes. These protocols use different techniques to achieve stateless multicasting. |
In [2], a stateless multicast routing protocol termed Differential Destination Multicast (DDM) is proposed. It differs from the other approaches in two ways. First, instead of distributing membership control throughout the network, DDM concentrates this authority at the data sources (i.e., senders), thereby giving sources the knowledge of group membership. Second, differentially encoded, variableâÃâ¬Ã length destination headers are inserted in data packets, which are used in combination with unicast routing tables to forward multicast packets towards multicast receivers. In DDM, a source encapsulates a list of destination addresses in the header of each data packet it sends out. When an intermediate node receives the packet, its DDM agent queries the unicast routing protocol about which nextâÃâ¬ÃÂhop node to forward the packet toward each destination in the packet header. DDM is intended for small groups, therefore, it intrinsically excels only in horizontal scalability. When group size is large, placing the addresses of all members into the packet headers will not be efficient. The protocol has a caching mode, so that only the difference from the previous states is actually placed in the headers. However, as the forwarding set at the onâÃâ¬ÃÂroute nodes inevitably grow large, each intermediate node needs to keep routes for a large set of destinations. This poses a heavy burden on the supporting unicast protocol even under moderate mobility. |
Luo and Eugster [20] proposed another stateless multicast routing algorithm for wireless ad hoc networks called RDG, short for Route Driven Gossip. RDG uses a probabilistically controlled flooding technique, termed as gossiping, to deliver packets to all the group members. RDG relies on a unicast protocol such as DSR [21] to provide routing information, which is used for guiding the gossip process. Each node maintains the following data structures for each multicast group: a data buffer which stores data packets received, and a view which is a list of all other group member nodes known to this node. The view at each node is divided into two parts: active view, which contains the IDs of known members to which at least one routing path is known, and passive view which contains the IDs of known member to which no routing path is currently available. A node intending to join a group floods the network with a GroupâÃâ¬ÃÂRequest message. All members receiving the message update their active view. They also return a GroupâÃâ¬ÃÂReply to the request initiator with a certain probability. The initiator also updates its active view after receiving the GroupâÃâ¬ÃÂReply. Each member node periodically generates a gossip message and gossips it to a set of other nodes randomly chosen from its active view. The message includes a selected subset of the data buffer, and the sequence number of the most recent missing data packets. A group member receiving a gossip message will update its view of other group members and update its data buffer with newly received data. In responding the gossip initiator's request of recovering the missing data, the receiving node will unicast the missing data back to the initiator if the data is in its data buffer |
CONCLUSION |
Multicasting is used when the same message or the same stream of data must be forwarded to multiple destinations. Multicasting is an efficient data transmission method to support groupâÃâ¬ÃÂoriented communications in oneâÃâ¬ÃÂtoâÃâ¬ÃÂmany or manyâÃâ¬ÃÂtoâÃâ¬ÃÂmany applications such as audio/video conferencing, collaborative works, and so on. In MANETs, the most challenging issue in multicast routing is to effectively handle the frequent and unpredictable topology changes caused by host mobility, link breakage and host failure. This paper provided a survey of most recent multicast routing protocols for MANETs. This study showed that each multicast routing protocol may improve network performance in terms of delay, throughput, reliability or lifetime. Due to severe constraints of mobile wireless ad hoc networks such as host mobility, limited resources and very unreliable communication channel, single protocol or a set of protocols that can improve all these performance parameters is extremely hard to find. Selection of a multicast routing protocol is as much dependent on the nature of application, and different applications have diverse requirements. Stability against the host mobility, energy efficiency, low overhead, reliability, and scalability are several requirements for which the multicast routing protocols are designed. This survey enables the researchers to identify the strengths and weaknesses of different multicast routing protocols and helps them to choose the best one for a particular application |
References |
|