CSS334 — Control Plane, Routing Algorithms & SDN Cheat Sheet

Exam-ready summary | Lecture 10 | All topics included

0. Control Plane: Two Approaches

Per-Router: Like every taxi driver independently knowing the city map — no central dispatcher.
SDN: Like separating the GPS app (control plane) from the car's engine (data plane) — updatable independently.

1. Graph Abstraction of a Network

Network = graph $G = (N, E)$

• $N$ = set of routers (nodes): ${u, v, w, x, y, z}$
• $E$ = set of links (edges): ${(u,v), (u,x), (v,w), \ldots}$
• $c_{a,b}$ = cost of direct link between nodes $a$ and $b$
  • $c_{a,b} = \infty$ if $a$ and $b$ are not direct neighbours

Cost can represent:

• Always 1 (hop count)
• Inversely proportional to bandwidth (lower bandwidth = higher cost)
• Inversely proportional to congestion
• Operator-defined metric

Analogy: Like a GPS map where road "costs" can represent distance, traffic, or road quality.

2. Routing Algorithm Classification

By Information Type (more important for exam)

By Rate of Change

3. Dijkstra's Link-State Algorithm

Properties

• Global: requires complete topology known to all nodes (distributed via link-state broadcast)
• Computes least-cost path from one source to all other nodes
• Builds the forwarding table for that source router
• Iterative: after $k$ iterations, knows least-cost path to $k$ destinations

Notation

Pseudocode

Initialization:
  N' = {u}                          ← start: only source is confirmed
  for all nodes v:
    if v is adjacent to u:
      D(v) = c(u, v),  p(v) = u
    else:
      D(v) = ∞

