Raj JainThe Ohio State University5-1Routing AlgorithmsRouting AlgorithmsRaj JainProfessor of CISThe Ohio State UniversityColumbus, OH [email protected] presentation is available on-line at:http://www.cis.ohio-state.edu/~jain/cis677-98/Raj JainThe Ohio State University5-2❑ Routing algorithms❑ Dykstra’s Algorithm❑ Bellman Ford Algorithm❑ ARPAnet routingOverviewRaj JainThe Ohio State University5-3RoutingRoutingFig 9.5Raj JainThe Ohio State University5-4Rooting or RoutingRooting or Routing❑ Rooting is what fans do at football games, what picsdo for truffles under oak trees in the Vaucluse, andwhat nursery workers intent on propagation do tocuttings from plants.❑ Routing is how one creates a beveled edge on a tabletop or sends a corps of infanctrymen into full scale,disorganized retreatRef: Piscitello and Chapin, p413Raj JainThe Ohio State University5-5RouteingRouteing or Routing or Routing❑ Routeing: British❑ Routing: American❑ Since Oxford English Dictionary is much heavier thanany other dictionary of American English, BritishEnglish generally prevalis in the documents producedby ISO and CCITT; wherefore, most of theinternational standards for routing standards use therouteing spelling.Ref: Piscitello and Chapin, p413Raj JainThe Ohio State University5-6Routing 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, adjacentnodes, nodes along route, all nodes❑ Routing strategy: Fixed, adaptive, random, flooding❑ Adaptive routing update time: Continuous, periodic,topology change, major load changeRaj JainThe Ohio State University5-7Distance Vector vs Link StateDistance Vector vs Link State❑ Distance Vector: Each router sends a vector ofdistances to its neighbors. The vector containsdistances to all nodes in the network.Older method. Count to infinity problem.❑ Link State: Each router sends a vector of distances toall nodes. The vector contains only distances toneighbors. Newer method. Used currently in internet.Raj JainThe Ohio State University5-8Dijkstra’sDijkstra’s Algorithm Algorithm❑ Goal: Find the least cost paths from a given node to allother nodes in the network❑ Notation:dij = Link cost from i to j if i and j are connectedDn = Total path cost from s to nM = Set of nodes so far for which the least cost path isknown❑ Method:❑ Initialize: M={s}, Dn = dsn❑ Find node w ∉ M, whose Dn is minimum❑ Update DnRaj JainThe Ohio State University5-9ExampleExampleRaj JainThe Ohio State University5-10Example (Cont)Example (Cont)Table 9.4aM D2 Path D3 Path D4 Path D5 Path D6 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-6Raj JainThe Ohio State University5-11BellmanBellman-Ford Algorithm-Ford Algorithm❑ Notation:h = Number of hops being consideredD(h)n = Cost of h-hop path from s to n❑ Method: Find all nodes 1 hop awayFind all nodes 2 hops awayFind all nodes 3 hops away❑ Initialize: D(h)n = ∞ for all n ≠ s; D(h)n = 0 for all h❑ Find jth node for which h+1 hops cost is minimum D(h+1)n = minj [D(h)j +djn]Raj JainThe Ohio State University5-12ExampleExampleFig 9.23bRaj JainThe Ohio State University5-13Example (Cont)Example (Cont)Table 9.4bh 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-6Raj JainThe Ohio State University5-14FloodingFloodingFig 8.11bRaj JainThe Ohio State University5-15FloodingFlooding12 356412 356412 3564Raj JainThe Ohio State University5-16ARPAnet Routing (1969-78)ARPAnet Routing (1969-78)❑ Features: Cost=Queue length,❑ Each node sends a vector of costs (to all nodes) toneighbors. Distance vector❑ Each node computes new cost vectors based on thenew info using Bellman-Ford algorithmRaj JainThe Ohio State University5-17ARPAnet 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 = 1Fig 9.9Raj JainThe Ohio State University5-18ARPAnet Routing (1979-86)ARPAnet Routing (1979-86)❑ Problem with earlier algorithm: Thrashing (packetswent to areas of low queue length rather than thedestination), Speed not considered❑ Solution: Cost=Measured delay over 10 seconds❑ Each node floods a vector of cost to neighbors.Link-state. Converges faster after topology changes.❑ Each node computes new cost vectors based on thenew info using Dijkstra’s algorithmFig 9.10Raj JainThe Ohio State University5-19ARPAnet Routing (1987+)ARPAnet Routing (1987+)❑ Problem with 2nd Method: Correlation betweendelays reported and those experienced later : High inlight loads, low during heavy loads⇒ Oscillations under heavy loads ⇒ Unused capacity at some links, over-utilization ofothers, More variance in delay more frequent updatesMore overheadFig 9.11Raj JainThe Ohio State University5-20Routing AlgorithmRouting Algorithm❑ Delay is averanged over 10 s❑ Link utilization = r = 2(s-t)/(s-2t)where t=measured delay,s=service time per packet (600 bit times)❑ Exponentially weighted average utilizationU(n+1) = α U(n)+(1-α)r(n+1)=0.5 U(n)+0.5 r(n+1) with α = 0.5❑ Link cost = fn(U)Fig 9.12Raj JainThe Ohio State University5-21SummarySummary❑ Distance Vector and Link State❑ Routing: Least-cost, Flooding, Adaptive❑ Dijkstra’s and Bellman-Ford algorithms❑