A Multicast Routing Mechanism in Mobile Ad Hoc Network Through Label Switching

Published Online October 2011 in MECS

Available online at

Efficient multicasting in Mobile Ad hoc network faces challenges not encountered in other types of networks such as the mobility of nodes, the tenuous status of communication links, limited resources, and indefinite knowledge of the network topology. In the designing space of multicast protocol, trade-offs must be made between some metrics such as scalability and reliability, flexibility and generality, efficiency and fairness etc. to reach a special objective. On the other hand, the application environments and connection with the Internet require that multicasting should support Quality-of-Service. This is a more challenging requirement because of the inherent characteristics of Mobile Ad hoc Network [1].

MPLS as a QOS provisioning tool has emerged as an elegant solution to meet the bandwidth-management and service requirements for next generation IP based backbone network. We think that multicast and MPLS are two complementary technologies and multicasting over MPLS networks can benefit from the reduction of multicast traffic on one hand, and MPLS ’ flexibility, speed and quality of service on the other hand. Merging MPLS into multicast routing protocol in Mobile Ad hoc network is not only a viable approach, but an elegant solution to enhance the network performance and an efficient solution for multicast scalability and control overhand problems.

* Corresponding author.

In this paper, we present at first the mechanism of a new multicast protocol, the Label Switching Multicast Routing Protocol (LSMRP) for Mobile Ad hoc network, which is based on Wireless MPLS technology.

Secondly, to enable completely separating of control plane and data plane in the mobile ad hoc network, a framework for MAC layer multicast packet forwarding is proposed. A forwarding node in a multicast group can shift the packet forwarding functionality away from the host processor to the wireless network interface card. This is made possible by carrying a label in RTS/ACK control packet of the 802.11 DCF channel access scheme which allowed the MAC layer to determine the packet ’s next hop. Using this novel label-driven packet forwarding mechanism within LSMRP multicast architecture can dramatically enhance the performance of the whole networks.

Finally, we conducted an extensive performance evaluation of LSMRP and ODMRP (On-Demand Multicast Routing Protocol) [2] which explores the effectiveness of different multicast mechanisms in a wide range of Mobile Ad hoc network simulation scenarios. The results of simulation show that LSMRP works well and generates less control packet overhead than ODMRP.

• 2.    Libel Switching Multicast Routing Mechanism

To enable MPLS based multicasting, the multicast tree with JOIN (), LEAVE (), DESTROY (), and RPF () messages should be directly implemented in LDP signaling protocol. With new and extended messages introduced to the CD-LDP, LSMRP sets up and maintains multicast forwarding state in an on-demand fashion. The features of LSMRP can be summarized as follows:

• •    LSMRP is designed to work independently of the unicast protocol used in the Mobile Ad hoc network and can thus work with any unicast protocol or even without a unicast protocol.

• •    LSMRP is completely distributed and does not rely on any centralized coordination or control.

• •    LSMRP adapts its behavior to various network conditions and different sending pattern, can automatically switch to appropriate forwarding topology (tree, mesh, and network-wide flooding) to enable efficient multicasting.

• •    LSMRP uses no periodic control packet, periodic neighbor sensing, or periodic routing table exchanges through network-wide floods.

• •    LSMRP uses label-driven packet forwarding mechanism to separate control plane and data plane in the Mobil Ad hoc network.

All the features above are derived from the flexibility of label-driven packet forwarding mechanism in MPLS.

• A.    Data Structure

LSMRP uses following data structures stored in every wireless node to support all multicasting operations:

• •    Forwarding Equivalence Classes (FEC) table, {FEC, actor, local label, packet interval time, time factor, keep alive count, pointer to output Label}, which is used to manage FEC information and maintain multicasting topology.

• •    Message table, {message type, node ID, message ID, FEC, previous hop, hop count}, is operated by each forwarding node to process control packets and data packets as well.

• •    Output Label table, {status flag, output label, MAC address}, manages information concerning packet forwarding.

• B.    Setting up Multicast Topology

