Lecture 10 - Network Layer (Part 4)

Table of Contents

• Control Plane Overview
• Per-Router Control Plane
• Dynamic Routing
• Routing Protocols
• Graph Abstraction & Link Costs
• Routing Algorithm Classification
• Dijkstra's Link-State Algorithm
• Distance Vector Algorithm
• Comparison: DV vs LS
• Scalable Routing – Autonomous Systems (AS)
• Intra-AS Routing Protocols
• Inter-AS Routing: BGP
• SDN Control Plane
• Generalized Forwarding & OpenFlow
• SDN Controller Components

Control Plane Overview

Two approaches to structuring the network control plane:

• Per-router control (traditional) – each router runs its own routing algorithm
• Logically centralized control – Software Defined Networking (SDN)

Two Key Network-Layer Functions

Think of forwarding as physically moving a car through a road intersection, and routing as planning the trip on a map beforehand.

Per-Router Control Plane

• Individual routing algorithm components run in each and every router
• Routers interact with each other in the control plane
• Each router maintains its own local forwarding table

• แต่ละ router ต้องรัน routing algorithm
• Router แต่ละตัวสื่อสาร แชร์ information

Like every taxi driver knowing their own city map and independently deciding the best route — no central dispatcher.

Dynamic Routing

• Also known as Adaptive Routing
• Router adds a new route in the routing table for each packet in response to changes in condition or topology of the network
• Dynamic protocols are used to discover new routes
• If any route goes down → automatic adjustment is made

Dynamic Routing Protocol Hierarchy

Dynamic Routing
├── IGP (Interior Gateway Protocol)
│   ├── Distance Vector
│   │   ├── RIP
│   │   └── IGRP
│   ├── Link State
│   │   └── OSPF
│   └── Hybrid
│       └── EIGRP
└── EGP (Exterior Gateway Protocol)
    └── Path Vector
        └── BGP

Routing Protocols

• Goal: Determine "good" paths from sending host to receiving host through the network of routers
• Path: Sequence of routers packets traverse from source to destination
• "Good" means: least cost, fastest, least congested
  • Cost อาจจะเป็น number of hop??
• Routing is considered a "top-10" networking challenge

Graph Abstraction & Link Costs

• Network modeled as a graph: $G = (N, E)$
  • $N$: set of routers = $\{u, v, w, x, y, z\}$
  • $E$: set of links = $\{(u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z)\}$
• $c_{a,b}$ = cost of direct link connecting node $a$ and $b$
  • $c_{w,z} = 5$, $c_{u,z} = \infty$ (not direct neighbors)
• Cost defined by network operator:
  • Could always be 1
  • Inversely related to bandwidth
  • Inversely related to congestion

Like a GPS map where road "costs" can represent distance, traffic, or road quality — the router picks the cheapest path.

Routing Algorithm Classification

By Information Type

By Rate of Change

Dijkstra's Link-State Algorithm

Properties

• Centralized: network topology and link costs known to all nodes (via link state broadcast)
• Computes least-cost paths from one source node to all other nodes → gives forwarding table
• Iterative: after $k$ iterations, knows least-cost path to $k$ destinations

Notation

Algorithm (Pseudocode)

Initialization:
  N' = {u}
  for all nodes e:
    if e adjacent to u:
      D(e) = c(u, e)
    else:
      D(e) = ∞

Loop:
  find a not in N' such that D(a) is minimum
  add a to N'
  update D(b) for all b adjacent to a and not in N':
    D(b) = min(D(b), D(a) + c(a, b))
until all nodes in N'

Key Update Formula

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

Like Google Maps updating your estimated arrival time at each turn — it always keeps the shortest known path and revises when a faster route is found.

Example Table (source = u)

Resulting Forwarding Table (from u)

แต่ของอาจารย์จะมี notation พิเศษ via อะไรสักอย่าง D(w),p(w) ไรงี้ ลองแก้ ๆ ดูนะ
ถ้าจากข้างบน จะอ่านว่า cost via (ต้องผ่าน) p(w)

Distance Vector Algorithm

Receive destination based on its neighbour only!!

Bellman-Ford Equation (Dynamic Programming)

Let $D_a(b)$ = cost of least-cost path from $a$ to $b$. Then:
$\boxed{D_a(b) = \min_e\{ c_{a,e} + D_e(b)\}}$

