Computer Networking — Chapter 5: The Network Layer: Control Plane

Introduction

The control plane determines the paths taken by packets through the network. Two approaches:

• Per-router control — each router runs routing algorithms and builds its own forwarding table (traditional)
• Software-Defined Networking (SDN) — a remote SDN controller computes and distributes forwarding tables to routers

Routing Algorithms

Goal: find the least-cost path from source to destination.

Classification:

• Global (Link-State): all routers have complete topology and link cost info
• Decentralized (Distance-Vector): each router knows neighbors, iterative computation

Link-State (LS) Routing Algorithm — Dijkstra’s Algorithm

All nodes know the complete network topology and link costs.

Dijkstra’s Algorithm:
N’ = set of nodes whose least-cost path is known
Initially N’ = {u} (source)
For all nodes v: D(v) = c(u,v) (direct cost)
Loop: Find w not in N’ with minimum D(w), add w to N’, update D(v) = min(D(v), D(w) + c(w,v)) for all v not in N’
Stop when N’ = all nodes

Complexity: O(n^2) with simple implementation, O(n log n) with heap

Oscillations: Possible when link cost = traffic load, causing routing instability (solved by randomizing link update times)

Distance-Vector (DV) Routing Algorithm — Bellman-Ford

Distributed, asynchronous, based on the Bellman-Ford equation:

Bellman-Ford Equation:
d_x(y) = min_v { c(x,v) + d_v(y) }

Where d_x(y) is the least cost from x to y, and v is x’s neighbors.

Poison Reverse: If router Z routes to destination Y through X, Z tells X its cost to Y is infinity — preventing certain count-to-infinity scenarios.

Count-to-Infinity Problem: Can still occur with loops involving 3+ nodes.

LS vs DV Comparison:

Intra-AS Routing in the Internet: OSPF

OSPF (Open Shortest Path First):

• Link-state routing protocol
• Uses Dijkstra’s algorithm
• Each router floods LSAs (Link-State Advertisements) to all other routers in the AS
• Hierarchical OSPF: two-level hierarchy
  • Backbone area (Area 0) connects all other areas
  • Area border routers summarize routing info between areas
• Supports authentication, multiple same-cost paths, TOS-aware routing

Inter-AS Routing: BGP

BGP (Border Gateway Protocol): the de facto inter-domain routing protocol

• eBGP: between ASes (exterior)
• iBGP: within an AS (interior)

BGP Route Advertisement:

• BGP routers exchange routes via UPDATE messages
• A route includes: NLRI (prefix) + AS-PATH + NEXT-HOP
• AS-PATH: list of ASes the route has traversed (loop detection)
• NEXT-HOP: IP address of the next-hop router

BGP Route Selection (preference order):

1. Highest local preference (local admin policy)
2. Shortest AS-PATH
3. Closest NEXT-HOP (hot potato routing / closest exit)
4. Additional criteria (eBGP over iBGP, router ID, etc.)

IP-Anycast: Multiple servers advertise the same IP prefix; BGP directs clients to the “closest” server.

Routing Policy: ISPs use BGP to implement business relationships (customer-provider peering, settlement-free peering).

Obtaining Internet Presence:

1. Get IP address block from ISP or registry
2. Register domain name
3. Run authoritative DNS server
4. Advertise prefix via BGP

The SDN Control Plane

Four Key Features of SDN:

1. Flow-based forwarding — forwarding decisions based on multiple header fields
2. Separation of data and control planes — switches are simple, controller is smart
3. Network control functions — external to forwarding devices
4. Programmable network — control plane is software-based

SDN Controller Architecture (e.g., OpenDaylight, ONOS):

• Communication layer — communicates with switches (OpenFlow protocol)
• Network-wide state management layer — stores topology, state
• Interface to control apps — API for SDN applications

OpenFlow Protocol:

• Operates between controller and switch over TCP (port 6653)
• Three message types: controller-to-switch, asynchronous (packet-in), symmetric (hello)
• Flow table entries: match fields, priority, counters, instructions, timeouts, cookie

Data and Control Plane Interaction Example:

1. Packet arrives at switch, no matching flow entry
2. Switch sends PacketIn message to controller
3. Controller determines path, installs flow entries on all switches along path
4. First packet is forwarded; subsequent packets match flow entries (fast path)

ICMP: The Internet Control Message Protocol

• Used by hosts and routers to communicate network-level information
• ICMP messages carried in IP datagrams
• Common message types:

  Type	Code	Description
  0	0	Echo reply (ping)
  3	0-3	Destination unreachable
  8	0	Echo request (ping)
  11	0	TTL expired (traceroute)

Network Management and SNMP

Network Management Framework:

• Managing server — runs network management application
• Managed devices — routers, switches, hosts
• MIB (Management Information Base) — collection of managed objects
• SMI (Structure of Management Information) — defines data types for MIB objects
• SNMP (Simple Network Management Protocol) — protocol for querying/updating MIB objects

SNMP Protocol Operations: