DSDV Routing Protocol

Views:
 
     
 

Presentation Description

Ad-Hoc Routing Protocol

Comments

Presentation Transcript

DSDVDestination Sequenced Distance Vector Protocol : 

Felix Peter, Dec. 2, 2003 1 DSDVDestination Sequenced Distance Vector Protocol Seminar presentation for PG MANET-WLAN December 2, 2003

Classification of Routing Protocols for MANETS : 

Felix Peter, Dec. 2, 2003 2 Classification of Routing Protocols for MANETS

Ad-hoc Networks : 

Felix Peter, Dec. 2, 2003 3 Ad-hoc Networks Ad-hoc network: A collection of wireless mobile hosts forming a temporary network without the aid of any established infrastructure or centralized administration. Significant differences to existing wired networks: Wireless Self-starting No administrator Cannot assume, that every computer is within communication range of every other computer Possibly quite dynamic topology of interconnections

Distance-Vector routing : 

Felix Peter, Dec. 2, 2003 4 Distance-Vector routing Each node maintains a routing table containing list of all available destinations number distance to each each destination next hop to reach a destination The succession of next hops leads to a destination Each node periodically broadcasts its current estimate of the shortest distance to each available destination to all of its neighbors Typical representative: Distributed Bellman-Ford (DBF)

Bellman-Ford Algorithm : 

Felix Peter, Dec. 2, 2003 5 Bellman-Ford Algorithm Bellmann-Ford (G,w,s) Initialize-Single-Source (G,s) for i  1 to |V[G]|-1 do for each edge (u,v) E[G] do Relax (u,v,w) for each edge (u,v) E[G] do if d[v] > d[u]+w(u,v) then return FALSE return TRUE

Initialize-Single-Source & Relax : 

Felix Peter, Dec. 2, 2003 6 Initialize-Single-Source & Relax Initialize Single Source (G,s) for each vertex v V[G] do d[v]  [v]  NIL d[s]  0 Relax (u,v,w) if d[v] > d[u] + w(u,v) then d[v]  d[u] + w(u,v) [v]  u

Bellman-Ford Algorithm : 

Felix Peter, Dec. 2, 2003 7 Bellman-Ford Algorithm

Bellman-Ford Routing : 

Felix Peter, Dec. 2, 2003 8 Bellman-Ford Routing Computationally efficient Easy to implement Problem: Can cause loops Problem: Counting to infintiy Modifications elminate the problem of loops but need some internodal coordination mechanisms which imply few topological changes Not designed to handle rapid topological changes

DSDV : 

Felix Peter, Dec. 2, 2003 9 DSDV Design goals: Keep the simplicity of Bellman-Ford Avoid the looping problem Remain compatible in cases where a base station is available Idea: modify the conventional Bellman-Ford routing algorithm Approach: Model each host as a router Tag each routing table entry with a sequence number

The Routing Table : 

Felix Peter, Dec. 2, 2003 10 The Routing Table All available destinations Next hop for each destination Number of hops to each available destination A sequence number for each route table entry, originated by the destination station

Transmitting Route Information : 

Felix Peter, Dec. 2, 2003 11 Transmitting Route Information Routing information is transmitted by broadcast Updates are transmitted periodically or immediately when any significant topology change is available Sequence numbers are assigned by destination (even numbers) If a broken link is detected: metric and updated odd sequence number are assigned by detecting host Full dump: all information from the transmitting node Incremental dump: all information that has changed since the last full dump Full dump if incremental dump exceeds one NPDU (network protocol data unit)

Selection of Routes : 

Felix Peter, Dec. 2, 2003 12 Selection of Routes If new routing information is received Any route with a more recent sequence number is used If the new route has equal seqence number but better metric, this route is chosen Newly recorded routes are scheduled for immediate advertisement

Receiving Fluctuating Routes : 

Felix Peter, Dec. 2, 2003 13 Receiving Fluctuating Routes Mobile Host Collection I Mobile Host Collection II MH9 MH6 MH2 MH4 What might happen: MH9 broadcasts update information to MH Collections I and II MH2 transmits new routing information to MH4 MH4: new sequence number  routing table update  broadcast update MH6 transmits new routing information to MH4, same sequence number, better metric MH4: same seq.no., better metric  update routing table  broadcast update

Damping Fluctuation : 

Felix Peter, Dec. 2, 2003 14 Damping Fluctuation Causes for Fluctuation: Many hosts with irregular updates Different propagation speed Different transmission intervals Broadcasts are asynchronous events Solution: Keep a route settling time table in each node with a time to wait for a route with a better metric before advertising the update message. Settling time: Calculated by maintaining a running weighted average over the most recent updates of the routes for each destination.

Stale Entries : 

Felix Peter, Dec. 2, 2003 15 Stale Entries Stale entries are defined to be entries that have not been updated the last few update periods Stale entries are deleted at the same time when routing updates are applied to the routing table Any route using that host as a next hop is deleted, included the route indicating that host as the actual destination

