Chapter 8. MULTICAST ROUTING IN AD HOC WIRELESS NETWORKS

8.1 INTRODUCTION

Ad hoc wireless networks find applications in civilian operations (collaborative and distributed computing), emergency search-and-rescue, law enforcement, and warfare situations, where setting up and maintaining a communication infrastructure may be difficult or costly. In all these applications, communication and coordination among a given set of nodes are necessary. Multicast routing protocols play an important role in ad hoc wireless networks to provide this communication. It is always advantageous to use multicast rather than multiple unicast, especially in the ad hoc environment, where bandwidth comes at a premium.

Conventional wired network Internet protocol (IP) multicast routing protocols, such as DVMRP [1], MOSPF [2], CBT [3], and PIM [4], do not perform well in ad hoc networks because of the dynamic nature of the network topology. The dynamically changing topology, coupled with relatively low bandwidth and less reliable wireless links, causes long convergence times and may give rise to formation of transient routing loops which rapidly consume the already limited bandwidth.

In a wired network, the basic approach adopted for multicasting consists of establishing a routing tree for a group of routing nodes that constitute the multicast session. Once the routing tree (or the spanning tree, which is an acyclic connected subgraph containing all the nodes in the tree) is established, a packet sent to all nodes in the tree traverses each node and each link in the tree only once. Such a multicast structure is not appropriate for ad hoc networks because the tree could easily break due to the highly dynamic topology.

Multicast tree structures are not stable and need to be reconstructed continuously as connectivity changes. Maintaining a routing tree for the purpose of multicasting packets, when the underlying topology keeps changing frequently, can incur substantial control traffic. The multicast trees used in the conventional wired network multicast protocols require a global routing sub-structure such as a link state or a distance vector sub-structure. The frequent exchange of routing vectors or link state tables, triggered by continuous topology changes, yields excessive control and processing overhead. Further, periods of routing table instability lead to instability of the multicast tree, which in turn results in increased buffering time for packets, higher packet losses, and an increase in the number of retransmissions. Therefore, multicast protocols used in static wired networks are not suitable for ad hoc wireless networks. This chapter addresses the multicast routing problem (the problem of determining which nodes in the network should participate for targeting of multicast data packets, transmitted from a source, to a select set of receivers) and presents several multicast routing protocols for ad hoc wireless networks.

8.2 ISSUES IN DESIGNING A MULTICAST ROUTING PROTOCOL

Limited bandwidth availability, an error-prone shared broadcast channel, the mobility of nodes with limited energy resources, the hidden terminal problem [5], and limited security make the design of a multicast routing protocol for ad hoc networks a challenging one. There are several issues involved here which are discussed below.

• Robustness: Due to the mobility of the nodes, link failures are quite common in ad hoc wireless networks. Thus, data packets sent by the source may be dropped, which results in a low packet delivery ratio. Hence, a multicast routing protocol should be robust enough to sustain the mobility of the nodes and achieve a high packet delivery ratio.

• Efficiency: In an ad hoc network environment, where the bandwidth is scarce, the efficiency of the multicast protocol is very important. Multicast efficiency is defined as the ratio of the total number of data packets received by the receivers to the total number of (data and control) packets transmitted in the network.

• Control overhead: In order to keep track of the members in a multicast group, the exchange of control packets is required. This consumes a considerable amount of bandwidth. Since bandwidth is limited in ad hoc networks, the design of a multicast protocol should ensure that the total number of control packets transmitted for maintaining the multicast group is kept to a minimum.

• Quality of service: One of the important applications of ad hoc networks is in military/strategic applications. Hence, provisioning quality of service (QoS) is an issue in ad hoc multicast routing protocols. The main parameters which are taken into consideration for providing the required QoS are throughput, delay, delay jitter, and reliability.

• Dependency on the unicast routing protocol: If a multicast routing protocol needs the support of a particular routing protocol, then it is difficult for the multicast protocol to work in heterogeneous networks. Hence, it is desirable if the multicast routing protocol is independent of any specific unicast routing protocol.

• Resource management: Ad hoc networks consist of a group of mobile nodes, with each node having limited battery power and memory. An ad hoc multicast routing protocol should use minimum power by reducing the number of packet transmissions. To reduce memory usage, it should use minimum state information.

8.3 OPERATION OF MULTICAST ROUTING PROTOCOLS

Based on the type of operation, multicast protocols for ad hoc wireless networks are broadly classified into two types: source-initiated protocols and receiver-initiated protocols. There exist certain other multicast protocols (such as MCEDAR [6] and AMRoute [7]) which may not strictly fall under the above two types. In this section, a general framework for understanding the operation of multicast routing protocols is discussed.

8.3.1 Source-Initiated Protocols

Figure 8.1 (a) shows the events as they occur in a source-initiated protocol that uses a soft state maintenance approach. In the soft state maintenance approach, the multicast tree or mesh is periodically updated by means of control packets. In such protocols, the source(s) of the multicast group periodically floods a JoinRequest (JoinReq) packet throughout the network. This JoinReq packet is propagated by other nodes in the network, and it eventually reaches all the receivers of the group. Receivers of the multicast group express their wish to receive packets for the group by responding with a JoinReply (JoinRep) packet, which is propagated along the reverse path of that followed by the JoinReq packet. This JoinRep packet establishes forwarding states (forwarding state refers to the information regarding the multicast group maintained at nodes in the multicast tree or mesh, which aids the nodes in forwarding multicast packets to the appropriate next-hop neighbor nodes) in the intermediate nodes (either in the tree or mesh), and finally reaches the source. Thus, this is a two-pass protocol for establishing the tree (or mesh). There is no explicit procedure for route repair. In soft state protocols, the source periodically (once every refresh period) initiates the above procedure.

Figure 8.1. Source-initiated multicast protocols.

In Figure 8.1 (b), the operation of a hard state source-initiated protocol is shown. It is similar to that of a soft state source-initiated protocol, except that there is an explicit route repair procedure that is initiated when a link break (in the tree or mesh) is detected. The route repair procedure shown in Figure 8.1 (b) is a simple solution: The upstream node which detects that one of its downstream nodes has moved away, initiates a tree construction procedure (similar to the one initiated by the source). Different protocols adopt different strategies for route repair. Some protocols choose to have the downstream node search for its former parent (in the tree or mesh) by means of limited flooding, while others impose this responsibility on the upstream node.

8.3.2 Receiver-Initiated Protocols

In the receiver-initiated multicasting protocols, the receiver uses flooding to search for paths to the sources of the multicast groups to which it belongs. The soft state variant is illustrated in Figure 8.2 (a). The tree (or mesh) construction is a three-phase process. First, the receiver floods a JoinReq packet, which is propagated by the other nodes. Usually, the sources of the multicast group and/or nodes which are already part of the multicast tree (or mesh), are allowed to respond to the JoinReq packet with a JoinRep packet, indicating that they would be able to send data packets for that multicast group. The receiver chooses the JoinRep with the smallest hop count (or some other criterion) and sends a JoinAcknowledgment (JoinAck) packet along the reverse path (taken by the JoinRep). Route maintenance is accomplished by the periodic initiation of this procedure by the receiver.

Figure 8.2. Receiver-initiated multicast protocols.

In Figure 8.2 (b), the hard state variant is illustrated. The initial tree- (or mesh-) joining phase is the same as that in the corresponding soft state protocol. The route repair mechanism comes into play when a link break is detected: The responsibility to restore the multicast topology can be ascribed to either the downstream or to the upstream node. In Figure 8.2 (b), the downstream node searches for a route to the multicast tree (or mesh) through a procedure similar to the initial topology construction procedure.

8.4 AN ARCHITECTURE REFERENCE MODEL FOR MULTICAST ROUTING PROTOCOLS

In this section, a reference model for understanding the architecture of multicast routing protocols is presented. This will aid the reader in understanding the different modules in the implementation of multicast routing protocols for ad hoc wireless networks. There are three layers in the network protocol stack concerned with multicasting in ad hoc wireless networks (The transport layer is ignored for the sake of simplicity):

1. Medium access control (MAC) layer: The important services provided by this layer to the ones above are transmission and reception of packets. This layer also arbitrates access to the channel. Apart from these functions, three other important functions are performed by this layer that are particularly important in wireless multicast: detecting all the neighbors (nodes at a hop distance of 1), observing link characteristics, and performing broadcast transmission/reception. Corresponding to these services, the MAC layer can be thought of as consisting of three principal modules:
   1. Transmission module: This module also includes the arbitration module which schedules transmissions on the channel. The exact nature of this scheduling depends on the MAC protocol. In general, the MAC protocol might maintain multicast state information based on past transmissions observed on the channel, and the scheduling is dependent on that state.
   2. Receiver module.
   3. Neighbor list handler: This module informs the higher layers whether a particular node is a neighbor node or not. It maintains a list of all the neighbor nodes. This functionality can be implemented by means of beacons or by overhearing all packets on the channel.
2. Routing layer: This layer is responsible for forming and maintaining the unicast session/multicast group. For this purpose, it uses a set of tables, timers, and route caches. The important multicast services it provides to the application layer are the functions to join/leave a multicast group and to transmit/receive multicast packets. Most of the multicast routing protocols operate in the routing layer. Other layers have been touched upon here in order to clarify the interactions in which the routing layer is involved. The routing layer uses the following components/modules:
   1. Unicast routing information handler: This serves to discover unicast routes (by an on-demand or a table-driven mechanism).
   2. Multicast information handler: This maintains all the pertinent information related to the state of the current node with respect to the multicast groups of which it is a part, in the form of a table. This state might include a list of its downstream nodes, the address of its upstream node(s), sequence number information, etc. This table might be maintained per group or per source per group.
   3. Forwarding module: This uses the information provided by the multicast information handler to decide whether a received multicast packet should be broadcast, or be forwarded to a neighbor node, or be sent to the application layer.
   4. Tree/mesh construction module: This module is used to construct the multicast topology. It can use information provided by the unicast routing information handler for this purpose; for example, this module might initiate flooding on being requested to join a group by the application layer. Also, when the application layer process (through module 10) sends session termination messages to this module, this module transmits the appropriate messages to the network for terminating the participation of the current node in the multicast session.
   5. Session maintenance module: This module initiates route repair on being informed of a link break by the lower layer. It might use information from the multicast and unicast routing tables to perform a search (possibly localized) for the node (upstream or downstream) in order to restore the multicast topology.
   6. Route cache maintenance module: The purpose of this module is to glean information from routing packets overheard on the channel for possible use later. Such information might be the addresses of nodes which have requested for a route to a multicast group source, etc. The route cache is updated as newer information is obtained from the more recent packets heard on the channel. This module is usually optional in most multicast protocols. It increases efficiency by reducing the control overhead.
3. Application layer: This layer utilizes the services of the routing layer to satisfy the multicast requirements of applications. It primarily consists of two modules:
   1. Data packet transmit/receive controller
   2. Multicast session initiator/terminator

All the above modules and the interactions between them are illustrated in Figure 8.3. The interactions between these modules can be understood by considering some actions that take place during the lifetime of a multicast session:

1. Joining a group: Module 10, which exists in the application layer, makes a request to join a group to module 5 present in the routing layer, which can use cached information from module 4 and the unicast route information from module 9. It then initiates flooding of JoinReq packets (or other mechanisms) by using module 2 of the MAC layer. These JoinReq packets are passed by module 3 of other nodes to their forwarding module, which updates the multicast table and propagates this message. During the reply phase, the forwarding states in the multicast tables of intermediate nodes are established.
2. Data packet propagation: Data packets are handled by module 11 in the application layer, which passes them on to module 8 (forwarding module), which makes the decision on whether to broadcast the packets after consulting module 7 (multicast information handler). A similar process occurs in all nodes belonging to the multicast topology until eventually the data packets are sent by the forwarding module of the receivers to the application layer.
3. Route repair: Route repair is handled by module 6 on being informed by module 1 of link breaks. It uses the unicast and multicast routing tables to graft the node back into the multicast topology.

Figure 8.3. Architectural framework of an ad hoc multicast protocol.

All modules do not operate in all the nodes at any given time. Table 8.1 indicates the different modules which are in operation at different nodes.

Table 8.1. Active modules in different nodes

8.5 CLASSIFICATIONS OF MULTICAST ROUTING PROTOCOLS

Multicast routing protocols for ad hoc wireless networks can be broadly classified into two types: application-independent/generic multicast protocols and application-dependent multicast protocols (refer to Figure 8.4). While application-independent multicast protocols are used for conventional multicasting, application-dependent multicast protocols are meant only for specific applications for which they are designed. Application-independent multicast protocols can be classified along three different dimensions.

1. Based on topology: Current approaches used for ad hoc multicast routing protocols can be classified into two types based on the multicast topology: tree-based and mesh-based. In tree-based multicast routing protocols, there exists only a single path between a source-receiver pair, whereas in mesh-based multicast routing protocols, there may be more than one path between a source-receiver pair. Tree-based multicast protocols are more efficient compared to mesh-based multicast protocols, but mesh-based multicast protocols are robust due to the availability of multiple paths between the source and receiver. Tree-based multicast protocols can be further divided into two types: source-tree-based and shared-tree-based. In source-tree-based multicast protocols, the tree is rooted at the source, whereas in shared-tree-based multicast protocols, a single tree is shared by all the sources within the multicast group and is rooted at a node referred to as the core node. The source-tree-based multicast protocols perform better than the shared-tree-based protocols at heavy loads because of efficient traffic distribution. But the latter type of protocols are more scalable. The main problem in a shared-tree-based multicast protocol is that it heavily depends on the core node, and hence, a single point failure at the core node affects the performance of the multicast protocol.
2. Based on initialization of the multicast session: The multicast group formation can be initiated by the source as well as by the receivers. In a multicast protocol, if the group formation is initiated only by the source node, then it is called a source-initiated multicast routing protocol, and if it is initiated by the receivers of the multicast group, then it is called a receiver-initiated multicast routing protocol. Some multicast protocols do not distinguish between source and receiver for initialization of the multicast group. We call these source-or-receiver-initiated multicast routing protocols.
3. Based on the topology maintenance mechanism: Maintenance of the multicast topology can be done either by the soft state approach or by the hard state approach. In the soft state approach, control packets are flooded periodically to refresh the route, which leads to a high packet delivery ratio at the cost of more control overhead, whereas in the hard state approach, the control packets are transmitted (to maintain the routes) only when a link breaks, resulting in lower control overhead, but at the cost of a low packet delivery ratio.

Figure 8.4. Classifications of multicast routing protocols.

8.6 TREE-BASED MULTICAST ROUTING PROTOCOLS

