1
|
- Thomas Kunz
- Systems and Computer Engineering
- Carleton University
- http://kunz-pc.sce.carleton.ca/
- tkunz@sce.carleton.ca
|
2
|
- Infrastructure-less, wireless links, may need to traverse multiple links
to reach a destination
|
3
|
- Mobility causes route changes
|
4
|
- Ease of deployment
- Speed of deployment
- Decreased dependence on infrastructure
|
5
|
- Personal area networking
- cell phone, laptop, ear phone, wrist watch
- Military environments
- Civilian environments
- taxi cab network
- meeting rooms
- sports stadiums
- boats, small aircraft
- Emergency operations
- search-and-rescue
- policing and fire fighting
|
6
|
- 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
|
- 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
|
- 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
|
|
10
|
- 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
|
- 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
|
- 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
|
|
14
|
|
15
|
|
16
|
- 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
|
|
18
|
- 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
|
|
20
|
- 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 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
|
- 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
|
- 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
|
- 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
|