Chapter_5_v8.0Routing Protocol for Computer network from kurose and ross

Routing protocol goal: determine “good”
paths (equivalently, routes), from sending
hosts to receiving host, through network of
routers
 path: sequence of routers packets
traverse from given initial source host to
final destination host
 “good”: least “cost”, “fastest”, “least
congested”
 routing: a “top-10” networking challenge!
Routing protocols mobile network
enterprise
network
national or global ISP
datacenter
network
application
transport
network
link
physical
application
transport
network
link
physical
network
link
physical
network
link
physical
network
link
physical
network
link
physical network
link
physical
Network Layer: 5-1

Graph abstraction: link costs
Network Layer: 5-2
u
y
x
w
v
z
2
2
1
3
1
1
2
5
3
5
graph: G = (N,E)
ca,b: cost of direct link connecting a and b
e.g., cw,z = 5, cu,z = ∞
cost defined by network operator:
could always be 1, or inversely related
to bandwidth, or inversely related to
congestion
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) }

Dijkstra’s link-state routing algorithm
Network Layer: 5-3
 centralized: network 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
 cx,y: direct link cost from node
x to y; = ∞ if not direct
neighbors
 D(v): current estimate of cost
of least-cost-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
notation

Dijkstra’s algorithm: an example
Network Layer: 5-4
Step
0
1
2
3
4
5
N' D(v),p(v) D(x),p(x) D(y),p(y) D(z),p(z)
u
y
x
w
v
z
2
2
1
3
1
1
2
5
3
5
4,y
D(w),p(w)
4,y
3,y
5,u ∞
∞
1,u
2,u
∞
2,x
4,x
2,u
4,y
3,y
2,u
uxyvwz
uxyvw
uxyv
uxy
ux
u
v w x y z
find a not in N' such that D(a) is a 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) + ca,b )
Initialization (step 0): For all a: if a adjacent to then D(a) = cu,a

Dijkstra’s algorithm: an example
Network Layer: 5-5
u
y
x
w
v
z
2
2
1
3
1
1
2
5
3
5
u
y
x
w
v
z
resulting least-cost-path tree from u: resulting forwarding table in u:
v
x
y
w
x
(u,v)
(u,x)
(u,x)
(u,x)
(u,x)
destination outgoing link
route from u to v directly
route from u to all
other destinations
via x

Dijkstra’s algorithm: another example
Network Layer: 5-6
w
3
4
v
x
u
5
3
7 4
y
8
z
2
7
9
Step N'
D(v),
p(v)
0
1
2
3
4
5
D(w),
p(w)
D(x),
p(x)
D(y),
p(y)
D(z),
p(z)
u ∞
∞
7,u 3,u 5,u
uw ∞
11,w
6,w 5,u
14,x
11,w
6,w
uwx
uwxv 14,x
10,v
uwxvy 12,y
notes:
 construct least-cost-path tree by tracing predecessor nodes
 ties can exist (can be broken arbitrarily)
uwxvyz
v w x y z

Based on Bellman-Ford (BF) equation (dynamic programming):
Distance vector algorithm
Network Layer: 5-7
Let Dx(y): cost of least-cost path from x to y.
Then:
Dx(y) = minv { cx,v + Dv(y) }
Bellman-Ford equation
min taken over all neighbors v of x
v’s estimated least-cost-path cost to y
direct cost of link from x to v

Bellman-Ford Example
Network Layer: 5-8
u
y
z
2
2
1
3
1
1
2
5
3
5
Suppose that u’s neighboring nodes, x,v,w, know that for destination z:
Du(z) = min { cu,v + Dv(z),
cu,x + Dx(z),
cu,w + Dw(z) }
Bellman-Ford equation says:
Dv(z) = 5
v
Dw(z) = 3
w
Dx(z) = 3
x
= min {2 + 5,
1 + 3,
5 + 3} = 4
node achieving minimum (x) is
next hop on estimated least-
cost path to destination (z)