Loop (repeat until all nodes in N'):
  find node a NOT in N' with minimum D(a)
  add a to N'                        ← a is now confirmed
  for all b adjacent to a, b NOT in N':
    D(b) = min( D(b),  D(a) + c(a, b) )
    if updated: p(b) = a

Key Update Formula

$\boxed{D(b) = \min\bigl(D(b),\ D(a) + c_{a,b}\bigr)}$

Analogy: Google Maps updating your ETA at every turn — always keeps the shortest known path, revises when a faster route is found.

Worked Example (source = u)

Graph: u–v(2), u–x(1), u–w(5), v–x(2), v–w(3), x–w(3), x–y(1), w–y(1), w–z(5), y–z(2)

Reading the table: $D(w)=3, p(w)=y$ means: cost to $w$ is 3, reached via $y$.

Resulting Forwarding Table (from u)

Everything from u routes through (u,x) except the direct link to v — x is the central hub in this topology.

4. Distance Vector (DV) Algorithm

Bellman-Ford Equation

$\boxed{D_a(b) = \min_e\{ c_{a,e} + D_e(b)\}}$

• $D_a(b)$ = node $a$'s estimate of least-cost path to destination $b$
• $\min$ taken over all direct neighbours $e$ of $a$
• $c_{a,e}$ = direct link cost from $a$ to neighbour $e$
• $D_e(b)$ = neighbour $e$'s reported cost to reach $b$

Analogy: Ask all your friends "how far are you from the airport?" Then pick whichever friend is cheapest to reach + they're cheapest to the airport.

Worked Example

For node $u$ finding cost to $z$ (neighbours: v, x, w):

$D_u(z) = \min{c_{u,v}+D_v(z),\ c_{u,x}+D_x(z),\ c_{u,w}+D_w(z)}$ $= \min{2+5,\ 1+3,\ 5+3} = \min{7,\ 4,\ 8} = \boxed{4}$

→ Next hop to $z$ from $u$ = x (the one achieving the minimum)

How DV Works in Practice

1. Each node initialises its DV: $D_v(v) = 0$, $D_v(\text{others}) = \infty$
2. Each node periodically sends its DV to all direct neighbours
3. On receiving a neighbour's DV, update own DV using Bellman-Ford
4. Only notify neighbours if DV changed (self-stopping)

State diffusion speed:

Analogy: Rumour spreading through a social network — each round of gossip spreads info one more hop.

"Good News Travels Fast"

• Link cost decreases → converges in 2 steps (fast ✅)
• Link cost increases → can cause count-to-infinity problem (slow ⚠️)

5. DV vs LS Comparison

DV = asking friends for directions (each only knows their local area).
LS = having a complete city map yourself.

6. Scalable Routing: Autonomous Systems (AS)

Why AS?

• Scale: Billions of destinations → impossible to store all in one routing table
• Administrative autonomy: Each organisation controls its own routing policy
• Solution: Group routers into Autonomous Systems (AS) — a network under single admin control

Two Levels of Routing

• Gateway router: edge router of an AS — has links to routers in other ASes
• Gateway routers run both intra-AS (e.g., OSPF) and inter-AS (BGP) protocols simultaneously
• Forwarding table built by combining intra-AS + inter-AS routing info

7. Intra-AS Routing Protocols

RIP — Routing Information Protocol (RFC 1723)

• Type: Distance Vector
• Metric: Hop count
• Max hops: 15 (hop count = 16 → destination unreachable/∞)
• Sends full routing table to neighbours every 30 seconds
• Administrative distance: 120
• Multicast address: 224.0.0.9
• No longer widely used

RIPv1 vs RIPv2

RIP's fatal flaw: Max 15 hops — useless for large networks. Modern Internet has far more than 15 hops.

EIGRP — Enhanced Interior Gateway Routing Protocol

• Type: Advanced Distance Vector (Hybrid) — developed by Cisco, open standard since 2013 (RFC 7868)
• Very fast convergence with minimal bandwidth usage
• Enhancement of IGRP

Composite Metric (default = Bandwidth + Delay):

OSPF — Open Shortest Path First (RFC 2328)

• Type: Link State
• Algorithm: Dijkstra (each router computes full shortest-path tree)
• "open": publicly available (non-proprietary) standard
• Each router floods OSPF link-state advertisements (LSAs) to every router in the entire AS
• Carried directly over IP (not TCP/UDP) — Protocol number 89
• Security: All OSPF messages authenticated (prevents malicious injection)
• Multiple cost metrics: bandwidth, delay, etc.

Hierarchical OSPF (Two-Level)

┌─────────────────────────────────────────────┐
│                  Backbone                    │  ← backbone routers + area border routers
│         (Area 0 — links ASes together)       │
└───────┬──────────────────────┬──────────────┘
        │                      │
   ┌────▼────┐            ┌────▼────┐
   │ Area 1  │            │ Area 2  │   ← internal routers flood LS only within area
   └─────────┘            └─────────┘

Benefit of hierarchy: LS advertisements flood only within an area — backbone area never flooded with every internal link. Greatly reduces update traffic for large networks.

Dynamic Routing Protocol Comparison

Why OSPF/EIGRP are faster than RIP: They only send what changed, not the full table. RIP sends its entire routing table every 30 seconds regardless.

8. Inter-AS Routing: BGP

BGP = "the glue that holds the Internet together"

What is BGP?

• Border Gateway Protocol — the de facto standard inter-AS routing protocol
• Protocol type: Path Vector (advertises complete AS-path, not just cost)
• Allows each subnet to advertise its existence to the rest of the Internet
• Two BGP routers ("peers") exchange messages over TCP

eBGP vs iBGP

Gateway routers run both eBGP and iBGP simultaneously.

BGP Path Advertisement Flow

X (new subnet) joins AS3
Step 1: AS3 gateway (3a) → announces "AS3, X" to AS2 via eBGP
Step 2: AS2 propagates "AS3, X" to all AS2 routers via iBGP
Step 3: AS2 gateway (2a) → announces "AS2, AS3, X" to AS1 via eBGP
Step 4: AS1 now knows: to reach X, go through AS2 → AS3

BGP Path Attributes

• AS-PATH: list of all ASes the advertisement has passed through
  • e.g., AS2 AS3 means "pass through AS2 then AS3 to reach destination"
  • Used to detect loops (if own AS number appears → discard)
• NEXT-HOP: IP address of the router at the entry point of the next AS

BGP Route Selection (Priority Order)

1. Local preference value — policy decision set by admin (highest = preferred)
2. Shortest AS-PATH — fewest ASes to traverse
3. Closest NEXT-HOP — hot potato routing: pick the gateway with the lowest intra-AS cost to reach the next-hop router (get rid of the packet as fast as possible within your AS)
4. Additional tiebreaking criteria

Hot potato routing: "I have a hot potato — throw it to the nearest exit as fast as possible!" Don't care what happens after it leaves your AS.

Policy-Based Routing

• Each AS can use import policy to decide whether to accept a route
• Each AS can decide whether to advertise (export) a path to its neighbours
• Example: AS2 may learn a path but refuse to advertise it to AS1 (commercial reasons)
• Policy dominates over performance in inter-AS routing — unlike intra-AS

Why Different Intra-AS vs Inter-AS?

9. SDN Control Plane

Motivation: Problems with Traditional Routing

• Each router runs proprietary OS (e.g., Cisco IOS) — hard to program
• Traffic engineering is very difficult:
  • Want to force path u→v→w→z instead of u→x→y→z? → Must re-define ALL link weights
  • Want load balancing across both paths? → Can't do with traditional routing
  • Want different routing based on source IP? → Can't do with destination-based forwarding

SDN Solution

$\text{Generalised forwarding + SDN = any routing policy achievable}$

Key insight: Separate the Control Plane (brain) from the Data Plane (body)

4 Key SDN Characteristics

1. Generalised "flow-based" forwarding — match on any header field, not just dest IP
2. Control/data plane separation — control runs on separate servers
3. Control plane external to data-plane switches — switches are "dumb" fast hardware
4. Programmable control applications — routing, firewall, load balancer all as software apps

SDN Architecture (3 Layers)

┌──────────────────────────────────────────────┐
│         Network-Control Applications          │  ← "Brains": routing, firewall, load balance
│    (Routing)  (Access Control)  (Load Bal.)  │     (can be 3rd party!)
└──────────────┬───────────────────────────────┘
               │ northbound API (REST)
┌──────────────▼───────────────────────────────┐
│          SDN Controller (Network OS)          │  ← Control Plane
│  state management + network-wide view         │     (distributed system for fault-tolerance)
└──────────────┬───────────────────────────────┘
               │ southbound API (OpenFlow)
┌──────────────▼───────────────────────────────┐
│           SDN-Controlled Switches             │  ← Data Plane
│   (fast commodity hardware, flow tables)      │     (no routing logic — just match+action)
└──────────────────────────────────────────────┘

SDN Controller Components (3 Layers Internal)

SDN Link Failure Example (End-to-End Flow)

1. Switch S1 detects link failure
   → sends OpenFlow "port status" message to SDN controller

2. SDN controller receives message
   → updates link-state info in state DB

3. Dijkstra routing app (listening for link changes) is triggered
   → reads updated network graph from controller

4. Dijkstra computes new shortest paths

5. Flow-table computation component calculates new flow tables

6. SDN controller pushes new flow tables to affected switches via OpenFlow

10. Generalised Forwarding & OpenFlow

Match Plus Action

$\text{Incoming packet header} \xrightarrow{\text{match}} \text{Flow table entry} \xrightarrow{\text{action}} \text{forward / drop / modify / send to controller}$

Flow Table Entry Structure

Priority field: disambiguates overlapping rules (higher priority wins)

Matchable Header Fields (OpenFlow — across all layers)

OpenFlow Actions Available

1. Forward packet to specific port(s)
2. Drop packet
3. Modify fields in header (change src/dst IP, port, MAC, VLAN — like NAT!)
4. Encapsulate and send to controller

OpenFlow Examples

Router behaviour (dest-based forwarding):

match: IP Dst = 51.6.0.8  →  action: forward(port 6)

Firewall behaviour (block SSH):

match: TCP d-port = 22    →  action: drop

Firewall behaviour (block specific host):

match: IP Src = 128.119.1.1  →  action: drop

NAT behaviour:

match: IP address + port  →  action: rewrite address and port

OpenFlow Unifies All Network Devices

One device (SDN switch) can act as router, switch, firewall, NAT simultaneously — just program different flow table entries!