Computer Networking and Applications
Distance Vector Routing Algorithm
iterative:
• continues until no nodes exchange info.
Copyright By PowCoder代写 加微信 powcoder
• self-terminating: no “signal” to stop
asynchronous:
• nodes need not exchange info/iterate in lock step!
distributed:
• each node communicates only with directly- attached neighbors
Distance Table data structure
• each node has its own
– row for each possible destination
– column for each directly-attached neighbor to node
• example: in node X, for dest. Y via neighbor Z:
distance from X to Y, via Z as next hop
c(X,Z) + minw {DZ(Y,w)}
Computer Networking and Applications
Distance Table: example
cost to destination via
c(E,D) + minW{DD(C,w)} = 2+2 =4
D() A B C D
= c(E,D) + minW{DD(A,w)}
=2+3=5 loop!
c(E,B) + minW{DB(A,w)}
Computer Networking and Applications
c(E,D) + minW{DD(C,w)} = 2+2 =4
Distance Table: example
Cost of going to C via D
BD 14 5 85 94 11 2
Cost of going to D via A
cost to destination via
D() A A1 B7 C6 D4
= c(E,D) + minW{DD(A,w)} = 2+3 =5 loop!
c(E,B) + minW{DB(A,w)}
Computer Networking and Applications
Distance Table: example
cost to destination via
D() A B C D
Computer Networking and Applications
Distance table gives routing table
E cost to destination via D() A B D
A1 B7 C6 D4
Distance table
Outgoing link to use, cost
A A,1 B D,5 C D,4 D D,2
Routing table
14 5 85 94
Computer Networking and Applications
Iterative, asynchronous: each local iteration caused by:
• local link cost change
• message from neighbor: its least
cost path change from neighbor
Distributed:
• each node notifies neighbors only when its least cost path to
any destination changes
– neighbors then notify their neighbors if necessary
Each node:
wait for (change in local link cost or msg from neighbor)
recompute distance table
if least cost path to any dest has
changed, notify neighbors
Distance Vector Routing: overview
Computer Networking and Applications
Distance Vector Algorithm: example
D (Z,Y) = c(X,Y) + min {D (Z,w)}
= 2+1 = 3 w
D (Y,Z) = c(X,Z) + min {D (Y,w)}
= 7+1 = 8 w
Computer Networking and Applications
Distance Vector Algorithm: example
Computer Networking and Applications
Link cost changes
Link cost changes:
• node detects local link cost change
• updates distance table
• if cost change in least cost path, notify neighbors
“good news travels fast”
algorithm terminates
Computer Networking and Applications
Link cost changes
Link cost changes:
• good news travels fast
• bad news travels slow – “count to infinity” problem!
algorithm continues on!
Computer Networking and Applications
Link cost changes
Link cost changes:
• good news travels fast
• bad news travels slow – “count to infinity” problem!
• When will it STOP?
algorithm continues on!
Computer Networking and Applications
DV: 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?
algorithm terminates
Computer Networking and Applications
Comparison of LS and DV algorithms
Message complexity
• LS: Each node needs to know the cost of each link ( n nodes, E links) O(nE) messages
• DV: exchange between neighbors only – convergencetimevaries
Speed of Convergence
• LS: O(n**2) algorithm requires O(nE)
– may have oscillations
• DV: convergence time varies
– mayberoutingloops
– count-to-infinityproblem
Robustness: what happens if router malfunctions?
– node can advertise incorrect link cost
– each node computes only its own table
– DV node can advertise incorrect path cost
– each node’s table used by others
• error propagate thru network
Computer Networking and Applications
Making routing scalable
our routing study thus far – idealized all routers identical
network “flat”
… not true in practice
scale: with billions of destinations:
• can’t store all destinations 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
Network Layer: Control Plane
Computer Networking and Applications
Internet approach to scalable routing
aggregate routers into regions known as “autonomous systems” (AS) (a.k.a.“domains”)
intra-AS routing
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 “edge” of its own AS, has link(s) to router(s) in other AS’es
inter-AS routing
• routing among AS’es
• gateways perform inter- domain routing (as well as intra-domain routing)
Computer Networking and Applications
Intra-AS and Inter-AS routing
•perform inter-AS routing amongst themselves
b •perform intra-AS routers with other routers in their AS
network layer link layer
physical layer
inter-AS, intra-AS routing in gateway A.c
Computer Networking and Applications
Intra-AS and Inter-AS routing
Inter-AS routing
between B.a A and B
Host a b A.c a c h2
Host d h1 A
c Intra-AS routing within AS B
Intra-AS routing within AS A
• Intra-AS protocols include RIP (DV), EIGRP (Hybrid) and OSPF (LSA).
• Inter-AS protocols include BGP (Path Vector Protocol). BGP lets every AS in the Internet know about the subnets in YOUR AS.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com