• $\min$ taken over all neighbors $e$ of $a$
• $c_{a,e}$ = direct cost of link from $a$ to $e$
• $D_e(b)$ = neighbor $e$'s estimated least-cost path to $b$

Like asking all your friends "how far are you from the airport?" and choosing whichever friend is closest + cheapest to get to.

Bellman-Ford Example

For node $u$ finding cost to $z$:
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} = \boxed{4}
The node achieving minimum ($x$) is the next hop on estimated least-cost path to $z$.

Key Idea

• Each node periodically sends its own distance vector estimate to neighbors
• When node $a$ receives a new DV estimate from neighbor, it updates its own DV using Bellman-Ford:

$D_a(b) \leftarrow \min_{e}{c_{a,e} + D_e(b)} \quad \text{for each node } b \in N$

Algorithm Behavior

• Iterative, asynchronous: each local iteration caused by:
  • Local link cost change
  • DV update message from neighbor
• Distributed, self-stopping: node notifies neighbors only when its DV changes
  • No notification received → no actions taken

State Information Diffusion

📄 10ComputerNetwork-NetworkLayer_Part4 pages 19 - 32.pdf

Like a rumor spreading through a social network — each round of gossip spreads the information one more step away.

Link Cost Changes

• "Good news travels fast":
  • $t_0$: node detects link-cost decrease → updates DV → informs neighbors
  • $t_1$: neighbor receives update → recomputes → sends new DV
  • $t_2$: original node receives update → no change → stops

Comparison: DV vs LS

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

Scalable Routing – Autonomous Systems (AS)

Why Scalability Matters

• Billions of destinations → can't store all in routing tables; exchange would swamp links
• Administrative autonomy → each network admin wants control over their own network

Solution: Aggregate into Autonomous Systems (AS)

• Intra-AS (intra-domain): routing within the same AS
  • All routers in AS run the same intra-domain protocol
  • Gateway router: at edge of AS, has links to routers in other ASes
    
• Inter-AS (inter-domain): routing between ASes
  • Gateway routers perform inter-domain routing
    
    

Forwarding Table Construction

• Intra-AS routing determines entries for destinations within AS
• Inter-AS + Intra-AS together determine entries for external destinations

Inter-AS Routing Role

When AS1 router receives datagram destined outside AS1:

1. Learn which destinations are reachable through AS2
2. Propagate reachability info to all routers in AS1

Intra-AS Routing Protocols

Most common protocols:

RIP (Routing Information Protocol) — RFC 1723

Protocol นี้ถ้ามี Hop เยอะ (20 hops) อะไรงี้ คือมันจะไม่เวิร์คเลยนะ

Based on Distance Vector (Check!!)

• Type: Distance Vector (DV)
• Sends full routing table to neighbor every 30 seconds
• Maximum hops: 15 routers (16 = infinity/unreachable)
• Summarizes networks to class-full boundary by default
• Administrative distance: 120
• Multicast address: 224.0.0.9
• No longer widely used

RIPv1 vs RIPv2

EIGRP (Enhanced Interior Gateway Routing Protocol)

Based on Distance Vector (Check!!)

• Advanced Distance Vector protocol developed by Cisco (open since 2013 — RFC 7868)
• Enhancement of IGRP
• Extremely quick convergence with minimal network traffic

Default composite metric uses:

• Bandwidth — slowest bandwidth along the path (source → destination)
• Delay — cumulative sum of all interface delays (in tens of microseconds)

Optional (not recommended — causes frequent recalculation):

• Reliability — worst reliability between source and destination
• Load — worst load on a link between source and destination

OSPF (Open Shortest Path First) — RFC 2328

• "open": publicly available standard
• Type: Link-State
• Each router floods OSPF link-state advertisements directly over IP (not TCP/UDP) to all routers in entire AS
• Multiple link cost metrics possible: bandwidth, delay
• Each router has full topology → uses Dijkstra's algorithm to compute forwarding table
• Security: all OSPF messages authenticated (prevent malicious intrusion)

Hierarchical OSPF

• Two-level hierarchy: local area + backbone
  • Link-state advertisements flooded only within area or backbone
  • Each node has detailed area topology; only knows direction to reach other destinations

Router types:

Dynamic Routing Protocol Comparison

• RIP เวลามันส่ง ส่งทั้งตาราง, OSPF, EIGRP ส่งเฉพาะตัวที่เปลี่ยน มันก็เลยเร็วกว่าป้ะ???? CHECK!

Inter-AS Routing: BGP

For connecting multiple AS together!!

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

