Computer Networking and Applications
Routing protocol
Goal: determine “good” path (sequence of routers) thru network from source to dest.
Graph abstraction for routing algorithms:
Copyright By PowCoder代写 加微信 powcoder
• graph nodes are routers
• graph edges are physical links
– link cost: delay, $ cost, or congestion level
D1E2 “good” path:
– typically means minimum cost path
• Cost for whom?
– other definitions possible
Computer Networking and Applications
Routing Algorithm classification
Global or decentralized information?
• 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
Static or dynamic?
• routes change slowly over time Dynamic:
routes change more quickly
– periodicupdate
– in response to link cost changes
• People with backhoes!
Computer Networking and Applications
A Link-State Routing Algorithm
Dijkstra’s algorithm Notation:
• net topology, link costs known to all nodes – accomplished via link state
– allnodeshavesameinfo
• computes least cost paths from one node (“source”) to all other nodes
– gives routing table for that node • iterative:
– after k iterations, know least cost path to k dest.’s
• c(i,j): link cost from node i to j. cost infinite 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, that is next v
• N: set of nodes whose least cost path definitively known
Computer Networking and Applications
10 addwtoN
Dijsktra’s Algorithm
Initialization:
for all nodes v
if v adjacent to A then D(v) = c(A,v)
else D(v) = Loop
find w not in N such that D(w) is a minimum
15 until all nodes in N
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 */
Computer Networking and Applications
Dijkstra’s algorithm: example
Step start N 0A 1
Computer Networking and Applications
Step start N 0 A 1AD 2 ADE 3 ADEB 4 ADEBC 5 ADEBCF
Dijkstra’s algorithm: example
D(B),p(B) D(C),p(C) 2,A 5,A 2,A 4,D 2,A 3,E 3,E
D(D),p(D) D(E),p(E) D(F),p(F) 1,A 2,D 4,E 4,E 4,E
Computer Networking and Applications
Dijkstra’s algorithm, discussion
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(nlogn)
Oscillations possible:
• e.g., link cost = amount of carried traffic
D 0 0 B 0 C e
D 1+e1 B 0 C 0
… recompute routing
D 0 0 B 1 C 1+e
… recompute
D 1+e1 B 0 C 0
… recompute
Computer Networking and Applications
Dijkstra’s algorithm, discussion
Make sure all the re-computations don’t happen at the same time Unfortunately routing updated tend to happen at the same time.. Don’t use traffic as the cost in Link State
OSFP is a link state routing algo – what cost is used? (number of hops)
How can we fix it?
D 1+e1 B 0 C 0
… recompute routing
D 0 0 B 1 C 1+e
… recompute
D 1+e1 B 0 C 0
… recompute
D 0 0 B 0 C e
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com