LSMRP sets up multicast topology in an on-demand fashion, and the whole process can be initiated by both source and destination node. Fig. 1 illustrates the process of setting up multicast topology initiated by source node.

Figure 1. setting up multicast topology

When a sender has the first multicast packet to send, it launches an initiating process which includes assigning FEC to packets flow, computing sending-interval according to various application mode, and generating a new FEC table item etc. Then, it generates and sends a Label-Request message through flooding.

During the setup process, not only a multicasting tree but also a mesh is generated. These two kinds of forwarding topology can work alternatively to match the varying network environment. This is made possible by down-stream nodes sending Label-Mapping message to up-stream nodes with two different modes: unicasting via inverse path and flooding. Nodes which have received the Label-Mapping message can potentially become forwarding nodes of the multicasting mesh. Thus, the multicast topology is determined by destination nodes according to their judgments to the network conditions, and source nodes have no need to maintain the multicast topology.

• C.    Adapting to Varying Network Environments

Forwarding topology is the key element to affect the performance of Mobile Ad hoc Network, and it should have the ability to adapt to changing environment. LSMRP uses three different kinds of topology which can be dynamically shifted to appropriately match the varying network conditions and different kinds of application modes. They are: multicasting tree, multicasting mesh, and flooding. Fig. 2 shows how these three kinds of topology shift during a multicast session.

• •    shift tree to mesh

After the first round of setup, packets are forwarded via a multicast tree. Whenever a receiver does not receive Label-Mapping RPLY message within a given time slot, it will flood the Label-Mapping message to launch the second round setup process. Then, each neighbor node will set a temporary output label for the receiver, and packets will be forwarded via a mesh during a period of time.

• •    shift mesh to tree

When source node receive Label-Mapping message via flooding, it will echo with a Label-Mapping RPLY message via an optimal inverse path to the destination. Nodes on this path will set an output label for destination node with a period of time longer than that of temporary label. Then, the forwarding topology shifts to a tree again.

• •    shift mesh to flooding

To handle with link failure problem in Mobile Ad hoc network, forwarding nodes will frequently launch the local repair process. Whenever source node finds there are too much repairing, it can be determine that the network topology is under too much frequent fluctuation. Then, source node will take steps to send packets via flooding by which label switching is not used.

• •    shift flooding to tree

When receiver senses the flooding packets, it will launch the next stage setup process, and a new multicasting tree will be formed to match the new network environment.

Figure 2. multicast topology pattern

LSMRP uses label-switching mechanism in network layer to maintain multicast topology effectively. In order to get better network performance, there is a need to separate the packet forwarding from network layer to MAC layer, and implement MAC layer forwarding through label switching [3]. This demands MAC layer has the ability to identify the next hop of packets. LSMRP transfers Label-switching Forwarding table to MAC layer synchronically, so that MAC layer can determine the next hop of packets without any operation in network layer [4].

The ACK mechanism in MAC layer is crucial for LSMRP to sense changes of network topology [5]. Therefore, we use IEEE 802.11 DCF as the media access control protocol and extend it to support labelswitching in MAC layer. Fig.3 depicts the extending messages and time slots used by LSMRP.

Figure 3. packet forwarding in MAC layer through label-switching

When network-layer forwarding works in mesh and flooding pattern, MAC layer will broadcast to all neighboring nodes, which will in turn receive all broadcasting frames and determine whether to forward them. Broadcasting will waste processing resources of some irrelevant nodes [6]. To solve this problem, LSMRP uses Wireless MPLS packet format to carry data-load and implement constrained broadcasting. In the header of WMPLS packet, the label stack can carry multiple output labels on demand. A convergence node in multicast topology sends packets in this multi-label fashion, which can be used by neighboring nodes to determine whether to forward or just to drop these packets.

a + p = x.                                                                                    (1)Si^uXaTiov РесиХтс

We use Network Simulator 2.1b8 with CMU wireless extensions to evaluate the performance of LSMRP. And we choose the On Demand Multicast Routing Protocol (ODMRP) as a comparison.

