Tanenbaum《计算机网络》原版课件第5章

TheNetworkLayerChapter5NetworkLayerDesignIsues•Store-and-ForwardPacketSwitching•ServicesProvidedtotheTransportLayer•ImplementationofConnectionlessService•ImplementationofConnection-OrientedService•ComparisonofVirtual-CircuitandDatagramSubnetsStore-and-ForwardPacketSwitchingTheenvironmentofthenetworklayerprotocols.fig5-1ImplementationofConnectionlessServiceRoutingwithinadiagramsubnet.ImplementationofConnection-OrientedServiceRoutingwithinavirtual-circuitsubnet.ComparisonofVirtual-CircuitandDatagramSubnets5-4RoutingAlgorithms•TheOptimalityPrinciple•ShortestPathRouting•Flooding•DistanceVectorRouting•LinkStateRouting•HierarchicalRouting•BroadcastRouting•MulticastRouting•RoutingforMobileHosts•RoutinginAdHocNetworksRoutingAlgorithms(2)Conflictbetweenfairnessandoptimality.TheOptimalityPrinciple(a)Asubnet.(b)AsinktreeforrouterB.ShortestPathRoutingThefirst5stepsusedincomputingtheshortestpathfromAtoD.Thearrowsindicatetheworkingnode.FloodingDijkstra'salgorithmtocomputetheshortestpaththroughagraph.5-8topFlooding(2)Dijkstra'salgorithmtocomputetheshortestpaththroughagraph.5-8bottomDistanceVectorRouting(a)Asubnet.(b)InputfromA,I,H,K,andthenewroutingtableforJ.DistanceVectorRouting(2)Thecount-to-infinityproblem.LinkStateRoutingEachroutermustdothefollowing:1.Discoveritsneighbors,learntheirnetworkaddress.2.Measurethedelayorcosttoeachofitsneighbors.3.Constructapackettellingallithasjustlearned.4.Sendthispackettoallotherrouters.5.Computetheshortestpathtoeveryotherrouter.LearningabouttheNeighbors(a)NineroutersandaLAN.(b)Agraphmodelof(a).MeasuringLineCostAsubnetinwhichtheEastandWestpartsareconnectedbytwolines.BuildingLinkStatePackets(a)Asubnet.(b)Thelinkstatepacketsforthissubnet.DistributingtheLinkStatePacketsThepacketbufferforrouterBinthepreviousslide(Fig.5-13).HierarchicalRoutingHierarchicalrouting.BroadcastRoutingReversepathforwarding.(a)Asubnet.(b)aSinktree.(c)Thetreebuiltbyreversepathforwarding.MulticastRouting(a)Anetwork.(b)Aspanningtreefortheleftmostrouter.(c)Amulticasttreeforgroup1.(d)Amulticasttreeforgroup2.RoutingforMobileHostsAWANtowhichLANs,MANs,andwirelesscellsareattached.RoutingforMobileHosts(2)Packetroutingformobileusers.RoutinginAdHocNetworksPossibilitieswhentheroutersaremobile:1.Militaryvehiclesonbattlefield.–Noinfrastructure.2.Afleetofshipsatsea.–Allmovingallthetime3.Emergencyworksatearthquake.–Theinfrastructuredestroyed.4.Agatheringofpeoplewithnotebookcomputers.–Inanarealacking802.11.RouteDiscoverya)(a)RangeofA'sbroadcast.b)(b)AfterBandDhavereceivedA'sbroadcast.c)(c)AfterC,F,andGhavereceivedA'sbroadcast.d)(d)AfterE,H,andIhavereceivedA'sbroadcast.Shadednodesarenewrecipients.Arrowsshowpossiblereverseroutes.RouteDiscovery(2)FormatofaROUTEREQUESTpacket.RouteDiscovery(3)FormatofaROUTEREPLYpacket.RouteMaintenance(a)D'sroutingtablebeforeGgoesdown.(b)ThegraphafterGhasgonedown.NodeLookupinPeer-to-PeerNetworks(a)Asetof32nodeidentifiersarrangedinacircle.Theshadedonescorrespondtoactualmachines.Thearcsshowthefingersfromnodes1,4,and12.Thelabelsonthearcsarethetableindices.(b)Examplesofthefingertables.CongestionControlAlgorithms•GeneralPrinciplesofCongestionControl•CongestionPreventionPolicies•CongestionControlinVirtual-CircuitSubnets•CongestionControlinDatagramSubnets•LoadShedding•JitterControlCongestionWhentoomuchtrafficisoffered,congestionsetsinandperformancedegradessharply.GeneralPrinciplesofCongestionControl1.Monitorthesystem.–detectwhenandwherecongestionoccurs.2.Passinformationtowhereactioncanbetaken.3.Adjustsystemoperationtocorrecttheproblem.CongestionPreventionPoliciesPoliciesthataffectcongestion.5-26CongestionControlinVirtual-CircuitSubnets(a)Acongestedsubnet.(b)Aredrawnsubnet,eliminatescongestionandavirtualcircuitfromAtoB.Hop-by-HopChokePackets(a)Achokepacketthataffectsonlythesource.(b)Achokepacketthataffectseachhopitpassesthrough.JitterControl(a)Highjitter.(b)Lowjitter.QualityofService•Requirements•TechniquesforAchievingGoodQualityofService•IntegratedServices•DifferentiatedServices•LabelSwitchingandMPLSRequirementsHowstringentthequality-of-servicerequirementsare.5-30BufferingSmoothingtheoutputstreambybufferingpackets.TheLeakyBucketAlgorithm(a)Aleakybucketwithwater.(b)aleakybucketwithpackets.TheLeakyBucketAlgorithm(a)Inputtoaleakybucket.(b)Outputfromaleakybucket.Outputfromatokenbucketwithcapacitiesof(c)250KB,(d)500KB,(e)750KB,(f)Outputfroma500KBtokenbucketfeedinga10-MB/secleakybucket.TheTokenBucketAlgorithm(a)Before.(b)After.5-34AdmissionControlAnexampleofflowspecification.5-34PacketScheduling(a)ArouterwithfivepacketsqueuedforlineO.(b)Finishingtimesforthefivepackets.RSVP-TheReSerVationProtocol(a)Anetwork,(b)Themulticastspanningtreeforhost1.(c)Themulticastspanningtreeforhost2.RSVP-TheReSerVationProtocol(2)(a)Host3requestsachanneltohost1.(b)Host3thenrequestsasecondchannel,tohost2.(c)Host5requestsachanneltohost1.ExpeditedForwardingExpeditedpacketsexperienceatraffic-freenetwork.AssuredForwardingApossibleimplementationofthedataflowforassuredforwarding.LabelSwitchingandMPLSTransmittingaTCPsegmentusingIP,MPLS,andPPP.Internet