cs/ee 143 Communication Networks
Chapter 5 Routing
Text: Walrand & Parakh, 2010
Steven Low
CMS, EE, Caltech
Warning
These notes are not self-contained,
probably not understandable,
unless you also were in the lecture
They are supplement to not replacement for class attendance
Lecture outline
Inter-domain routing
BGP
Intra-domain routing
Shortest path algortihms
Coding
FEC, network coding
What is routing?
Choose red or blue.
Internet
How to route?
Two layers of routing:
1. Choose which AS?
- BGP
2. How to route inside an AS?
- OSPF
Autonomy system (AS)
e.g., AT&T, Verizon, MIT.
Internet
A
Why two layers?
Different objectives
Choose AS: special policies
Inside AS: minimize delay, # hops
Simplify routing
Choose AS: ignore details inside AS
Inside AS: only details inside AS
Inter-domain routing: BGP
Peering relation: A-B, B-C
A, B, C carry each others traffic
free
of charge
B only advertises B to A and to C
A does not know how to reach C
through this. A must have transit
relation with anther ISP (not shown
here) that carries its traffic to C.
Transit relation: A-B, B-C
Customer-provider relation, e.g., B
is provider for A and for C. A (C)
pays B for carrying to/from A (C).
B advertises {B,C} to A and {A, B} to
C so that all ISPs know how to
reach all destinations.
Inter-domain routing: BGP
A typical configuration
Inter-domain routing: BGP
BGP is policy-based routing
Generally not shortest-path
Other factors are generally more important
in determining an AS-path than performance
Peering agreement
Pricing (revenue/cost) with next hop
Reliability, security, political reasons
Can lead to oscillation and bad performance
Inter-domain routing: BGP
Example
BGP policy at Berkeley:
1. If possible, avoid AT&T
2. Choose path with smallest #hops
3. Alphabetical
Berkeley decision:
use path Sprint-Verizon-MIT to reach MIT
Border Gateway Protocol (BGP)
Every AS keeps a list of (Destination, Path) pairs & policies.
Policy: avoid AT&T.
How to reach MIT from Berkeley?
Verizon
(MIT, Verizon---MIT)
AT&T
(MIT, AT&T---MIT)
Sprint
(MIT, NA)
Berkeley
(MIT, NA)
Border Gateway Protocol (BGP)
Every AS keeps a list of (Destination, Path) pairs & policies.
Policy: avoid AT&T.
How to reach MIT from Berkeley?
Verizon
(MIT, Verizon---MIT)
(MIT, Verizon---AT&T---MIT)
AT&T
(MIT, AT&T---MIT)
(MIT, AT&T---Verizon---MIT)
Sprint
(MIT, Sprint---Verizon---MIT)
(MIT, Sprint---AT&T---MIT)
Berkeley
(MIT, Berkeley---AT&T---MIT)
Border Gateway Protocol (BGP)
Every AS keeps a list of (Destination, Path) pairs & policies.
Policy: avoid AT&T.
How to reach MIT from Berkeley?
Verizon
(MIT, Verizon---MIT)
AT&T
(MIT, AT&T---MIT)
Sprint
(MIT, Sprint---Verizon---MIT)
Berkeley
(MIT, Berkeley---AT&T---MIT) (MIT, Berkeley---Sprint---Verizon---MIT)
Border Gateway Protocol (BGP)
In BGP, each AS
Announces itself to other ASes and which
ASes it can reach
Obtains ASes reachability info from
neighboring Ases
Propagate reachability info to all routers
internal to the AS
Determine good routes to ASes based on
reachability info and AS policy
BGP: potential oscillation
Example
BGP policy to reach D:
1. Prefer 2-hop path to 1-hop
2. Avoid 3-hop paths
Oscillation:
Every node will alternate between choosing an 1hop path and 2-hop path
Some questions
Q1: Why not 3-level, or N-level, routing?
Q2: How can a source ensure that its
packets follow the inter-domain path it
wants?
Q3: In BGP, can one prevent a domain
from lying and funneling all traffic
through itself in order eavesdrop?
Lecture outline
Inter-domain routing
BGP
Intra-domain routing
Shortest path algortihms
Coding
FEC, network coding
Shortest-path algorithm
Input: graph G (V , E ),
link costs dij (d ij if (i, j ) E)
Execution: algorithm run at each node
Output:
Dijkstra: shortest-path tree rooted at the node
Bellman-Ford: next hop to all destinations from the node
(entries in forwarding table)
Notation:
D (i ) : min cost to reach node i from x
x
predx(i) : parent node of i (for Dijkstra)
nextx(i) : next hop to i from x (for Bellman-Ford)
Dijkstra algorithm
Init: Dx (i ) d xi , Dx ( x) 0, R {x}, predx(i) = null
Each node x sends dxi to all other nodes i
while R V do
*
i
Dx (i )
{ arg min
iR
Run at each source node x
R R {i * }
*
j
N
(
i
)\R
for all
{ if Dx ( j ) Dx (i * ) d i* j then
Dx ( j ) Dx (i * ) d i* j
pred(j) =
}if
}for
}while
i*
Which step requires global info?
Dijkstra algorithm
Init: Dx (i ) d xi , Dx ( x) 0, R {x}, predx(i) = null
Each node x sends dxi to all other nodes i
while R V do
*
i
Dx (i )
{ arg min
iR
Run at each source node x
R R {i * }
*
j
N
(
i
)\R
for all
{ if Dx ( j ) Dx (i * ) d i* j then
Dx ( j ) Dx (i * ) d i* j
pred(j) =
}if
}for
}while
i*
Which step requires global info?
Dijkstra algorithm
Bellman-Ford algorithm
Init: Dx (i ) d xi , Dx ( x) 0, R {x}, predx(i) = null
Each node x sends distance vector Dx (i ), i V to all its
neighbors whenever Dx (i ), i V changes
do
(execute when link cost changes or on receipt of a DV from neighbor)
{
for all destination nodes i
{
Dx (i) : min dxj Dj (i)
jN( x)
nextx(i) =
}for
}
until no change
j * : arg min dxj Dj (i)
jN(i )
Run at each source node x
Bellman-Ford algorithm
Consider the calculations at all nodes
to reach node D
Every node has access to distance
estimates from neighbors to D
Assume synchronous operation
iteration
DA(D)
nextA(D)
DB(D)
nextB(D)
Inf
Inf
Inf
3
4
DC(D)
nextC(D)
DE(D)
nextE(D)
DF(D)
nextF(D)
Inf
Compare Dijsktra & BF
Message exchange
Dijkstra: every node sends only its incident link costs to all
other nodes. This requires O(|V| |E|) messages.
BF: every node sends only to its neighbors least-cost
estimates from itself to all other nodes
Speed of convergence
Disjstra: above implementation takes O(|V|2); can be
reduced using heap
BF: can converge slowly and have routing loops during
transient; count-to-infinity problem (can be solved using
poisoned reverse)
No clear winner
Both are used on Internet
RIP: distance-vector protocol
OSPF: link-state protocol (meant to be successor to RIP)
Count-to-infinity problem
Example
Link between B & C fails
A and B will not realize it, a routing route is created and their cost
estimate to C keeps going up
A solution: poisoned reverse: instead of telling B its true cost (2)
to reach C, A tells B that its cost to reach C is infinity because A
uses B to reach C.
Compare Dijsktra & BF
Dijkstra algorithm
Needs global information (link-state alg)
Each node broadcasts link-state packets to all
other nodes in network
Each node executes Dijkstra alg to calculate
shortest paths to all other nodes
After k iteration, shortest paths to k destinations
are known (and they are the k shortest paths
among the shortest paths to all nodes)
Terminates after N-1 iterations (N = #nodes)
Compare Dijsktra & BF
Bellman-Ford algorithm
Only needs local information (distance-vector alg)
Each node exchanges with neighbors the vector of
distances from itself to all other nodes
Each node then updates the next hop and
associated distance to all other nodes using
Bellman-Ford (DP) equation
Decentralized, asynchronous, distributed
Lecture outline
Inter-domain routing
BGP
Intra-domain routing
Shortest path algortihms
Coding
FEC, network coding
FEC: packet erasure code
Recover from packet loss
Coding
Input: n packets P1,, Pn
Output: m packets C1,,Cm, m n
Ck = bit-by-bit XOR of a random subset of P1,, Pn
Ck : Pi1 Pi2 Pi jk
Header of
Ck
specifies the subset used to generate
Ck
FEC: packet erasure code
Decoding
If C j Pi for some i, then
Ck : Ck Pi for all pkts Ck that contains Pi
Remove C j from the collection of recd pkts
Repeat until all P ,, P have been decoded
1
n
If at one step, there is no C P ,, P
j
1
n
then decoding fails
FEC: example
: received pkt
Decoding: received pkts C C1,C3,C5,C6
C C1,C3,C5,C6
C1 P1
C3 P1 P2 P3
C5 P4
C3 C3 C1 P2 P3
C C3,C5, C6
P P1
C6 P3 P4
FEC: example
: received pkt
Decoding:
C C1,C3,C5,C6
C1 P1
C3 P1 P2 P3
C5 P4
C3 C3 C1 P2 P3
C C3,C5, C6
P P1
C6 P3 P4
FEC: example
: received pkt
Decoding:
C C1,C3,C5,C6
C1 P1
C3 P1 P2 P3
C5 P4
C3 C3 C1 P2 P3
C C3,C5, C6
P P1
C6 P3 P4
FEC: example
: received pkt
Decoding:
C C3,C5,C6
C3 P2 P3
P P1
C5 P4
C6 P3 P4
C6 C6 C5 P3
C C3,C6
P P1, P4
FEC: example
: received pkt
Decoding:
C C3,C5,C6
C3 P2 P3
P P1
C5 P4
C6 P3 P4
C6 C6 C5 P3
C C3,C6
P P1, P4
FEC: example
: received pkt
Decoding:
C C3,C5,C6
C3 P2 P3
P P1
C5 P4
C6 P3 P4
C6 C6 C5 P3
C C3,C6
P P1, P4
FEC: example
: received pkt
Decoding:
C C3,C6
C3 P2 P3
P P1, P4
C6 P3
C3 C3 C6 P2
C C6
P P1, P3, P4
FEC: example
: received pkt
Decoding:
C C3,C6
C3 P2 P3
P P1, P4
C6 P3
C3 C3 C6 P2
C C6
P P1, P3, P4
FEC: example
: received pkt
Decoding:
C C3,C6
C3 P2 P3
P P1, P4
C6 P3
C3 C3 C6 P2
C C3
P P1, P3, P4
FEC: example
: received pkt
Decoding:
C C3
P P1, P2 , P4
C3 P3
C
P P1, P2 , P3, P4
FEC: example
: received pkt
Decoding:
C C3
P P1, P2 , P4
C3 P3
C
P P1, P2 , P3, P4
Network coding: example
link rate = R
on every link
multicast to
both Y & Z
throughput = 1.5R
throughput = 2R
Network coding: example
X and Y want to exchange A & B
Without network coding, needs 4 pkt xmissions
With network coding, needs 3 pkt xmissions