source

04 Advanced Routing And Qos

Advanced Routing and Quality of Service

Prerequisites: 02-Network-Layer-and-Routing Learning Goals: After reading this, you will understand router architecture internals, packet classification algorithms, Head-of-Line blocking, QoS scheduling algorithms (Fair Queuing, DRR), and traffic shaping mechanisms (Token/Leaky Bucket).

Introduction

Moving beyond basic destination-based forwarding, modern routers must handle complex tasks: classifying traffic based on multiple criteria (firewall rules, QoS policies), switching packets at line rate, and managing traffic to prevent congestion. This file covers the hardware and algorithmic challenges of high-speed routers, from lookup optimizations to sophisticated scheduling and traffic shaping.

Key Challenges Addressed:

Router Architecture Internals

The Two Planes Revisited

Control Plane (The Brain):

Forwarding Plane (The Muscle):

Key Insight: Separating these planes allows innovation in control logic (SDN) without changing hardware.

Key Router Components

1. Input Ports:

2. Switching Fabric:

3. Output Ports:

4. Routing Processor:

Lookup Algorithms Revisited

Challenge: IP forwarding requires Longest Prefix Match (LPM) on every packet

Why Simple Solutions Fail:

Trie-Based Solutions:

Unibit Trie:

Multibit Trie:

Example:

Stride = 2 (check 2 bits at once)

Original Prefixes:
  1*    → Port A
  11*   → Port B
  101*  → Port C

After Expansion (to align with stride 2):
  10*   → Port A  (expanded from 1*)
  11*   → Port B  (already length 2)

Level 1: Check bits [0:1]
  00, 01, 10*, 11*

Level 2 (for 10*): Check bits [2:3]
  100*, 101*, 110*, 111*

Lookup for 10110...:
  Step 1: Check first 2 bits = 10 → match 10*
  Step 2: Check next 2 bits = 11 → match 101*
  Result: Forward to Port C

Packet Classification

Motivation

Problem: Longest prefix matching only considers destination IP

Need: Route/filter based on multiple fields simultaneously:

Classification Criteria:

Simple Classification Approaches

1. Linear Search:

2. Caching:

3. MPLS (Multi-Protocol Label Switching):

2D Classification Algorithms

Problem: Classify based on two dimensions (e.g., source IP and destination IP)

Representation: Rules as rectangles in 2D space

Destination IP Prefix
^
|  [Rule 2]
|     +------+
|     |      |
|  [Rule 1]  |
|  +------+  |
|  |      +--+
|  +------+
+----------------> Source IP Prefix

1. Set-Pruning Tries:

Structure:

Lookup:

Advantages:

Disadvantages:

Memory Formula: O(N × W) where N = number of rules, W = address width

2. Backtracking:

Structure:

Lookup:

Advantages:

Disadvantages:

Example:

Destination Trie:
  Root
    ├─ 0* → Source Trie A
    └─ 1* → Source Trie B
         └─ 11* → Source Trie C

Lookup for (src=101*, dst=110*):
  Step 1: Traverse to 11* (longest dst match)
  Step 2: Check Source Trie C for 101* → No match
  Step 3: Backtrack to 1*
  Step 4: Check Source Trie B for 101* → Match found

3. Grid of Tries:

Structure:

Lookup:

Advantages:

Disadvantages:

Example:

Destination nodes with switch pointers:

  11* → Source Trie C --switch--> Source Trie B --switch--> Source Trie A
   |
  1* → Source Trie B --switch--> Source Trie A
   |
  Root → Source Trie A

Lookup for (src=101*, dst=110*):
  Step 1: Check Source Trie C → No match
  Step 2: Follow switch pointer to Source Trie B → Match found
  (No backtracking needed!)

Switching and Scheduling

Crossbar Switches

Structure: N inputs × N outputs with N² crosspoints

How It Works:

Example (3×3 crossbar):

Input 1 ---+---+---+
           |   |   |
Input 2 ---+---+---+
           |   |   |
Input 3 ---+---+---+
           |   |   |
         Out1 Out2 Out3

Advantages:

Challenge: Head-of-Line (HOL) Blocking

Head-of-Line (HOL) Blocking

Problem: In an input-queued crossbar switch, packets at the head of the queue can block packets behind them

Example:

Input Queue 1: [Packet A → Output 1] [Packet B → Output 2]
Input Queue 2: [Packet C → Output 1] [Packet D → Output 3]

Time Slot 1:
  Packet A and Packet C both want Output 1 (conflict!)
  Arbitration: Packet A wins
  Packet C waits (blocked)

  BUT: Packet D wants Output 3 (free!)
  Problem: Packet D is stuck behind Packet C
  Packet D cannot be switched even though Output 3 is available

Result: Throughput limited to ~58% of capacity (even with infinite buffers)

Why 58%?

Solutions to HOL Blocking

1. Output Queuing (Knockout Scheme):

Idea: Move all buffering to output ports instead of input ports

How It Works:

Advantages:

Disadvantages:

Typical k value: 4-8× speedup

2. Virtual Output Queues (VOQs) with Parallel Iterative Matching (PIM):