Tree-based multicasting is a well-established concept used in several wired multicast protocols to achieve high multicast efficiency. In tree-based multicast protocols, there is only one path between a source-receiver pair. The main drawback of these protocols is that they are not robust enough to operate in highly mobile environments. Tree-based multicast protocols can be classified into two types: source-tree-based multicast routing protocols and shared-tree-based multicast routing protocols (refer to Figure 8.4). In a source-tree-based protocol, a single multicast tree is maintained per source, whereas in a shared-tree-based protocol, a single tree is shared by all the sources in the multicast group. Shared-tree-based multicast protocols are more scalable compared to source-tree-based multicast protocols. By scalability, we mean the ability of the protocol to work well without any degradation in performance when the number of sources in a multicast session or the number of multicast sessions is increased. In source-tree-based multicast routing protocols, an increase in the number of sources gives rise to a proportional increase in the number of source-trees. This results in a significant increase in bandwidth consumption in the already-bandwidth-constrained network. But in a shared-tree-based multicast protocol, this increase in bandwidth usage is not as high as in source-tree-based protocols because, even when the number of sources for multicast sessions increases, the number of trees remains the same. Another factor that affects the scalability of source-tree-based protocols is the memory requirement. When the multicast group size is large with a large number of multicast sources, in a source-tree-based multicast protocol, the state information that is maintained per source per group consumes a large amount of memory at the nodes. But in a shared-tree-based multicast protocol, since the state information is maintained per group, the additional memory required when the number of sources increases is not very high. Hence shared-tree-based multicast protocols are more scalable compared to source-tree-based multicast protocols. The rest of this section describes some of the existing tree-based multicast routing protocols for ad hoc wireless networks.

8.6.1 Bandwidth-Efficient Multicast Routing Protocol

Ad hoc networks operate in a highly bandwidth-scarce environment, and hence bandwidth efficiency is one of the key design criteria for multicast protocols. Bandwidth efficient multicast routing protocol (BEMRP) [8] tries to find the nearest forwarding node, rather than the shortest path between source and receiver. Hence, it reduces the number of data packet transmissions. To maintain the multicast tree, it uses the hard state approach, that is, to rejoin the multicast group, a node transmits the required control packets only after the link breaks. Thus, it avoids periodic transmission of control packets and hence bandwidth is saved. To remove unwanted forwarding nodes, route optimization is done, which helps in further reducing the number of data packet transmissions. The multicast tree initialization phase and the tree maintenance phase are discussed in the following sections.

Tree Initialization Phase

In BEMRP, the multicast tree construction is initiated by the receivers. When a receiver wants to join the group, it initiates flooding of Join control packets. The existing members of the multicast tree, on receiving these packets, respond with Reply packets. When many such Reply packets reach the requesting node, it chooses one of them and sends a Reserve packet on the path taken by the chosen Reply packet. When a new receiver R3 (Figure 8.5) wants to join the multicast group, it floods the Join control packet. The nodes S, I1, and R2 of the multicast tree may receive more than one Join control packet. After waiting for a specific time, each of these tree nodes chooses one Join packet with the smallest hop count traversed. It sends back a Reply packet along the reverse path which the selected Join packet had traversed. When tree node I1 receives Join packets from the previous nodes I9 and I2, it sends a Reply packet to receiver R3 through node I2. The receiver may receive more than one Reply packet. In this case, it selects the Reply packet which has the lowest hop count, and sends a Reserve packet along the reverse path that the selected Reply packet had traversed. Here, in Figure 8.5, receiver R3 receives Reply packets from source S, receiver R2, and intermediate node I1. Since the Reply packet sent by intermediate node I1 has the lowest hop count (which is 3), it sends a Reserve packet to node I3, and thus joins the multicast group.

Figure 8.5. Multicast tree initialization in BEMRP.

Tree Maintenance Phase

To reduce the control overhead, in BEMRP, tree reconfiguration is done only when a link break is detected. There are two schemes to recover from link failures.

1. Broadcast-multicast scheme: In this scheme, the upstream node is responsible for finding a new route to the previous downstream node. This is shown in Figure 8.6. When receiver R3 moves from A to B, it gets isolated from the remaining part of the tree. The upstream node I3 now floods broadcast-multicast packets (with limited TTL). After receiving this packet, receiver R3 sends a Reserve packet and joins the group again.

   Figure 8.6. Multicast tree maintenance in broadcast-multicast scheme.

   

2. Local rejoin scheme: In this scheme, the downstream node of the broken link tries to rejoin the multicast group by means of limited flooding of the Join packets. In Figure 8.7, when the link between receiver R3 and its upstream node I3 fails (due to movement of node R3), then R3 floods the Join control packet with a certain TTL value (depending on the topology, this value can be tuned). When tree nodes receive the Join control packet, they send back the Reply packet. After receiving the Reply packet, the downstream node R3 rejoins the group by sending a Reserve packet to the new upstream node I4.

   Figure 8.7. Multicast tree maintenance in local rejoin scheme.

   

Route Optimization Phase

When a tree node or a receiver node comes within the transmission range of other tree nodes, then unwanted tree nodes are pruned by sending the Quit message. In Figure 8.8, when receiver R3 comes within the transmission range of the intermediate node I2, it will receive a multicast packet from node I2 earlier than from node I5. When node R3 receives a multicast packet from node I2, it sends a Reserve packet to node I2 to set up a new route directly to node I2, and sends a Quit packet to node I5. Since node R3 is no more its downstream node, node I5 sends a Quit packet to node I4, node I4 sends a Quit packet to node I3, and node I3 in turn sends a Quit packet to node I2. Thus unnecessary forwarding nodes are pruned. This mechanism helps to reduce the number of data packet transmissions.

Figure 8.8. Multicast tree optimization in BEMRP.

Advantages and Disadvantages

The main advantage of this multicast protocol is that it saves bandwidth due to the reduction in the number of data packet transmissions and the hard state approach being adopted for tree maintenance. Since a node joins the multicast group through its nearest forwarding node, the distance between source and receiver increases. This increase in distance increases the probability of path breaks, which in turn gives rise to an increase in delay and reduction in the packet delivery ratio. Also, since the protocol uses the hard state approach for route repair, a considerable amount of time is spent by the node in reconnecting to the multicast session, which adds to the delay in packet delivery.

8.6.2 Multicast Routing Protocol Based on Zone Routing

In multicast zone routing protocol (MZRP) [9], the flooding of control packets by each node which searches for members of the multicast group is controlled by using the zone routing mechanism [10]. In zone routing, each node is associated with a routing zone. For routing, a pro-active approach is used inside the zone (the node maintains the topology inside the zone, using a table-driven routing protocol), whereas a reactive approach is used across zones. In a nutshell, it attempts to combine the best of both on-demand and table-driven routing approaches.

Tree Initialization Phase

To create a multicast delivery tree over the network, the source initiates a two-stage process. In the first stage, the source tries to form the tree inside the zone, and then in the second stage it extends the tree to the entire network. In Figure 8.9, to create the tree, initially source S sends a TREE-CREATE control packet to nodes within its zone through unicast routing as it is aware of the topology within its zone, then node R1, which is interested in joining the group, replies with a TREE-CREATE-ACK packet and forms the route (for the sake of clarity, routing zones of nodes have been represented as circular regions in the figure; however, they need not always take the shape of circles). To extend the tree outside the zone, source S sends a TREE-PROPAGATE packet to all the border nodes of the zone. When node B (which is at the border of the zone of node S) receives the TREE-PROPAGATE packet, it sends a TREE-CREATE packet to each of its zone nodes. Thus receivers R2 and R3 receive the TREE-CREATE packets and join the multicast session by sending TREE-CREATE-ACK packets.

Figure 8.9. Multicast tree initialization in MZRP.

Tree Maintenance Phase

Once the multicast tree is created, the source node periodically transmits TREE-REFRESH packets down the tree to refresh the multicast tree. If any tree node does not receive a TREE-REFRESH packet within a specific time period, it removes the corresponding stale multicast route entry. When a link in the multicast tree breaks, downstream nodes are responsible for detecting link breaks and rejoining the multicast group. Due to movement of the intermediate node I (Figure 8.10), receiver R2 gets isolated from the rest of the multicast tree. Node R2 first unicasts a Join packet to all zone nodes. Since a tree node R3 is already in the zone, it replies back by sending a JoinAck to node R2. Thus receiver R2 again joins the multicast group. It may be that there are no tree nodes in the zone of receiver R2. In this case, receiver R2 does not get any reply from zone nodes, it sends JoinPropagate control packets to border nodes (node B), and it joins the tree through intermediate node I (see Figure 8.11).

Figure 8.10. Multicast tree maintenance in MZRP.

Figure 8.11. Multicast tree maintenance in MZRP.

Advantages and Disadvantages

MZRP has reduced control overhead as it runs over ZRP. The fact that the unicast and multicast routing protocols can exchange information with each other is another advantage of MZRP. MZRP is important as it shows the efficacy of the zone-based approach to multicast routing. The size of the zone is very important in MZRP. The size should be neither too large nor too small. The optimum value for the zone radius is likely to vary with multicast group size, network load conditions, etc. A disadvantage of this protocol is that a receiver node which is located far off from the source needs to wait for a long time before it can join the multicast session, because the propagation of the TREE-PROPAGATE message takes considerable time.

8.6.3 Multicast Core-Extraction Distributed Ad Hoc Routing

It is known that tree-based multicast protocols are efficient but less robust. To increase the robustness while maintaining the efficiency, a different approach is used in multicast core-extraction distributed ad hoc routing (MCEDAR) [6]. A source-tree over an underlying mesh infrastructure called mgraph is used for forwarding data packets. The CEDAR [11] architecture is used by this protocol for the mesh construction. In this architecture, a minimum dominating set (MDS), which consists of certain nodes (called core nodes) in the network, is formed using a core computation algorithm. After joining the MDS, each core node issues a piggy-backed broadcast through its beacon packet to inform its presence up to the next three hops. This process helps each core node to identify its nearby core nodes and to build virtual links. In Figure 8.12, the MDS of the ad hoc network is shown. Each non-core node is only one hop away from at least one core node and it (the non-core node) selects one of the core nodes as its dominator node. For example, node C4 is the dominator of the non-core node R3 (Figure 8.12). In addition to creating the MDS, the CEDAR architecture provides a mechanism for core broadcast based on reliable unicast, which dynamically establishes a source-tree.

Figure 8.12. JoinReq sent by dominating core node.

In Figure 8.12, when a new receiver R3 wants to join the multicast group, it requests its dominator (node C4) to transmit a JoinReq packet. The JoinReq packet consists of an option called JoinID, which is used to prevent any loop formation in the mgraph. Initially, the value of JoinID is set to infinity. When a tree node (node C1) of the multicast group receives this JoinReq packet, it replies with a JoinAck packet if its JoinID is less than the JoinID of the requesting node. Before sending the JoinAck, the node sets its own JoinID in the JoinAck packet. When an intermediate node on the reverse path receives the JoinAck packet, it decides on whether to accept or reject it based on one parameter, the robustness factor. If the number of JoinAck packets received by the intermediate node C3 is less than the robustness factor, then it accepts the JoinAck packet and adds the upstream mgraph member to its parent set; otherwise, it rejects it. Afterwards, intermediate node C3 forwards the packet to its downstream core node C4 and adds the downstream node to its child set.

Now, the dominator node C4 may receive more than one JoinAck packet from the members of the multicast group. For example, if the robustness factor is 2, and if core node C4 receives three JoinAck packets, it accepts only two JoinAcks and rejects the third. In this way, the receiver joins the multicast group. Although the mgraph for the multicast group is a mesh structure, the forwarding of data packets is done only on a source-tree due to the core broadcast mechanism (Figure 8.13). If the core node C4 loses connectivity with all its parents due to movement, then it issues a JoinReq again (with its current JoinID) and joins the multicast group. To reduce the overhead on mgraphs, optimization is performed by decoupling the control infrastructure from the data-forwarding infrastructure.

Figure 8.13. Data forwarded over source-tree.

Advantages and Disadvantages

Due to the underlying mesh structure, this multicast routing protocol is robust, and using source-tree over mesh for forwarding the data packets makes it as efficient as other tree-based multicast routing protocols. Depending on the robustness factor parameter, the dominator node of a receiver has multiple paths to the multicast session. So even if the current path breaks, the dominator node always has an alternate path to the multicast session. But the disadvantage of MCEDAR is that it is more complex compared to other multicast routing protocols. The increase in complexity may not result in a proportional increase in the performance of the protocol. When the mobility is very high, the nodes need to frequently change their core nodes, which increases the control overhead.

8.6.4 Associativity-Based Ad Hoc Multicast Routing

Associativity-based ad hoc multicast routing (ABAM) [12] is an on-demand source-tree-based multicast protocol in which a path (from source to receiver) is constructed based on link stability rather than hop distance. Hence, this multicast protocol is adaptive to the network mobility.

Tree Initialization Phase

The source node initiates the multicast tree construction phase. Joining a group is a three-step process: flooding by the source, replies along the stable path by the receivers, and path setup by the source. The tree initialization phase is illustrated in Figure 8.14. For creating the multicast tree, initially the source broadcasts a multicast broadcast query (MBQ) packet in the network to inform all potential receivers. When an intermediate node receives the MBQ packet, it appends its ID, associativity ticks [13] (the number of beacons continuously received from neighboring nodes which reflects the stability of the link), along with QoS information, to the MBQ packet, and rebroadcasts it. After receiving MBQ packets through different paths, each of the receivers R1, R2, and R3 responds by sending an MBQ-Reply packet through the most stable path. After receiving a number of MBQ-Reply packets, the source sends MC-Setup packets to all receivers in order to establish the multicast tree.

Figure 8.14. Multicast tree initialization in ABAM.

Tree Maintenance Phase

Due to the movement of the nodes, the links between nodes break frequently. ABAM uses different procedures to repair the multicast tree, depending on the type of the moved node. If a leaf receiver R3 moves and the link breaks (Figure 8.15), then the upstream node I3 of the broken link tries to find a new route to the receiver by transmitting a LocalQuery packet with the TTL field set as 1. When receiver R3 receives a LocalQuery packet from the upstream node, it replies by sending a LocalQuery-Reply message. Receiver R3 now rejoins the multicast group after receiving an MC-Setup packet from the upstream node. If the receiver fails to join the group again, then the immediate upstream node I2 of node I3 takes the responsibility of finding a route to R3 by transmitting a LocalQuery message with the TTL field value set to 2. This backtracking process terminates at branch node I1, if all previous attempts fail, or the timer (this timer is set immediately after a link failure is detected) expires at node R3. After the timer expiry, receiver R3 sends a JoinQuery packet to join the multicast group.

Figure 8.15. Multicast tree maintenance in ABAM.

When a branch node moves away, then many receivers connected through that branch node get affected. Here in Figure 8.15, when branch node I1 moves, then receivers R2 and R3 are cut off from the multicast group. In this case, the branch node I1 broadcasts a LocalQuery packet with TTL field value of 3 (the hop distance between branch node I1 and the farthest affected receiver, R3). ABAM allows a new receiver to join the multicast group (if it has not joined the multicast group at the time of tree establishment) by sending a JoinQuery packet. To leave the group, a receiver sends the Leave message to its upstream node, and that branch gets pruned if there are no other receivers on that branch.

Advantages and Disadvantages

In ABAM, the path between a source and receiver is more stable compared to other multicast protocols, and hence it achieves a higher packet delivery ratio. Also, the control overhead is less due to a fewer number of link failures. But increased hop distance between the source-receiver pair makes the protocol less efficient. When there are a lot of receivers belonging to the same multicast session close by, it results in congestion of the most stable path, which in turn may result in increased delay and reduction in the packet delivery ratio. As such, the protocol is not scalable. For scalability, it needs to employ load-balancing techniques.

