Pro-Active Route Maintenance in DSR

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

Mobile Ad Hoc Networks

	Infrastructure-less, wireless links, may need to traverse multiple 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

	Routing protocols (both “pro-active” and “on-demand” protocols) keep using a route until a link breaks
	Result:
		Rebuild the route (takes time)
		Packets are dropped

Related Work

	Lots of work on ROUTING PROTOCOLS, though very little on avoiding packet loss due to route failure
		Flow Oriented Routing Protocol (FORP): destination predicts topology change based on the Link Expiration Time
		Associativity Based Routing (ABR), Signal Stability-Based Adaptive Routing (SSA) favor longer-live routes
	Paper in MobiCom 2001
		Also uses signal power strength
		But uses different metrics: preemptive zone, packet latency etc.
		At least 2 times increase in routing protocol overhead for DSR

Prediction Algorithm

	Basic Idea:
		Predict the link breakage time (prediction algorithm)
		Rebuild a route before link breaks (pro-active route maintenance)
	Prediction Algorithm
		Monitor unicast packets from neighboring nodes
		Using signal power strength to predict the link breakage time

Prediction Algorithm (continued)

Simulation Environment

	The Network Simulator (NS2)
		Open Source
		Trace file
		AODV, DSR, etc. have been implemented
	Simulation metrics:
		Dropped Packets: total, due to no route
		Normalized Routing Load
		Hop count ratio
		Packet latency
	Simulation parameters
		50 mobile nodes, 1500x300 m area, 4 data packets per second

Prediction Algorithm Simulation

	Implemented in NS2 to validate the algorithm
		No modification to the routing protocol yet
		Compare the predicted and “real link breakage time”
	Parameter setting
		Critical Time: the time needed to rebuild a new route
	Result:
		Nodes with active link have above 90% prediction accuracy
		Node movement pattern changes may cause false prediction

Dynamic Source Routing Protocol

	Why DSR
		Popular on-demand protocol
		Good performance, complex, packet salvaging
	Route Discovery and Route Maintenance
		When node S wants to send a packet to node D, but does not know a route to D, node S initiates a route discovery
		Source node S floods Route Request (RREQ)
		Each node appends own identifier when forwarding RREQ

Route Discovery in DSR

Route Discovery in DSR

Route Discovery in DSR

Route Reply in DSR

	Route Reply can be sent by reversing the route in Route Request (RREQ) only if links are guaranteed to be bi-directional
		To ensure this, RREQ should be forwarded only if it received on a link that is known to be bi-directional
	If unidirectional (asymmetric) links are allowed, then RREP may need a route discovery for S from node D
		Unless node D already knows a route to node S
		If a route discovery is initiated by D for a route to S, then the Route Reply is piggybacked on  the Route Request from D.
	If IEEE 802.11 MAC is used to send data, then links have to be bi-directional (since Ack is used)

Route Reply in DSR

Route Reply in DSR

	Node S, on receiving RREP, caches the route included in the RREP
	When node S sends a data packet to D, the entire route is included in the packet header
		hence the name source routing
	Intermediate nodes use the source route included in a packet to determine to whom a packet should be forwarded

Route Error in DSR

Pro-active Route Maintenance in DSR

	D calculates predicted link breakage time upon receiving packet from J
	Send Prediction Route Error message to source node if link in critical state
		Source node can rebuild the route
	Maintain source-previous hop node table to limit number of Prediction Route Error messages (up to 3)
	Block Route Request from bad link
		Bad link will not appear in new route
	Timeout mechanism
		Nodes may move closer later

Simulation Results

	Simulation parameters:
		Critical Time: 1s, maximum 3 Prediction Route Error messages
		Simulation length: 900 seconds
		Mobility scenarios: mostly high mobility, averages of seven cases each (95% confidence intervals confirm that results are statistically significant)
	x-y-z: number of senders – pause time – maximum speed

Simulation Results (continued)

	27% to 43% improvement in number of dropped packets due to link breakage
	The number of control messages increased by less than 25% (remember MobiCom paper: 200%)
	High mobility scenarios show consistent improvement (across all seven repetitions)
	Average packet latency not worse (though often better)
	No change to hop count ratio: paths as good as in unmodified version of DSR (metric: shortest path)

Conclusions

	Proposed & implemented Prediction Algorithm
	Proposed & implemented pro-active route maintenance in DSR
	Significant reduction in dropped packets due to link breakage
	Increased number of control messages does not cause network congestion
	No negative impact on other routing protocol metrics (hop count, packet latency)

Future Work

	Pro-active route maintenance in AODV (ongoing): AODV supports multicasting (tree-based), preventing packet drop even more crucial in this case
	Non-constant transmit power levels
	Monitor multicast packets: increase prediction accuracy,  deal with non-constant transmit power
	Remove stale routes in route cache using prediction algorithm
	“Soft handoff”: use old route while source node finds new route
	Impact on TCP (evidence so far is mixed)
	Other ways to predict/monitor/deal with link availability