📡Systems Approach to Computer Networks Unit 12 – Routing: Link State & Distance Vector

What's This All About?

• Routing algorithms enable network devices to determine optimal paths for data transmission between source and destination nodes
• Efficient routing is crucial for minimizing network congestion, reducing latency, and ensuring reliable packet delivery
• Routing algorithms use various metrics (bandwidth, hop count, delay) to calculate the best routes
• Two primary categories of routing algorithms are link state and distance vector routing
• Link state routing uses a global view of the network topology, while distance vector routing relies on information from neighboring nodes
• Routing algorithms dynamically adapt to network changes (link failures, congestion) to maintain optimal paths
• Routing protocols (OSPF, RIP) implement these algorithms to facilitate communication between routers and exchange routing information

Key Concepts

• Routing table contains information about network destinations and the best paths to reach them
• Convergence refers to the process of all routers in a network agreeing on the optimal routes
• Routing metrics are used to determine the best path, considering factors like bandwidth, delay, and hop count
• Autonomous System (AS) is a collection of networks under a single administrative domain
• Interior Gateway Protocols (IGPs) are used for routing within an AS (OSPF, IS-IS)
• Exterior Gateway Protocols (EGPs) are used for routing between different ASes (BGP)
• Dijkstra's algorithm is a key component of link state routing, used to calculate the shortest paths

How It Works

• Routers exchange information about network topology and link states with neighboring routers
• Each router builds a complete view of the network topology using the received information
• Routers use routing algorithms to calculate the best paths to each destination based on the available information
• The calculated best paths are stored in the routing table, which is consulted for forwarding packets
• When a packet arrives at a router, the router looks up the destination address in its routing table to determine the next hop
• The packet is then forwarded to the next hop router, which repeats the process until the packet reaches its destination
• Routing algorithms continuously update the routing tables to reflect changes in the network topology

Types of Routing Algorithms

• Link State Routing
  • Each router has a complete view of the network topology
  • Routers flood link state information to all other routers in the network
  • Dijkstra's algorithm is used to calculate the shortest paths to each destination
  • Examples: OSPF, IS-IS
• Distance Vector Routing
  • Routers exchange routing information only with their directly connected neighbors
  • Each router maintains a vector of distances (costs) to all known destinations
  • Bellman-Ford algorithm is used to calculate the shortest paths based on the received distance vectors
  • Examples: RIP, EIGRP
• Path Vector Routing
  • Similar to distance vector routing but includes path information in addition to distance
  • Routers exchange path vectors containing the entire path to each destination
  • Helps prevent routing loops and provides more control over route selection
  • Example: BGP

Link State Routing Deep Dive

• Each router creates a link state packet (LSP) containing information about its directly connected links and their states
• LSPs are flooded throughout the network, allowing each router to build a complete network topology map
• Flooding is a reliable way to ensure all routers have the same view of the network
• Dijkstra's algorithm is run on the topology map to calculate the shortest paths to all destinations
• The resulting shortest paths are installed in the routing table for packet forwarding
• When a link state change occurs (link failure or restoration), the affected router floods an updated LSP
• Other routers update their topology maps and recalculate the shortest paths if necessary
• Link state routing provides fast convergence and is less prone to routing loops compared to distance vector routing

Distance Vector Routing Explained

• Each router maintains a routing table (distance vector) containing the distance (cost) to each known destination
• Routers periodically exchange their distance vectors with directly connected neighbors
• Upon receiving a distance vector from a neighbor, a router updates its own distance vector using the Bellman-Ford algorithm
• The Bellman-Ford algorithm calculates the shortest path to each destination based on the received distance vectors
• The algorithm iteratively updates the distance vector until convergence is achieved
• Split Horizon and Poison Reverse techniques are used to prevent routing loops
  • Split Horizon prevents a router from advertising a route back to the neighbor from which it learned the route
  • Poison Reverse advertises an infinite distance (unreachable) for a route back to the neighbor from which it learned the route
• Distance vector routing is simpler to implement compared to link state routing but has slower convergence and is more prone to routing loops

Pros and Cons

• Link State Routing Pros:
  • Fast convergence due to the complete network topology view
  • Less prone to routing loops
  • Supports multiple paths to a destination (equal-cost multi-path routing)
• Link State Routing Cons:
  • Higher memory and processing requirements due to the need to store and process the entire network topology
  • Increased bandwidth consumption due to flooding of link state packets
• Distance Vector Routing Pros:
  • Simpler to implement and configure
  • Lower memory and processing requirements compared to link state routing
  • Suitable for smaller networks with fewer routers
• Distance Vector Routing Cons:
  • Slower convergence due to the iterative Bellman-Ford algorithm
  • More prone to routing loops, even with loop prevention techniques
  • Limited scalability due to the need to maintain and exchange distance vectors with all neighbors

Real-World Applications

• OSPF (Open Shortest Path First) is a widely used link state routing protocol
  • Commonly deployed in large enterprise networks and ISP backbones
  • Supports hierarchical routing using areas to improve scalability
  • Provides fast convergence and efficient use of network resources
• IS-IS (Intermediate System to Intermediate System) is another link state routing protocol
  • Primarily used in ISP networks and large data centers
  • Designed for high scalability and supports both IP and OSI protocols
• RIP (Routing Information Protocol) is a distance vector routing protocol
  • Suitable for small to medium-sized networks
  • Easy to configure and deploy
  • Limited scalability due to a maximum hop count of 15
• EIGRP (Enhanced Interior Gateway Routing Protocol) is a Cisco-proprietary distance vector routing protocol
  • Combines features of both distance vector and link state routing
  • Provides faster convergence and better scalability compared to traditional distance vector protocols
  • Supports unequal-cost load balancing and advanced routing metrics