Distance vector algorithm
Network Layer: 5-9
key idea:
 from time-to-time, each node sends its own distance vector estimate to
neighbors
 under minor, natural conditions, the estimate Dx
(y) converge to the
actual least cost dx(y)
Dx
(y) ← minv
{cx,v + Dv
(y)} for each node y ∊ N
 when x receives new DV estimate from any neighbor, it updates its
own DV using B-F equation:

Distance vector algorithm:
Network Layer: 5-10
iterative, asynchronous: each local
iteration caused by:
 local link cost change
 DV update message from neighbor
wait for (change in local link
cost or msg from neighbor)
each node:
distributed, self-stopping: each
node notifies neighbors only when
its DV changes
 neighbors then notify their
neighbors – only if necessary
 no notification received, no
actions taken!
recompute DV estimates using
DV received from neighbor
if DV to any destination has
changed, notify neighbors

DV in a:
Da(a)=0
Da(b) = 8
Da(c) = ∞
Da(d) = 1
Da(e) = ∞
Da(f) = ∞
Da(g) = ∞
Da(h) = ∞
Da(i) = ∞
Distance vector: example
Network Layer: 5-11
g h i
1 1
1 1 1
1 1
1 1
8 1
t=0
 All nodes have
distance estimates
to nearest
neighbors (only)
A few asymmetries:
 missing link
 larger cost
d e f
a b c
 All nodes send
their local
distance vector to
their neighbors

Distance vector example: iteration
Network Layer: 5-12
All nodes:
 receive distance
vectors from
neighbors
 compute their new
local distance
vector
 send their new
local distance
vector to neighbors
t=1
g h i
1 1
1 1 1
1 1
1 1
8 1
d e f
a b c

Network Layer: 5-13
g h i
1 1
1 1 1
1 1
1 1
8 1
d e f
a b c
All nodes:
vectors from
neighbors
local distance
vector
 send their new
local distance
vector to neighbors
t=1
compute compute compute

Network Layer: 5-14
g h i
1 1
1 1 1
1 1
1 1
8 1
d e f
a b c
All nodes:
vectors from
neighbors
local distance
vector
 send their new
local distance
vector to neighbors
t=1

Network Layer: 5-15
g h i
1 1
1 1 1
1 1
1 1
8 1
d e f
a b c
All nodes:
vectors from
neighbors
local distance
vector
 send their new
local distance
vector to neighbors
t=2

Network Layer: 5-16
g h i
1 1
1 1 1
1 1
8 1
2 1
d e f
a b c
All nodes:
vectors from
neighbors
local distance
vector
 send their new
local distance
vector to neighbors
t=2

Network Layer: 5-17
g h i
1 1
1 1 1
1 1
1 1
8 1
d e f
a b c
All nodes:
vectors from
neighbors
local distance
vector
 send their new
local distance
vector to neighbors
t=2

Network Layer: 5-18
…. and so on
Let’s next take a look at the iterative computations at nodes

DV in a:
Da(a)=0
Da(b) = 8
Da(c) = ∞
Da(d) = 1
Da(e) = ∞
Da(f) = ∞
Da(g) = ∞
Da(h) = ∞
Da(i) = ∞
Distance vector example: computation
Network Layer: 5-19
g h i
1 1
1 1 1
1 1
1 1
8 1
t=1
DV in b:
Db(f) = ∞
Db(g) = ∞
Db(h) = ∞
Db(i) = ∞
Db(a) = 8
Db(c) = 1
Db(d) = ∞
Db(e) = 1
 b receives DVs
from a, c, e
a b c
d e f
DV in c:
Dc(a) = ∞
Dc(b) = 1
Dc(c) = 0
Dc(d) = ∞
Dc(e) = ∞
Dc(f) = ∞
Dc(g) = ∞
Dc(h) = ∞
Dc(i) = ∞
DV in e:
De(a) = ∞
De(b) = 1
De(c) = ∞
De(d) = 1
De(e) = 0
De(f) = 1
De(g) = ∞
De(h) = 1
De(i) = ∞