Idea: Eliminate HOL blocking by maintaining separate queues at each input for each output

Structure:

Example (3×3 switch):

Input 1: [Queue for Out1] [Queue for Out2] [Queue for Out3]
Input 2: [Queue for Out1] [Queue for Out2] [Queue for Out3]
Input 3: [Queue for Out1] [Queue for Out2] [Queue for Out3]

No More HOL Blocking:

New Problem: How to schedule which input-output pairs to connect each time slot?

Parallel Iterative Matching (PIM) Algorithm:

Goal: Find a maximal matching (connect as many input-output pairs as possible without conflicts)

Three Phases per Iteration:

1. Request:

2. Grant:

3. Accept:

Iterate: Repeat 3-4 times to find better matchings

Example:

Initial state:
  Input 1: has packets for Output 1, 3
  Input 2: has packets for Output 1, 2
  Input 3: has packets for Output 2, 3

Iteration 1:
  Request: I1→[O1,O3], I2→[O1,O2], I3→[O2,O3]
  Grant: O1→I1 (random), O2→I2 (random), O3→I3 (random)
  Accept: I1→O1, I2→O2, I3→O3

Result: Schedule transfers I1→O1, I2→O2, I3→O3 (perfect matching!)

Advantages:

Disadvantages:

Quality of Service (QoS)

Motivation

Problem: All traffic treated equally (best-effort)

Issues:

Solution: Quality of Service - Differentiate traffic and provide guarantees

QoS Dimensions:

FIFO with Tail Drop

Simplest Approach: First-In-First-Out queue with drop when full

How It Works:

Packets arrive → Queue (FIFO) → Transmit
If queue full → Drop incoming packet (tail drop)

Advantages:

Disadvantages:

Example Problem:

Flow A: Sending video (delay-sensitive)
Flow B: Sending file download (bulk, not delay-sensitive)

Flow B fills the queue → Flow A's packets dropped → Video freezes

Fair Queuing (Bit-by-Bit Round Robin)

Goal: Allocate bandwidth fairly among competing flows

Ideal Algorithm: Bit-by-Bit Round Robin

How It Works (Conceptual):

  1. Identify all active flows (flows with queued packets)
  2. In each “round”, serve 1 bit from each flow
  3. Repeat until all queues empty

Example:

Flow A: 3000 bits queued
Flow B: 2000 bits queued
Flow C: 1000 bits queued

Round 1: Serve 1 bit from A, B, C (3 bits total)
Round 2: Serve 1 bit from A, B, C
...
Round 1000: C finishes
Round 1001-2000: Serve 1 bit from A, B
Round 2001-3000: Serve 1 bit from A

Finish times:
  C: Round 1000
  B: Round 2000
  A: Round 3000

Finish Time Formula:

Finish_time(packet) = max(Current_round, Finish_time(previous_packet_in_flow)) + Packet_size

Fairness Property:

Problem: Cannot send 1 bit at a time in practice (packets are indivisible)

Packet-by-Packet Fair Queuing (FQ)

Practical Implementation: Simulate bit-by-bit round robin at packet granularity

How It Works:

  1. Calculate “finish time” for each packet (as if sending bit-by-bit)
  2. Always transmit the packet with the smallest finish time
  3. Update virtual time (simulated round number)

Data Structures:

Algorithm:

On packet arrival (flow i, size P):
  finish_time = max(virtual_time, finish_time_prev[i]) + P
  Insert packet into flow i's queue
  Insert finish_time into priority queue

On link available:
  packet = extract_min(priority_queue)
  Transmit packet
  virtual_time = packet.finish_time

Example:

Flow A: Packet 1 arrives (size 1000) at time 0
  finish_time = max(0, 0) + 1000 = 1000

Flow B: Packet 1 arrives (size 500) at time 0
  finish_time = max(0, 0) + 500 = 500

Priority Queue: [B:500, A:1000]

Link available:
  Transmit B's packet (smallest finish time = 500)
  virtual_time = 500

Flow B: Packet 2 arrives (size 500) at time 0
  finish_time = max(500, 500) + 500 = 1000

Priority Queue: [A:1000, B:1000]

Link available:
  Transmit A's packet (finish_time = 1000, tie broken arbitrarily)

Complexity: O(log n) per packet (priority queue operations)

Advantages:

Disadvantages:

Deficit Round Robin (DRR)

Goal: Approximate fair queuing with O(1) complexity

Key Idea: Use “credits” (quantum) to allow flows to send multiple packets per round

Data Structures:

Algorithm:

Each round:
  For each flow i in active list:
    DC[i] += Q  (add quantum)

    While (DC[i] >= size of head packet in flow i):
      Transmit packet
      DC[i] -= size of transmitted packet

    If flow i has no more packets:
      DC[i] = 0  (reset deficit)
      Remove from active list

Example:

Q = 1000 bytes

Round 1:
  Flow A: DC=0, Packet size=1500
    DC = 0 + 1000 = 1000 < 1500 → Cannot send
    DC[A] = 1000 (carry deficit forward)

  Flow B: DC=0, Packet size=500
    DC = 0 + 1000 = 1000 ≥ 500 → Send packet
    DC = 1000 - 500 = 500 (carry forward)

