Sujith's Library

Appearance

Routing Algorithms ​

Routing is the process at the network layer of selecting a path for traffic to travel from a source to a destination. For routing, a network is modeled as a graph where routers are nodes and the links between them are edges. Each edge has an associated cost (or metric), and the goal is to find the least-cost path between any two nodes. Common metrics include hop count, bandwidth, delay, and reliability.

A routing algorithm is the core logic or calculation that determines the best path. It's the "brain" that computes the route based on information about the network's topology and link costs. The output of the algorithm is used to populate the router's forwarding table.

  • Example: Dijkstra's algorithm or the Bellman-Ford algorithm.

A routing protocol is the set of rules and messages that routers use to communicate with each other. It's the system they use to exchange the information needed to run their routing algorithms, such as network topology changes or link failures.

The protocol ensures all routers have an up-to-date view of the network to make correct routing decisions.

  • OSPF (Open Shortest Path First), which uses Dijkstra's algorithm.

  • RIP (Routing Information Protocol), which uses the Bellman-Ford algorithm.

  • BGP (Border Gateway Protocol).

Classification of Routing Algorithms ​

Routing algorithms can be classified based on how they gather information and adapt to changes.

1. Global vs. Decentralized ​

This classification is based on whether a router has a complete picture of the network (Network State Awareness).

  • Global (Link-State) Algorithms: Every router has a complete map of the entire network topology and all link costs. It uses this global information to compute the best path from itself to all other nodes.

    • Example Algorithm: Dijkstra's Algorithm
    • Example Protocol: OSPF (Open Shortest Path First)

  • Decentralized (Distance-Vector) Algorithms: Each router only knows the cost to its directly connected neighbors. It calculates routes iteratively by exchanging information with these neighbors, gradually building a picture of the network.

    • Example Algorithm: Bellman-Ford Algorithm
    • Example Protocol: RIP (Routing Information Protocol)

2. Static vs. Dynamic ​

This classification is based on how routes are updated (Based on Adaptivity).

  • Static (Non-Adaptive) Routing: Routes are configured manually by a network administrator. They predefined and do not change automatically in response to network conditions.

  • Dynamic (Adaptive) Routing: Routers use a routing protocol to automatically adjust routes in response to events like link failures or changes in topology. This is the approach used in most modern networks using metrics like hop count, latency and bandwidth.

Based on Traffic Awareness:

  • Load-Sensitive Routing: Link costs are dynamically adjusted based on current congestion levels.

  • Load-Insensitive Routing: Link costs remain static and do not reflect real-time traffic conditions.

The two main classes of dynamic routing algorithms used by routing protocols are Link-State and Distance-Vector routing.

It is a Global Routing Algorithm, where each router has complete knowledge of the network topology and link costs.

It is an Adaptive or Dynamic Routing Algorithm as it responds to topology changes.

The core idea behind link-state routing is that every router acts as a mapmaker. Each router builds a complete and identical map of the entire network's topology. Once it has the full map, it can independently calculate the shortest path from itself to every other possible destination.

  1. Discover Neighbors: Each router first discovers its directly connected neighbors and the cost (e.g., delay, bandwidth) of the link to each one.

  2. Broadcast Information: Each router then broadcasts this information about its direct links, known as its Link-State Packet (LSP) to every other router in the network. LSP contains, IDs of its directly connected neighbors, Link costs to each of those neighbors.

  3. Build the Map: By collecting the LSPs from all other routers, every router in the network can construct an identical and complete graph of the entire network topology.

  4. Calculate Shortest Paths: With the full map, each router uses Dijkstra's algorithm to independently compute the shortest path from itself to every other router. The results are used to build its forwarding table.

The algorithm uses a weighted graph model where:

  • Nodes represent routers
  • Edges represent links with associated costs

Key Terms:

  • D(v) - current shortest distance estimate from source node u to node v
  • p(v) - predecessor of node v on the shortest path
  • N' - set of nodes whose shortest path from u has been finalized

Dijkstra's Algorithm Steps: ​

  1. Initialization:

    • N' = {u}
    • For each node v in N:
      • If v is a neighbor of u: D(v) = c(u,v)
      • Else: D(v) = ∞

  2. Loop:

    • Select w not in N' such that D(w) is minimum
    • Add w to N'
    • For each neighbor v of w not in N':
      • D(v) = min(D(v), D(w) + c(w,v))

  3. Repeat until N' = N

