10-04-2014, 11:20 AM
Routing Protocols for Ad Hoc Mobile Wireless Network
Routing Protocols.ppt (Size: 278.5 KB / Downloads: 69)
Distance-Vector Routing Algorithm
Distributed Bellman-Ford
Each node constructs a one-dimensional array (a vector) containing the “distance”(costs) to all other nodes and next hop id
Routers exchange their routing tables with immediate neighbors
Information includes the distance and next hop id
Typical exchange periods (30s-several minutes)
Slow convergence
Convergence-The process of getting consistent routing information to all the nodes
A loses contact with E
A doesn’t know if there is another path to E
In a table exchange it finds B has a route to E with distance 2
A advertises that it has route to E with distance 3
B advertises that it has route to E with distance 4 to A and C
Cycle repeats-count to infinity problem
Routing tables do not stabilize-slow convergence
Slow Convergence Solution
Split Horizon-Don’t send those routes it learned from each neighbor back to that neighbor.
Poison Reverse-Advertise routes with infinite distance
Hold down-When a major change occurs advertise the change quickly,but don’t accept the new routes for a period of time
Link-State Routing Algorithm
Routers broadcast their neighbor connections to all routers in the network
Information mainly connectivity and cost of the link to each neighbor
Every node has a complete map of the network.
Dijkstra's Shortest Path Algorithm can be used to select the best route to the destination.
No slow convergence problems.
Somewhat larger capacity requirement.
Ad Hoc Protocol Routing Requirements
Simple, reliable and efficient
Distributed but lightweight in nature
Quickly adapts to changes in topology
Protocol reaction to topology changes should result in minimal control overhead
Bandwidth efficient
Mobility management involving user location and hand-off management
Route Table Entry Structure in DSDV
When advertisement, each mobile node contain its new sequence number and the following information for each new route
The destination’s address
The number of costs (hops) required to reach the destination
The sequence number of the information received,originally stamped by the destination.
Expanding Ring Search in AODVd
To reduce the impact of flooding
Broadcast a RREQ with low time to live (TTL)
If no response received, re-transmit request with increased TTL
Fixed values for TTL start, increment and threshold
Beyond threshold, the RREQ is broadcast across the entire network up to rreq-retries times