DV in a:
Da(a)=0
Da(b) = 8
Da(c) = ∞
Da(d) = 1
Da(e) = ∞
Da(f) = ∞
Da(g) = ∞
Da(h) = ∞
Da(i) = ∞
DV in b:
Db(f) = ∞
Db(g) = ∞
Db(h) = ∞
Db(i) = ∞
Db(a) = 8
Db(c) = 1
Db(d) = ∞
Db(e) = 1
DV in c:
Dc(a) = ∞
Dc(b) = 1
Dc(c) = 0
Dc(d) = ∞
Dc(e) = ∞
Dc(f) = ∞
Dc(g) = ∞
Dc(h) = ∞
Dc(i) = ∞
DV in e:
De(a) = ∞
De(b) = 1
De(c) = ∞
De(d) = 1
De(e) = 0
De(f) = 1
De(g) = ∞
De(h) = 1
De(i) = ∞
Network Layer: 5-20
g h i
1 1
1 1 1
1 1
1 1
8 1
t=1
 b receives DVs
from a, c, e,
computes:
a b c
d e f
DV in b:
Db(f) =2
Db(g) = ∞
Db(h) = 2
Db(i) = ∞
Db(a) = 8
Db(c) = 1
Db(d) = 2
Db(e) = 1
e
compute
b
Db(a) = min{cb,a+Da(a), cb,c +Dc(a), cb,e+De(a)} = min{8,∞,∞} = 8
Db(c) = min{cb,a+Da(c), cb,c +Dc(c), cb,e +De(c)} = min{∞,1,∞} = 1
Db(d) = min{cb,a+Da(d), cb,c +Dc(d), cb,e +De(d)} = min{9,2,∞} = 2
Db(f) = min{cb,a+Da(f), cb,c +Dc(f), cb,e +De(f)} = min{∞,∞,2} = 2
Db(i) = min{cb,a+Da(i), cb,c +Dc(i), cb,e+De(i)} = min{∞,∞, ∞} = ∞
Db(h) = min{cb,a+Da(h), cb,c +Dc(h), cb,e+De(h)} = min{∞,∞, 2} = 2
Db(e) = min{cb,a+Da(e), cb,c +Dc(e), cb,e +De(e)} = min{∞,∞,1} = 1
Db(g) = min{cb,a+Da(g), cb,c +Dc(g), cb,e+De(g)} = min{∞,∞, ∞} = ∞

DV in a:
Da(a)=0
Da(b) = 8
Da(c) = ∞
Da(d) = 1
Da(e) = ∞
Da(f) = ∞
Da(g) = ∞
Da(h) = ∞
Da(i) = ∞
Network Layer: 5-21
g h i
1 1
1 1 1
1 1
1 1
8 1
t=1
DV in b:
Db(f) = ∞
Db(g) = ∞
Db(h) = ∞
Db(i) = ∞
Db(a) = 8
Db(c) = 1
Db(d) = ∞
Db(e) = 1
 c receives DVs
from b
a b c
d e f
DV in c:
Dc(a) = ∞
Dc(b) = 1
Dc(c) = 0
Dc(d) = ∞
Dc(e) = ∞
Dc(f) = ∞
Dc(g) = ∞
Dc(h) = ∞
Dc(i) = ∞
DV in e:
De(a) = ∞
De(b) = 1
De(c) = ∞
De(d) = 1
De(e) = 0
De(f) = 1
De(g) = ∞
De(h) = 1
De(i) = ∞

Network Layer: 5-22
g h i
1 1
8 1
t=1
DV in b:
Db(f) = ∞
Db(g) = ∞
Db(h) = ∞
Db(i) = ∞
Db(a) = 8
Db(c) = 1
Db(d) = ∞
Db(e) = 1
 c receives DVs
