Efficient Multicast Routing in MANETs Using Prefix Labels

Efficient Multicast Routing in MANETs Using Prefix Labels J.J. Garcia-Luna-Aceves †∗ Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, CA 94304 Email: jj@soe.ucsc.edu Abstract—We introduce Prefix-based Multicast Routing (PMR), the first approach to multicast routing in MANETs in which the network-wide dissemination of control information is independent of the number of groups and sources per group. PMR establishes a labeled directed acyclic graph (LDAG) rooted at an elected node in the MANET and assigns a prefix label to each node denoting its network location relative to the root of the LDAG. Routes between any two prefix labels are implicit in the labels themselves. The sources and receivers of a multicast group use a consistent hashing function to map the identifier of the group (e.g., an IP multicast address) onto the group-prefix-label. The node whose prefix label is the closest match to the group- prefix-label serves as the core of the group. As in prior receiver- initiated multicast approaches, receivers join a multicast group by sending join requests towards the group core, and multicast sources simply forward their multicast data packets towards the cores of the groups. We use simulation experiments to compare PMR with ODMRP and MAODV for different mobility scenarios with varying number of nodes, groups and receivers. The results clearly show that PMR is far more efficient than traditional multicast routing approaches, even in relatively small networks. I. I NTRODUCTION The objective of a multicast routing protocol is to establish routing structures between the sources and receivers of multi- cast groups, such that they can communicate with each other even when they do not enjoy direct physical connectivity. In a MANET, the multicast routing structures linking multicast sources with the receivers of the target multicast groups can be trees or meshes, and a critical aspect in the design of such a protocol consists of limiting the amount of bandwidth consumed in building the necessary trees or meshes. Interestingly, as Section II describes, the traditional ap- proach adopted by the multicast routing protocols proposed and implemented to date for MANETs, consists of building multicast trees or meshes by either having the core of each multicast group, or each source of each multicast group, dis- seminate control packets to the entire MANET. This network- wide dissemination of control information per multicast group, is an approach that does not work well in large-scale MANETs or large MANETs with many multicast groups. However, it is actually a necessity resulting from adopting the IP multicast model for the maintenance of multicast groups, together with with the use of IP or MAC addresses for packet forwarding. More specifically, IP and MAC addresses are really names, Dhananjay Sampath ∗ Computer Engineering Department University of California, Santa Cruz Santa Cruz, CA 95064 Email: dsampath@soe.ucsc.edu especially when they denote multicast groups, in that, they are assigned to nodes independently of their relative location in the MANET. In the IP multicast model, the constituency of a multicast group is not known to any one node, and the only identifiers used for multicast forwarding are the names of the multicast groups. Accordingly, the only way for either the core or a source of a multicast group to update potential receivers, of its relative location, is by sending updates to the entire network. Receivers can then send join requests towards the core, or towards sources of a multicast group, to build a multicast tree or mesh. Multicast data packets can then be forwarded over this routing structure, using the name of the group. The main contribution of this paper is the introduction of the first approach to multicast routing in MANETs in which the network-wide dissemination of routing information grows only linearly with the number of nodes in the network and independently of the number of multicast groups or sources per group. This makes it far more efficient than traditional sender- or receiver-initiated approaches. In this paper, we assume that the MANET is connected, and leave the handling of network partitions and disruption-tolerant multicasting for future work. Section III presents the Prefix-based Multicast Routing (PMR) protocol, which adopts the IP multicast model and enables receiver-initiated multicasting for any number of mul- ticast groups. PMR first establishes a labeled directed acyclic graph (LDAG) rooted at an elected node in the MANET, and uses prefix labels for forwarding of control and multicast data packets. A prefix label is assigned to each node denoting its network location relative to the root of the LDAG. Routing between any two prefix labels is implicit owing to the ordering with respect to the root of the LDAG. Multicast sources and receivers use a consistent hashing function to map the name of a multicast group (e.g., an IP multicast address) onto its group prefix label. The node with a prefix label that is the closest to the group prefix label becomes the core of the multicast group. Based on this simple indirection, PMR supports receiver- initiated multicasting as in CBT [1] or CAMP [3]. Receivers build a multicast routing tree by sending join-requests towards the group-prefix-label, and a source similarly forwards data packets towards the group-prefix-label as well. Section IV compares the performance of PMR with that of