程序代写代做代考 algorithm Computer Systems

Computer Systems
Week 10b – Network Layer Routing Algorithms
Based on material and slides from
Computer Networking: A Top Down
Approach, 7th Edition – Chapter 5 Jim Kurose, Keith Ross Pearson/Addison Wesley

Lecture Objective
The objective of this lecture is to understand the conceptual aspects of network layer routing algorithms
Slide# 2 of 33

Lecture Outline
 Routing vs. Forwarding – Recap
 Graph Abstraction
 Routing Algorithms – Classification
 Link State Routing – Dijkstra’s Algorithm
 Distance Vector Routing – Bellman-Ford Algorithm  Hierarchical Routing
 Summary
Slide# 3 of 33

Recap – Network Layers
Slide# 4 of 33

Interplay between Routing & Forwarding
routing algorithm determines end-end-path through network
forwarding table determines local forwarding at this router
Slide# 5 of 33

Graph Abstraction
graph: G = (N,E)
N = set of routers = { u, v, w, x, y, z }
E = set of links ={ (u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
Aside: graph abstraction is useful in other network contexts, e.g., P2P, where N is set of peers and E is set of TCP connections
Slide# 6 of 33

Graph Abstraction
cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
c(x,x’) = cost of link (x,x’)
e.g., c(w,z) = 5
cost could always be 1, or inversely related to bandwidth, or inversely related to congestion
Key Question: What is the least-cost path between u and z ? Routing Algorithm: Algorithm that finds that least cost path
Slide# 7 of 33

Routing Algorithm Classification
Q: 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
Q: static or dynamic?
Static:
 Routes change slowly over time
Dynamic:
 Routes change more quickly
 periodic update
 in response to link cost changes
Slide# 8 of 33

A Link-State Algorithm
Dijkstra’s Algorithm
 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,y): link cost from node x to y; = ∞ if not direct neighbors
 D(v): current value of cost of path from source to dest. v
 p(v): predecessor node along path from source to v
 N’: set of nodes whose least cost path definitively known
Slide# 9 of 33

Dijkstra’s Algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Initialization: N’={u}
for all nodes v
if v adjacent to u then D(v) = c(u,v)
else D(v) = ∞
Loop
find w not in N’ such that D(w) is a minimum addwtoN’
update D(v) for all v adjacent to w and not in N’ : D(v) = min( D(v), D(w) + c(w,v) )
/* new cost to v is either old cost to v or known shortest path cost to w plus cost from w to v */
until all nodes in N’
Slide# 10 of 33

Dijkstra’s Algorithm – Example
D(v) D(w) D(x) D(y) D(z) Step N’ p(v) p(w) p(x) p(y) p(z)
0 u 7,u 3,u 5,u ∞ ∞ 1uw6,w 5,u11,w∞
2 uwx 6,w 3 uwxv
11,w 14,x
x
10,v 14,x 12,y
9
4 uwxvy
5uwxvyz 547
Notes:
3
8
w y2z
3
4
 construct shortest path tree by tracing predecessor nodes
 ties can exist (can be broken 7 arbitrarily)
u
v
Slide# 11 of 33

Dijkstra’s Algorithm – Another Example
Step N’ 0 u 1 ux 2 uxy 3 uxyv 4 uxyvw 5 uxyvwz
D(v),p(v) D(w),p(w) 2,u 5,u 2,u 4,x 2,u 3,y 3,y
D(x),p(x) D(y),p(y) D(z),p(z) 1,u ∞ ∞
2,x

4,y 4,y 4,y
Slide# 12 of 33

Dijkstra’s Algorithm – Least Cost Path and Forwarding Table for Node u
Resulting shortest-path tree from u: Resulting forwarding table in u:
Slide# 13 of 33

Dijkstra’s Algorithm – Complexity
Algorithm Complexity: n nodes
 Each iteration: need to check all nodes, w, not in N’
 n(n+1)/2 comparisons: O(n2)
 More efficient implementations possible: O(n logn)
Slide# 14 of 33

Dijkstra’s Algorithm – Oscillations
Support link cost equals amount of carried traffic.
Given these costs, find new routing…. resulting in new costs
Slide# 15 of 33

Distance-Vector (DV) Routing Algorithm
Bellman-Ford equation:
let
dx(y) := cost of least-cost path from x to y then
dx(y) = minv {c(x,v) + dv(y) }
cost from neighbor v to destination y
cost to neighbor v
min taken over all neighbors v of x
Slide# 16 of 33

Bellman-Ford – Example
Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
B-F equation gives:
du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z),
c(u,w) + dw(z) }
= min {2 + 5, 1 + 3,
5 + 3} = 4
Node achieving minimum is next-hop in shortest path, used in forwarding table.
Slide# 17 of 33

Distance Vector Algorithm
 Dx(y) = estimate of least cost from x to y
 x maintains distance vector Dx = [Dx(y): y є N ]
Node x:
 knows cost to each neighbor v: c(x,v)
 maintains its neighbors’ distance vectors. For each neighbor v, x maintains:
Dv = [Dv(y): y є N ]