from b computes:
a b c
d e f
DV in c:
Dc(a) = ∞
Dc(b) = 1
Dc(c) = 0
Dc(d) = ∞
Dc(e) = ∞
Dc(f) = ∞
Dc(g) = ∞
Dc(h) = ∞
Dc(i) = ∞
Dc(a) = min{cc,b+Db(a}} = 1 + 8 = 9
Dc(b) = min{cc,b+Db(b)} = 1 + 0 = 1
Dc(d) = min{cc,b+Db(d)} = 1+ ∞ = ∞
Dc(e) = min{cc,b+Db(e)} = 1 + 1 = 2
Dc(f) = min{cc,b+Db(f)} = 1+ ∞ = ∞
Dc(g) = min{cc,b+Db(g)} = 1+ ∞ = ∞
Dc(i) = min{cc,b+Db(i)} = 1+ ∞ = ∞
Dc(h) = min{cbc,b+Db(h)} = 1+ ∞ = ∞
DV in c:
Dc(a) = 9
Dc(b) = 1
Dc(c) = 0
Dc(d) = 2
Dc(e) = ∞
Dc(f) = ∞
Dc(g) = ∞
Dc(h) = ∞
Dc(i) = ∞
compute
* Check out the online interactive
exercises for more examples:
http://gaia.cs.umass.edu/kurose_ross/interactive/

Network Layer: 5-23
1 1
1 1 1
1 1
1 1
8 1
t=1
DV in b:
Db(f) = ∞
Db(g) = ∞
Db(h) = ∞
Db(i) = ∞
Db(a) = 8
Db(c) = 1
Db(d) = ∞
Db(e) = 1
 e receives DVs
from b, d, f, h
a b c
DV in f:
Dc(a) = ∞
Dc(b) = ∞
Dc(c) = ∞
Dc(d) = ∞
Dc(e) = 1
Dc(f) = 0
Dc(g) = ∞
Dc(h) = ∞
Dc(i) = 1
DV in e:
De(a) = ∞
De(b) = 1
De(c) = ∞
De(d) = 1
De(e) = 0
De(f) = 1
De(g) = ∞
De(h) = 1
De(i) = ∞
DV in h:
Dc(a) = ∞
Dc(b) = ∞
Dc(c) = ∞
Dc(d) = ∞
Dc(e) = 1
Dc(f) = ∞
Dc(g) = 1
Dc(h) = 0
DV in d:
Dc(a) = 1
Dc(b) = ∞
Dc(c) = ∞
Dc(d) = 0
Dc(e) = 1
Dc(f) = ∞
Dc(g) = 1
Dc(h) = ∞
Dc(i) = ∞ d e f
g h i
Q: what is new DV computed in e at
t=1?
compute

Distance vector: state information diffusion
t=0 c’s state at t=0 is at c only
g h i
1 1
1 1 1
1 1
1 1
8 1
d e f
a b c
c’s state at t=0 has propagated to b, and
may influence distance vector computations
up to 1 hop away, i.e., at b
t=1
c’s state at t=0 may now influence distance
vector computations up to 2 hops away, i.e.,
at b and now at a, e as well
t=2
c’s state at t=0 may influence distance vector
computations up to 3 hops away, i.e., at b,a,e
and now at c,f,h as well
t=3
c’s state at t=0 may influence distance vector
computations up to 4 hops away, i.e., at b,a,e,
c, f, h and now at g,i as well
t=4
Iterative communication, computation steps diffuses information through network:
t=1
t=2
t=3
t=4

Distance vector: link cost changes
Network Layer: 5-25
“good news
travels fast”
t0 : y detects link-cost change, updates its DV, informs its neighbors.
t1 : z receives update from y, updates its table, computes new least
cost to x , sends its neighbors its DV.
t2 : y receives z’s update, updates its distance table. y’s least costs
do not change, so y does not send a message to z.
link cost changes:
 node detects local link cost change
 updates routing info, recalculates local DV
 if DV changes, notify neighbors
x z
1
4
50
y
1