8.6.5 Differential Destination Multicast Routing Protocol

The multicast protocols discussed above follow distributed group membership management and distributed multicast routing state maintenance policies. A totally different approach to ad hoc multicast routing is proposed in differential destination multicast (DDM) [14] routing protocol, which is a stateless multicast routing protocol that avoids maintaining multicast states in the nodes. It is particularly applicable where the group size is small.

Tree Initialization Phase

To join a particular multicast session, each interested destination node unicasts a Join control packet to the source. When the source receives a Join packet from a destination, it checks its validity (for security reasons) and sends an ACK control packet to the destination after storing the destination address in its member list (ML). Each destination periodically sends Join control packets to the source to show its interest in the multicast session. These Join control packets refresh the ML table at the source. The source removes stale member information if it does not receive any Join message from that particular destination for a certain time period.

Tree Maintenance Phase

DDM can operate in stateless mode as well as in soft state mode to maintain the tree. Stateless mode is straightforward, where source S inserts the destination address in a field called DDM block of the data packet and unicasts it to the next node I1, using the underlying unicast routing protocol (see Figure 8.16). When node I1 receives the data packet, it gets the next hop address from the DDM block of the received data packet and unicasts the packet to nodes I2 and I3. DDM blocks in the data packets sent to nodes I2 and I3 contain the address of destinations D1 and D2, respectively. In the soft state mode, each node along the forwarding path remembers the destination address by storing it in the forwarding set (FS). By caching this information, there is no need to list all the destination addresses in every data packet. When changes occur, the upstream node informs the downstream node about the difference through a D-type DDM block. In Figure 8.16, due to the movement of destination D2 from location A to B, D2 loses contact with I3. Since there exists an alternate route to D2 through intermediate node I2, node I1 now sends a D-type DDM block to nodes I2 and I3 informing them about the changes. To detect the loss of data packets which contain the D-type DDM block, both the upstream node and the downstream node maintain the DDM block sequence number. When there is a loss of these data packets, the downstream node sends an RSYNC message to its upstream node to get the complete list of destination addresses.

Figure 8.16. Multicast tree maintenance in DDM.

Advantages and Disadvantages

Since DDM does not maintain the multicast state, it uses minimum memory resources. Due to the centralized admission control policy, security is assured. Any shift in the location of a receiver results in the automatic rerouting of packets to its new location. But the main drawback is that it is not scalable when the multicast group size increases. DDM involves periodic control packet transmissions from the receiver nodes to the source node. This results in a significant consumption of bandwidth when the number of receivers is high. As the number of receivers increases, the size of the DDM block carried in the data packets becomes large, leading to more bandwidth consumption. Hence, this multicast protocol is suitable only when the multicast group size is small.

8.6.6 Weight-Based Multicast Protocol

The weight-based multicast (WBM) [15] protocol uses the concept of weight when deciding upon the entry point in the multicast tree where a new multicast member node is to join. Before joining a multicast group, a node takes into consideration not only the number of newly added forwarding nodes (here, forwarding nodes refers to the nodes which are currently not part of the multicast tree, but which need to be added to the tree in order to connect the new multicast receiver to the multicast session), but also the distance between the source node and itself in the multicast tree. The weight concept provides flexibility for a receiver to join either the nearest node in the multicast tree or the node nearest to the multicast source.

Tree Initialization Phase

The main aim here is to find the best point of entry for a new node joining the multicast group. A receiver-initiated approach is adopted here. When a new receiver R5 (Figure 8.17) intends to join the group, it broadcasts a JoinReq packet with a certain time-to-live (TTL) value set. These JoinReq packets are forwarded until they are received by a tree node. Consider the example illustrated in Figure 8.17. Upon receiving a JoinReq packet, a tree node for example I1, sends a JoinReply (Reply) packet. There can be several such replier nodes which send Reply packets. The Reply packet initially contains the distance of the node I1 from the source S. As Reply packets are forwarded, the count of hops taken from I1 is maintained in the Reply packet. Thus, the Reply packet upon its receipt at node R5, will have the hop distance of the node R5 from node I1 and also the hop distance of node I1 from source S. As shown in Figure 8.17 node R5 receives several Reply packets from nodes in the multicast tree. If it joins the group through node I2, then the hop distance of the receiver R5 from the source S will be only three, at the cost of two additional forwarding nodes, whereas if it joins through node I4, then no additional forwarding node needs to be added. But this is at the cost of increased hop distance, which is seven in this case. In case it joins through node I3, then the hop distance is five at the cost of only one additional forwarding node. A parameter called joinWeight is used, which tries to find the best path by considering not only the number of added forwarding nodes, but also the hop distance between the source and the receiver. After receiving a number of Reply packets, the node maintains a best reply which is updated when new Reply packets are received. The best reply minimizes the quantity, Q = (1 - joinWeight) × (hd(R5, I1) - 1) + (joinWeight × hd(R5, S)), where hd(x, y) refers to the hop distance of x from y, and joinWeight is a parameter that governs the behavior of the protocol. A timer is set upon the receipt of the first Reply packet. Once this timer expires, node R5 sends a joinConf along the reserved path that the selected Reply had traversed.

Figure 8.17. Multicast tree initialization in WBM. Reproduced with permission from [15], © IEEE, 2002.

Tree Maintenance Phase

The tree maintenance is done using a soft state approach. WBM uses a localized prediction technique. A link-life time period called TriggerHandoff is used to set the handoff process on. Each node maintains a neighbor multicast tree (NMT) table which contains tree node information such as the tree node identifier (ID) and its hop distance from the source. The node refreshes the NMTExistence timer each time it receives a data packet from a tree node. Once this timer times out, the stale tree node information is removed from the NMT table. When a downstream node receives data from its parent node, it can predict the time duration for which the parent node remains within its transmission range. On receiving data packets, if the link-life period calculated is less than the TriggerHandoff time period, then the downstream node transmits the data packet after setting on the InitiateHandoff bit in the packet. After being set, this bit indicates that the sender of the data packet requires a handoff. A neighboring node, on receiving such a data packet in the promiscuous mode,¹ sends a Handoff control packet if it has information regarding any tree member node for that multicast group in its NMT table, and if the hop distance of that tree member node from the source is less than that of the data packet sender node. The second condition avoids loop formation. When the node requiring a handoff receives many such Handoff packets, it chooses the one whose corresponding tree member node is nearest to the source, and sends a HandoffConf packet to the neighbor node. The neighbor node, on receiving this HandoffConf packet, forwards it to the tree member node so that the node in need of the handoff rejoins the multicast tree.

¹ When a node operates in the promiscuous mode, it can listen to and extract information from packets that it hears, that may not be actually intended for it.

Advantages and Disadvantages

The decision taken by newly joining nodes on the entry point to join the tree, which balances the number of additional nodes to be added to the existing multicast tree and the hop distance to the source node, results in high efficiency of the protocol. The prediction-based preventive route repair mechanism avoids path breaks and, as such, packet loss is less and packet delivery is high. The disadvantage of this scheme is that the localized prediction scheme may not work consistently well under all network conditions. There is always a finite probability that the prediction might be inaccurate, resulting in unnecessary handoffs. Further, the joinWeight parameter depends on several factors such as network load and the size of the multicast group.

8.6.7 Preferred Link-Based Multicast Protocol

The preferred link-based multicast (PLBM) protocol [16] uses a preferred link approach for forwarding JoinQuery packets. PLBM is an extension of the PLBR protocol [17] described in Chapter 7. The main concepts involved in PLBM are the selection of a set of links to neighbor nodes, called preferred links, and the use of only those links for forwarding of JoinQuery packets.

Tree Initialization Phase

PLBM is a tree-based receiver-initiated protocol. Each member node is responsible for getting connected to the multicast source. Each node maintains its two-hop local network topology information and multicast tree information in two tables: neighbors neighbors table (NNT) and connect table (CT), respectively. Every node in the network periodically transmits small control packets called beacons. On receiving each beacon, a node updates the corresponding entry in its NNT. Thus, the NNT is kept up-to-date by means of the beacon packets. When a new member wants to get connected to the multicast group, it checks if there are tree nodes (multicast source, or connected member nodes, or forwarding nodes) present in its NNT. If so, the node sends a JoinConfirm message to one of them directly without flooding any JoinQuery packet in the network. Otherwise, it initiates a JoinQuery packet transmission if at least one eligible neighbor node is present in its NNT for further forwarding of the JoinQuery packet. The eligibility of a neighbor node to further forward JoinQuery packets is determined using the preferred link-based algorithm (PLBA) (described in Section 7.7.1). The first K eligible nodes from the NNT are called preferred nodes. Only these preferred nodes are eligible for further processing of the received JoinQuery packet. The list of K preferred nodes is inserted into the preferred list (PL) field of the JoinQuery packet. The JoinQuery packet is then sent as a unicast packet to only one of the preferred nodes; all other preferred nodes receive the JoinQuery packet in the promiscuous mode.

On receiving a JoinQuery packet a node first checks its eligibility for forwarding the packet. If it is not eligible, it discards the packet. The eligibility criterion is that it should be in the PL field of the received JoinQuery packet. If an eligible node is connected to the multicast tree, it sends back a JoinReply packet to the node that originated the JoinQuery packet and starts a timer awaiting a JoinConfirm packet from that node. Otherwise, it forwards the JoinQuery using the same procedure described above. The JoinReply packet follows the route traversed by the JoinQuery packet, in the reverse order. When an intermediate node receives a JoinReply packet, a check is made to verify that the packet had not been processed already. Any processed JoinReply, identified through the multicast group ID, multicast source ID, and sequence number fields on the packet is discarded, while unprocessed JoinReply packets are forwarded. Similar to the JoinQuery transmission, the JoinReply message is transmitted using a unicast approach. All neighboring nodes process the JoinReply in their promiscuous mode and mark the JoinReply as processed. This prevents multiple JoinReply packets from reaching the JoinQuery source node (new receiver node) and also reduces the transmission of redundant JoinReply packets. When the first JoinReply reaches the JoinQuery source node, the JoinQuery source node confirms its connectivity to the sender of this JoinReply by sending back a JoinConfirm packet. Each intermediate node receiving the JoinConfirm packet marks itself as connected and forwards the JoinConfirm packet. It also stores, in its CT, the path information regarding the next two hops on both sides, obtained using the path information carried by the JoinConfirm packet. The path information toward the multicast source node and the path information toward the member node are termed uplink and downlink information, respectively.

In Figure 8.18, when node 1 wants to connect to the multicast source (node 18), it first computes the PL using PLBA. Nodes 3 and 4 are the nodes in the preferred list, as determined using PLBA. When node 3 and node 4 receive the JoinQuery packet from node 1, they in turn compute their preferred neighbors using PLBA. Node 3 sends JoinQuery to nodes 10 and 11, while node 4 forwards JoinQuery to nodes 5, 8, and 9. The JoinQuery is dropped at nodes 5 and 11 as no preferred nodes are available at these nodes. Nodes 8, 9, and 10 further forward JoinQuery to nodes 16, 16, and 9, respectively. Finally, a single JoinQuery reaches the multicast source, which then sends a JoinReply to node 1 through path 18-16-9-4-1 (path 1) [or 18-16-8-4-1 (path 2)]. Node 1 finally confirms its connectivity to the multicast source node, that is, to node 18. When member node 6 wants to connect to the multicast source, it first checks whether any tree node (forwarding nodes or connected member nodes) is in its NNT. As node 4 is a forwarding node for the multicast group, node 6 connects directly to the multicast group by sending JoinConfirm to node 4 without flooding JoinQuery. For node 12, which wants to join the multicast group, no tree nodes are present in its NNT. It initiates a JoinQuery to be flooded in a limited manner in the network using the PLBA algorithm. It forwards JoinQuery to node 13 and node 11. Nodes 13 and 11 have tree nodes in their NNTs and hence they forward JoinQuery directly to those nodes. Node 9 receives JoinQuery through node 10, forwarded by node 13. Similarly, node 4 receives JoinQuery forwarded by node 11 through node 3. Node 12 receives two JoinReply packets, one from node 4 and one from node 9. It connects to the forwarding node whose JoinReply comes first, by sending a JoinConfirm message.

Figure 8.18. Multicast tree initialization in PLBM. Reproduced with permission from [16], © IEEE, 2003.

Instead of transmitting the data packet in the broadcast mode, which is more prone to collisions, the PLBM protocol, taking advantage of the promiscuous mode support at the nodes, transmits each data packet as a unicast packet, which provides reliable data packet delivery at the cost of slightly higher processing overhead. A node piggy-backs the list of downlink nodes on each multicast data packet it transmits. This serves the following purposes. It explicitly specifies the downlink nodes that are eligible to further forward the data packet, thereby eliminating the possibility of the formation of loops. It also helps in informing nodes hearing the packet about tree nodes that are located within their neighborhood. Thirdly, it helps in removing inconsistencies in the CTs maintained at the nodes.

Tree Maintenance Phase

In the PLBM multicast protocol, link breaks can be detected in two ways. Since the PLBM protocol is beacon-based, a node can detect a link break if it has not received a beacon for a certain duration of time, called the T_CkBcon period. The selection of the T_CkBcon period is very important. If it is too long, then link break detection is delayed, resulting in loss of data packets. If it is too short, it results in detection of false link breaks as beacons are also prone to collisions. The other mechanism that is used to detect a link break is based on unicast packet transmission characteristics. Transmission of each unicast packet is preceded by the RTS-CTS control packet exchange. A link is assumed to be broken if the sender node does not receive any CTS packet in response to multiple retransmissions of RTS packets. Since in the PLBM protocol each data packet is transmitted as a unicast packet to one of the preferred neighbor nodes (other preferred nodes receive the data packet in the promiscuous mode), a link break can be detected quickly. Using the two-hop local topology information maintained in the NNT, and the two-hop tree information maintained in the CT, the broken link is bypassed quickly. The end node of the broken link toward the multicast source is termed the uplink node, while the one toward the member node is termed the downlink node. The following steps are taken by a node when it detects a link break. It deletes the neighbor (moved uplink node) and its neighbors' information from its NNT and CT. If the node is a multicast group member or has multiple downlink nodes or member nodes, the node tries to repair the tree by reconnecting to any of the tree nodes in its local two-hop topology. If no tree nodes are available, it initiates a JoinQuery and sends a StickToMe message to its downlink nodes. The purpose of this message is to maintain intact the subtree for which the current downlink node is the root. This helps in reducing the flooding of JoinQuery packets by multiple nodes when a single link breaks. If only a single downlink node is present, the node informs the single downlink member node about the link break, which then reconnects to the multicast tree as described in the tree initialization phase.

