Routing in Switched NetworksOverviewRoutingRooting or RoutingRouteing or RoutingRouting Techniques ElementsRandom RoutingFixed Routing TablesFloodingSlide 10Adaptive: Distance Vector vs Link StateDijkstra’s AlgorithmDijkstra Example (1)Dijkstra Example (2)Dijkstra Example (3)Bellman-Ford AlgorithmBellman-Ford ExampleBellman-Ford Example (Cont)ARPAnet Routing (1969-78)ARPAnet Routing AlgorithmARPAnet Routing (1979-86)ARPAnet Routing (1987+)Routing AlgorithmSummaryReading AssignmentHomeworkThank You!Solution to HomeworkSlide 2915-1©2005 Raj JainCSE473sWashington University in St. LouisRouting in Routing in Switched NetworksSwitched NetworksRaj Jain Washington UniversitySaint Louis, MO [email protected] slides are available on-line at:http://www.cse.wustl.edu/~jain/cse473-05/15-2©2005 Raj JainCSE473sWashington University in St. LouisOverviewOverviewRouting algorithmsDijkstra’s AlgorithmBellman-Ford AlgorithmARPAnet routing15-3©2005 Raj JainCSE473sWashington University in St. LouisRoutingRouting15-4©2005 Raj JainCSE473sWashington University in St. LouisRooting or RoutingRooting or RoutingRooting is what fans do at football games, what pigs do for truffles under oak trees in the Vaucluse, and what nursery workers intent on propagation do to cuttings from plants.Routing is how one creates a beveled edge on a table top or sends a corps of infantrymen into full scale, disorganized retreatRef: Piscitello and Chapin, p41315-5©2005 Raj JainCSE473sWashington University in St. LouisRouteing or RoutingRouteing or RoutingRouteing: BritishRouting: AmericanSince Oxford English Dictionary is much heavier than any other dictionary of American English, British English generally prevails in the documents produced by ISO and CCITT; wherefore, most of the international standards for routing standards use the routeing spelling.Ref: Piscitello and Chapin, p41315-6©2005 Raj JainCSE473sWashington University in St. LouisRouting Techniques ElementsRouting Techniques ElementsPerformance criterion: Hops, Distance, Speed, Delay, CostDecision time: Packet, sessionDecision place: Distributed, centralized, SourceNetwork information source: None, local, adjacent nodes, nodes along route, all nodesRouting strategy: Fixed, adaptive, random, floodingAdaptive routing update time: Continuous, periodic, topology change, major load change15-7©2005 Raj JainCSE473sWashington University in St. LouisRandom RoutingRandom RoutingNode selects one outgoing path for retransmission of incoming packetSelection can be random or round robinNo network info neededRoute is typically not least cost nor minimum hop15-8©2005 Raj JainCSE473sWashington University in St. LouisFixed Routing TablesFixed Routing TablesFrom NodeTo NodeNode 1 Node 2 Node 3Node 4Node 5 Node 615-9©2005 Raj JainCSE473sWashington University in St. LouisFloodingFloodingPacket sent by node to every neighborIncoming packets retransmitted on every link except incoming linkEach packet is uniquely numbered so duplicates can be discarded15-10©2005 Raj JainCSE473sWashington University in St. LouisFloodingFloodingUses all possible pathsUses minimum hop path Used for source routing15-11©2005 Raj JainCSE473sWashington University in St. LouisAdaptive: Distance Vector vs Link StateAdaptive: Distance Vector vs Link StateDistance Vector: Each router sends a vector of distances to its neighbors. The vector contains distances to all nodes in the network.Older method. Count to infinity problem.Link State: Each router sends a vector of distances to all nodes. The vector contains only distances to neighbors. Newer method. Used currently in internet.15-12©2005 Raj JainCSE473sWashington University in St. LouisDijkstra’s AlgorithmDijkstra’s AlgorithmGoal: Find the least cost paths from a given node to all other nodes in the networkNotation: w(i,j) = Link cost from i to j if i and j are connectedL(n) = Total path cost from s to nT = Set of nodes so far for which the least cost path is knownMethod:Initialize: T={s}, L(n) = w(s,n) for n ≠ sFind node x  T, whose L(x) is minimumUpdate L(n) = min[L(n), L(x) + w(x,n)] for all n  T15-13©2005 Raj JainCSE473sWashington University in St. LouisDijkstra Example (1)Dijkstra Example (1)15-14©2005 Raj JainCSE473sWashington University in St. LouisDijkstra Example (2)Dijkstra Example (2)15-15©2005 Raj JainCSE473sWashington University in St. LouisDijkstra Example (3)Dijkstra Example (3)T L(2) Path L(3) Path L(4) Path L(5) Path L(6) Path1 {1} 2 1-2 5 1-3 1 1-4--2 {1,4} 2 1-2 4 1-4-3 1 1-4 2 1-4-5-3 {1,2,4} 2 1-2 4 1-4-3 1 1-4 2 1-4-5-4 {1,2,4,5} 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-65 {1,2,3,4,5} 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-66 {1,2,3,4,5,6}2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-615-16©2005 Raj JainCSE473sWashington University in St. LouisBellman-Ford AlgorithmBellman-Ford AlgorithmNotation:s = Source nodew(i,j) = link cost from i to jh = Number of hops being consideredLh(n) = Cost of h-hop path from s to n with < h hopsMethod: Find all nodes 1 hop awayFind all nodes 2 hops awayFind all nodes 3 hops awayInitialize: L0(n) =  for all n  s; Lh(s) = 0 for all hFind jth node for which h+1 hops cost is minimum Lh+1(n) = minj [Lh(j) +w(j,n)]15-17©2005 Raj JainCSE473sWashington University in St. LouisBellman-Ford ExampleBellman-Ford Example15-18©2005 Raj JainCSE473sWashington University in St. LouisBellman-Ford Example (Cont)Bellman-Ford Example (Cont)h D(h2)Path D(h3)Path D(h4)Path D(h5)Path D(h6)Path0-----1 2 1-2 5 1-3 1 1-4--2 2 1-2 4 1-4-3 1 1-4 2 1-4-5 10 1-3-63 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-64 2 1-2 3 1-4-5-3 1 1-4 2 1-4-5 4 1-4-5-615-19©2005 Raj JainCSE473sWashington University in St. LouisARPAnet Routing (1969-78)ARPAnet Routing (1969-78)Features: Cost=Queue length, Each node sends a vector of costs (to all nodes) to neighbors. Distance vectorEach node computes new cost vectors based on the new info using Bellman-Ford algorithm15-20©2005 Raj JainCSE473sWashington University in St. LouisARPAnet Routing AlgorithmARPAnet Routing Algorithm123456025168Ñ23433123456023124Ñ24444203235330213122013D1Desti- nationS1D2D3D4DelayNext nodeDesti- nation DelayNext node(a) Node 1ås routing table before update(b) Delay vectors sent to node 1 from neighbor nodes(c) Node 1ås routing table after update and link costs used in update11,2 = 211,3 = 511,4 =