Transcript Document

Routing & IP Routing Protocols
1
Routing: Problem Definition
• You are a router in a packet switched network and you receive a
packet destined to some remote node
– E.g., router A below receives a packet destined to node F
• Question: How does A know where to send this packet?
– Does A send it to B? C? or D?
• Answer: Recall from our earlier discussion in IP that router A
consults a forwarding table to make this decision
• Routing Problem: How does router A build this forwarding table?
– Built by a routing algorithm (protocol): The job of the routing algorithm
is to determine the next hop router for ALL destinations in the network
Forwarding Table in A
Dest.
B
D
C
E
F
Next Hop
B
D
D
D
D
Cost
2
1
3
2
4
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
2
End-to-End Path Determination:
Routing principles
Routing protocol
Goal: determine “good” path
(sequence of routers) thru
network from source to dest.
Graph abstraction for
routing algorithms:
• graph nodes are routers
• graph edges are physical
links
– link cost: delay, $ cost, or
congestion level (amount of
traffic carried on the link)
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
• “good” path:
– typically means minimum
cost path
3
Forwarding vs Routing
• Distinction between “Forwarding” and “Routing”
– Forwarding consists of taking a packet, looking at its destination
address, consulting the forwarding table, and sending the packet
in a direction determined by the table
• Very easy once the forwarding table has been built
– Routing is the process by which the forwarding table is built
• Need a routing protocol to dynamically build and maintain the table
Forwarding table in A
5
Dest.
Next Hop
Cost
B
D
C
E
F
B
D
D
D
D
2
1
3
2
4
B
2
A
2
1
D
3
C
3
1
5
F
1
E
2
4
Routing Algorithm classification
Global or decentralized information?
Global:
• all routers have complete topology, link cost info
• “link state” algorithms
Decentralized:
• router knows physically-connected neighbors, link costs
to neighbors
• iterative process of computation, exchange of info with
neighbors
• “distance vector” algorithms
5
Link-State Algorithms: General Idea
• Have each router build the complete topology of the
network
• Once the complete topology is built, have each router
run an algorithm to compute the shortest path from
itself to all other routers (nodes) in the network
2 Issues
• How does a router build the
complete topology of the
network?
• How does a router compute the
shortest path to all other nodes
in the network using this
topology information?
– Dijkstra’s Shortest Path Algorithm
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
6
Building the Network Topology
• At the heart of a link state algorithm is the discovery
of a node’s links’ states
– Each node is assumed to capable of finding out the state of
the link to its neighbors (up or down) and the cost of each link
– Each node creates an update packet, also called a link-state
packet (LSP) and periodically sends this information to all of
its neighbors
– Node’s neighbors send the packet to their neighbors and so on
until the LSP is received by all nodes in the network
LSP Contents
• ID of the node -- A
• List of neighbors and the cost to
each neighbor – (B, 2), (C, 5), (D, 1)
• A sequence number
• A time-to-live (TTL)
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
7
Reliable Flooding
• Reliable flooding is the process of making sure that all nodes get a
copy of LSP from all other nodes in the network
• When a node X receives a copy of an LSP that originated at some
other node Y, it checks to see if it has already stored a copy of an
LSP from Y.
• If not, it stores the LSP.
• If it already has a copy, it compares the SeqNos; if the new LSP
has a larger SeqNo, it is assumed to be more recent, and the last
LSP is stored replacing the old one. Otherwise the new LSP is
discarded
• The new LSP is then forwarded on
all neighbors of X except the
neighbor from which the LSP was
just received
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
8
Computing the Shortest Path:
Dijkstra’s Algorithm
Notation:
• Cost(i,j): link cost from node i to j.
– Cost(A, B) = 2
– Cost(A, C) = 5
– Cost(A, F) = infinity
5
• Distance(v): current value of cost of
path from source to destination V
– Distance(D) = 1
• Pred(v): predecessor node of v along
path from source to v
– Pred(D) = A
2
A
B
2
1
D
3
C
3
1
5
F
1
2
E
• N: set of nodes whose least cost path
definitively known
9
Dijsktra’s Algorithm – where A is
the source node
1 Initialization:
2 N = {A}
3 for all nodes v
4
if v adjacent to A
5
then Distance (v) = cost(A,v)
6
else Distance (v) = infinity
7
8 Loop
9 find w not in N such that Distance(w) is a minimum
10 add w to N
11 update Distance(v) for all v adjacent to w and not in N:
12
Distance(v) = min( Distance(v), Distance(w) + cost(w,v) )
13 /* new distance to v is either old distance to v or known
14 shortest path distance to w plus cost from w to v */
15 until all nodes in N
10
Dijkstra’s algorithm: example
Step
0
1
2
3
4
5
N
A
AD
ADE
ADEB
ADEBC
ADEBCF
D(B),p(B)
2,A
2,A
2,A
D(C),p(C) D(D),p(D) D(E),p(E)
1,A
5,A
infinity
4,D
2,D
3,E
3,E
D(F),p(F)
infinity
infinity
4,E
4,E
4,E
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
Algorithm complexity: n nodes
• each iteration: need to check all nodes, w, not in N
• n*(n+1)/2 comparisons: O(n2) – O(nlogn) algorithm possible
11
Distance Vector Algos: General Idea
• We do NOT need to know the complete topology of
the network to build the forwarding table!
• If a node X simply tells its neighbor Y the cost of
reaching another node Z via itself (X), then
– neighbor Y can compute the cost of reaching Z via X by
simply adding the cost of reaching X from Y and the cost of
reaching Z from X, which was advertised by X
Example
• If D tells A that it can reach E with a
cost of 1, then A knows it can reach E
via D with a cost of 1+1 = 2
• If D tells A that it can reach F with a
cost of 3, then A knows it can reach F
via D with a cost of 1+3 = 4
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
12
Distance Vector Routing Algorithm
• Each node tells its
neighbors the cost of
reaching every other node
via itself
• A node computes its cost
of reaching a destination
via each of its neighbors
and picks the best one
distributed:
• each node communicates
only with directlyattached neighbors
iterative:
• continues until no nodes
exchange new information
• self-terminating: no
“signal” to stop
X
D (Y,Z)
distance from X to
= Y via Z as next hop
Y
= c(X,Z) + D (Z)
X
D (Y)
X
= min {D (Y,w)}
w
X C(X,Y)
Y
D (Z)
Y
T
Z
T
D (Z)
13
Distance Table Structure
Distance Table Data Structure
• each node has its own distance table
• row for each possible destination
• column for each directly-attached
neighbor to node
• example: in node X, for dest. Y via
neighbor Z:
7
A
B
1
C
2
8
1
E
2
cost to destination via
DE ()
A
B
D
A
1
14
5
B
7
8
5
C
6
9
4
D
4
11
2
D
14
Distance Table gives Forwarding Table
E
cost to destination via
Outgoing link
D ()
A
B
D
A
1
14
5
A
A,1
B
7
8
5
B
D,5
C
6
9
4
C
D,4
D
4
11
2
D
D,4
Distance Table
to use, cost
Forwarding (Routing) Table
15
Distance Vector Routing: overview
Each node:
Initialize the Distance Table Structure
wait for (msg from neighbor)
recompute distance table
if least cost path to any dest
has changed, notify
neighbors
16
Initialization
At all nodes, X:
1 Initialization:
2 for all adjacent nodes v:
3
D X(*,v) = infinity
/* the * operator means "for all rows" */
4
D X(v,v) = c(X,v)
5 for all destinations, y
6
send DX(y) to each neighbor /* Cost of reaching Y via X */
17
Distance Vector Algorithm: Example
This column
shows the
Init. results
X
2
Y
7
1
Init
Info
sent
We need to
adjust
values
if necessary
Z
18
Distance Vector Algorithm (cont.):
8 loop
9 wait (until I receive update from neighbor V)
10 if (update received from neighbor V wrt destination Y)
11 /* shortest path from V to some Y has changed */
12 /* V has sent a new value for its DV(Y) */
13 /* call this received new value is "newval" */
14 for the single destination Y: D X(Y,V) = c(X,V) + newval
15
X
16 if we have a new D (Y) for any destination Y
17
send new value of D X(Y) to all neighbors
18
19 forever
19
Distance Vector Algorithm: Example
Initial values
X
2
Y
7
1
Z
info
sent
Adjusted
new value
X
Y
X
Z
D (Z,Y) = c(X,Y) + D (Z)
= 2+1 = 3
D (Y,Z) = c(X,Z) + D (Y)
= 7+1 = 8
20
Distance Vector Algorithm: Example
This column
Shows the
Init. results
X
2
Y
7
1
Init
Info
sent
Adjusted
new
values
New
Info
sent
Adjust
values
if
necessary
Z
21
Hierarchical Routing
Our routing study thus far assumed
• all routers to be “identical” and the network to be “flat”
• 2 Problems exist with such a model:
1. scale: with 200 million destinations:
– can’t store all destinations in routing tables!
– routing table exchange would swamp links!
2. administrative autonomy
– Can’t assume that a network with the scale of Internet will be
administered by a single authority
• Solution?
– Internet is NOT flat, but is a network of networks
– each network admin controls routing in its own network – next
– http://www.ilkertemir.com/backbone-map/
• Turkey’s past and current Internet backbone map
22
Hierarchical Routing
C.b
a
C
B.a
A.a
b
A.c
d
A
a
b
• aggregate routers into
regions, “autonomous
systems” (AS)
• routers in same AS run same
routing protocol
– “intra-AS” routing protocol
– routers in different AS can
run different intra-AS
routing protocol
a
c
B
b
c
gateway routers
• special routers in AS
• run intra-AS routing protocol
with all other routers in AS
• also responsible for routing to
destinations outside AS
– run inter-AS routing
protocol with other
23
gateway routers
Intra-AS Routing
• Also known as Interior Gateway Protocols (IGP)
• Most common Intra-AS routing protocols:
– OSPF: Open Shortest Path First
– RIP: Routing Information Protocol
– IGRP: Interior Gateway Routing Protocol (Cisco
proprietary)
24
OSPF (Open Shortest Path First)
• “open”: publicly available
• Uses Link State algorithm
– LS advertisement dissemination to entire AS via flooding
– Topology map at each node
– Route computation using Dijkstra’s algorithm
– Carried in OSPF messages directly over IP
• OSPF has its own network layer protocol number like IP!
25
RIP (Routing Information Protocol)
• Distance vector algorithm
• Included in BSD-UNIX Distribution in 1982
• Distance metric: # of hops (max = 15 hops)
– 16 is the infinity to eliminate routing loops
• Distance vectors: exchanged among neighbors every
30 sec via Response Message (also called
advertisement)
• Each advertisement: list of up to 25 destination nets
within AS
– If more destinations, send multiple advertisements
26
RIP: Example
z
w
A
x
D
B
y
C
Destination Network
w
y
z
x
….
Next Router
Num. of hops to dest.
….
....
A
B
B
--
2
2
7
1
Routing table in D
27
RIP: Example
Dest
w
x
z
….
Next
C
…
w
hops
4
...
A
Advertisement
from A to D
z
x
Destination Network
w
y
z
x
….
D
B
C
y
Next Router
Num. of hops to dest.
….
....
A
B
B A
--
Routing table in D
2
2
7 5
1
28
RIP Table processing
• RIP routing tables managed by application-level
process called route-d (daemon)
• advertisements sent in UDP packets, periodically
repeated
routed
routed
Transprt
(UDP)
network
(IP)
link
physical
Transprt
(UDP)
forwarding
table
forwarding
table
network
(IP)
link
physical
29
Inter-AS routing in the Internet: BGP
R4
R5
R3
BGP
AS1
AS2
(RIP intra-AS
routing)
(OSPF
intra-AS
routing)
BGP
R1
R2
AS3
(OSPF intra-AS
routing)
• Each BGP router communicates only with its
neighbors
Figure 4.5.2-new2: BGP use for inter-domain routing
– R1 with R2, R3 with R4
– Global info about routes to destination networks
propagates in an AS-by-AS manner via the exchange
of BGP messages
30
Why different Intra- and Inter-AS routing ?
Policy:
• Intra-AS: single admin, so no policy decisions
needed
• Inter-AS: admin wants control over how its
traffic routed, who routes through its net.
Performance:
• Intra-AS: can focus on performance
• Inter-AS: policy may dominate over
performance
31