1	Pro-Active Route Maintenance in DSR Thomas Kunz Systems and Computer Engineering Carleton University http://kunz-pc.sce.carleton.ca/ tkunz@sce.carleton.ca
2	Mobile Ad Hoc Networks Infrastructure-less, wireless links, may need to traverse multiple links to reach a destination
3	Mobile Ad Hoc Networks Mobility causes route changes
4	Why Ad Hoc Networks ? Ease of deployment Speed of deployment Decreased dependence on infrastructure
5	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
6	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
7	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
8	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
9	Prediction Algorithm (continued)
10	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
11	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
12	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
13	Route Discovery in DSR
14	Route Discovery in DSR
15	Route Discovery in DSR
16	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)
17	Route Reply in DSR
18	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
19	Route Error in DSR
20	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
21	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
22	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)
23	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)
24	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