12.2 Distance Vector Routing

Distance vector routing is a key method for routers to determine the best paths through a network. It relies on routers sharing their routing tables with neighbors, allowing each to calculate the shortest paths to destinations using the Bellman-Ford algorithm.

This approach has strengths in simplicity and distributed operation, but also faces challenges. Slow convergence, potential routing loops, and scalability issues can arise, especially in larger networks. Understanding these trade-offs is crucial for network design and troubleshooting.

Distance Vector Routing

Principles of distance vector routing

Top images from around the web for Principles of distance vector routing

• 

  CS 360: Lecture 21: Single Source Shortest Paths - Bellman-Ford Algorithm View original

  Is this image relevant?

• 

  Bellman-Ford algorithm - Algowiki View original

  Is this image relevant?

• 

  Distance Vector Routing Protocols | CCNAX 200-120 View original

  Is this image relevant?

• 

  CS 360: Lecture 21: Single Source Shortest Paths - Bellman-Ford Algorithm View original

  Is this image relevant?

• 

  Bellman-Ford algorithm - Algowiki View original

  Is this image relevant?

1 of 3

Top images from around the web for Principles of distance vector routing

• 

  CS 360: Lecture 21: Single Source Shortest Paths - Bellman-Ford Algorithm View original

  Is this image relevant?

• 

  Bellman-Ford algorithm - Algowiki View original

  Is this image relevant?

• 

  Distance Vector Routing Protocols | CCNAX 200-120 View original

  Is this image relevant?

• 

  CS 360: Lecture 21: Single Source Shortest Paths - Bellman-Ford Algorithm View original

  Is this image relevant?

• 

  Bellman-Ford algorithm - Algowiki View original

  Is this image relevant?

1 of 3

• Each router maintains a routing table
  • Contains best known distance to each destination (e.g. number of hops)
  • Learned from neighboring routers through periodic updates
• Routers share their routing tables with directly connected neighbors
  • Exchange updates periodically (e.g. every 30 seconds in RIP) or when network topology changes (e.g. link failure)
• Routers use received information to update their own routing tables
  • Bellman-Ford algorithm calculates shortest paths based on neighbor updates

Exchange of routing information

• Routers send their entire routing table to neighboring routers
  • Typically using a routing protocol like RIP (Routing Information Protocol)
• Routing updates exchanged periodically
  • Usually every 30 seconds in RIP to ensure consistent information
• Triggered updates sent when network topology changes
  • Link failure or addition of a new router prompts immediate update
• Routers process received updates and update their own routing tables
  • Best path to each destination chosen based on shortest distance metric (e.g. hop count)

Bellman-Ford algorithm in routing

• Bellman-Ford algorithm calculates shortest paths in distance vector routing
• Each router maintains a distance vector
  • Contains the shortest known distance to each destination (e.g. number of hops)
• Algorithm iteratively updates distance vectors based on information from neighbors
  • $d_x(y) = min_v\{c(x,v) + d_v(y)\}$
    • $d_x(y)$: Shortest distance from router $x$ to destination $y$
    • $c(x,v)$: Cost of link between routers $x$ and $v$ (e.g. 1 for each hop)
    • $d_v(y)$: Shortest distance from router $v$ to destination $y$
• Algorithm converges when no further updates are made
  • Routers continue to share vectors until all have consistent shortest path information

Limitations of distance vector routing

• Slow convergence
  • Updates are periodic, so changes take time to propagate through the network
• Routing loops can occur
  • Inconsistent routing information during topology changes causes packets to loop
• Count-to-infinity problem
  • Occurs when a link or router fails and is no longer reachable
  • Routers keep incrementing distance to unreachable destination (e.g. 16 hops in RIP)
  • Can take a long time to detect and resolve, causing prolonged outages
• Scalability issues
  • Routing table size grows with network size, consuming memory
  • Periodic updates consume bandwidth, even when no changes occur
• Limited metrics
  • Typically only considers hop count, not other factors like bandwidth or delay
  • May not always choose the optimal path for traffic requirements