Example of DSDV in operation : 

Felix Peter, Dec. 2, 2003 16 Example of DSDV in operation MH3 MH6 MH2 MH1 MH7 MH4 MH8 MH5

Example of DSDV in operation : 

Felix Peter, Dec. 2, 2003 17 Example of DSDV in operation MH3 MH6 MH2 MH1 MH7 MH4 MH8 MH5 MH4 advertised table:

Example of DSDV in operation : 

Felix Peter, Dec. 2, 2003 18 Example of DSDV in operation MH3 MH6 MH2 MH1 MH7 MH4 MH8 MH5 MH1 Update triggered by MH1 , broadcasted to MH7 and MH8 On detection of broken link: Immediate incremental update triggered by MH2 with odd sequence number and infinite metric Updates are propagated through the network

Example of DSDV in operation : 

Felix Peter, Dec. 2, 2003 19 Example of DSDV in operation MH3 MH6 MH2 MH7 MH4 MH8 MH5 MH1 MH4 advertised table (updated):

Evaluation of DSDV: Performance : 

Felix Peter, Dec. 2, 2003 20 Evaluation of DSDV: Performance Each node maintains two tables The need of bandwidth and the size of tables grow simultaneously with mobility and number of nodes  overhead for maintaining and updating tables will increase  heavy routing overhead will degrade the performance of the network

Simulation results : 

Felix Peter, Dec. 2, 2003 21 Simulation results Simulation by Broch, Maltz, Johnson, Hu, Jetcheva DSDV fails to converge if nodes don‘t pause for at least 300 seconds Packet delivery ratio is in the range of 70%-92% at higher rate of mobility Packet loss is mainly caused by stale routing entries Routing overhead is approximately constant, regardless of movement rate or traffic load Nearly optimal path can be selected in routing procedure

Stability and Scalability : 

Felix Peter, Dec. 2, 2003 22 Stability and Scalability DSDV requires a full dump update periodically  DSDV is not efficient in route updating DSDV limits the number of nodes that can join the network Whenever topology of a network changes, DSDV is unstable until update packets propagate through the network

Conclusion : 

Felix Peter, Dec. 2, 2003 23 Conclusion DSDV is effective for creating ad-hoc networks for small populations of mobile nodes DSDV is a fairly brute force approach, because connectivity information needs periodical update througout the whole network

Current Status : 

Felix Peter, Dec. 2, 2003 24 Current Status DSDV is a well-known routing algorithm for ad hoc network routing No standard specifications or commercial implementations available Many improved protocols based on DSDV have been developed Example: AODV: Ad-hoc On-Demand Distance Vector Routing

AODV : 

Felix Peter, Dec. 2, 2003 25 AODV AODV is based on the DSDV algorithm Distance vector Sequence numbers Creation of routes on a demand basis Nodes that are not on a selected path do not maintain routing information or participate in routing table exchanges! Goal: Minimize broadcast overhead and transmission latency

AODV : 

Felix Peter, Dec. 2, 2003 26 AODV

AODV : 

Felix Peter, Dec. 2, 2003 27 AODV Path discovery Process: Source node initiates path discovery process by broadcasting RREQ Neighbors forward RREQ RREQ is forwarded until either destination or intermediate node with a „fresh enough“ route to it is located Destination or intermediate node responds by unicasting RREP along the reverse path Local connectivity checked on a regular basis by listening to retransmission or sending hello messages Link failure: Failure notification message (RREP with infinite metric) is passed upstream to the source, erasing that part of the route

AODV: Simulation results : 

Felix Peter, Dec. 2, 2003 28 AODV: Simulation results Simulation by Broch, Maltz, Johnson, Hu, Jetcheva Implementation without Hello mechanism Delivery of over 95% regardless of mobility rate Routing overhead drops as mobility rate drops Not optimal path, up to 4 or more hops longer paths Requires up to 5 times the overhead of DSR

Comparison: DSDV and AODV : 

Felix Peter, Dec. 2, 2003 29 Comparison: DSDV and AODV DSDV: Table driven, proactive Best performance when node mobility rate and movement speed are low Approximately constant overhead, regardless of movement rate or traffic load AODV: On demand Good performance at all mobility rates Still requires transmission of many routing overhead packets

References : 

Felix Peter, Dec. 2, 2003 30 References Charles E. Perkins and P. Bhagwat, „Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers“, ACM SIGCOMM’94, 1994 Guoyou He, „Destination-Sequenced Distance Vector (DSDV) Protocol“ Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, Jorjeta Jetcheva, „A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols“, MobiCom’98, 1998 Charles E. Perkins, Elizabeth M. Royer, „Ad-hoc On-Demand Distance Vector Routing“, 1999 Elizabeth M. Royer, Chai-Keong Toh, „A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks“, IEEE Personal Communications, April 1999 Andrew S. Tanenbaum, Computer Networks, 3rd Edition, Prentice Hall, 1996 T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, 1990