DOC PREVIEW
WUSTL CIS 677 - Packet Switching

This preview shows page 1-2-3-24-25-26 out of 26 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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-2Routing algorithms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 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 RoutingRouteing: BritishRouting: AmericanSince 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 RoutingRooting 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 RoutingRouteing: BritishRouting: AmericanSince 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 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 changeRaj JainThe Ohio State University5-9Distance Vector vs Link StateDistance 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.Raj JainThe Ohio State University5-10Dijkstra’s AlgorithmDijkstra’s AlgorithmGoal: Find the least cost paths from a given node to all other 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 is knownMethod:Initialize: M={s}, Dn = dsnFind node w  M, whose Dn is minimumUpdate 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 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-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 hopUses all possible pathsUses 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 vectorEach 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

WUSTL CIS 677 - Packet Switching

Download Packet Switching
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Packet Switching and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Packet Switching 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?