In Figure 8.18, consider the case when node 9 moves away. This causes a link break between node 16 and node 9. On detecting this link break, node 16 reroutes the data packets using the two-hop topology information from its NNT and the two-hop path information from its CT. Node 9 is bypassed, and the new path between multicast source node 18 and receiver node 1 is 18-16-8-4-1. When node 10 is connected to the tree through node 9 and does not receive data packets for a specified waiting period, it assumes a link break. Each forwarding node tries to locally repair the tree using its NNT and CT information. In case no tree node is present in its NNT and more than one downlink node is present in its CT, it broadcasts the JoinQuery packet. Otherwise, the link break information is propagated to the corresponding receiver node (node 12). Node 12 refloods the JoinQuery using PLBA algorithm in order to reconnect to the multicast tree.

Advantages and Disadvantages

The PLBM protocol makes use of two-hop local topology information for efficient multicast routing. PLBM provides better flexibility and adaptability through the preferred link concept. The criterion for selecting the preferred list need not be restricted to the neighbor degree alone (PLBA algorithm); any other node or link characteristic (such as link stability, link load, residual bandwidth, and link delay) can be used for computing the preferred links. One of the shortcomings of PLBM is the usage of periodic beacons. Transmission of periodic beacons by each and every node in the network incurs significant control overhead in the already bandwidth-constrained ad hoc wireless networks.

Preferred Link-Based Unified Routing Protocol

The preferred link-based unified routing protocol (PLBU) [18], which is an extension of the PLBM protocol described above, is the only known protocol of its kind to date. PLBU routes both unicast as well as multicast traffic simultaneously in a transparent manner. Using separate unicast and multicast routing protocols has several disadvantages. The actual traffic in an ad hoc wireless network consists of simultaneous unicast and multicast sessions. Separate unicast and multicast protocols generate separate overheads/control packets; the overheads which are redundant in most cases lead to wastage of bandwidth and decrease in the overall efficiency of the system. A unicast session (e.g., a voice session) may need to be converted into a multicast session at any time. This would be very complex if separate unicast and multicast protocols are used. PLBU overcomes the above disadvantages. PLBU handles unicast as well as multicast traffic seamlessly. The advantages of a unified approach are as follows. The need for a separate protocol for each type of traffic is eliminated, which reduces complexity and the memory requirements in resource-constrained ad hoc wireless networks. The path established by multicast sessions can be used by unicast sessions, and vice versa. This reduces the control overhead in the network.

PLBU has two phases: connect phase and reconfiguration phase. For a unicast session, the source node initiates the connect phase for getting connected to the destination node, whereas for a multicast session, receiver nodes invoke the connect phase in order to connect to the multicast source. A node that initiates a connect phase is termed ConnectSource node. A receiver-initiated approach is used for multicast tree construction. It is performed in the same manner as is done in PLBM. In the connect phase, the ConnectSource node finds a route to the appropriate destination node, which is the multicast source for a multicast session and the final destination node for a unicast session. During the connect phase, the ConnectSource node initiates the transmission of RouteProbe packets. For a unicast session, only the destination node is allowed to respond to this RouteProbe packet. In case of a multicast session, any multicast tree node receiving the RouteProbe can send back a RouteReply packet. This RouteReply packet is received by the ConnectSource node. For a unicast session, the ConnectSource node immediately starts transmission of data packets. In case of a multicast session, the ConnectSource node, on receiving the RouteReply packet, transmits a ConnectConfirm, and gets connected to the multicast group. Once route establishment gets completed, the actual data transfer can begin.

PLBU does not differentiate between unicast and multicast traffic, and hence it finds routes for both types of sessions in almost the same way. The only difference is that the multicast connect session has to confirm the connectivity to one of the tree nodes as it may receive RouteReply packets from many tree nodes. This difference is also eliminated if only the multicast source is allowed to send a reply to the RouteProbe packet, but this is at the cost of high control overhead. The transmission of data packets is also done in the same manner for both types of traffic. Source routing is not used; the data packet is transmitted in a hop-by-hop manner. A data packet carries the path it has traversed so far. This traversed path information is used by the intermediate nodes to refresh their existing route cache entries. This refreshing helps in maintaining an up-to-date view of the path in the route cache tables of the intermediate nodes. The cache table is used by multicast sessions to obtain paths to the multicast source nodes, thereby helping in reducing the control overhead. The routing of a data packet is done as follows. The source node sends the data packet to the next node, the address of which is obtained from the route cache table. The reason for not using source routing is to maintain homogeneity while routing data packets for multicast sessions, where source routing is not possible. As mentioned above, the data packet carries the path traversed by it so far. After receiving a data packet, a forwarding node appends its address to the traversed path field of the packet, and forwards the packet to the next hop node, the identifier (ID) of which is available in the route cache table. Data packets belonging to multicast sessions are also routed in the same way. When a data packet transmitted by the source arrives at an intermediate node, it is forwarded as a unicast packet. The data packet carries the list of nodes to which it is intended. All downlink nodes process the data packet in the promiscuous mode. This list carried by the data packet gives the intermediate nodes information about the current multicast session and thereby helps in removing inconsistencies in the multicast tree information maintained at the node.

PLBU makes use of the route cache. The main motivation behind maintaining route cache information is to reduce the control overhead. Lack of route cache information at intermediate nodes does not affect the functioning of PLBU. It is just an enhancement made to the protocol for reducing control overhead. The key information that PLBU maintains about any session at the intermediate nodes is the two-hop path information toward both the sender and the receiver, which is used to quickly reconfigure a broken path.

Dynamic movement of nodes in an ad hoc wireless network causes frequent link breaks. Such broken links are dealt with in the reconfiguration phase. These link breaks, if not repaired locally, result in the flooding of RouteProbe packets by the ConnectSource nodes for reestablishing the path. Local route repair can be performed if the local topology information is available at each node. The usual approach is to inform the source node(s) about the link break, which floods the network and finds alternate paths. The other approaches are to bypass the broken link by using the local one-hop topology information regarding nearby alternate nodes, or to use a local broadcast route maintenance scheme. Since in PLBU the two-hop local topology information is maintained, the broken link is bypassed efficiently.

As mentioned above, the PLBU protocol offers several advantages over separate unicast and multicast routing. The unified approach makes minimum differentiation between unicast and multicast traffic and is very suitable for practical networks where both unicast and multicast traffic are generated simultaneously.

8.6.8 Multicast Ad Hoc On-Demand Distance Vector Routing Protocol

Multicast ad hoc on-demand distance vector (MAODV) routing protocol [19], [20] is an extension of the AODV [21] protocol. MAODV adds multicast capability to the AODV protocol; multicast, unicast, and broadcast features have been streamlined into MAODV. MAODV uses sequence numbers to ensure that the most recent route to the multicast group is used.

Tree Initialization Phase

MAODV uses the notion of a group leader which updates the sequence number of the group periodically and broadcasts it using group hellos (GRPHs). The group leader is typically the first node to join the group. Nodes which wish to join the group, if they have the address of the group leader (recorded by the node when the group leader joined the group), unicast a route request (RREQ) to the group leader. If they do not have any record of the address of the leader for the group, they broadcast a RREQ packet. This RREQ is rebroadcast by nodes which are not members of the multicast tree (which also establish the reverse path and keep the state information consisting of the group address, requesting node id, and next-hop information). The RREQ is answered with a route reply (RREP) by a member of the multicast group. This RREP, containing the distance of the replying node from the group leader and the current sequence number of the multicast group, is unicast to the requesting node (which establishes the forward path). Note that only the nodes which have recorded a sequence number greater than that in the RREQ packet can reply. The receiver node selects the most recent and the shortest path from all the RREPs it receives and sends a multicast activation (MACT) message. MACT confirms to the intermediate relaying nodes that they are part of the tree. Only after an MACT is received is the forward path, established during the RREP propagation, activated. Nodes that wish to send data to the source use a similar procedure, which differs from the previously outlined procedure in only one respect: Any node with a recent (in terms of sequence numbers) route to the multicast group can reply to a non-join RREQ. In Figure 8.19, R3 attempts to join the multicast tree rooted at S by flooding RREQ packets, which invites replies from S, I1, and R2. R3 chooses the reply sent by I1 and sends a MACT message along the reverse path taken by the RREP.

Figure 8.19. Node joining the multicast tree in MAODV.

Tree Maintenance Phase

Tree maintenance is accomplished by means of an expanding ring search using the RREQ, RREP, MACT cycle. The downstream node is responsible for issuing a fresh RREQ for the group. This RREQ contains the hop count of the requesting node from the group leader and the last known sequence number for that group. This RREQ can be answered only by member-nodes whose recorded sequence number is greater than that indicated in the RREQ and whose hop distance is lesser (to ensure that nodes on the same side of the break do not reply to this RREQ). When a leaf-node wishes to leave the group, it sends a prune message upstream which might be propagated further up the tree. A non-leaf node continues to be a member of the multicast tree and forwards packets for other multicast receivers, even after it has left the multicast group. Partition repair is facilitated by the GRPH message: Any node which overhears GRPH messages from different nodes initiates a group leader election protocol, which finally elects a single group leader for the newly formed component. Figure 8.20 shows the tree repair initiated by the R3–I3 link break.

Figure 8.20. Tree repair in MAODV.

Advantages and Disadvantages

One of the advantages of MAODV is the integration of unicast and multicast into a unified framework. Thus, information gleaned during unicast route discovery can be used in the multicast route discovery and vice versa. This sharing of information helps in reducing the control overhead, which is one of the aims of an ad hoc multicast protocol. The protocol is also free from loops. The disadvantage stems from its tree-based multicast topology: poor packet delivery under mobility, congestion along links in the tree, etc. This protocol uses a shared-tree, which is not efficient when the number of multicast sessions is high. Usage of a shared-tree always carries along with it the risk of single-point failure of the group leader, which might severely affect all multicast sessions in progress.

8.6.9 Ad Hoc Multicast Routing Protocol Utilizing Increasing ID-Numbers

Ad hoc multicast routing protocol utilizing increasing id-numbers (AMRIS) [22] is a source-initiated multicast routing protocol in which a shared-tree is constructed to support multiple sources and receivers. The main idea in this protocol is that each tree node has a session-specific multicast session member identifier (MSM-ID) which indicates its logical height in the shared tree. The purpose of MSM-ID is to avoid any loop formation and repair the broken links locally.

Tree Initialization Phase

To initialize the multicast tree, one of the sources in the multicast group (which is called Sid) broadcasts the NewSession message. The NewSession message contains Sid's MSM-ID, multicast session ID, and routing metrics. When all the nodes receive the NewSession message, they store the information derived from the NewSession message in their neighbor-status tables up to some fixed amount of time and generate their own MSM-ID. The new MSM-ID is larger than the received MSM-ID and it should not be consecutive in order to make use of the successive sequence numbers for quick local repair. In AMRIS, each node maintains a neighbor-status table which stores the list of existing neighbors and their MSM-IDs. The nodes in the ad hoc network periodically transmit beacons (which contain the MSM-ID of the node) to indicate their presence. In Figure 8.21, the number inside the circle represents the MSM-ID of the corresponding node. Note that some nodes may not have a valid MSM-ID due to their absence during NewSession propagation, or because the MSM-ID stored in the neighbor-status table might have been erased due to timeout.

Figure 8.21. Node joining the multicast tree in AMRIS.

When a node wants to join the multicast group, it gets the list of potential parent nodes from its neighbor-status table and sends the JoinReq control packet to one of its neighbor nodes. The potential parents are those neighbor nodes which have the MSM-ID less than the MSM-ID of the node which has to send the JoinReq control packets. Here in Figure 8.21, node S1 sends the JoinReq to its potential parent node I2. Since node I2 is not in the multicast tree, it repeats the same process by sending the JoinReq to node I1. After a successful search of the path, node I2 sends JoinAck to its downstream nodes to establish the route. Other members also join the multicast group in the same way.

Tree Maintenance Phase

Once the tree is formed, then the process of tree maintenance comes into the picture. Tree maintenance is required to repair the broken links. In AMRIS, when a node is isolated from the tree due to link failure, it rejoins the tree by executing branch reconstruction (BR), which has two subroutines: BR1 and BR2. The subroutine BR1 is executed if the node has neighboring potential parent nodes. If the node does not have any neighboring potential parent node, then the BR2 subroutine is executed. In Figure 8.22, when node R1 moves from A to B, the link I3-R1 fails. Since node R1 has neighboring potential node I4, it sends the JoinReq packet to node I4. The node I4 is not in the tree and hence it repeats the same process to join the tree. If node I4 succeeds, then it sends JoinAck to node R1; otherwise, it sends JoinNack. If node R1 receives JoinNack or times out on the reply, then it selects another neighboring potential parent node and repeats the same process. If none is available, node R1 executes the BR2 subroutine. The other case is that node R1 moves from A to C (Figure 8.23). Since node R1 does not have any neighboring potential parent node, it executes BR2 subroutine in which it floods the JoinReq packet with some TTL value. Hence it receives a number of JoinAck packets. It chooses one of the routes by sending a JoinConf packet.

Figure 8.22. Tree maintenance by BR1 subroutine.

Figure 8.23. Tree maintenance by BR2 subroutine.

Advantages and Disadvantages

Since AMRIS uses MSM-ID, it avoids loop formations, and link breaks are repaired locally. Hence, the control overhead is less. Another advantage of AMRIS is its simplicity as compared to other multicast protocols. The main disadvantages of this protocol are the wastage of bandwidth due to usage of beacons and the loss of many data packets due to collisions with beacons. Also, the hard state route maintenance scheme, where a node cut-off due to path break needs to search for a suitable parent node, wastes a lot of time and contributes toward an increased end-to-end delay in packet delivery and loss of packets. The selection of potential parent nodes based on MSM-ID tends to increase the average hop-length between the receivers and the source, leading to increased delay and increased probability of packet losses.

8.6.10 Ad Hoc Multicast Routing Protocol

A different approach is used in ad hoc multicast routing protocol (AMRoute) [7] in order to enhance the robustness of the tree-based approach. This multicast protocol emphasizes robustness even with high mobility by creating a multicast tree over the underlying mesh. It assumes the existence of an underlying unicast routing protocol (but does not depend on any particular unicast routing protocol) in the network environment, which is responsible for keeping track of the network dynamics. It has two main phases: mesh creation phase and virtual user-multicast tree creation phase. The logical core node initiates mesh creation and tree creation. Here the logical core is not the central point for all data as in core-based trees [3] and the logical core changes dynamically.

Tree Initialization Phase

When members (either source or receiver) want to join the multicast group, they declare themselves as logical cores of a one-node mesh and flood JoinReq control packets with increasing TTL to discover other members. When node A detects node B (Figure 8.24), a bidirectional tunnel is established between node A and node B. Thus, they form the mesh segment (of two member nodes) indicated by I. Since each segment should have only one logical core, by using a core resolution algorithm only one node remains as the logical-core node in the segment. In Figure 8.24, node A is the logical-core node in segment I. Now, node A again floods a JoinReq control packet to discover other group members and disjoint mesh segments. Keeping a single logical core in each segment to discover members and disjoint mesh segments makes the protocol scalable, as the control overhead is reduced. When member C in mesh segment II receives JoinReq, it responds with a JoinAck and a new bidirectional tunnel is established between nodes A and C. Note that any member, either core or non-core in the mesh segment, can respond to the JoinReq discovery message to avoid adding many links to a core. Since mesh segments I and II merge, the resultant mesh contains more than one logical core. Finally, only one of the core nodes (say, node C here) will be the logical core as selected by the core resolution algorithm. The logical core C periodically transmits a TreeCreate message to create a virtual user-multicast tree (Figure 8.25) over the mesh which is shared by all members of the group. The underlying mesh structure and periodic transmissions of the TreeCreate message for creating the multicast tree make this protocol robust. As long as there exists a path among all the nodes connected by mesh links, the multicast tree need not change because of movement of the nodes. The members of the multicast group forward the data packets through the unicast tunnel along the branches of the virtual multicast tree. Non-members are not required to replicate the data packets and support any IP multicast protocol, but this reduces the efficiency of the protocol.