Distance vector: link cost changes
Network Layer: 5-26
link cost changes:
 node detects local link cost change
 “bad news travels slow” – count-to-infinity problem:
x z
1
4
50
y
60
• y sees direct link to x has new cost 60, but z has said it has a path at cost of 5. So
y computes “my new cost to x will be 6, via z); notifies z of new cost of 6 to x.
• z learns that path to x via y has new cost 6, so z computes “my new cost to
x will be 7 via y), notifies y of new cost of 7 to x.
• y learns that path to x via z has new cost 7, so y computes “my new cost to
x will be 8 via y), notifies z of new cost of 8 to x.
• z learns that path to x via y has new cost 8, so z computes “my new cost to
x will be 9 via y), notifies y of new cost of 9 to x.
…
 see text for solutions. Distributed algorithms are tricky!

Comparison of LS and DV algorithms
Network Layer: 5-27
message complexity
LS: n routers, O(n2
) messages sent
DV: exchange between neighbors;
convergence time varies
speed of convergence
LS: O(n2
) algorithm, O(n2
) messages
• may have oscillations
DV: convergence time varies
• may have routing loops
• count-to-infinity problem
robustness: what happens if router
malfunctions, or is compromised?
LS:
• router can advertise incorrect link cost
• each router computes only its own
table
DV:
• DV router can advertise incorrect path
cost (“I have a really low cost path to
everywhere”): black-holing
• each router’s table used by others:
error propagate thru network

our routing study thus far - idealized
 all routers identical
 network “flat”
… not true in practice
Making routing scalable
Network Layer: 5-28
scale: billions of destinations:
 can’t store all destinations in
routing tables!
 routing table exchange would
swamp links!
administrative autonomy:
 Internet: a network of networks
 each network admin may want to
control routing in its own network

aggregate routers into regions known as “autonomous
systems” (AS) (a.k.a. “domains”)
Internet approach to scalable routing
Network Layer: 5-29
intra-AS (aka “intra-domain”):
routing among within same AS
(“network”)
 all routers in AS must run same intra-
domain protocol
 routers in different AS can run different
intra-domain routing protocols
 gateway router: at “edge” of its own AS,
has link(s) to router(s) in other AS’es
inter-AS (aka “inter-domain”):
routing among AS’es
 gateways perform inter-domain
routing (as well as intra-domain
routing)

Interconnected ASes
Network Layer: 5-30
3b
1d
3a
1c
2a
AS3
AS1
AS2
1a
2c
2b
1b
3c
intra-AS
routing
intra-AS
routing
intra-AS
routing
inter-AS routing
forwarding
table
forwarding table configured by intra-
and inter-AS routing algorithms
Intra-AS
Routing
Inter-AS
Routing  intra-AS routing determine entries for
destinations within AS
 inter-AS & intra-AS determine entries
for external destinations

Inter-AS routing: a role in intradomain forwarding
Network Layer: 5-31
3b
1d
3a
1c
2a
AS3
AS1
AS2
1a
2c
2b
1b
3c
other
networks
other
networks
 suppose router in AS1 receives
datagram destined outside of AS1:
AS1 inter-domain routing must:
1. learn which destinations reachable
through AS2, which through AS3
2. propagate this reachability info to all
routers in AS1
• router should forward packet to
gateway router in AS1, but which
one?

Inter-AS routing: routing within an AS
Network Layer: 5-32
most common intra-AS routing protocols:
 RIP: Routing Information Protocol [RFC 1723]
• classic DV: DVs exchanged every 30 secs
• no longer widely used
 EIGRP: Enhanced Interior Gateway Routing Protocol
• DV based
• formerly Cisco-proprietary for decades (became open in 2013 [RFC 7868])
 OSPF: Open Shortest Path First [RFC 2328]
• link-state routing
• IS-IS protocol (ISO standard, not RFC standard) essentially same as OSPF

OSPF (Open Shortest Path First) routing
Network Layer: 5-33
 “open”: publicly available
 classic link-state
