Multicasting in Ad-Hoc Networks: Comparing AODV and ODMRP

Thomas Kunz and Ed Cheng

Systems and Computer Engineering

Carleton University

http://kunz-pc.sce.carleton.ca/

tkunz@sce.carleton.ca

Mobile Ad Hoc Networks

Infrastructure-less, may need to traverse multiple wireless links to reach a destination

Mobile Ad Hoc Networks

Mobility causes route changes

Why Ad Hoc Networks ?

Ease of deployment

Speed of deployment

Decreased dependence on infrastructure

Many Applications

Personal area networking

cell phone, laptop, ear phone, wrist watch

Military environments

soldiers, tanks, planes

Civilian environments

taxi cab network

meeting rooms

sports stadiums

boats, small aircraft

Emergency operations

search-and-rescue

policing and fire fighting

Motivation

Many envisioned applications for ad hoc networks require one-to-many communication

Multicast protocols are intended to efficiently support such communication patterns

Multicasting well researched in fixed networks (i.e., the Internet), but host and router mobility cause problems

MANET specific protocols are being proposed

MAODV: multicast extensions for AODV, establishes shared tree

ODMRP: new multicast protocol, based on per-source mesh

Goal: study and compare protocols to identify possible avenues for improvement

Related Work

Bagrodia et al.: compared a number of MANET multicast protocols, found that mesh-based protocols outperform tree-based protocols (includes ODMRP but not MAODV)

Lim and Kim: proposed generic approach to reduce flooding inherent in multicast tree construction

Royer and Perkins: studied effect of transmission range on AODV performance

Our work: compare two proposed protocols based on very different design principles and study performance under various scenarios

MAODV

MAODV: Multicast Ad Hoc On-Demand Distance Vector protocol

Routes discovered on-demand via broadcast

MAODV (cont)

Nodes in the multicast tree reply

MAODV (cont)

Source selects and activates one route, based on AODV route selection criteria (freshest info, shortest route)

MAODV (cont)

First node to join a group becomes leader

Leader periodically broadcasts group hello messages (including updated group sequence number)

Multicast tree based on hard state, nodes joining or leaving require action to reconfigure the tree

Downstream nodes who detect link failure will try to reconnect to tree

In case of network partition, two trees get established, after network partitions merge, multicast trees are merged again as well.

One node will receive two group hello messages for some multicast group and will ask the leader with lower ID for permission to reconnect and will do so by joining multicast group

ODMRP

ODMRP: On-demand Multicast Routing Protocol

Each source periodically broadcasts join requests, interested receivers reply, mesh gets established

ODMRP (cont)

Qualitative Comparison

Simulation Environment

NS2

Widely used network simulator

Simple physical model (free space propagation plus two-way ground reflection)

MAC: 802.11 RTS/CTS

Provides support for node mobility, unicast protocols such as DSR, AODV for ad hoc networks already implemented

Simulation parameters

1000 x 1000 meter area, 250 m radio range, 2 Mbps link capacity

50 nodes, 1 multicast group

900 seconds simulation time

Mobility model: Random Waypoint model, 0 seconds pause time, max speed between 1 m/s to 20 m/s

Traffic: CBR (4 packets of 512 bytes per second and sender)

Parameters varied: Number of Senders, Node Mobility, Group Size

Simulation Environment:
Evaluation Criteria

Packet Delivery Ratio: The ratio of the number of packets actually delivered to the destinations versus the number of data packets supposed to be received

Number of data packets transmitted per data packet delivered: includes retransmissions and dropped packets

Number of control packets transmitted per data packet delivered: routing protocol overhead, normalized by user traffic (protocols are on-demand)

Number of control packets and data packets transmitted per data packet delivered: This measure tries to capture a protocol’s channel access efficiency, as the cost of channel access is high in contention-based link layers

Results I: Number of Senders

Twenty group members, maximum speed 1m/s

Results I: Number of Senders (cont)

Results II: Node Mobility

Twenty multicast group members, five senders

Results II: Node Mobility (cont)

Results III: Multicast Group Size

Five senders, maximum speed 1m/s

Results III: Multicast Group Size (cont)

Conclusions

MAODV has poorer packet delivery ratio

MAODV uses a shared tree for data dissemination. If a single tree link breaks because of node movement, packet collision, or congestion, destinations cannot receive packets

ODMRP provides redundant routes with a mesh topology and the chances of packet delivery to destinations remain high even when the primary routes are unavailable

ODMRP suffers from scalability issues as the multicast group increases or the sender size increases

ODMRP maintains per-source meshes connecting receivers and senders. As the number of senders increase, periodic Join Query packets increase, causing higher amounts of congestion and control overhead

MAODV uses a single multicast group leader to send out periodic Hellos through the network. Increasing the number of senders has minimal impact

Future Work

Study impact of traffic (not just CBR)

Preliminary results show that MAODV is more sensitive to traffic type

Reduce flooding overhead inherent in both protocols using pruning and dominant pruning

MAODV: lower data delivery ratio, but also lower overheads

