Network Layer
Introduction
Routing protocols
ICMP
Network-layer functions
Recall : two network-layer functions
- Forwarding : move packets from routers' input to appropriate router output -> data plane
- Routing : determine route taken by packets from source to destination -> control plane
Two approaches to structuring network control plane
- per-router control (tranditional, still popular)
- logically centralized control (software defined networking SDN)
Per-router control plane
Individual routing algorithm components in each and every router interact with each other in control plane to compute forwarding table
Logically centralized control plane
A distinct (typically remote ) controller (centralized) interacts with local control agents (CAs) in routers to compute forwarding tables
Routing Protocols
Routing protocol goal
- determine "good" paths (equivalently, routes), from sending hosts to receiving host, through network fo routers
> path : sequence of routers that packets will traverse in going from givien initial source host to given final destination host
> good : least cost. fastest (least latency, highest thorughput), least congested, etc )
Graph abstraction of the network
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(x, x') = cost of link (x, x')
cost could always be 1, or inversely related to bandwidth, or related to latency/congestion
cost of path $(x_1, x_2,x_3, \cdots, x_p) = c(x_1, x_2) + c(x_2, x_3) + \cdots + c(x_{p-1}, x_p)$
- Key Question : what is the least-cost path between u and z?
- Routing algorithm : algorithm that finds that least cost path
Routing algorithm classification
Q : Global or decentralized information ?
- global ( router know all of graph ( cost , router )
> all router have complete topology, link cost info
> "link state" algorithms
- decentralized ( router do not know the complete topology )
> router knows physically-connected neighbors, link costs to neighbors
> iterative process of computation, exchange of info with neighbors
> "distance vector" algorithms
Q : static or dynamic?
- static
> routes change slowly over time
- dynamic ( movable device, wifi router... )
> routes change more quickly : periodic update , inresponse to link cost changes
Routing protocols - Link state
Dijkstra's algorithm (complete global )
- net topology, link costs known to all nodes
> accomplished via "link state broadcast" (
> all nodes have same info
- computes least cost paths from one node ('source') to all other nodes
> gives forwarding table for that node
- iterative : after k iterations, know least cost path to k destinations
Notation
> c(x,) : link cost from node x to h; c(x,y) = $\infty$ if not direct neighbors
> D(v) : current value of cost of path from source to destination v
> p(v) : predecessor node along path from source to v
> N' : set of nodes whose least cost path definitively known
Discussion
- algorithm complexity : n nodes
> each iteration : need to check all nodes, w, not in N
> $n(n+1)/2$ comparisons $ O(n^2)$
> more efficient implementations possible using heap : $O(n \log n)$
- oscillations possible
> e.g., suppose link cost equals amount of carried traffic (congestion change -> dynamic )
Routng protocols - Distance vector
Bellman-Ford algorithm (dynamic programming)
- let $d_x(y) =$ cost of least-cost path from x to y
- then, $d_x(y) = \min_v {c(x,y), d_v(y)}$
> $d_v(y)$ : cost from neighbor v to destination y
> $c(x,y)$ : cost to neighbor v
> $\min_v$ : min taken over all neighbors v of x
- $D_x(y)$ : estimate of least cost from x to y
> x maintains distance vector $D_x = [D_x(y) : y \in N]$
- node x
> knows cost to each neighbor v : c(x,v)
> maintains its neighbors' distance vectors. For each neighbor v, x maintains $D_v[D_v(y) : y \in N]$
- Key idea
> from time-to-time, each node sends its own distance vector estimate to neighbors
> when x receives new DV estimate from neighbor, it updates its own DV using B-F equation : $D_x(y) \leftarrow \min_v {c(x,y) + D_v(y)}$ for each node $y \in N$
> under minor, natural conditions, the estimate $D_x(y)$ converge to the actual least cost $d_x(y)$
Iterative, asynchronous
- each local iteration caused by
> local link cost change
> DV update message from neighbor
Distributed
- each node notifies neighbors only when its DV changes
> neighbors then notify their neighbors if necessary
Each node
- wait : for change in local link cost or msg from neighbor
- recompute : estimates
- notify : if DV to any dest has changed, notify neighbors
Distance vector : link cost changes
link cost changes
- node detects local link cost change
- updates routing info, recalculates distance vector
- if DV changes, notify neighbors
"Good news travels fast" - 한 노드의 DV가 변하면 다른 노드에게 전달 -> 온 정보로 노드의 DV가 변화해서 전달 -> 받는 노드는 결국 최소 cost 에 도달하게됨
"bad news travels slow" - "count to infinity" problem! ( 목적 노드를 다른 노드를 통해서 가는 경로인경우 중간 노드의 cost가 높게 변하게 되면, 두 노드 사이에 DV 변화가 무한정 반복된다. -> 44 iterations before algorithm stabilizes : see textbook
Poisoned reverse :
- if Z routes through Y to get to X
> Z tells Y its (Z's) distance to X is infinite (so Y won't route to X via Z)
- will this completely solve count to infinity problem? -> NO...
Compare of LS and DV algorithms
Message compleity
- LS : with n nodes, E links, O(nE) msgs sent
- DV : exchange between neighbors only
Speed of convergence
- LS : $O(n^2)$ algorithm requires O(nE) msgs
- DV : convergence time varies
> may be routing loops
> count-to-infinity problem
Robustness : what happens if router malfunction?
- LS: node can adverties incorrect link cost
> each node computes only its own table
- DV : node can adverties incorrect path cost
> each node's table used by others : error propagate through network
Intra-AS routing in the Internet : OSPF
Making routing scalable
our routing study thus far idealized
- all routers identical
- network "flat"
- ... not ture in practice
scale : with billions of destinations
- can't store all destinations in routing tables!
- routing table exchange would swamp links -> hierarchy
administrative autonomy
- internet = network of networks
- each network admin may want to control routing in tis own network
Internet approach to scalable routing
- aggregate routers into regions known as "autonomous system AS" (aka domains)
- Intra-AS routing ( routing in AS )
> routing among hosts, routers in same AS ("network")
> all routers in AS must run same intra-domain protocol
> routers in different AS can run different intra-domain routing protocol
> gateway router : at "dege" of its own AS, has link(s) to router(s) in other AS'es
- Inter-AS routing
> routing among AS'es => BGP ( protocol of inter intranet )
> gateways preform inter-domain routing (as well as intra-domain routing)
Interconnected AS'es
Forwarding table configured by both intra and inter-AS routing algorithm
- intra-AS routing determine entries for destinations within AS
- inter-AS & intra-AS determin entries for external destinations
Inter-AS tasks
suppose router in AS1 receives datagram destined outside of AS1
- router should forward packet to gateway router, but which one?
AS1 must
1. learn which destinations are reachable though AS2, which trough AS3...
2. propagate this reachability info to all routers in AS1
Intra-AS Routing
Also known as interior gateway progocols (IGP)
Most common intra-AS routing protocols
- RIP : Routing Information Protocol
> Variant of Bellman-Ford algorithm
- OSPF : Open Shortest Path First
> IS-IS protocol essentially smae as OSPF
> variant of Dijkstra's algorithm
- IGRP : inerior Gateway Routing Protocl
> Cisco proprietary for decades, untill 2016
OSPF Open Shortest Path First (Intra protocol)
"Open":publicly available
Uses link-state algorithm
- link state packet disseination
- topology map at each node
- route computation using Dijkstra' algorithm
Router floods OSPF link-state advertisements to all other routers in entire AS
- carried in OSPF messages drectly over IP (rather than TCP or UDP)
- link state : for each attached link
IS-IS routing protocol : nearly identical to OSPF