• each router floods OSPF link-state advertisements (directly over IP
rather than using TCP/UDP) to all other routers in entire AS
• multiple link costs metrics possible: bandwidth, delay
• each router has full topology, uses Dijkstra’s algorithm to compute
forwarding table
 security: all OSPF messages authenticated (to prevent malicious
intrusion)

Hierarchical OSPF
Network Layer: 5-34
 two-level hierarchy: local area, backbone.
• link-state advertisements flooded only in area, or backbone
• each node has detailed area topology; only knows direction to reach
other destinations
area border routers:
“summarize” distances to
destinations in own area,
advertise in backbone
area 1
area 2
area 3
backbone
internal
routers
backbone router:
runs OSPF limited
to backbone
boundary router:
connects to other ASes
local routers:
• flood LS in area only
• compute routing within
area
• forward packets to outside
via area border router

 BGP (Border Gateway Protocol): the de facto inter-domain routing
protocol
• “glue that holds the Internet together”
 allows subnet to advertise its existence, and the destinations it can
reach, to rest of Internet: “I am here, here is who I can reach, and how”
 BGP provides each AS a means to:
• eBGP: obtain subnet reachability information from neighboring ASes
• iBGP: propagate reachability information to all AS-internal routers.
• determine “good” routes to other networks based on reachability information
and policy
Internet inter-AS routing: BGP
Network Layer: 5-35

eBGP, iBGP connections
Network Layer: 5-36
eBGP connectivity
logical iBGP connectivity
1b
1d
1c
1a
2b
2d
2c
2a
3b
3d
3c
3a
AS 2
AS 3
AS 1
1c
∂
∂
gateway routers run both eBGP and iBGP protocols

BGP basics
Network Layer: 5-37
 when AS3 gateway 3a advertises path AS3,X to AS2 gateway 2c:
• AS3 promises to AS2 it will forward datagrams towards X
 BGP session: two BGP routers (“peers”) exchange BGP messages over
semi-permanent TCP connection:
• advertising paths to different destination network prefixes (BGP is a “path
vector” protocol)
2b
2d
2c
2a
AS 2
3b
3d
3c
3a
AS 3
1b
1d
1c
1a
AS 1
X
BGP advertisement:
AS3, X

Path attributes and BGP routes
Network Layer: 5-38
 BGP advertised route: prefix + attributes
• prefix: destination being advertised
• two important attributes:
• AS-PATH: list of ASes through which prefix advertisement has passed
• NEXT-HOP: indicates specific internal-AS router to next-hop AS
 policy-based routing:
• gateway receiving route advertisement uses import policy to
accept/decline path (e.g., never route through AS Y).
• AS policy also determines whether to advertise path to other other
neighboring ASes

2b
2d
2c
2a
AS 2
3b
3d
3c
3a
AS 3
1b
1d
1c
1a
AS 1
X
BGP path advertisement
Network Layer: 5-39
 based on AS2 policy, AS2 router 2c accepts path AS3,X, propagates (via iBGP) to all
AS2 routers
AS2,AS3,X
 AS2 router 2c receives path advertisement AS3,X (via eBGP) from AS3 router 3a
 based on AS2 policy, AS2 router 2a advertises (via eBGP) path AS2, AS3, X to
AS1 router 1c
AS3, X

BGP path advertisement (more)
Network Layer: 5-40
AS2,AS3,X
 AS1 gateway router 1c learns path AS2,AS3,X from 2a
gateway router may learn about multiple paths to destination:
AS3,X
 AS1 gateway router 1c learns path AS3,X from 3a
 based on policy, AS1 gateway router 1c chooses path AS3,X and advertises path
within AS1 via iBGP
AS3, X
2b
2d
2c
2a
AS 2
3b
3d
3c
3a
AS 3
1b
1d
1c
1a
AS 1
X
AS3,X
AS3,X
AS3,X