• D.    Simulation Enironment

  • •    Wireless model: Lucent Wave LAN 802.11, 2Mbps.

  • •    Mobile scenario: Random Way Point Model, 100 nodes within 1000*800m², and 300 nodes within 2200*1260m²; 2m/s motion velocity.

  • •    Communication scenario: multicast sender and receiver join group randomly; multiple groups is allowed with maximum 10 senders and 50 receivers per group; the packet flow type is CBR.

• E.    Metrics

• •    Packet Delivery Ratio (PDR) measures ratio of successfully received packets within a group and all sent packets by multicast sender.

• •    End-to-End Delay (EED) measures the average delay from sender to receivers in a group.

• •    Control Packet Load (CPL) records the numbers of all control packets in a multicast session.

• F.    Results

• •    Affection of various number of receiver

TABLE I.     Affection of Various Number of Receiver

metrics	protocol	(1,1,10)	(1,1,30)	(2,5,50)
EED	LSMRP	16	18	31
	ODMRP	17	20	25
CPL	LSMRP	0.1	0.1	0.5
	ODMRP	0.4	0.6	1.3
PDR	LSMRP	0.99	0.99	0.99
	ODMRP	0.99	0.99	0.99

An increase of the number of receiver leads to more forwarding nodes and packets, so that results in higher PDR in both LSMRP and ODMRP. But ODMRP generates more multicast forwarding nodes than LSMRP. TABLE I shows metrics of two protocols respectively. And we use “(group number, sender number, receiver number)” to represent a multicasting communication scenario.

• •    Affection of various number of sender

• 4.    Conclusion

When the number of sender increases, LSMRP remains a relatively high PDR, while ODMRP exhibits a slow decrease of PDR. The reason of these phenomena is that more senders will generate more flooding packets in ODMRP, and then the packet crashing ratio became higher and higher, eventually leads to large number of dropped packets.

TABLE II. Affection of Various Number of Sender

metrics	protocol	(1,1,10)	(1,1,30)	(2,5,50)
EED	LSMRP	12	20	23
	ODMRP	11	15	20
CPL	LSMRP	0.16	0.35	0.36
	ODMRP	0.65	3.1	6.3
PDR	LSMRP	0.98	0.98	0.97
	ODMRP	0.99	0.99	0.93

Our study proved that using MPLS with multicast in the Mobile Ad hoc network has many benefits not only for reducing multicast forwarding states but also for traffic engineering and QoS issues. Merging MPLS into multicast routing protocol in Mobile Ad hoc network will give rise to more potential advantages, such as saving more processing resources and energy of mobile host, timely adapting to the network conditions with protocol ’s behavior, and extending wired network services to wireless network more conveniently, etc.

• [1]    Garbinato B ， Rupp. P. From ad hoc networks to ad hoc applications. Telecommunications ， 2003. ConTEL, 2003. Proceedings of the 7^th International Conference on ， Vol. 1 ， June 11~13, 2003 pp. 145~149

• [2]    Sang Ho Bae, ， Sung Ju Lee ， William Su ， and Mario Gerla. The design ， implementation ， and performance evaluation of the on-demand multicast routing protocol in multi-hop wireless networks. IEEE Network January/February 2000 ， pp. 70–77.

• [3]    Ranveer Chandra ， Paramvir Bahl ， and Pradeep Bahl ， “Multinet: Connecting to multipleIEEE 802.11 networks using a single wireless card ， ” in IEEE Infocom ， Hong Kong ， March 2004.

• [4]    A. El-Gamal ， J. Mammen ， B. Prabhakar ， and D. Shah. Throughput-delay trade-offs in wireless networks. In Proc. of IEEE Infocom, March 2004.

• [5]    S. Xu and T. Saadawi. “Does the IEEE 802.11 MAC Protocol Work Well in Multi-hop Wireless Ad Hoc Networks?” ， IEEE Communications Magazine . 39(6) ， June 2001 ， pp. 130-137.

• [6]    Paramvir Bahl ， Ranveer Chandra ， and John Dunagan, “Ssch: Slotted seeded channel hopping for capacity improvement in ieee 802.11 ad-hoc wireless networks ， ” in ACM Mobicom ， 2004.