Unit 5: NETWORK LAYER: Routing & Congestion Control

1. Introduction to Routing Algorithms

The main function of the Network Layer is routing packets from the source machine to the destination machine. A Routing Algorithm is that part of the network layer software responsible for deciding which output line an incoming packet should be transmitted on.

Properties of Desirable Routing Algorithms

• Correctness & Simplicity: Packets must be delivered; the algorithm should be simple to implement.
• Robustness: The ability to function in the face of topology changes or hardware failures.
• Stability: The algorithm should converge to equilibrium quickly.
• Fairness vs. Optimality: A trade-off often exists between maximizing total network throughput (optimality) and ensuring every node gets service (fairness).

Classification of Routing Algorithms

2. Shortest Path Algorithm

The foundation of many routing protocols is finding the "shortest" path between two nodes. "Shortest" can be defined by hops, physical distance, transmission delay, or bandwidth cost.

Dijkstra’s Algorithm

Dijkstra's algorithm builds a "Shortest Path Tree" from a specific source node to all other nodes in the graph. It requires a network topology where edge weights are non-negative.

Mechanism:

1. Initialization: Mark the source node as current. Set the tentative distance to the source as 0 and to all other nodes as infinity ().
2. Calculation: For the current node, consider all of its unvisited neighbors. Calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one.
3. Marking: Once all neighbors of the current node are considered, mark the current node as "visited". A visited node will never be checked again.
4. Selection: Select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node," and repeat step 2.
5. Termination: The algorithm finishes when the destination node has been marked visited (or all nodes have been visited).

Pseudocode:

function Dijkstra(Graph, source):
    dist[source] = 0
    for each vertex v in Graph:
        if v != source:
            dist[v] = infinity
        add v to Q (unvisited set)

    while Q is not empty:
        u = vertex in Q with min dist[u]
        remove u from Q

        for each neighbor v of u:
            alt = dist[u] + length(u, v)
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
    return dist, prev

3. Distance Vector Routing (DVR)

Distance Vector Routing is a dynamic routing algorithm based on the Bellman-Ford equation. It was the original ARPANET routing algorithm.

Core Concepts

• Knowledge: Each router knows the distance (metric) to its immediate neighbors.
• Vector: Each router maintains a routing table (vector) containing the best known distance to every destination and which line to use to get there.
• Exchange: Routers periodically send their entire routing table to their immediate neighbors only.

The Algorithm

Let be the cost of the least-cost path from node to node . The Bellman-Ford equation states:

Where:

• is a neighbor of .
• is the direct cost from to .
• is the distance from neighbor to destination .

The Count-to-Infinity Problem

DVR reacts rapidly to good news (a new link or reduced cost) but slowly to bad news (link failure).

• Scenario: If A is connected to B, and B to C. If C fails, B detects it immediately. However, A thinks it can reach C through B. A tells B "I have a path to C", B updates its table to go through A (which actually goes back to B), creating a routing loop. The cost increments theoretically to infinity.

Solutions

1. Split Horizon: A router never advertises a route back to the neighbor from whom it learned that route.
2. Poison Reverse: A variation of Split Horizon where the router advertises the route back as "infinity" (unreachable) rather than just remaining silent.
3. Triggered Updates: Send updates immediately upon a topology change rather than waiting for the timer.

4. Link State Routing (LSR)

Link State Routing was developed to address the slow convergence and loops of Distance Vector Routing. The philosophy is: "Tell everyone what you know about your neighbors."

Five Steps of LSR

1. Discover Neighbors: Send "Hello" packets to discover immediate neighbors and their network addresses.
2. Measure Cost: Send "Echo" packets to measure the delay or cost to each neighbor.
3. Construct Link State Packet (LSP): Create a packet containing:
   • Identity of the sender.
   • Sequence number and age.
   • List of neighbors and the associated costs.
4. Flooding: Distribute the LSP to every other router in the network (not just neighbors). To prevent loops during flooding, sequence numbers are used.
5. Compute Shortest Path: Once a router has a full set of LSPs (the complete network map), it runs Dijkstra’s Algorithm locally to construct the routing table.

Comparison: DVR vs. LSR

5. Unicast Routing Protocols

