Increasing Packet Delivery Ratio in DSR by Link Prediction

	Liang Qin and Thomas Kunz
	Carleton University
	http://kunz-pc.sce.carleton.ca/
	tkunz@sce.carleton.ca

Motivation

	Packet loss in MANET due to unpredictable topology:
		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
		Cached routes become stale (i.e., invalid)
			Result: packets are lost when using stale routes
	Basic idea: can we predict link breakage and utilize this information to reduce packet losses

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
		Goal: reduce packet latency
		Different approach: preemptive zone, based on threshold
		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)
		Invalidate cached routes before they become stale
	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

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)
	Idea can be applied to other aspects as well, for example cache maintenance (see paper)

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
	“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
		NS2 has simplistic radio propagation model