Lecture 20 Routing in data Networks Eytan Modiano
Lecture 20 Routing in Data Networks Eytan Modiano Eytan Modiano Slide 1
Routing Must choose routes for various origin destination pairs (o/d pairs) or for various sessions Datagram routing: route chosen on a packet by packet basis Using datagram routing is an easy way to split paths Virtual circuit routing: route chosen a session by session basis Static routing: route chosen in a prearranged way based on O/D pairs
Routing • Must choose routes for various origin destination pairs (O/D pairs) or for various sessions – Datagram routing: route chosen on a packet by packet basis Using datagram routing is an easy way to split paths – Virtual circuit routing: route chosen a session by session basis – Static routing: route chosen in a prearranged way based on O/D pairs Eytan Modiano Slide 2
Routing is a global problem 5 units 5 units 10 15 units Either session Both sessions alone is best must split their routed through traffic between center path, but OAll links two paths both cannot oAll links have go throug have capacity center capacity 10 units o 10 units Static routing is not desirable Datagam routing is a natural way to split the traffic How?
Routing is a global problem 5 units 5 units All links have capacity 10 units Either session alone is best routed through center path, but both cannot go through center. • Static routing is not desirable All links have capacity 10 units 10 units 15 units Both sessions must split their traffic between two paths. • Datagam routing is a natural way to split the traffic – How? Eytan Modiano Slide 3
Shortest Path routing Each link has a cost that reflects The length of the link Delay on the link Congestion ss cost Cost may change with time The length of the route is the sum of the costs along the route The shortest path is the path with minimum length Shortest Path algorithms Bellman-Ford: centralized and distributed versions Dijkstra’ s algorithm Many others
Shortest Path routing • Each link has a cost that reflects – The length of the link – Delay on the link – Congestion – $$ cost • Cost may change with time • The length of the route is the sum of the costs along the route • The shortest path is the path with minimum length • Shortest Path algorithms – Bellman-Ford: centralized and distributed versions – Dijkstra’s algorithm – Many others Eytan Modiano Slide 4
Directed graphs(digraphs) A directed graph(digraph)G=(N,A is a finite nonempty set of nodes N and a set of ordered node pairs a called directed arcs. N={1,2,34} A={(1,2),(2,1),(1,4) (4,2),(4,3),(3,2)} Directed walk:(4, 2, 1, 4, 3, 2) Directed path:(4, 2, 1) Directed cycle: (4, 2, 1, 4) Data networks are best represented with digraphs, although ty pically links tend to be bi-directional (cost may differ in each direction) For simplicity we will use bi-directional links of equal costs in our examples
Directed graphs (digraphs) • A directed graph (digraph) G = (N,A) is a finite nonempty set of nodes N and a set of ordered node pairs A called directed arcs. 1 2 3 4 N = {1,2,3,4} A = {(1,2), (2,1),(1,4), (4,2), (4,3),(3,2)} • Directed walk: (4,2,1,4,3,2) • Directed path: (4,2,1) • Directed cycle: (4,2,1,4) • Data networks are best represented with digraphs, although typically links tend to be bi-directional (cost may differ in each direction) – For simplicity we will u se bi-directional links of equ al costs in our examples Eytan Modiano Slide 5
Bellman Ford algorithm Finds the shortest paths, from a given source node, say node 1, to all other nodes General idea: First find the shortest single arc path, Then the shortest path of at most two arcs, etc Let dij=o if (i,j)is not an arc Let Di()be the shortest distance from 1 to i using at most h arcs D()=d1i;萨1D1(1)=0 Di(h+1)=min 0 [Dj(h)+ dj];i1 D1(h +1)=0 If all weights are positive, algorithm terminates in N-1 steps
Bellman Ford algorithm • Finds the shortest paths, from a given source node, say node 1, to all other nodes. • General idea: – First find the shortest single arc path, – Then the shortest path of at most two arcs, etc. – Let dij= ∞ if (i,j) is not an arc. • Let Di(h) be the shortest distance fro m 1 to i using at most h arcs. – Di(1) = d1i ; i≠1 D1(1) = 0 – Di(h+1) = min {j} [Dj(h) + dji] ;i ≠1 D1(h +1) = 0 • If all weights are positive, algorithm terminates in N-1 steps. Eytan Modiano Slide 6
Bellman Ford -example
Bellman Ford - example Eytan Modiano Slide 7
Distributed Bellman Ford Link costs may change over time Changes in traffic conditions Link failures Mobility Each node maintains its own routing table Need to update table regularly to reflect changes in network Let di be the shortest distance from node i to the destination Di=min 0[Dj+ di: update equation Each node regularly updates the values of Di using the update equation Each node maintains the values of dif to its neighbors, as well as values of Dj received from its neighbors Uses those to compute Di and send new value of Di to its neighbors If no changes occur in the network, algorithm will converge to shortest paths in no more than n steps
Eytan Modiano Slide 8 Distributed Bellman Ford • Link costs may change over time – Changes in traffic conditions – Link failures – Mobility • Each node maintains its own routing table – Need to update table regularly to reflect changes in network • Let Di be the shortest distance from node i to the destination – Di = min {j} [Dj + dij] : update equation • Each node (i) regularly updates the values of Di using the update equation – Each node maintains the values of dij to its neighbors, as well as values of Dj received from its neighbors – Uses those to compute Di and send new value of Di to its neighbors – If no changes occur in the network, algorithm will converge to shortest paths in no more than N steps
Slow reaction to link failures Start with d3=1 and d2=100 After one iteration node 2 receives d3=1 and D2=min[1+1,100=2 100 In practice, link lengths occasionally change Suppose link between 3 and fails(Le, d31=infinity) Node 3 will update D3= d32+D2= 3 In the next step node 2 will update: D2=d23+D3=4 It will take nearly 100 iterations before node 2 converges on the correct route to node 1 Possible solutions: Propagate route information as well Wait before rerouting along a path with increasing cost Node next to failed link should announce d=infinity for some time to prevent loops
Eytan Modiano Slide 9 Slow reaction to link failures • Start with D3=1 and D2=100 – After one iteration node 2 receives D3=1 and D2 = min [1+1, 100] = 2 • In practice, link lengths occasionally change – Suppose link between 3 and 1fails (I.e., d31=infinity) – Node 3 will update D3 = d32 + D2 = 3 – In the next step node 2 will update: D2 = d23+D3 = 4 – It will take nearly 100 iterations before node 2 converges on the correct route to node 1 • Possible solutions: – Propagate route information as well – Wait before rerouting along a path with increasing cost Node next to failed link should announce D=infinity for some time to prevent loops 3 2 1 1 1 1 100
Instability =3 DA=6 =6 1+ D6=6 D7=5+2 B=3+ Assume d is equal to the flow on( Note that D6=D5+0 As routes change due to traffic conditions, they affect the Loadings on the links, hence routes may oscillate
Eytan Modiano Slide 10 Instability 1 1 1 1 1 1 ε Destination ε 1+ 2+ 3+ ε ε ε 3 2 1 2 3 4 1 5 6 7 8 Assume d is equal to the flow on (i,j) Note that D ij D = 3 D = 5 D = 6 D = 6 D = 6 D = 5+2 D = 3+ 2 3 4 5 6 7 8 ε ε 6 5 = D + 0 As routes change due to traffic conditions, they affect the Loadings on the links, hence routes may oscillate