Called the "glue that holds the Internet (network of network (AS)) together"

• Allows subnet to advertise its existence and the destinations it can reach to the rest of the Internet
• Provides each AS a means to:
  • eBGP: obtain subnet reachability info from neighboring ASes
  • iBGP: propagate reachability info to all AS-internal routers
  • Determine "good" routes based on reachability information and policy

BGP Session

สมมติ X (SIIT) มา join ใหม่ AS 3 ขอซื้อ 5 public IP, AS3 ต้อง broadcast ผ่าน gateway router ไปให้ autonomous system อื่น ๆ
AS 2 ก็มีสิทธิที่จะส่ง (forward) information ให้ AS 1 หรือไม่ส่งก็ได้
ถ้าส่ง → ทีนี้ทุกคนก็จะรู้แล้ว ถ้าอยาก reach X ต้องไปไหน

• Two BGP routers ("peers") exchange BGP messages over TCP
• Advertising paths to different destination network prefixes
• BGP is a "path vector" protocol

eBGP vs iBGP

• Gateway routers run both eBGP and iBGP

Path Attributes

• BGP advertised route = prefix + attributes
  • AS-PATH: list of ASes through which the prefix advertisement has passed
  • NEXT-HOP: specific internal-AS router to next-hop AS

Policy-Based Routing

• Gateway uses import policy to accept/decline path (e.g., never route through AS Y)
• AS policy determines whether to advertise path to other neighboring ASes

BGP Route Selection Order

Path selection เลือกยังไงงง???

1. Local preference value attribute: policy decision
2. Shortest AS-PATH
3. Closest NEXT-HOP router: hot potato routing → choose local gateway with least intra-domain cost
   • เวลามี hot potato อยู่ในมือ ก็อยากจะรีบส่ง ๆ ไป55555
4. Additional criteria

BGP Path Advertisement Example

1. AS3 router 3a sends path AS3, X to AS2 router 2c (via eBGP)
2. AS2 router 2c accepts AS3, X → propagates (via iBGP) to all AS2 routers
3. AS2 router 2a advertises path AS2, AS3, X to AS1 router 1c (via eBGP)

Why Different Intra- vs Inter-AS Routing?

SDN Control Plane

แต่ละ router ต้องลง Control Agent → เช็ค status of everything, network แล้วก็ report ให้ server
ถ้ามีข้อมูลมาใหม่ remote controller ก็จะทำ re-calculation!

• ตัวใหญ่ เปลี่ยนเป็น Switch L3 ???? ถามจารย์

Motivation (~2005 renewed interest)

Traditional Internet layer: distributed, per-router control

• Monolithic routers run proprietary OS (e.g., Cisco IOS) with proprietary protocol implementations
• Different "middleboxes" for different functions (firewalls, NAT, load balancers)

Problem: Traffic engineering is very difficult with traditional routing

• จากรูปด้านบนนะ
• Want to force path u→v→w→z instead of u→x→y→z? → Must re-define link weights
• Want load balancing across both paths? → Can't do with traditional routing
• Want to route same destination differently based on source? → Can't do with destination-based forwarding

SDN Solution

$\text{Generalized forwarding + SDN can achieve any routing desired}$

Data plane act like a BODY (มีการส่งข้อมูลจริง ๆ ก็ตรงนี้)
Control plane act like a BRAIN (อันนี้ทำการ Calculate ให้แทน) → Routing, Security, Access Control

Table ที่อยู่ในแต่ละ Router ที่ได้มาจาก Server มันไม่ใช่แค่ normal forwarding table anymore เราจะเรียกว่า Flow Table, contain much more information

4 Key SDN Characteristics

1. Generalized "flow-based" forwarding (e.g., OpenFlow)
2. Control, data plane separation
3. Control plane functions external to data-plane switches
4. Programmable control applications

SDN is like separating the GPS navigation app (control plane) from the car's engine (data plane) — the app can be updated independently.

Why Logically Centralized Control?

• Easier network management: avoid router misconfigurations; greater traffic flow flexibility
• Table-based forwarding (OpenFlow API) allows "programming" of routers
  • Centralized programming: compute tables centrally and distribute → easier
  • Distributed programming: run algorithm in every router → harder
• Open (non-proprietary) implementation of control plane

SDN Architecture

┌──────────────────────────────────────────┐
│        Network-Control Applications       │  ← routing, access control, load balance
│  (Routing) (Access Ctrl) (Load Balance)  │
└──────────────┬───────────────────────────┘
               │ northbound API