Forwarding Table Construction: For each destination, the router selects the next-hop router based on the path computed using Dijkstra's algorithm.

Advantages: ​

  • Full Topology Knowledge: Each router has a synchronized and comprehensive view of the network, which can be useful for troubleshooting.

  • Loop-Free Paths: The algorithm guarantees the calculation of optimal, loop-free paths.

  • Fast Convergence: Since every router has a complete map, it can react quickly to changes in the network topology.

Disadvantages: ​

  • Higher Overhead: Broadcasting link-state information can consume significant bandwidth, especially in large networks.

  • Resource Intensive: It requires more memory to store the entire network map and more CPU power to run Dijkstra's algorithm.

  • May suffer from Routing Oscillations if link costs depend on traffic

Common Protocols: OSPF (Open Shortest Path First) and IS-IS (Intermediate System to Intermediate System).

Distance Vector Routing (Bellman-Ford Algorithm) ​

Distance Vector routing is a dynamic routing algorithm where routers make decisions in a decentralized way, based on information received from their immediate neighbors, rather than having a complete map of the network. This approach is often described as "routing by rumor."

Each router only needs to know the cost to reach its direct neighbors and relies on them to learn about more distant parts of the network. The algorithm is based on the Bellman-Ford algorithm.

It was initially implemented in ARPAnet, earliest packet-switching networks, and later standardized in protocols like the Routing Information Protocol (RIP).

The process is iterative and involves three key steps that repeat until the network's routing information stabilizes (converges).

  1. Maintain a Vector: Each router maintains a routing table, known as a distance vector. Lists all known destinations in the network with it's:

    • Estimated cost (or "distance") to reach them, and
    • The next-hop router (preferred neighbor to use to reach that destination).
    • The distance is typically measured in hop count (the number of routers a packet must traverse).
    • Delay estimation might also be used with ECHO packets to measure response time.

  2. Share with Neighbors: Periodically, each router broadcasts its entire distance vector to all of its directly connected neighbors. This sharing is how "rumors" about the network topology spread.

  3. Update Local Information: When a router receives a distance vector from a neighbor, it compares the received information with its own routing table.

    • If the neighbor provides a shorter path to a destination, the router updates its table with this new, more efficient route. This update is calculated using the Bellman-Ford equation.

This cycle of sharing and updating continues until no more changes are sent, meaning all routers have converged on the optimal routes based on the information they have.

The Bellman-Ford Equation ​

When a router x receives a distance vector from its neighbor v, it calculates the cost to reach any destination y through that neighbor and chooses the path with the minimum cost.

Dₓ(y) = minᵥ{c(x,v) + Dᵥ(y)}

  • Dₓ(y): Estimated cost from node x to destination y
  • c(x,v): Known cost from node x to its neighbor v
  • Dᵥ(y): Neighbor v's estimate of cost to reach y

The router selects the neighbor v that provides the lowest total cost to reach y and sets that neighbor as the next hop for that destination.

Widely used in practical routing protocols such as:

  • RIP (Routing Information Protocol)
  • BGP (Border Gateway Protocol) uses a variant called Path-Vector Protocol

Advantages: ​

  • Simplicity: It is generally simpler to implement and requires less computational power than link-state algorithms.

  • Low Resource Usage: Routers only need to store their own distance vector and the vectors of their immediate neighbors, not the entire network map.

Limitations: ​

  • Slow Convergence: Because information propagates from neighbor to neighbor, it can take a long time for all routers to learn about a change in the network, especially a link failure.

  • Count-to-Infinity Problem: This is a major drawback where routing loops can occur after a link failure. In this scenario, two or more routers might send traffic for a downed link back and forth, continuously increasing the hop count metric for that destination until it reaches a predefined maximum, effectively timing out the route.

Routing in the Internet ​

Internet routing protocols determine the path a datagram takes from source to destination.

Core Routing Algorithms: Link-State and Distance-Vector Routing Internet routing protocols are built upon two main types of algorithms:

  • Link-State (LS) Routing Algorithms: In this approach, each router possesses a complete and global understanding of the entire network topology and all link costs. Routers acquire this information by broadcasting "link-state packets" to all other nodes, detailing their directly connected neighbors and the costs of those links. With this comprehensive map, each router independently runs an algorithm, such as Dijkstra's algorithm, to compute the shortest path to all other nodes.

  • Distance-Vector (DV) Routing Algorithms: Unlike LS, DV algorithms are decentralized and iterative. Each router initially only knows the costs to its immediate neighbors. Routes are computed by iteratively exchanging "distance vectors" (estimates of costs to all other nodes) with directly connected neighbors. This process continues until no more information is exchanged, with decisions made based on local knowledge and information received from neighbors.