Figure 8.24. Formation of mesh segments.

Figure 8.25. A virtual user-multicast tree.

Tree Maintenance Phase

Due to movement of the nodes or due to node failures, the mesh may split into parts, as shown in Figure 8.26. Nodes D and E in the fragmented part II expect a TreeCreate message from the logical core. After waiting for a random time period, one of the members (e.g., node D) becomes the core node and initiates the process of discovering the other disjoint mesh (part I) as well as tree creation. Again when part I and part II join, then multiple cores are resolved by a core resolution algorithm.

Figure 8.26. Tree maintenance in AMRoute.

Advantages and Disadvantages

AMRoute protocol is robust due to its tree structure over an underlying mesh. But it is less efficient due to loop formations in the multicast tree. Also, under mobility conditions the hop count of the unicast tunnels increases, thereby decreasing the throughput. Similar to other shared-tree-based protocols, AMRoute also has the risk of single point failure of the core node. Failure of the core node causes loss of packets and increases the delay, as considerable time is wasted before one of the existing nodes is made as the core node. When the size of the network is large and the node mobility is high, the core nodes keep changing frequently. This leads to a continuous transfer of state information from the existing core nodes to the new core nodes, resulting in wastage of already scarce bandwidth.

8.6.11 Adaptive Shared-Tree Multicast Routing Protocol

The above described multicast routing protocols are either source-tree-based or shared-tree-based. A source-tree is rooted at the source node, whereas a shared-tree is rooted at the rendezvous point (RP) and is shared by multiple sources. Source-tree-based multicast protocols are better compared to shared-tree-based protocols because of the less delay involved (due to shortest path between source and receiver) and even traffic distribution. The main problem with source-tree-based protocols is that they are not stable in case the source is moving fast. Shared-tree-based protocols are scalable as the number of sources in the multicast group increases.

There are three schemes for shared-tree protocol [23] implementation: (1) unicast sender mode, (2) multicast sender mode, and (3) adaptive per source multicasting. The first two are purely shared-tree-based multicast routing protocols. But in adaptive shared-tree multicast routing protocol, an attempt is made to combine the best features of both approaches (source-tree-based and shared-tree-based).

In all these three schemes to create the shared-tree, receivers periodically send the JoinReq packet along with the forward list. The forward list contains the list of source addresses from which the receivers expect to get the data packets.

In unicast shared mode, to send the data packets to receivers, a source unicasts the data packets to RP. After receiving the data packets, RP forwards the data packets to all the interested receivers. In Figure 8.27, it is shown that receiver R1 receives the data packets from RP, which had been sent to RP by senders S1 and S2. Duplicate data packet transmissions result in inefficient bandwidth utilization. To avoid this, in multicast shared mode, sources S1 and S2 send unencapsulated data packets to RP so that intermediate node I2 can forward the data packets to receiver R1 directly, after receiving them from source S1. This can be clearly seen from Figures 8.27 and 8.28. In multicast sender mode, intermediate node I1 does not forward data packets (sent by source S1) when it receives them from RP because it has already seen those unencapsulated data packets.

Figure 8.27. Data packets traversal in unicast sender mode.

Figure 8.28. Data packets traversal in multicast sender mode.

In the above two schemes (based on shared-tree), there is scope for further improvement in the efficiency of the multicast routing protocol. This can be achieved by allowing the receiver to receive the data packets directly from the source, in case the data packets traverse (through RP) a path which is much longer than the shortest path between source and receiver. In Figure 8.29 receiver R1 receives the data packets from source S2 (through RP) with hop count eight, which is much longer than the actual distance between R1 and S2, which is two. In addition to that, the actual distance between R1 and S2 is less than the distance between receiver R1 and RP. Hence, receiver R1 connects to source S2 through the shortest path by sending JoinReq to S2. Now RP does not forward the data packets (which are sent by source S2) to receiver R1. Further due to movement of the nodes, if the distance between R1 and S2 increases, then it switches over to RP-rooted shared-tree from per source-tree.

Figure 8.29. Data packets traversal in adaptive per source mode.

Advantages and Disadvantages

Due to the adaptive nature of the tree configuration, it is scalable (due to shared-tree) and achieves high packet delivery ratio (due to per source-tree). The control overhead is reduced because of the shared-tree, and at the same time, it allows sources to send packets to receivers by the shortest path, resulting in better throughput. Similar to other shared-tree-based protocols, this scheme also carries with it the risk of single point failure of the RP. Failure of the RP affects multiple sessions and results in significant packet losses.

8.7 MESH-BASED MULTICAST ROUTING PROTOCOLS

In ad hoc wireless networks, wireless links break due to the mobility of the nodes. In the case of multicast routing protocols, the path between a source and receiver, which consists of multiple wireless hops, suffers very much due to link breaks. Multicast routing protocols which provide multiple paths between a source-receiver pair are classified as mesh-based multicast routing protocols. The presence of multiple paths adds to the robustness of the mesh-based protocols at the cost of multicast efficiency. In this section, some of the existing mesh-based multicast routing protocols are described in detail.

8.7.1 On-Demand Multicast Routing Protocol

In the on-demand multicast routing protocol (ODMRP) [24], a mesh is formed by a set of nodes called forwarding nodes which are responsible for forwarding data packets between a source-receiver pair. These forwarding nodes maintain the message-cache which is used to detect duplicate data packets and duplicate JoinReq control packets.

Mesh Initialization Phase

In the mesh initialization phase, a multicast mesh is formed between the sources and the receivers. To create the mesh, each source in the multicast group floods the JoinReq control packet periodically. Upon reception of the JoinReq control packet from a source, potential receivers can send JoinReply through the reverse shortest path. The route between a source and receiver is established after the source receives the JoinReply packet. This is illustrated in Figure 8.30. For initializing the mesh, sources S1 and S2 in the multicast group flood the JoinReq control packets. The nodes that receive a JoinReq control packet store the upstream node identification number (ID) and broadcast the packet again. When receivers R1, R2, and R3 receive the JoinReq control packet, each node sends a JoinReply control packet along the reverse path to the source. Here in Figure 8.30, receiver R2 receives JoinReq control packets from sources S1 and S2 through paths S1-I2-I3-R2 and S2-I6-I4-I5-R2, respectively. The JoinReply packet contains the source ID and the corresponding next node ID (the upstream node through which it received the JoinReq packet). When node I2 receives the JoinReply control packet from receiver R1, it sets a forwarding flag and becomes the forwarding node for that particular multicast group. After waiting for a specified time, it composes a new JoinReply packet and forwards it. The format of the JoinReply packet sent by the node R2 is shown in Table 8.2. In this way, subsequent forwarding of JoinReply packets by the intermediate nodes along the reverse path to the source establishes the route.

Table 8.2. Format of JoinReply packet sent by receiver R2

Figure 8.30. Mesh topology in ODMRP.

Mesh Maintenance Phase

In this phase, attempts are made to maintain the multicast mesh topology formed with sources, forwarding nodes, and receivers. To some extent, the multicast mesh protects the session from being affected by mobility of nodes. For example, due to movement of the receiver R3 (from A to B), when the route S2-I9-I10-R3 breaks (Figure 8.31), R3 can still receive data packets through route S2-I6-I4-I7-I8-R3 and this contributes to the high packet delivery ratio. ODMRP uses a soft state approach to maintain the mesh, that is, to refresh the routes between the source and the receiver, the source periodically floods the JoinReq control packet. In Figure 8.31, when receiver R3 receives a new JoinReq control packet from node I11 (sent by the source S2), it sends a JoinReply on this new shortest path R3-I11-I10-I9-S2, thereby maintaining the mesh structure.

Figure 8.31. Maintenance of mesh topology in ODMRP.

Advantages and Disadvantages

Since ODMRP uses the soft state approach for maintaining the mesh, it exhibits robustness. But this robustness is at the expense of high control overhead. Another disadvantage is that the same data packet (from source S2 to receiver R3) propagates through more than one path to a destination node, resulting in an increased number of data packet transmissions, thereby reducing the multicast efficiency.

8.7.2 Dynamic Core-Based Multicast Routing Protocol

The dynamic core-based multicast routing protocol (DCMP) [25] attempts to improve the efficiency of the ODMRP multicast protocol by reducing control overhead and providing better packet delivery ratio. Mesh-based protocols, such as ODMRP, suffer from two disadvantages:

1. Excessive data forwarding: Too many nodes become forwarding nodes, resulting in an excessive number of retransmissions of data packets. In ODMRP, all nodes on the shortest path between each source and each receiver become forwarding nodes, resulting in too many forwarding nodes. (The advantage of such a mesh containing many forwarding nodes is, of course, the superior packet delivery ratio and robustness under mobility.)
2. High control overhead: In ODMRP, each source periodically floods its JoinReq packets and the mesh is reconstructed periodically. This leads to a heavy control overhead.

DCMP attempts to increase the packet delivery ratio and at the same time reduce the control overhead by reducing the number of sources which flood JoinReq packets, thereby reducing the number of forwarding nodes.

Mesh Initialization Phase

In the mesh initialization phase, DCMP attempts to reduce the number of sources flooding their JoinReq packets. In DCMP, there are three kinds of sources: passive sources, active sources, and core active sources. Each passive source is associated with a core active source, which plays the role of a proxy for the passive source, by forwarding data packets from the passive source, over the mesh created by its JoinReq packets. Passive sources do not flood JoinReq packets, unlike active and core active sources. Sources which flood JoinReq packets on their behalf as well as on the behalf of some passive source are called core active sources. The mesh establishment protocol is similar to that in ODMRP. Data packets of the active sources and core active sources are sent over the mesh created by themselves, while a passive source forwards the packet to its proxy core active node, which in turn sends it over its mesh. The control overhead is reduced, as compared to ODMRP, because there are a fewer number of sources which flood their JoinReq packets, and thus the number of forwarding nodes is also fewer. To allow the mesh to have enough forwarding nodes for robust operation, the number of passive sources has to be limited: This is done in DCMP by limiting the maximum number of passive sources a single core active source can serve (this maximum number is called MaxPassSize). To ensure that the packet delivery ratio is not reduced because of the fact that the average passive source-to-receiver distance is likely to be higher (because it is reusing the mesh created by its proxy core active node), the maximum hop distance between a passive source and its proxy core active node is also limited (this maximum hop distance is called MaxHop).

The example in Figure 8.32 shows mesh construction in DCMP, with the MaxHop and MaxPassSize parameters set to two. There are four sources in the multicast group, S1, S2, S3, and S4 and two receivers labeled R. Since S3 and S4 are at a hop distance of two from each other (which is equal to MaxHop), S3 goes passive and uses a proxy in the core active node S4. No other set of sources is within a hop distance of two from each other, so eventually S1 and S2 are the active sources, S3 is a passive source, and S4 is a core active source. The mesh consists of all the shortest paths between the sources S1, S2, and S3 and the two receivers R. Thus, the number of forwarding nodes is reduced, as compared to ODMRP, without much reduction in robustness and packet delivery ratio.

Figure 8.32. Construction of mesh in DCMP. Reproduced with permission from [25], © ACM, 2002.

Mesh Maintenance Phase

DCMP's mesh maintenance is soft state, similar to that of ODMRP. Thus, the mesh is reconstructed periodically and forwarding nodes that are no longer part of the mesh, cancel their forwarding status after a timeout period. In the example shown in Figure 8.33, source S3 has moved away from its core active node S4, with the hop distance between them increasing to three (which is greater than the MaxHop parameter=2). Thus, S3 goes active, and begins flooding periodically with its own JoinReq packets. Therefore, more nodes attain forwarding status and are grafted onto the mesh.

Figure 8.33. Maintenance of mesh topology in DCMP. Reproduced with permission from [25], © ACM, 2002.

Advantages and Disadvantages

The primary advantage of DCMP is its scalability due to decreased control overhead and its superior packet delivery ratio. The performance improvement of DCMP over ODMRP increases with the number of sources in the multicast group (though they start performing on par beyond a certain number of sources, when almost all nodes are part of the mesh). One of the drawbacks of DCMP is that the parameters associated with it, MaxPassSize and MaxHop, are likely to depend on the network load conditions, group size, and number of sources, and optimal values of these parameters may even vary from one node to another. Failure of an active core node might result in multiple session failures.

8.7.3 Forwarding Group Multicast Protocol

Another mesh-based multicast routing protocol, which is also based on the forwarding group concept, is forwarding group multicast protocol (FGMP-RA [receiver advertising]) [26]. The major difference between ODMRP and FGMP-RA lies in who initiates the multicast group formation. ODMRP is a source-initiated multicast routing protocol, whereas FGMP (FGMP-RA) is a receiver-initiated multicast routing protocol.

Mesh Initialization Phase

In order to form the multicast mesh, each receiver floods the JoinReq control packet in the network. When the sources receive these JoinReq control packets, each source updates its member table and creates a forwarding table. The member table keeps the IDs of all the receivers in the multicast group. After creating the forwarding table, the source forwards this table toward the receivers. When the forwarding table reaches the receivers, the routes between the source-receiver pairs get established.

In Figure 8.34, when receivers R1, R2, and R3 want to join the multicast group, they send JoinReq control packets. After receiving the JoinReq control packets, sources S1 and S2 update their member tables. After refreshing the member tables, each source creates its forwarding table and broadcasts it. The forwarding table contains the next-hop information, which is obtained by using the underlying unicast routing protocol. The forwarding table at source node S2 is shown in Table 8.3. After receiving the forwarding table, neighbor nodes I6 and I9, whose node ID matches with the entry in the forwarding table, set their forwarding flags and become the forwarding nodes for that particular multicast group. Now nodes I6 and I9 build their own forwarding tables and forward them again. In this way, the forwarding tables reach receivers R1, R2, and R3 along the reverse shortest path and the route is established.

Table 8.3. Format of forwarding table sent by source S2

Figure 8.34. Mesh topology in FGMP.

Mesh Maintenance Phase

If, due to the movement of the receiver R3, the route S2-I9-I10-R3 breaks (Figure 8.31), R3 can still receive data packets through route S2-I6-I4-I7-I8-R3. To maintain a route, FGMP uses the soft state approach, that is, receivers periodically flood the JoinReq packet to refresh the route. When source S2 receives a new JoinReq control packet through the route R3-I11-I10-19-S2, it sends the forwarding table along that path and establishes a new route between the source S2 and receiver R3.

Advantages and Disadvantages

Due to its mesh topology and soft state maintenance scheme, it is more robust as compared to the tree-based multicast routing protocols. But the soft state maintenance approach increases the control overhead. It is more advantageous to use FGMP (FGMP-RA) when the number of senders is greater than the number of receivers.