Round 2:
  Flow A: DC=1000
    DC = 1000 + 1000 = 2000 ≥ 1500 → Send packet
    DC = 2000 - 1500 = 500

  Flow B: DC=500
    DC = 500 + 1000 = 1500 ≥ 500 → Send packet
    DC = 1500 - 500 = 1000

Why “Deficit”?

Fairness:

Complexity: O(1) per packet (no priority queue, no sorting)

Advantages:

Disadvantages:

Typical Deployment: High-speed routers (where O(log n) is too expensive)

Traffic Shaping and Policing

Motivation

Problem: Bursty traffic can overwhelm the network

Example:

Solution: Traffic Shaping - Smooth out bursts to match contracted rate

Related Concept: Traffic Policing - Drop/mark packets exceeding rate (enforced by network)

Leaky Bucket

Analogy: Bucket with a hole at the bottom

How It Works:

Model:

         Packets arrive (variable rate)
                |
                v
         +-------------+
         |   Bucket    |  ← Buffer (size B)
         |             |
         +-------------+
                |
                v
        Constant rate R (leak)

Parameters:

Algorithm:

On packet arrival:
  If bucket_level + packet_size <= B:
    Add packet to bucket
  Else:
    Drop packet

Continuously (every time unit):
  If bucket not empty:
    Transmit R bits
    bucket_level -= R

Characteristics:

Example:

B = 5000 bytes, R = 1000 bytes/sec

Time 0: Burst of 3000 bytes arrives → bucket_level = 3000
Time 1: Transmit 1000 bytes → bucket_level = 2000
Time 1.5: Burst of 4000 bytes arrives → bucket_level = 6000 > B
  → Accept 3000 bytes (bucket now full at 5000), drop 1000 bytes
Time 2: Transmit 1000 bytes → bucket_level = 4000
...

Use Case: Smoothing traffic for constant bitrate (CBR) services (e.g., voice)

Token Bucket

Analogy: Bucket accumulates tokens at a fixed rate; need token to send a packet

How It Works:

Model:

     Tokens arrive at rate R
                |
                v
         +-------------+
         | Token Bucket|  ← Capacity B tokens
         |             |
         +-------------+
                ↑
                | Consume tokens to send packet
         Packets arrive

Parameters:

Algorithm:

Continuously (every time unit):
  If tokens < B:
    tokens += R × time_elapsed
    tokens = min(tokens, B)  (cap at B)

On packet arrival (size P):
  If tokens >= P:
    Transmit packet
    tokens -= P
  Else:
    Queue packet (or drop if policing)

Characteristics:

Example:

B = 5000 bytes, R = 1000 bytes/sec

Time 0: tokens = 5000 (bucket full)
  Burst of 4000 bytes arrives → Send immediately
  tokens = 5000 - 4000 = 1000

Time 1: tokens = 1000 + 1000 = 2000
  Packet of 1500 bytes arrives → Send
  tokens = 2000 - 1500 = 500

Time 2: tokens = 500 + 1000 = 1500
  Burst of 3000 bytes arrives → Can only send 1500 bytes
  Send 1500 bytes, queue 1500 bytes
  tokens = 0

Key Difference from Leaky Bucket:

Use Case: Rate limiting with burst tolerance (e.g., SLAs allowing bursts up to B)

Token Bucket vs Leaky Bucket Summary

AspectToken BucketLeaky Bucket
Output RateVariable (allows bursts)Constant
Burst HandlingAllows burst up to B immediatelySmooths burst over time
Average RateR (long-term)R (always)
Use CaseRate limiting with burst toleranceTraffic smoothing for CBR
ExampleISP SLA: 10 Mbps average, 50 MB burstVoIP codec: constant 64 Kbps

Analogy Comparison:

Summary

Key Takeaways

  1. Router Architecture:

    • Control plane (software) computes routes, forwarding plane (hardware) moves packets
    • Multibit tries achieve line-rate lookups (2-4 memory accesses for IPv4)

  2. Packet Classification:

    • Required for firewalls, QoS, NAT (multi-field matching)
    • Grid of Tries: O(W) time, eliminates backtracking with switch pointers
    • Trade-off: Memory vs. time complexity

  3. Head-of-Line Blocking:

    • Limits input-queued switches to 58% throughput
    • Solutions: Output queuing (expensive) or Virtual Output Queues + PIM (practical)

  4. QoS Scheduling:

    • FIFO: Simple but unfair
    • Fair Queuing: Perfect fairness but O(log n) complexity
    • Deficit Round Robin: O(1) approximation of fair queuing, scalable

  5. Traffic Shaping:

    • Leaky Bucket: Smooths traffic to constant rate (CBR services)
    • Token Bucket: Allows bursts up to B, average rate R (SLAs)

Common Patterns

Router Design Trade-offs:

QoS Mechanisms:

Algorithm Selection:

See Also

Next: 05-Modern-Architectures