Autonomous Systems (AS) ​

The Internet is not a single, homogeneous network but rather a network of networks. To manage this complexity, routers are organized into Autonomous Systems (ASs).

An AS is defined as a collection of IP networks and routers under the control of a single organization that presents a common routing policy to the Internet.

This organizational structure addresses problems related to scale and administrative autonomy. Each AS is identified by a globally unique Autonomous System Number (ASN), assigned by ICANN regional registries.

Intra-AS Routing Protocols : Within a single Autonomous System, all routers run the same intra-AS routing protocol. These protocols are used to determine routes within the AS itself. For instance, Open Shortest Path First (OSPF) is a widely used link-state protocol for intra-AS routing in the Internet, where each router constructs a complete topological map of its AS and runs Dijkstra's algorithm to find shortest paths.

Subnets and Internal Routing Consistency : Each AS typically contains multiple subnets and is responsible for maintaining internal routing consistency among its routers. Subnets are portions of an IP address range (e.g., 223.1.1.0/24) that represent a segment of the network where devices share a common IP address prefix.

Internet as Interconnected ASes: Intra-AS and Inter-AS Routing : The Internet's architecture, being a network of interconnected ASes, necessitates both intra-AS and inter-AS routing protocols.

  • Intra-AS protocols manage routing within a single administrative domain, focusing on performance and specific internal policies.

  • Inter-AS protocols, such as the Border Gateway Protocol (BGP), are crucial for gluing these thousands of ISPs (ASes) together, enabling datagrams to be routed across multiple autonomous systems. Inter-AS routing is heavily influenced by policy issues between different organizations and ISPs, which often prioritize business relationships and traffic exchange agreements over purely least-cost paths.

Routing Information Protocol (RIP) ​

Routing Information Protocol (RIP) is a dynamic routing algorithm that operates within a single Autonomous System (AS). It is built upon the Distance Vector (DV) approach and leverages the Bellman-Ford algorithm for its operations.

RIP's characteristics and functionality:

  • Layer and Port: RIP operates at the application layer and uses UDP port 520 for communication.

  • Routing Table (Distance Vector Table): Each router running RIP maintains a routing table. This table contains one entry for each destination subnet, specifying the next-hop router and the hop count (distance) to that destination.

  • Metric: The primary metric used by RIP is hop count, where each link (or router traversal) is assigned a cost of 1.

  • Hop Count Limitation: The maximum hop count allowed is 15. A hop count of 16 indicates an unreachable network. This limitation means RIP is suitable only for smaller networks.

  • Routing Updates (RIP Advertisements): Routers running RIP send routing updates to their directly connected neighbors every 30 seconds. These updates are exchanged using RIP Response Messages, which can carry information for up to 25 destination subnets.

  • Unreachability Detection: If a router does not receive an update from a neighbor within 180 seconds, that neighbor is considered unreachable.

  • Update Process: When a router receives an update, it merges the new information with its existing routing table. If a shorter path (fewer hops) is found to a destination, the routing table is updated accordingly.

RIP version 2 introduced support for route aggregation, which helps to minimize the size of routing tables.

Advantages and Limitations:

  • Simplicity: RIP is simple and easy to implement.
  • Limitations:
    • Slow Convergence: It converges slowly.
    • Small Network Restriction: It is limited to small networks due to its 15-hop restriction.
    • Vulnerability: It is susceptible to routing loops and the count-to-infinity problem.

Example: RIP Routing Table Update

Consider a small network of 4 routers: A, B, C, and D connected as shown below:

A  — B

|    |

C  — D

(1 hop for each link)

Initially, each router knows only about its direct neighbors. Below is the routing table of router A:

DestinationNext HopHop Count
BB1
CC1

After the first RIP update from router B and C, router A updates its table:

DestinationNext HopHop Count
BB1
CC1
DB or C2

Thus, router A learns it can reach router D in 2 hops via either B or C.

Made with ❤️ for students, by a fellow learner.

© 2025 Sujith.