8.7.4 Neighbor Supporting Ad Hoc Multicast Routing Protocol

Neighbor supporting ad hoc multicast routing protocol (NSMP) [27] is a mesh-based multicast protocol which does selective and localized forwarding of control packets. Like in ODMRP and FGMP, to initialize the mesh, the source floods the control message throughout the network. But for maintenance of the mesh, local route discovery is used, that is, only mesh nodes and multicast neighbor nodes forward the control message to refresh the routes. Multicast neighbor nodes are those nodes which are directly connected to at least one mesh node.

Mesh Initialization Phase

Consider Figure 8.35. In order to form the multicast mesh, initially the multicast source S1 floods the FLOOD-REQ packets which are forwarded by all the nodes in the network. When receiver R1 receives this FLOOD-REQ packet, it sends a reply packet (REP) along the reverse path to the source S1, establishing the route. Similarly, when receiver R2 receives the FLOOD-REQ packet, it sends back a REP packet to the source along the reverse path and joins the multicast group. Each source node periodically transmits a LOCAL-REQ packet, which is relayed by all mesh nodes and multicast neighbor nodes. If new receiver R3 wants to join the multicast group, it waits for a specified time for a LOCAL-REQ packet from any mesh node or multicast neighbor node. When receiver R3 receives a LOCAL-REQ packet from the multicast neighbor node I2, it joins the group by sending a REP control packet. This REP packet is relayed back to the multicast source through nodes I2 and I1. Some receivers may not be within the range of any multicast mesh node or multicast neighbor node. In Figure 8.35, receiver R4, which is more than two hops away from the mesh, does not get any LOCAL-REQ packet. Hence it floods MEM-REQ control packets. Any node that is part of the multicast mesh which receives the MEM-REQ packet sends back a reply route discovery packet. Node R4 receives route discovery packets sent by nodes I5 and R1, through paths I5-I7-I8-R4 (path I) and R1-I10-I9-I8-R4 (path II), respectively. When any new receiver node receives multiple route discovery packets, NSMP uses a relative weight metric for selecting one of the multiple routes. The relative weight metric is given as ((1 - α) × FC+α × NC), where FC is the count of forwarding nodes on the path from the source node till the current node, and NC is the count of non-forwarding nodes from the source node till the current node. A path with the lowest value for the relative weight is chosen. The NC and FC values received on the route discovery packet through path I are five and two, respectively, and are three and three, respectively, on the route discovery packet received through path II. NSMP chooses a path which has a larger number of existing forwarding nodes, which makes the protocol efficient since the total number of multicast packet transmissions in the network gets reduced. For this, an a value above 0.5 is used. In the example shown in Figure 8.35, if an a value of 0.8 is used, the relative weight metric on path I and path II would be 2.6 and 3, respectively. Node R4 selects path I which has a lower value, and sends back a REP packet, which is relayed back to the multicast source node.

Figure 8.35. Mesh initialization in NSMP.

Mesh Maintenance Phase

To maintain the multicast mesh, each source periodically transmits LOCAL-REQ packets which are forwarded by mesh nodes and neighbor nodes only. The local route discovery and maintenance mechanisms are quite effective in repairing most of the link failures. If receiver R3 moves from A to B, it can still receive LOCAL-REQ control packets from neighbor node I12 (Figure 8.36). By sending the REP packet to source S2 through node I12, the path to source S2 is repaired. Due to the localized maintenance scheme, the control overhead is reduced. But this mesh may not be able to repair all the link failures causing mesh partitions. Hence, it exhibits less data packet delivery compared to ODMRP. To repair the mesh partition, a group leader is selected among the sources, which floods the FLOOD-REQ packet at every FLOOD-PERIOD interval.

Figure 8.36. Mesh maintenance in NSMP.

Advantages and Disadvantages

Due to localized route discovery and maintenance, NSMP reduces control overhead while maintaining a high packet delivery ratio. Its joining policy, which is based on a weight parameter, makes it more efficient compared to the previous schemes. The value for the relative weight parameter may not be globally constant. It is likely to vary with different network load conditions. So the relative weight parameter must be made adaptive to the network load conditions.

8.7.5 Core-Assisted Mesh Protocol

It is known that mesh-based multicast protocols deliver more data packets compared to tree-based multicast protocols, due to the existence of multiple paths between the source and receiver. But some of the existing mesh-based multicast protocols such as ODMRP and FGMP use the flooding approach to create and maintain the mesh topology, which results in reduced efficiency in bandwidth utilization. To eliminate flooding of control packets, core-assisted mesh protocol (CAMP) [28] uses core nodes in the mesh.

Mesh Initialization Phase

CAMP is a receiver-initiated multicast routing protocol. Initially, to join the shared mesh, a receiver extracts the core node ID from its core-to-group address mapping (CAM) table (the CAM table contains the core node IDs of the multicast group) and unicasts a JoinReq packet toward this core node. In Figure 8.37, when a new receiver R3 wants to join the multicast group, it gets the core node ID I2 from its CAM table and sends a JoinReq toward it. To forward the JoinReq toward the core node, the next node I6 is obtained by using the underlying unicast routing protocol. CAMP assumes the existence of an underlying unicast routing protocol in the network environment which provides the next node ID. When the mesh node I1 receives this JoinReq, it sends an ACK to receiver R3, and thus it becomes a part of the multicast group. Unlike in the core-based tree [3], if receiver R1 (which has a neighbor node I2 already present in the mesh) wants to join the group, then there is no need to send a JoinReq packet explicitly. In this case, receiver R2 joins the multicast group by announcing its membership using a MulticastRoutingUpdate message and modifies the multicast routing table (MRT). MRT contains the multicast group address of which the node is the member.

Figure 8.37. Joining of the source S2 to the multicast group.

In CAMP, there is a provision for a sender-only node to join in the simplex mode, that is, there will be a flow of data in only one direction (from sender-only node to mesh). In Figure 8.37, source S2 has joined the group in the simplex mode. When node I7 receives a data packet (sent by the source S1) from node I4, it does not forward the data packet toward node S2, due to its simplex mode behavior. After source S2 joins the multicast group, receiver R2 receives data packets (sent by the source S2) through path S2-I7-I4-I1-I2-I3-R2, which is not the shortest path between source S2 and receiver R2 (Figure 8.38). Hence, receiver R2 sends a HeartBeat or PushJoin control packet periodically to node I8 (This next node ID I8 is obtained through the underlying unicast routing protocol). When node I8 receives this HeartBeat message, it forwards it to node I4. Thus, a route through the shortest path between source S2 and receiver R2 gets established. In this way, CAMP makes sure that all the shortest paths are part of the mesh.

Figure 8.38. Sending PushJoin message by receivers R2 and R3.

Mesh Maintenance Phase

Link failures are not very critical in CAMP. For example, in Figure 8.39, when the link I10-R3 breaks (caused due to movement of node R3), receiver R3 can still receive data packets through the next shortest route S2-I7-I4-I5-I6-R3. Now receiver R3 sends a PushJoin message to node I15, thereby establishing a new shortest path S2-I9-I10-I15-R3. Due to the mobility of nodes, the multicast mesh may become partitioned. CAMP ensures partition repair by means of the CoreExplicitJoin message which is sent by each active core in the mesh component to the cores in the other mesh components. The partition is repaired when a core receives the CoreExplicitJoin message and replies with an Ack message.

Figure 8.39. Mesh maintenance in CAMP.

Advantages and Disadvantages

The main improvement in CAMP is that it exhibits a high packet delivery ratio while keeping its total control overhead less, compared to other multicast routing protocols, by avoiding the flooding of control packets. Core node failures cause significant packet losses. Another drawback of CAMP is that it needs the support of a routing protocol that can work correctly in the presence of router failures and network partitions. As such, not all routing protocols are compatible with CAMP.

8.8 SUMMARY OF TREE- AND MESH-BASED PROTOCOLS

Table 8.4 summarizes the characteristics of the various multicast routing protocols for ad hoc wireless networks described so far. It helps in characterizing and identifying the qualitative behavior of multicasting protocols. However, a quantitative comparison study in terms of their performance under a wide range of parameters such as connectivity and size of the network, mobility of nodes, number of multicast sources, and multicast group size requires extensive analytical and/or simulation studies.

Table 8.4. Summary of multicast routing protocols

8.9 ENERGY-EFFICIENT MULTICASTING

Since the nodes in an ad hoc wireless network are battery-operated, it is important to find energy-conserving mechanisms and protocols that optimize the use of battery power in order to increase the lifetime of the network. This section describes some energy-efficient multicasting protocols for ad hoc wireless networks.

8.9.1 Energy-Efficient Reliable Broadcast and Multicast Protocols

In [29], the authors propose a set of power-efficient schemes which are based upon the existing power-aware broadcast algorithms for wireless networks such as broadcast incremental power (BIP) algorithm, broadcast least unicast (BLU) algorithm, and broadcast link-based minimum spanning tree (BLiMST) algorithm. These schemes also take into consideration the packet-error probability on a link to determine the expected energy required for reliably transmitting a packet on that link. The expected energy required for the reliable transmission of a packet from node i to node j is given by where p_ij is the packet-error probability and is the expected number of retransmissions required from node i to node j. E_ij refers to the energy required to transmit a packet once from node i to node j. The modified BIP, BLU, and the BLiMST algorithms take this E_ij(reliable) value into consideration in their respective multicast tree formation algorithms in order to construct energy-efficient trees.

8.9.2 A Distributed Power-Aware Multicast Routing Protocol

In [30], an underlying unicast routing protocol is expected to be present which can give the least-cost path from the current node to all other nodes in the network. The information gained from the unicast routing protocol is used to construct the multicast tree. The authors of [30] propose schemes which take the power factor into consideration to find these minimum cost paths. To find the minimum cost path (consisting of nodes 1, 2, 3, ...., j - 1, j, where j is the destination), the cost C is given by , where K_i is the number of free transceivers available at node i, and P_i,j is the power required for transmitting a packet from node i to node j. The denominator in this expression takes care of the congestion factor, and the numerator covers the power requirements. A strictly additive metric to determine the cost is also given as follows. The distance D_i,j between nodes i and j is given as . The end-to-end path distance D is given by , where 0 is the ID of the source node, and n is the ID of the destination node. The lowest-cost path corresponds to the path with the smallest value for D.

8.9.3 Energy-Efficient Multicast Routing Protocol

Energy-efficient multicast routing protocol (E²MRP) [31] is a mesh-based protocol. The protocol operates in two phases. The first phase uses a heuristic called minimum energy consumed per packet (MECP). The received power at a node is directly proportional to the quantity d^-θ, where d is the distance of the receiving node from the sender and θ is a constant. If p_i,j is the power required to transmit a packet from node i to node j, and d_i,j is the distance between nodes i and j, then R_k, the cost of power for a route from a source with ID 1, to a destination with ID n, is given as . θ is taken as 2 here. The route selected is the one with the lowest value. The main idea here is to minimize the total end-to-end power consumed in sending a packet from the source to its final destination.

The second phase uses a heuristic called the minimum maximum node cost (MMNC). Here the cost function used is , where Y is a constant, and V_i(t) is the energy consumed by node i until time t. , the cost of a route, consisting of nodes 1, 2, ..., n, is given as , and the route with minimum is chosen. This heuristic gives more importance to the power available at nodes on the route.

The protocol switches between two phases: the MECP phase and the MMNC phase. First, in the MECP phase, a set of routes is selected based on the MECP heuristic and a mesh is formed. Once the mesh establishment is completed, a timer, called cost function switcher (CFS), is set. Just before the CFS times out, the system shifts to the MMNC phase. Here again, a mesh based on the MMNC heuristic is established and the CFS timer is set. As before, just before the timer expires, the system goes back to the MECP phase, and the whole process repeats continuously, alternately switching between the MECP and the MMNC phases.

8.9.4 Energy-Efficient Cluster Adaptation of Multicast Protocol

In [32], a cluster-based scheme for power optimization is proposed. There exist several clusters of nodes in the network. Each cluster has a cluster-head, and all cluster-heads are connected through a super-node network. In a cluster-based scheme, when the number of cluster-heads is less, then more number of nodes can be reached by a cluster-head in a single hop, but the cluster-heads need to expend more energy and energy gets wasted when the cluster-head tries to reach a lone farthest node within its cluster. On the other hand, when the number of clusters is greater, energy again gets wasted on trying to reach a greater number of nodes in the super-node network. Hence, a balance between these two cases needs to be achieved.

In this scheme, each node initially starts off as a cluster-head. The node periodically sends beacons with its highest power level. In the cluster-building phase, each node increases its power level by one step at a time until the incremental change in the number of nodes seen reduces, or the power level reaches a specific maximum level. It then sends a recruiting message to nodes within its reach, with the list of nodes in its range, and its power level. A node joins the first cluster it hears, whose cluster-head ID is greater than its own id. The nodes that still remain as cluster-heads send cluster-forming messages to nodes within their cluster. The cluster member nodes respond and the cluster-heads finally respond with finalizing messages. The objective of the cluster-forming and finalizing messages is to make sure that each node within the cluster is able to reach all other nodes within the same cluster. Nodes that are not part of any cluster finally act as singleton clusters. The ODMRP protocol [24] is applied on the super-node topology to establish a mesh network among the cluster-heads. The mesh comes into play only when the destination node is not within the same cluster as the source node. In order to balance energy depletion, nodes within a cluster take turns to become cluster-heads.

8.10 MULTICASTING WITH QUALITY OF SERVICE GUARANTEES

Provisioning quality of service (QoS) implies providing guarantees such as deterministic end-to-end delay, availability of a fixed amount of bandwidth, buffers, and computational resources to the multicast session. Two multicast protocols, the wireless ad hoc real-time multicasting protocol and the multicast priority scheduling protocol, that attempt to provide QoS guarantees are described below.

8.10.1 Wireless Ad Hoc Real-Time Multicasting Protocol

Wireless ad hoc real-time multicasting (WARM) protocol [33] enables spatial bandwidth reuse along a multicast mesh. Bandwidth is guaranteed for real-time [constant bit rate (CBR)] traffic. The protocol uses periodic message exchanges, but the messaging is localized to the neighborhood of the receiving multicast member and hence the control overhead is low. It mainly deals with the transmission scheduling problem for a multicast session. A receiver node reserves time division multiple access (TDMA) time-slots and attaches itself to the multicast mesh through a neighbor node which is a multicast member.

The protocol deals with two types of traffic: CBR traffic and variable bit rate (VBR) traffic. Time is slotted and is grouped into superframes. Each superframe consists of two frames, one for transmitting data and the other for receiving data. Each frame consists of two parts: a reserved part and a random-access part, as shown in Figure 8.40. Both the frames are slotted. Packets transmitted by a node are numbered sequentially for that frame. Each node marks its receive (transmit) slots with the frame-sequence numbers of the packets to be received (transmitted) in those slots. A node may transmit the same packet in more than one slot, for supporting different children that may not be able to receive the packet in the same slot (In Figure 8.40, it can be seen that the same packet P1 is transmitted in slots 1 and 2). Packets in a frame that are in excess of the reserved number of slots are transmitted or received in the random-access portion of the frame.

