Packet SwitchingSlide 2RoutingRooting or RoutingRouteing or RoutingSlide 6Slide 7Routing Techniques ElementsDistance Vector vs Link StateDijkstra’s AlgorithmExampleExample (Cont)Dijkstra's Routing AlgorithmDijkstra's routing algorithmBellman-Ford AlgorithmSlide 16Slide 17FloodingSlide 19ARPAnet Routing (1969-78)ARPAnet Routing AlgorithmARPAnet Routing (1979-86)ARPAnet Routing (1987+)Routing AlgorithmSummaryHomeworkRaj JainThe Ohio State University5-1Packet SwitchingPacket SwitchingRaj JainProfessor of CIS The Ohio State UniversityColumbus, OH [email protected] presentation is available on-line at:http://www.cse.ohio-state.edu/~jain/cis677-98/Raj JainThe Ohio State University5-2Routing algorithmsARPAnet routingOverviewRaj JainThe Ohio State University5-3RoutingRoutingFig 9.5Raj JainThe Ohio State University5-4Rooting or RoutingRooting or RoutingRooting is what fans do at football games, what pics 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 infanctrymen into full scale, disorganized retreatRef: Piscitello and Chapin, p413Raj JainThe Ohio State University5-5Routeing or RoutingRouteing or RoutingRouteing: BritishRouting: AmericanSince Oxford English Dictionary is much heavier than any other dictionary of American English, British English generally prevalis 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, p413Raj JainThe Ohio State University5-6Rooting or RoutingRooting or RoutingRooting is what fans do at football games, what pics 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 infanctrymen into full scale, disorganized retreatRef: Piscitello and Chapin, p413Raj JainThe Ohio State University5-7Routeing or RoutingRouteing or RoutingRouteing: BritishRouting: AmericanSince Oxford English Dictionary is much heavier than any other dictionary of American English, British English generally prevalis 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, p413Raj JainThe Ohio State University5-8Routing Techniques ElementsRouting Techniques ElementsPerformance criterion: Hops, Distance, Speed, Delay, CostDecision time: Packet, sessionDecision place: Distributed, centralized, SourceNetwork information source: None, local, adjacent nodes, nodes along route, all nodesRouting strategy: Fixed, adaptive, random, floodingAdaptive routing update time: Continuous, periodic, topology change, major load changeRaj JainThe Ohio State University5-9Distance Vector vs Link StateDistance Vector vs Link StateDistance 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.Raj JainThe Ohio State University5-10Dijkstra’s AlgorithmDijkstra’s AlgorithmGoal: Find the least cost paths from a given node to all other nodes in the networkNotation: 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 is knownMethod:Initialize: M={s}, Dn = dsnFind node w M, whose Dn is minimumUpdate DnRaj JainThe Ohio State University5-11ExampleExampleRaj JainThe Ohio State University5-12Example (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-13Dijkstra's Routing Algorithm Dijkstra's Routing Algorithm Apply to the following network and compute paths from node 1.124 53 6143 24111M D2 Path D3 Path D4 Path D5 Path D6 Path123456Raj JainThe Ohio State University5-14Dijkstra's routing algorithm Dijkstra's routing algorithm Apply to the following network and compute paths from node 1.124 53 6143 24111M D2 Path D3 Path D4 Path D5 Path D6 Path1 {1} 1 1-2- 4 1-4--2 {1,2} 1 1-2 4 1-2-3 4 1-43 {1,2,3} 1 1-2 4 1-2-3 4 1-4 2 1-2-5 6 1-2-3-64 {1,2,3,5} 1 1-2 4 1-2-3 3 1-2-5-1 2 1-2-5 6 1-2-3-65 {1,2,3,4,5} 1 1-2 4 1-2-3 3 1-2-5-1 2 1-2-5 6 1-2-3-66 {1,2,3,4,5,6} 1 1-2 4 1-2-3 3 1-2-5-1 2 1-2-5 6 1-2-3-6Raj JainThe Ohio State University5-15Bellman-Ford AlgorithmBellman-Ford AlgorithmNotation:h = Number of hops being consideredD(h)n = Cost of h-hop path from s to nMethod: Find all nodes 1 hop awayFind all nodes 2 hops awayFind all nodes 3 hops awayInitialize: D(h)n = for all n s; D(h)n = 0 for all hFind jth node for which h+1 hops cost is minimum D(h+1)n = minj [D(h)j +Djn]Raj JainThe Ohio State University5-16ExampleExampleFig 9.23bRaj JainThe Ohio State University5-17Example (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-5-4-3 1 1-4 2 1-4-5 4 1-4-5-64 2 1-2 3 1-5-4-3 1 1-4 2 1-4-5 4 1-4-5-6Raj JainThe Ohio State University5-18FloodingFloodingFig 8.11bRaj JainThe Ohio State University5-19FloodingFlooding12 356412 356412 3564(a) First hop(b) Second hop(c) Third hopUses all possible pathsUses minimum hop path Used for source routingFig 9.7Raj JainThe Ohio State University5-20ARPAnet Routing (1969-78)ARPAnet Routing (1969-78)Features: Cost=Queue length, Each node sends a vector of costs (to all nodes) to neighbors. Distance vectorEach node computes new cost vectors based on the new info using Bellman-Ford algorithmRaj JainThe Ohio State University5-21ARPAnet Routing AlgorithmARPAnet Routing Algorithm123456025168Ñ23433123456023124Ñ24444203235330213122013D1Desti- nationS1D2D3D4DelayNext nodeDesti- nation DelayNext node(a) Node 1ås routing table before update(b) Delay vectors sent to
View Full Document