Slide# 18 of 33

Distance Vector Algorithm
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:
Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N
 Under minor, natural conditions, the estimate Dx(y) converge to the actual least cost dx(y)
Slide# 19 of 33

Distance Vector Algorithm
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
if DV to any dest has changed, notify neighbors
Slide# 20 of 33

Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
node x
table x y z
x027 x023
yz ∞ ∞ ∞ yz ∞∞∞
cost to
cost to
x y z
node y
table x y z
201 710
cost to
2 y 1 xy∞∞∞ x7z
z
201 ∞∞∞
node z table
x∞∞∞
y z
cost to
xyz
∞∞∞ 710
time
Slide# 21 of 33
from from
from
from

Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
cost to
x y z
x027 x023 x023
y∞∞∞ y201 y201 z∞∞∞ z710 z310
node y cost to cost to cost to table x y z x y z x y z
x∞∞∞ x027 x023 y201 y201 y201 z∞∞∞ z710 z310
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
node x cost to table x y z
cost to
xyz
2 y 1
x z
7
node z table
x∞∞∞ x027 x023
y∞∞∞ y201 y201
z710 z310 z310 time
cost to
cost to cost to
xyz
xyz xyz
Slide# 22 of 33
from from
from
from from from
from
from from

Distance Vector – Link Cost Changes
Link Cost Changes:
 Node detects local link cost change  Updates routing info, recalculates
distance vector
1
4y1
x
 If DV changes, notify neighbors
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.
“Good news travels fast!”
What would happen if the link cost increases?
z 50
Slide# 23 of 33

Comparison of LS and DV Algorithms
Message Complexity
Robustness: what happens if router malfunctions?
LS:
 node can advertise incorrect link cost
 each node computes only its own table
DV:
 DV node can advertise incorrect path cost
► each node’s table used by others
► error propagate through the network
 LS: with N nodes, E links, O(NE) messages sent
 DV: exchange between neighbors only
 convergence time varies Speed of Convergence
 LS: O(N2) algorithm requires O(NE) messages
 may have oscillations
 DV: convergence time varies
 may be routing loops
 count-to-infinity problem
Slide# 24 of 33

Hierarchical Routing
Our routing study thus far – idealization  All routers identical
 Network is “flat” … not true in practice
Scale: with 600 million destinations:
 Can’t store all dest’s in routing tables!
 Routing table exchange would swamp links!
Administrative Autonomy
 Internet = network of networks
 Each network admin may want to control routing in its own network
Slide# 25 of 33

Hierarchical Routing
 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
Gateway Router:
 At “edge” of its own AS
 Has link to router in another AS
Slide# 26 of 33

Interconnected ASes
 Forwarding table configured by both intra- and inter-AS routing algorithm
 intra-AS sets entries for internal destinations
 inter-AS & intra-AS sets entries for external destinations
Slide# 27 of 33

Inter-AS Tasks
 Suppose a router (1d) in AS1 receives datagram destined outside of AS1:
 router should forward packet to gateway router, but which one?
3c
3b 3a AS3
AS1 must:
1) Learn which dests are reachable through AS2, which through AS3
2) Propagate this reachability info to all routers in AS1
Job of inter-AS routing!
1c 1a
2c
2a
other networks
other networks
1b AS1
2b AS2
1d
Slide# 28 of 33

Example: Setting Forwarding Table in Router 1d
 Suppose AS1 learns (via inter-AS protocol) that the subnet x is reachable via AS3 (gateway 1c), but not via AS2
 inter-AS protocol propagates reachability info to all internal routers  Router 1d determines from intra-AS routing info that its
interface I is on the least cost path to 1c  installs forwarding table entry (x,I)
3c
3b 3a AS3
x
1c 1a
2c
2a
other networks
other networks
1b AS1
2b AS2
1d
Slide# 29 of 33

Example: Choosing Among Multiple ASes
 Now suppose AS1 learns from inter-AS protocol that subnet x is reachable from AS3 and from AS2.
 To configure forwarding table, router 1d must determine which gateway it should forward packets towards for dest x
 This is also job of inter-AS routing protocol!
3c
3b 3a AS3
x
1c 1a
2c
2a
other networks
other networks
1b AS1
2b AS2
1d
?
Slide# 30 of 33

……

Example: Choosing Among Multiple ASes
 Now suppose AS1 learns from inter-AS protocol that subnet x is reachable from AS3 and from AS2.
 To configure forwarding table, router 1d must determine which gateway it should forward packets towards for dest x
 This is also job of inter-AS routing protocol!
 Hot Potato Routing: send packet towards closest of two routers.
Slide# 31 of 33

Summary
In this lecture, we have seen:
 The two main classes of routing algorithms i.e. Link State and Distance Vector routing.
 Dijkstra’s Algorithm is a Link State algorithm.
 Bellman-Ford as a Distance Vector algorithm.
 The importance of Hierarchical Routing.
Slide# 32 of 33

References / Links
 Chapter #5: The Network Layer: Control Plane,
Computer Networking: A Top-Down Approach (7th edition) by Kurose & Ross
Slide# 33 of 33