Figure 8.40. TDMA frame structure in WARM.

Each node maintains the following information for a particular multicast session: ID (the node's unique identifier), HC (the node's hop count, i.e., the number of hops from the multicast source), F (a bit which indicates which of the two frames in the superframe is the transmit frame), RS (the number of receive slots currently reserved by the node), RS_des (the desired number of receive slots as determined by the node, based on the current traffic load), RS_min (the minimum acceptable number of reserved slots), PID (a vector representing the parents of the node), RxSlot (a vector which lists the receive slots of the node), RxSeq (a vector indicating the frame-sequence in which packets are received in the receive slots), SIR (a vector containing the signal-to-interference ratios of the node in its receive slots), G_p (a vector representing the path losses between the node and each of its parents), TxSlot (a vector which lists the transmit slots of the node), TxSeq (a vector indicating the frame-sequence in which packets are transmitted in the transmit slots), and US (a vector listing the slot numbers of the transmit slots unusable by the node). A node considers itself to be connected to the multicast mesh as long as RS ≥ RS_min. If the node receives fewer than RS_min packets in its reserved receive slots, it becomes disconnected and sets its RS to zero. It then attempts to reconnect to the multicast session. Each node periodically transmits its status information consisting of ID, HC, F, RS, RxSlot, RxSeq, PID, TxSlot, TxSeq, and US. Transmission of this information is done on a separate signaling channel in a round-robin fashion.

In case RS is less than RS_des, the node attempts to receive more receive slots through the signaling message. Here the node appends the required extra receive slots, the potential parents from which it can receive in these slots, and also the frame-sequence numbers of packets it is missing, to the signaling message. Each node maintains a neighborhood database containing information regarding all nodes from which it receives signaling information.

Connection establishment when RS_min ≤ RS < RS_des is done as below. First, the node determines the frame-sequence numbers of the packets it is missing. It then looks into the neighborhood database to find nodes that are already transmitting those packets and whose hop-count is less than its own by one. For each such neighbor, it determines the SIR for the concerned slot. If the SIR is above a certain threshold value, then the node can receive data from the new parent node in that slot, and so it adds the new parent node's ID, slot number, and the frame-sequence to the appropriate vectors PID, RxSlot, and RxSeq, respectively. If, even after this process, the node misses packets, it identifies neighboring nodes with hop-length one less than its own and that can add transmit slots to their TxSlots in order to relay the missing packets. If the SIR it computes on these slots is acceptable, it makes these nodes its parents. Consider Figure 8.41, where node S is the source. Packets transmitted by node A are received without any collisions at node B and node C. Node B transmits packets P1, P2, and P3 in slots 0, 1, and 2, respectively. Node C transmits the same packets P1, P2, and P3 received from node A in slots 2, 4, and 5, respectively. Node B is the parent of node D. Packets P1 and P2 transmitted by node B are received by node D in slots 0 and 1 without any error. But in slot 2, both nodes B and C transmit packets simultaneously. Hence, the packets transmitted by them collide during slot 2 at node D. Node D therefore is unable to receive packet P3 from node B. It searches for other possible parent nodes transmitting packet P3. It finds that node C transmits packet P3 in slot 5. If slot 5 at node B is free and if the SIR on slot 5 is acceptable, it makes node C its parent and receives packet P3 in slot 5.

Figure 8.41. Example of WARM.

In case a node gets disconnected from the multicast mesh (RS = 0), it follows the same above procedure, but it tries to use neighbor nodes with the minimum hop-count as its parents. If RS_min slots cannot be found with these parents, it tries to obtain packets from neighbor nodes with hop-counts greater than the minimum by one, and so on.

8.10.2 Multicast Priority Scheduling Protocol

Multicast priority scheduling protocol (MPSP) [34] is a packet scheduling mechanism for multicast traffic in ad hoc wireless networks. The main objective of MPSP is to provide improved multicast packet delivery with bounded end-to-end delays. It is based on the DLPS protocol [35] (described in detail in Section 6.7.3) which uses laxity-based priority scheduling and guarantees higher packet delivery for unicast traffic under bounded end-to-end delay conditions. Packet transmissions in a multicast session are broadcast in nature and are not protected by the RTS-CTS exchange. Therefore, the RTS, CTS, and ACK packets are not available for carrying piggy-backed priority information as in DLPS. MPSP modifies the DLPS protocol to suit the characteristics of multicast transmissions.

MPSP can work with both tree-based as well as mesh-based multicast protocols. But since tree-based protocols are more efficient when compared to mesh-based protocol, the following discussion uses a tree-based multicast protocol for describing the operation of MPSP. Each node maintains a scheduling table (ST) which contains information about packets to be transmitted by the node and information about packets in the neighbor nodes (which is obtained by overhearing data packets carrying such information transmitted by neighbor nodes), sorted according to their priority index values. Priority index expresses the priority of a packet. The lower the priority index, the higher the packet's priority. The performance of MPSP was studied in [34] using the WBM protocol [15], which was explained in Section 8.6.6. MPSP consists of four main components, namely, feedback mechanism, priority index calculation, scheduling table updates, and a back-off mechanism.

The feedback mechanism is used to convey, to the multicast source, information regarding the percentage of packets delivered at the multicast receiver nodes. This task would be relatively simple in unicast routing as there exists only one receiver node, receiving packets from the source node through a single path. MPSP uses soft acknowledgments (described below) for this purpose. A leaf node l, on receiving a data packet from its parent node p, increments the count of packets received countPkts for the corresponding session, maintained by it. It sends back an acknowledgment (ACK) packet to its parent node p carrying the value of countPkts. If multiple leaf nodes are connected to a parent node, then that parent node receives an ACK from each of the leaf nodes. Now, parent p computes avgCount, the average of the received countPkts values. The value of avgCount is piggy-backed on each data packet transmitted by node p. This data packet is heard by node pp, which is the parent of node p. Node pp hears data packets transmitted by each of its child nodes. It computes the new avgCount from the avgCount values on the data packets heard. This new avgCount is piggy-backed by node pp on each DATA packet it sends. Thus, in this manner the value of avgCount moves up the multicast tree and reaches the source node after a small initial delay. This avgCount value is used in the calculation of priority index of packets, which is explained below.

After transmitting each multicast packet, a node increments the count of multicast packets transmitted for that session txCount. The average count of packets received at the multicast receiver nodes avgCount is available at each multicast tree node. Each transmitted packet carries its end-to-end delay target deadline, that is, the time by which it should reach the destination. Using the above quantities, the priority index PI of a packet is calculated. It is given by

(8.10.1)

