1	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
2	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
3	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
4	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
5	Prediction Algorithm (continued)
6	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
7	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
8	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
9	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
10	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
11	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)
12	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)
13	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