BGP messages
Network Layer: 5-41
 BGP messages exchanged between peers over TCP connection
 BGP messages:
• OPEN: opens TCP connection to remote BGP peer and authenticates
sending BGP peer
• UPDATE: advertises new path (or withdraws old)
• KEEPALIVE: keeps connection alive in absence of UPDATES; also ACKs
OPEN request
• NOTIFICATION: reports errors in previous msg; also used to close
connection

2b
2d
2c
2a
AS 2
3b
3d
3c
3a
AS 3
1b
1d
1c
1a
AS 1
X
Network Layer: 5-42
AS2,AS3,X
AS3,X
AS3, X
 recall: 1a, 1b, 1d learn via iBGP from 1c: “path to X goes through 1c”
 at 1d: OSPF intra-domain routing: to get to 1c, use interface 1
1
2
1
2
dest interface
…
…
…
…
local link
interfaces
at 1a, 1d
 at 1d: to get to X, use interface 1
1c 1
X 1
AS3,X
AS3,X
AS3,X

2b
2d
2c
2a
AS 2
3b
3d
3c
3a
AS 3
1b
1d
1c
1a
AS 1
X
Network Layer: 5-43
 recall: 1a, 1b, 1d learn via iBGP from 1c: “path to X goes through 1c”
 at 1d: OSPF intra-domain routing: to get to 1c, use interface 1
1
2
 at 1d: to get to X, use interface 1
dest interface
…
…
…
…
1c 2
X 2
 at 1a: OSPF intra-domain routing: to get to 1c, use interface 2
 at 1a: to get to X, use interface 2

Why different Intra-, Inter-AS routing ?
Network Layer: 5-44
policy:
 inter-AS: admin wants control over how its traffic routed, who
routes through its network
 intra-AS: single admin, so policy less of an issue
scale:
 hierarchical routing saves table size, reduced update traffic
performance:
 intra-AS: can focus on performance
 inter-AS: policy dominates over performance

2b
2d
2c
2a
AS 2
3b
3d
3c
3a
AS 3
1b
1d
1c
1a
AS 1
X
Hot potato routing
Network Layer: 5-45
 2d learns (via iBGP) it can route to X via 2a or 2c
 hot potato routing: choose local gateway that has least intra-domain
cost (e.g., 2d chooses 2a, even though more AS hops to X): don’t worry
about inter-domain cost!
AS3,X
AS1,AS3,X
OSPF link weights
201
112
263

BGP: achieving policy via advertisements
Network Layer: 5-46
B
legend:
customer
network:
provider
network
 A advertises path Aw to B and to C
 B chooses not to advertise BAw to C!
 B gets no “revenue” for routing CBAw, since none of C, A, w are B’s customers
 C does not learn about CBAw path
 C will route CAw (not using B) to get to w
ISP only wants to route traffic to/from its customer networks (does not want
to carry transit traffic between other ISPs – a typical “real world” policy)
w A
y
C
x
A,w
A,w

BGP: achieving policy via advertisements (more)
Network Layer: 5-47
B
ISP only wants to route traffic to/from its customer networks (does not want
to carry transit traffic between other ISPs – a typical “real world” policy)
w A
y
C
x
 A,B,C are provider networks
 x,w,y are customer (of provider networks)
 x is dual-homed: attached to two networks
 policy to enforce: x does not want to route from B to C via x
 .. so x will not advertise to B a route to C
legend:
customer
network:
provider
network

 router may learn about more than one route to destination
AS, selects route based on:
1. local preference value attribute: policy decision
2. shortest AS-PATH
3. closest NEXT-HOP router: hot potato routing
4. additional criteria
BGP route selection
Network Layer: 5-48

Chapter_5_v8.0Routing Protocol for Computer network from kurose and ross

Recommended

More Related Content

Similar to Chapter_5_v8.0Routing Protocol for Computer network from kurose and ross (20)

Recently uploaded (20)

Chapter_5_v8.0Routing Protocol for Computer network from kurose and ross