┌──────────────▼───────────────────────────┐
│         SDN Controller (Network OS)       │  ← control plane
└──────────────┬───────────────────────────┘
               │ southbound API
┌──────────────▼───────────────────────────┐
│         SDN-Controlled Switches           │  ← data plane
└──────────────────────────────────────────┘

Three SDN Component

1. Data-Plane Switches

• Fast, simple, commodity switches implementing generalized data-plane forwarding in hardware
• Flow (forwarding) table computed and installed under controller supervision
• API for table-based switch control (e.g., OpenFlow)
• Protocol for communicating with controller (e.g., OpenFlow)

2. SDN Controller (Network OS)

• Maintains network state information
• Interacts with network control apps "above" via northbound API
• Interacts with network switches "below" via southbound API
• Implemented as distributed system for performance, scalability, fault-tolerance, robustness

Example: RYU OpenFlow Controller (น่าจะเป็น Open Source รึเปล่า)

3. Network-Control Applications

• "Brains" of control: implement control functions using lower-level services from SDN controller
• Unbundled: can be provided by 3rd party (distinct from routing vendor or SDN controller)

Generalized Forwarding & OpenFlow

Generalized Forwarding: Match Plus Action

• Each router contains a forwarding table (aka: flow table)
• "Match plus action" abstraction: match bits in arriving packet → take action

Flow Table Abstraction

• Flow: defined by header field values (link-, network-, transport-layer fields)
• Generalized forwarding = simple packet-handling rules:
  • Match: pattern values in packet header fields
  • Actions: drop, forward, modify packet; or send to controller
    • Forward ก็สามารถ ระบุได้ว่าให้ไป port อะไร
    • Modify dst IP, src IP, port อะไร ทำได้หมด
  • Priority: disambiguate overlapping patterns
  • Counters: #bytes and #packets

Example Flow Table

OpenFlow: Flow Table Entries

Structure: Match | Action | Stats

Actions:

1. Forward packet to port(s)
2. Drop packet
3. Modify fields in header(s)
4. Encapsulate and forward to controller

Header fields matchable (across layers):

OpenFlow Examples

Flow Table และ concept SDN เราสามารถทำให้ Switch กลายเป็น router, firewall ก็ได้ + …. อื่น ๆ อีกมากมาย

Destination-based forwarding:

• IP datagrams to 51.6.0.8 → forward to port 6

Firewall:

• Block all datagrams to TCP port 22 (SSH): match TCP d-port = 22 → drop

• Block all from host 128.119.1.1: match IP Src = 128.119.1.1 → drop

OpenFlow Abstraction: Unifies Different Devices

SDN Controller Components

Three Layers of SDN Controller

┌──────────────────────────────────────────────────┐
│     Interface, abstractions for network control apps   │
│   [ network graph ]  [ RESTful API ]  [ intent ]  │
├──────────────────────────────────────────────────┤
│    Network-wide distributed, robust state management   │
│  [ statistics ] [ flow tables ] [ Link-state info ]│
│  [ host info ]  [ switch info ]                    │
├──────────────────────────────────────────────────┤
│        Communication to/from controlled devices        │
│           [ OpenFlow ]        [ SNMP ]             │
└──────────────────────────────────────────────────┘

SDN: Control/Data Plane Interaction Example (Link Failure)

1. Switch S1 experiences link failure → uses OpenFlow port status message to notify controller
2. SDN controller receives OpenFlow message → updates link status info
3. Dijkstra's routing algorithm (registered for link status changes) → is called
4. Dijkstra's algorithm accesses network graph info in controller → computes new routes
5. Link state routing app interacts with flow-table-computation component → computes new flow tables
6. Controller uses OpenFlow to install new tables in switches that need updating

Summary

Routing Algorithms

• Link State (Dijkstra): global view, fast convergence → used in OSPF
• Distance Vector (Bellman-Ford): local view, iterative → used in RIP

Routing Protocols

• RIP/RIPv2 — DV, hop count metric, max 15 hops
• EIGRP — advanced DV, Cisco, composite metric
• OSPF — LS, hierarchical, uses Dijkstra
• BGP — path vector, inter-AS, policy-based

SDN

• Separates control plane (centralized) from data plane (distributed switches)
• Uses OpenFlow for match+action forwarding
• Controller has northbound (to apps) and southbound (to switches) APIs