Here, is the packet delivery ratio of the flow to which the packet belongs, is the uniform laxity budget of the packet (currentTime denotes the current time according to the node's local clock), and M is a user-defined parameter representing the desired packet delivery ratio for the multicast session. remHops is the maximum number of hops remaining to be traversed by the multicast packet. It is obtained in the following manner.

In WBM, when a new receiver node wants to join the multicast group, it initiates a JoinReq. A multicast tree node, on receiving this JoinReq, responds by sending back a JoinReply packet. The receiver node may receive multiple JoinReply packets. It chooses one of them and confirms its selection by transmitting a JoinConf to the corresponding multicast tree node. This JoinConf packet is utilized by MPSP. Before transmitting the JoinConf packet, the new receiver node initializes a hopCount field on the JoinConf packet to zero. An intermediate node forwarding the JoinConf increments the hopCount by one. Hence, all nodes on the path to the node at which the new receiver node joins the multicast group (the node which initiated the JoinReply packet) know the remaining number of hops to be traversed by a multicast packet transmitted by it. The remaining number of hops remHops at node n is given by the maximum of hopCount to each receiver node through node n. A node piggy-backs this remHops value on each data packet it transmits. The node's parent, on hearing the transmitted data packet, extracts the piggy-backed value and computes its own remHops value, which it piggy-backs on the data packets it sends. Thus, the value of remHops moves up the multicast tree and finally reaches the multicast source node. Since each node in the multicast tree has a remHops value for the multicast session, the ULB of a packet queued at a node can now be computed. The above procedure is illustrated in Figure 8.42. Here, the new receiver node NR (node 1) initiates route discovery by transmitting a JoinReq packet. It reaches multicast tree nodes 3 and 8. Each of these two nodes responds by sending back a JoinReply packet. Node 1 chooses the JoinReply sent by node 3. It sends a JoinConf destined to node 3, with the hopCount value (HC) set to zero. When the packet reaches node 2, node 2 increments the HC by one and piggy-backs it on the next data packet it transmits. Node 3, on hearing this packet, retrieves the HC value one and computes the new HC value for node 1 as two. It is already connected to node 4, and so the HC from node 3 to node 4 is one. The new HC value for the multicast session at node 3 is computed as max(1, 2) = 2. This value is piggy-backed by node 3 on the next multicast packet it transmits, which would be heard by node 5. Nodes 5 and 6 compute the HC values in a similar fashion. When node 6 transmits a packet with the HC set to 4, node 8, the multicast source, would hear the packet and calculate the maximum number of hops remaining though node 6 as five.

Figure 8.42. Propagation of hopCount in MPSP.

Priority information regarding the highest priority ready packet to be transmitted next is piggy-backed on each data packet. A neighbor node, on hearing this packet, updates its scheduling table with the piggy-backed priority information. Hence, each node would know the priority of its own packet compared to the priorities of packets queued at its neighbor nodes.

The back-off mechanism used in MPSP is the same as that used in DLPS. The objective of the back-off mechanism used in DLPS is to reflect the priority of the node's highest priority packet on the back-off period to be taken by the node. If r is the rank (the rank of an entry is the position of that entry in the scheduling table of the node), in ST of the node, of the current packet to be sent, n is the number of retransmission attempts made for the packet, and nmax is the maximum number of retransmission attempts permitted, then the back-off interval is given by

(8.10.2) (8.10.3) (8.10.4)

where CW_mim is the minimum size of the contention window, and M is the desired packet delivery ratio. If the packet has the highest rank in the broadcast region of the node, then it has the lowest back-off period according to Equation 8.10.2 and faces very less contention. Else, if it is the first time the packet is being transmitted, the back-off distribution follows the second scheme as in Equation 8.10.3, where the back-off is more than that for the first case. Here the current PDR of the flow affects the back-off period. If PDR is very low, then the first term would be low, and if it is high, then the first term would be high and the node would have to wait for a longer time. Finally, if the packet does not fit into these two categories, then the back-off value is as per the third scheme in Equation 8.10.4 and is the longest of the three cases. The higher the value of ULB, the longer the back-off period.

The above-described mechanisms aid MPSP in providing better multicast packet delivery compared to other regular multicast protocols, under bounded end-to-end delay conditions.

8.11 APPLICATION-DEPENDENT MULTICAST ROUTING

There are some multicast routing protocols that cater to different needs of a user depending on the scenarios in which they are used. Some of them are described in this section.

8.11.1 Role-Based Multicast

Role-based multicast [36] is a multicast scheme designed to meet the special needs of inter-vehicle communication. The multicast group changes dynamically based on the location, speed, driving direction, and time. An example application, described and discussed in detail in [36], is the accident situation on highways where information about the accident needs to be disseminated to the relevant vehicles (receivers). A modified flooding technique floods information about the accident. Taking into consideration the speed, direction of movement, and distance from the source, a multicast group is calculated. This group includes all vehicles for which the information could be useful, so that the drivers can brake their vehicles before the accident zone. The information regarding the accident is flooded so that all such receivers receive it on time. Note that in this model the source is stationary and the receivers move at high speeds, mostly toward the source. This model cannot be used in situations where the sources are also in constant motion. The content-based multicast [37] model described below handles such situations.

8.11.2 Content-Based Multicast

Content-based multicasting [37] is used in areas where the source set and the receiver set for the information keep changing dynamically based on the content of the information and the mobility of the receivers themselves. An example of this kind of application is in a battlefield where the moving soldiers need to be continuously updated on the impending threats that may occur within a certain duration (say, in the next ten minutes) or that may be present at a certain distance (say, 5 Km) from the soldier. Information on the presence of their allies may also be of use to them. Autonomous sensors dropped in the forward area may be used to collect the information required. Thus, in the content-based multicast model, it can be assumed that nodes are interested in obtaining information about threats and resources that are (i) t time away from their current location and/or (ii) distance d away.

However, the main problem in such applications is that since the nodes, threats, and resources keep moving all the time, it is difficult for the information sources to determine their receiver sets, and it is also difficult for the receiver nodes to determine the identity of the senders. In [37], this problem is solved by means of a sensor-push and receiver-pull approach. The entire area is divided into geographical regions called blocks. Each block has a block leader.

In the sensor-push part of the scheme, sensor nodes generate information and pass them on to the leader of the block they are located in by means of ThreatWarning messages. Based on the location and velocity of the threat, this information is further pushed into other blocks by the block leader. In the receiver-pull part, if the time specification is t, then the receiver node sends a PullRequest to the leader of the block in which it is expected to be present after time period t. In case that leader has incomplete threat information, it further generates PullRequest messages to leaders of blocks in the direction of the threat, retrieves threat information if any, and forwards it to the requesting receiver.

Consider Figure 8.43. Here node I is moving at a speed s_i and is expected to reach block PQRS in time t_i. It sends a PullRequest message to node B which is the leader of block PQRS. This message contains node I's velocity along with a specification of threats about which the node needs to be warned. Node B sends back all information regarding the threats of which it is aware. In case node B has incomplete knowledge about threats that are time t_i away, which is very likely, it initiates additional PullRequest messages. If the maximum speed of the threats is s_max, then node B sends the PullRequest messages to the leaders of all blocks located at distance s_maxt_i away. These block leaders determine whether the threats they are aware of would affect nodes in block PQRS after time period t_i from the current point of time. If so, then they send the threat information to the node B, which then forwards the information received to node I.

Figure 8.43. Content-based multicast.

8.11.3 Location-Based Multicast

Location-based multicasting or geocasting, which is a variant of the conventional multicasting, makes use of geographical information for multicasting. Here, a group of nodes present in a particular geographic region constitutes the multicast receiver group. The global positioning system (GPS) plays an integral part in all location-based schemes. A node uses GPS to obtain its latitude, longitude, and altitude coordinates. Geocasting has several applications, such as sending emergency messages to people within a small area such as buildings, paging a person who is known to be present within a small area such as a suburb in a city, and sending advertisements meant only for a particular region. A few of the location-based multicast schemes are described below.

In [38], two schemes that use a modified flooding approach for geocasting are proposed. These schemes use the concept of forwarding regions. In the first scheme, a rectangle encompassing the source and the multicast receiver region, and whose sides are parallel to the X and Y axes, constitutes the forwarding region. A node, receiving a multicast message, forwards it only if it lies within the forwarding region. Otherwise, the message is discarded. Figure 8.44 illustrates this scheme. The forwarding region is shown by the dotted rectangle. Packets transmitted by source S reach nodes A and C. Node C, which is within the forwarding region, forwards the packets to nodes D and E. But since node A is not located within the forwarding region, it cannot further forward the packets, and so it just discards all incoming data packets for the multicast region. Similarly, packets transmitted by node E reach nodes F and G. Here again, node F, which is within the forwarding zone, forwards its incoming packets for the multicast region, while node G located outside the forwarding zone discards them.

Figure 8.44. Location-based multicast: Scheme 1.

In the second scheme, the forwarding region does not form any definite shape. When any node J receives a multicast data packet, which had been originated by a node S, from a node I, it forwards the packet only if it is, at most, δ distance farther from the center of the multicast region, than the node I. The distance is calculated as below. Before transmitting a data packet, the source node inserts its own coordinates (Xs, Ys) and the coordinates of the center point of the multicast region (Xc, Yc) on the packet. A receiving node, since it knows its own coordinates through GPS, calculates its distance from (Xc, Yc), and also the distance between its previous node and (Xc, Yc). If its distance is, at most, δ more than the distance of its previous node (source node) from the multicast region center, it forwards the packet; otherwise, it discards the packet. Before forwarding, it replaces the coordinates of its previous node on the packet with its own coordinates, so that the immediate receiver node can compute the two distances by means of which the decision on whether or not to forward the packet further is taken. This scheme can be better understood by means of Figure 8.45. Here δ is assumed to be zero. The notation DIST_i denotes the distance of node I from (Xc, Yc). Packets transmitted by source node S are received by both nodes A and C. Since both DIST_a and DIST_c are less than DIST_s, both node A and node C forward the packets. Packets transmitted by node C reach nodes D and E. But now, since DIST_e is greater than DIST_c, node E does not forward the packets further, but instead discards them. In case of node A, since DIST_a is less than DIST_s, node A forwards its incoming multicast packets to nodes B and D. Similarly, packets transmitted by node L reach nodes M and N. But since node M is located farther from (Xc,Yc) compared to node L, it does not forward the packets further.

Figure 8.45. Location-based multicast: Scheme 2.

8.12 SUMMARY

The challenges faced by multicast routing protocols for ad hoc wireless networks are much more complex than those faced by their wired network counterparts. In this chapter, the problem of multicast routing in ad hoc wireless networks was studied. After identifying the main issues involved in the design of a multicast routing protocol, a classification of the existing multicasting protocols was given. Several of these multicast routing protocols were described in detail with suitable examples. The advantages and drawbacks involved in each protocol were also listed. Some energy-conserving multicasting routing protocols were presented, as most of the nodes in ad hoc wireless networks are battery-operated.

Reliable multicasting has become indispensable for the successful deployment of ad hoc wireless networks as these networks support important applications such as military battlefields and emergency operations. Real-time multicasting that supports bounded delay delivery for streaming data is also a potential avenue for research. Security is another necessary requirement, which is still lacking in ad hoc multicast routing protocols, as multicast traffic of important and high security (e.g., military) applications may pass through unprotected network components (routers/links). Thus, multicasting in ad hoc networks is a significant problem that merits further exploration.

8.13 PROBLEMS

1. Comment on the scaling properties of source-initiated and receiver-initiated multicast protocols with respect to the number of sources and receivers in the group. Which of them would be suitable for (a) a teacher multicasting his lectures to a set of students (assume the students do not interact with one another) and (b) a distributed file sharing system?
2. Is hop length always the best metric for choosing paths? In an ad hoc network with a number of nodes, each differing in mobility, load generation characteristics, interference level, etc., what other metrics are possible?
3. Link-level broadcast capability is assumed in many of the multicast routing protocols. Are such broadcasts reliable? Give some techniques that could be used to improve the reliability of broadcasts.
4. What are the two basic approaches for maintenance of the multicast tree in bandwidth efficient multicast protocol (BEMRP)? Which of the two performs better? Why?
5. Though both MCEDAR and AMRoute form trees over their underlying meshes, MCEDAR is more efficient compared to AMRoute. Why?
6. Why is ABM not efficient? How can its efficiency be increased?
7. Why is DDM not scalable with respect to the group size?
8. Sometimes, AMRIS may not exhibit high packet delivery ratio even when all nodes exhibit mobility confined to a small region. Why?
9. Calculate the approximate control overhead for the ODMRP protocol over a 200-second time period (refer to Figure 8.46). Assume that all nodes are stationary. Number of nodes: 50. Time period for sending a JoinReq: 2 secs.

   Figure 8.46. ODMRP example.

   

10. Calculate the approximate control overhead in the dynamic core-based multicast routing protocol (DCMP) (refer to Figure 8.47), over a 200-second time period. Assume that all nodes are stationary. S1 is a core active source and S2 is a passive source. Number of nodes: 50. Time period for sending a JoinReq: 2 secs.

    Figure 8.47. DCMP example.

    

11. Calculate the efficiency of the ODMRP and DCMP protocols from Figures 8.46 and 8.47, respectively.
12. The CAMP protocol has been inspired from CBT. But it is more efficient compared to CBT. Give the reasons behind this.
13. What makes CAMP an efficient protocol?
14. What are the two different topology maintenance approaches? Which of the two approaches is better when the topology is highly dynamic? Give reasons for your choice.
15. Provide a timing diagram similar to that in Figure 8.1 or Figure 8.2 for a core-based multicast protocol.
16. Comment on how content-based multicasting (CBM) could be advantageous or disadvantageous as far as the bandwidth utilization of the network is concerned.

BIBLIOGRAPHY

[1] D. Waitzman, C. Partridge, and S. Deering, "Distance Vector Multicast Routing Protocol," Request For Comments 1075, November 1988.

[2] J. Moy, "Multicast Routing Extensions for OSPF," Communications of the ACM, vol. 37, no. 8, pp. 61-66, August 1994.

[3] A. Ballardie, P. Francis, and J. Crowcroft, "Core-Based Trees (CBT): An Architecture for Scalable Multicast Routing," Proceedings of ACM SIGCOMM 1993, pp. 85-95, September 1993.

[4] S. Deering, D. L. Estrin, D. Farinacci, V. Jacobson, C. G. Liu, and L. Mei, "The PIM Architecture for Wide-Area Multicast Routing," IEEE/ACM Transactions on Networking, vol. 4, no. 2, pp. 153-162, April 1996.

[5] C. L. Fullmer and J. J. Garcia-Luna-Aceves, "Solutions to Hidden Terminal Problems in Wireless Networks," Proceedings of ACM SIGCOMM 1997, pp. 39-49, September 1997.

[6] P. Sinha, R. Sivakumar, and V. Bharghavan, "MCEDAR: Multicast Core Extraction Distributed Ad Hoc Routing," Proceedings of IEEE WCNC 1999, pp. 1313-1317, September 1999.

[7] E. Bommaiah, M. Liu, A. McAuley, and R. Talpade, "AMRoute: Ad Hoc Multicast Routing Protocol," Internet draft (work in progress), draft-talpade-manet-amroute-00.txt, August 1998.

[8] T. Ozaki, J. B. Kim, and T. Suda, "Bandwidth Efficient Multicast Routing Protocol for Ad Hoc Networks," Proceedings of IEEE ICCCN 1999, pp. 10-17, October 1999.

[9] V. Devarapalli, A. A. Selcuk, D. Sidhu, "MZR: A Multicast Protocol for Mobile Ad Hoc Networks," Internet draft (work in progress), draft-vijay-manet-mzr-01.txt, July 2001.

[10] Z. J. Haas, M. R. Pearlman, and P. Samar, "Zone Routing Protocol (ZRP)," Internet draft (work in progress), draft-ietf-manet-zrp-04.txt, January 2001.

[11] P. Sinha, R. Sivakumar, and V. Bharghavan, "CEDAR: A Core-Extraction Distributed Ad Hoc Routing Algorithm," Proceedings of IEEE INFOCOM 1999, pp. 202-209, March 1999.

[12] C. K. Toh, G. Guichala, and S. Bunchua. "ABAM: On-Demand Associativity-Based Multicast Routing for Ad Hoc Mobile Networks," Proceedings of IEEE VTC 2000, pp. 987-993, September 2000.

[13] C. K. Toh, "Associativity-Based Routing for Ad Hoc Mobile Networks," Wireless Personal Communications Journal, vol. 4, no. 2, pp. 1-36, March 1997.

[14] L. Ji and M. S. Corson, "Differential Destination Multicast (DDM) Specification," Internet draft (work in progress), draft-ietf-manet-ddm-00.txt, July 2000.

[15] S. K. Das, B. S. Manoj, and C. Siva Ram Murthy, "Weight-Based Multicast Routing Protocol for Ad Hoc Wireless Networks," Proceedings of IEEE GLOBECOM 2002, vol. 1, pp. 17-21, November 2002.

[16] R. S. Sisodia, I. Karthigeyan, B. S. Manoj, and C. Siva Ram Murthy, "A Preferred Link-Based Multicast Protocol for Wireless Mobile Ad Hoc Networks," Proceedings of IEEE ICC 2003, vol. 3, pp. 2213-2217, May 2003.

[17] R. S. Sisodia, B. S. Manoj, and C. Siva Ram Murthy, "A Preferred Link-Based Routing Protocol for Ad Hoc Wireless Networks," Journal of Communications and Networks, vol. 4, no. 1, pp. 14-21, March 2002.

[18] R. S. Sisodia, I. Karthigeyan, B. S. Manoj, and C. Siva Ram Murthy, "A Novel Scheme for Supporting Integrated Unicast and Multicast Traffic in Ad Hoc Wireless Networks," revised version submitted to Journal of Parallel and Distributed Computing, 2004.

[19] E. M. Royer and C. E. Perkins, "Multicast Operation of the Ad Hoc On-Demand Distance Vector Routing Protocol," Proceedings of ACM MOBICOM 1999, pp. 207-218, August 1999.

[20] E. M. Royer and C. E. Perkins, "Multicast Ad Hoc On-Demand Distance Vector (MAODV) Routing," Internet draft (work in progress), draft-ietf-manet-maodv-00.txt, July 2000.

[21] C. E. Perkins and E. M. Royer, "Ad Hoc On-Demand Distance Vector Routing," Proceedings of IEEE WMCSA 1999, pp. 90-100, February 1999.

[22] C. W. Wu, Y. C. Tay, and C. K. Toh, "Ad Hoc Multicast Routing Protocol Utilizing Increasing id-numberS (AMRIS) Functional Specification," Internet draft (work in progress), draft-ietf-manet-amris-spec-00.txt, November 1998.

[23] C. C. Chiang, M. Gerla, and L. Zhang, "Adaptive Shared Tree Multicast in Mobile Wireless Networks," Proceedings of GLOBECOM 1998, pp. 1817-1822, November 1998.

[24] S. J. Lee, M. Gerla, and C. C. Chiang, "On-Demand Multicast Routing Protocol," Proceedings of IEEE WCNC 1999, pp. 1298-1302, September 1999.

[25] S. K. Das, B. S. Manoj, and C. Siva Ram Murthy, "A Dynamic Core-Based Multicast Routing Protocol for Ad Hoc Wireless Networks," Proceedings of ACM MOBIHOC 2002, pp. 24-35, June 2002.

[26] C. C. Chiang, M. Gerla, and L. Zhang, "Forwarding Group Multicasting Protocol for Multi-Hop, Mobile Wireless Networks," ACM/Baltzer Journal of Cluster Computing: Special Issue on Mobile Computing, vol. 1, no. 2, pp. 187-196, 1998.

[27] S. Lee and C. Kim, "Neighbor Supporting Ad Hoc Multicast Routing Protocol," Proceedings of ACM MOBIHOC 2000, pp. 37-50, August 2000.

[28] J. J. Garcia-Luna-Aceves and E. L. Madruga, "The Core-Assisted Mesh Protocol," IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1380-1994, August 1999.

[29] S. Banerjee, A. Misra, J. Yeo, and A. Agrawala, "Energy-Efficient Broadcast and Multicast Trees for Reliable Wireless Communication," http://www.umiacs.umd.edu/mind/documents/wirelesscom.pdf

[30] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, "Multicasting in Energy-Limited Ad Hoc Wireless Networks," Proceedings of IEEE MILCOM 1998, pp. 18-21, October 1998.

[31] H. Jiang, S. Cheng, Y. He, and B. Sun, "Multicasting along Energy-Efficient Meshes in Mobile Ad Hoc Networks," Proceedings of IEEE WCNC 2002, vol. 2, pp. 807-811, March 2002.

[32] C. Tang, C. S. Raghavendra, and V. Prasanna, "Energy-Efficient Adaptation of Multicast Protocols in Power-Controlled Wireless Ad Hoc Networks," Proceedings of IEEE International Symposium on Parallel Architectures, Algorithms, and Networks 2002, pp. 80-85, May 2002.

[33] G. D. Kondylis, S. V. Krishnamurthy, S. K. Dao, and Gregory J. Pottie, "Multicasting Sustained CBR and VBR Traffic in Wireless Ad Hoc Networks," Proceedings of IEEE ICC 2000, pp. 543-549, June 2000.

[34] I. Karthigeyan, B. S. Manoj, and C. Siva Ram Murthy, "Multicast Priority Scheduling Protocol for Ad Hoc Wireless Networks," Technical Report, Department of Computer Science and Engineering, Indian Institute of Technology, Madras, India, January 2004.

[35] I. Karthigeyan, B. S. Manoj, and C. Siva Ram Murthy, "A Distributed Laxity-Based Priority Scheduling Scheme for Time-Sensitive Traffic in Mobile Ad Hoc Networks," to appear in Ad Hoc Networks Journal.

[36] L. Briesemeister and G. Hommel, "Role-Based Multicast in Highly Mobile But Sparsely Connected Ad Hoc Networks," Proceedings of ACM MOBIHOC 2000, pp. 45-50, August 2000.

[37] H. Zhou and S. Singh, "Content-Based Multicast (CBM) in Ad Hoc Networks," Proceedings of ACM MOBIHOC 2000, pp. 51-60, August 2000.

[38] Y. B. Ko and N. H. Vaidya, "Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithms," Proceedings of IEEE WMCSA 1999, pp. 101-110, February 1999.

[39] C. C. Chiang, H. K. Wu, W. Liu, and M. Gerla, "Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel," Proceedings of IEEE SICON 1997, pp. 197-211, April 1997.

[40] R. Dube, C. D. Rais, K. Y. Wang, and S. K. Tripathi, "Signal Stability-Based Adaptive Routing for Ad Hoc Mobile Networks," IEEE Personal Communications Magazine, vol. 4, no. 1, pp. 36-45, February 1997.

[41] D. B. Johnson and D. A. Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks," Mobile Computing, Kluwer Academic Publishers, vol. 353, pp. 153-181, 1996.

[42] S. Murthy and J. J. Garcia-Luna-Aceves, "An Efficient Routing Protocol for Wireless Networks," ACM Mobile Networks and Applications Journal: Special Issue on Routing in Mobile Communication Networks, vol. 1, no. 2, pp. 183-197, October 1996.

[43] V. D. Park and M. S. Corson, "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks," Proceedings of IEEE INFOCOM 1997, pp. 1405-1413, April 1997.

[44] C. E. Perkins and P. Bhagwat, "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," Proceedings of ACM SIGCOMM 1994, pp. 234-244, August 1994.