Unicast routing involves sending a packet from one specific source to one specific destination. These protocols are classified into Interior Gateway Protocols (IGP) and Exterior Gateway Protocols (EGP).

A. Routing Information Protocol (RIP)

• Type: Interior Gateway Protocol (IGP).
• Algorithm: Distance Vector.
• Metric: Hop Count (1 hop = 1 link traverse).
• Limitations:
  • Max hop count is 15. 16 is considered infinite (unreachable). This limits RIP to small networks.
  • Updates are broadcast every 30 seconds.
• Transport: Uses UDP Port 520.

B. Open Shortest Path First (OSPF)

• Type: Interior Gateway Protocol (IGP).
• Algorithm: Link State Routing.
• Metric: Cost (usually inversely proportional to bandwidth: ).
• Hierarchical Routing: OSPF divides the network into Areas.
  • Backbone Area (Area 0): Connects all other areas. All inter-area traffic must pass through the backbone.
• Features: Supports Load Balancing, Authentication, and converges very quickly.

C. Border Gateway Protocol (BGP)

• Type: Exterior Gateway Protocol (EGP). Used between different Autonomous Systems (AS) (e.g., between ISPs).
• Algorithm: Path Vector Routing (a modification of Distance Vector).
• Metric: Policy-based (shortest path is not always chosen; business/political rules apply).
• Function: Prevents loops by carrying the full path of AS numbers traversed.

6. Congestion Control Algorithms

Congestion occurs when the number of packets sent to the network is greater than the number of packets the network can handle (capacity). This leads to packet loss and increased delay.

Congestion Control vs. Flow Control:

• Flow Control: Point-to-point (Sender to Receiver). Prevents a fast sender from drowning a slow receiver.
• Congestion Control: Global issue. Prevents the subnet from being swamped.

A. General Principles

1. Open Loop (Prevention): Designed to prevent congestion before it happens.

   • Retransmission Policy: A good timer prevents premature retransmission (which adds load).
   • Window Policy: Selective Repeat is better than Go-Back-N for congestion.
   • Admission Policy: Refuse new connections if the network is busy (Virtual Circuits).

2. Closed Loop (Removal): Detects congestion and removes it.

   • Backpressure: Propagate the choke effect hop-by-hop back to the source.
   • Choke Packets: Router sends a packet directly to the source to slow down (ICMP Source Quench).
   • Load Shedding: Drop packets (Random Early Detection - RED).

B. Traffic Shaping Algorithms

Traffic shaping restricts the flow of packets leaving a node to ensure traffic adheres to a specific profile.

1. Leaky Bucket Algorithm

Imagine a bucket with a small hole at the bottom.

• Input: Bursty traffic flows into the bucket.
• Output: Water (packets) flows out at a constant rate.
• Mechanism: If the bucket is full, incoming packets are discarded.
• Result: Converts bursty traffic into a fixed bit-rate stream.
• Disadvantage: Does not efficiently use available bandwidth during idle times; drops packets if burst is too large.

2. Token Bucket Algorithm

• Mechanism: A token generator adds tokens to the bucket at a constant rate.
• Transmission: To send a packet, a host must capture and destroy a token.
• Result: Allows bursts of traffic, but only up to the number of accumulated tokens. If the bucket is empty, the host must wait for tokens.
• Advantage: More flexible than Leaky Bucket as it allows bursts for faster transmission if the network has been idle.

C. TCP Congestion Control

TCP uses a congestion window (cwnd) to control the sending rate.

1. Slow Start:

   • Start with cwnd = 1 MSS (Maximum Segment Size).
   • Double cwnd every RTT (Round Trip Time) (Exponential growth: 1, 2, 4, 8...).
   • Stop exponential growth when cwnd reaches ssthresh (Slow Start Threshold).

2. Congestion Avoidance:

   • Once ssthresh is reached, increase cwnd linearly (add 1 MSS per RTT).
   • This probes for bandwidth gently.

3. Congestion Detection:

   • Timeout: Assume heavy congestion. Set ssthresh = cwnd / 2, reset cwnd = 1, restart Slow Start.
   • 3 Duplicate ACKs (Fast Retransmit): Assume light congestion (packet lost but network functioning). Set ssthresh = cwnd / 2, set cwnd = ssthresh, and enter Congestion Avoidance (skipping Slow Start).