12.1 Link State Routing

Link state routing is a powerful approach to network routing. It distributes complete topology information throughout the network, allowing routers to make informed decisions based on a comprehensive view of the network structure.

Routers exchange link state packets to build and maintain a database of the entire network topology. Using Dijkstra's algorithm, they calculate the shortest paths to all destinations, enabling efficient and accurate routing decisions.

Link State Routing

Concept of link state routing

Top images from around the web for Concept of link state routing

• 

  Dijkstra's algorithm - Wikipedia View original

  Is this image relevant?

• 

  networking - Link state routing protocol - Dijkstras Algorithm - Stack Overflow View original

  Is this image relevant?

• 

  OSPF Neighbor States and Link-State Database | ICND2 200-105 View original

  Is this image relevant?

• 

  Dijkstra's algorithm - Wikipedia View original

  Is this image relevant?

• 

  networking - Link state routing protocol - Dijkstras Algorithm - Stack Overflow View original

  Is this image relevant?

1 of 3

Top images from around the web for Concept of link state routing

• 

  Dijkstra's algorithm - Wikipedia View original

  Is this image relevant?

• 

  networking - Link state routing protocol - Dijkstras Algorithm - Stack Overflow View original

  Is this image relevant?

• 

  OSPF Neighbor States and Link-State Database | ICND2 200-105 View original

  Is this image relevant?

• 

  Dijkstra's algorithm - Wikipedia View original

  Is this image relevant?

• 

  networking - Link state routing protocol - Dijkstras Algorithm - Stack Overflow View original

  Is this image relevant?

1 of 3

• Link state routing protocol distributes topology information throughout a network
  • Each router maintains a database of the entire network topology (link state database)
  • Routers exchange link state packets (LSPs) to build and update their topology database (OSPF, IS-IS)
• Routers make routing decisions based on the complete network topology
  • Dijkstra's algorithm calculates the shortest path to each destination (shortest path tree)
• Link state routing is a proactive protocol
  • Routers proactively maintain the network topology and calculate paths
  • Routing tables are updated whenever there is a change in the network topology (link failure, new router)

Flooding of link state packets

• Each router creates an LSP containing information about its directly connected links
  • LSP includes the router's ID, list of directly connected neighbors, and link costs (bandwidth, delay)
• Routers flood their LSPs to all other routers in the network
  • LSPs are transmitted reliably to ensure they reach all routers (acknowledgments, retransmissions)
  • Sequence numbers identify the most recent LSP from each router (prevent outdated information)
• Routers store received LSPs in their link state database
  • Database represents the complete network topology (graph)
• Routers periodically refresh their LSPs and flood them again
  • Ensures that all routers have up-to-date topology information (synchronization)

Dijkstra's algorithm in routing

• Dijkstra's algorithm is a graph traversal algorithm used to find the shortest path
  • Operates on the link state database, which represents the network as a weighted graph (nodes, edges)
• Algorithm maintains two sets: visited nodes and unvisited nodes
  • Visited nodes have their shortest path determined (permanent label)
  • Unvisited nodes have not yet had their shortest path calculated (tentative label)
• Algorithm starts with the source router and assigns it a distance of 0
  • All other nodes are assigned a distance of infinity (unreachable)
• Algorithm selects the unvisited node with the smallest distance and marks it as visited
  • Updates the distances of its unvisited neighbors based on the link cost (relaxation)
• Process repeats until all nodes are visited
  • Resulting in the shortest path from the source to every other node in the network (shortest path tree)

Link state vs distance vector routing

• Advantages of link state routing:
  • Faster convergence time due to complete topology information (no "counting to infinity")
  • More accurate routing decisions based on the entire network topology (optimal paths)
  • Ability to detect and avoid routing loops (split horizon, poisoned reverse)
  • Supports multiple paths and load balancing (equal-cost multipath)
• Disadvantages of link state routing:
  • Higher memory and processing requirements due to storing the complete topology (scalability)
  • Increased bandwidth consumption due to flooding of LSPs (overhead)
  • More complex to implement and maintain compared to distance vector routing (configuration)
• Distance vector routing advantages:
  • Simpler to implement and maintain (Bellman-Ford algorithm)
  • Lower memory and processing requirements (only neighbor information)
  • Reduced bandwidth consumption due to incremental updates (triggered updates)
• Distance vector routing disadvantages:
  • Slower convergence time due to incremental updates (count to infinity problem)
  • Susceptible to routing loops and counting-to-infinity problem (split horizon, route poisoning)
  • Limited knowledge of the network topology (suboptimal paths)