Improve tree maintenance by pro-actively predicting link failure and triggering tree maintenance BEFORE receivers get disconnected

Results for unicast case show that link breakages based on received signal power strength can accurately be predicted and used to significantly reduce number of dropped packets

Reduce packet drop rates by 30% - 45%

Increase control messages by 19% - 43%

Reduce packet latency by up to 25% (though some increase possible at low mobility rates)


	Thomas Kunz and Ed Cheng
	Systems and Computer Engineering
	Carleton University
	http://kunz-pc.sce.carleton.ca/
	tkunz@sce.carleton.ca


	Infrastructure-less, may need to traverse multiple wireless links to reach a destination



	Ease of deployment

	Speed of deployment

	Decreased dependence on infrastructure


	Personal area networking
		cell phone, laptop, ear phone, wrist watch
	Military environments
		soldiers, tanks, planes
	Civilian environments
		taxi cab network
		meeting rooms
		sports stadiums
		boats, small aircraft
	Emergency operations
		search-and-rescue
		policing and fire fighting


	Many envisioned applications for ad hoc networks require one-to-many communication
	Multicast protocols are intended to efficiently support such communication patterns
	Multicasting well researched in fixed networks (i.e., the Internet), but host and router mobility cause problems
	MANET specific protocols are being proposed
		MAODV: multicast extensions for AODV, establishes shared tree
		ODMRP: new multicast protocol, based on per-source mesh
	Goal: study and compare protocols to identify possible avenues for improvement


	Bagrodia et al.: compared a number of MANET multicast protocols, found that mesh-based protocols outperform tree-based protocols (includes ODMRP but not MAODV)
	Lim and Kim: proposed generic approach to reduce flooding inherent in multicast tree construction
	Royer and Perkins: studied effect of transmission range on AODV performance
	Our work: compare two proposed protocols based on very different design principles and study performance under various scenarios


	MAODV: Multicast Ad Hoc On-Demand Distance Vector protocol
	Routes discovered on-demand via broadcast


	Source selects and activates one route, based on AODV route selection criteria (freshest info, shortest route)


	First node to join a group becomes leader
	Leader periodically broadcasts group hello messages (including updated group sequence number)
	Multicast tree based on hard state, nodes joining or leaving require action to reconfigure the tree
	Downstream nodes who detect link failure will try to reconnect to tree
	In case of network partition, two trees get established, after network partitions merge, multicast trees are merged again as well.
		One node will receive two group hello messages for some multicast group and will ask the leader with lower ID for permission to reconnect and will do so by joining multicast group


	ODMRP: On-demand Multicast Routing Protocol
	Each source periodically broadcasts join requests, interested receivers reply, mesh gets established


	NS2
		Widely used network simulator
		Simple physical model (free space propagation plus two-way ground reflection)
		MAC: 802.11 RTS/CTS
		Provides support for node mobility, unicast protocols such as DSR, AODV for ad hoc networks already implemented
	Simulation parameters
		1000 x 1000 meter area, 250 m radio range, 2 Mbps link capacity
		50 nodes, 1 multicast group
		900 seconds simulation time
		Mobility model: Random Waypoint model, 0 seconds pause time, max speed between 1 m/s to 20 m/s
		Traffic: CBR (4 packets of 512 bytes per second and sender)
		Parameters varied: Number of Senders, Node Mobility, Group Size


	Packet Delivery Ratio: The ratio of the number of packets actually delivered to the destinations versus the number of data packets supposed to be received
	Number of data packets transmitted per data packet delivered: includes retransmissions and dropped packets
	Number of control packets transmitted per data packet delivered: routing protocol overhead, normalized by user traffic (protocols are on-demand)
	Number of control packets and data packets transmitted per data packet delivered: This measure tries to capture a protocol’s channel access efficiency, as the cost of channel access is high in contention-based link layers


	MAODV has poorer packet delivery ratio
		MAODV uses a shared tree for data dissemination. If a single tree link breaks because of node movement, packet collision, or congestion, destinations cannot receive packets
		ODMRP provides redundant routes with a mesh topology and the chances of packet delivery to destinations remain high even when the primary routes are unavailable
	ODMRP suffers from scalability issues as the multicast group increases or the sender size increases
		ODMRP maintains per-source meshes connecting receivers and senders. As the number of senders increase, periodic Join Query packets increase, causing higher amounts of congestion and control overhead
		MAODV uses a single multicast group leader to send out periodic Hellos through the network. Increasing the number of senders has minimal impact


Study impact of traffic (not just CBR)
	Preliminary results show that MAODV is more sensitive to traffic type
Reduce flooding overhead inherent in both protocols using pruning and dominant pruning
MAODV: lower data delivery ratio, but also lower overheads
	Improve tree maintenance by pro-actively predicting link failure and triggering tree maintenance BEFORE receivers get disconnected
	Results for unicast case show that link breakages based on received signal power strength can accurately be predicted and used to significantly reduce number of dropped packets
		Reduce packet drop rates by 30% - 45%
		Increase control messages by 19% - 43%
		Reduce packet latency by up to 25% (though some increase possible at low mobility rates)