【文档说明】计算机网络第五版(英文版)(5)解析课件.ppt，共(75)页，3.546 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-5179.html

以下为本文档部分文字说明：

计算机网络TheNetworkLayerTheNetworkLayerTopicsNetworkLayerDesignIssuesStore-and-ForwardPacketSwitchingImplementationo

fConnectionlessServiceImplementationofConnection-OrientedServiceComparisonofVirtual-CircuitandDatagramSubnetsRoutingAlgorithmsCorrectne

ssSimplicityRobustnessStabilityFairnessOptimalityRoutingAlgorithms􀁺ShortestPathRouting􀁺Flooding􀁺DistanceVectorRouting􀁺Link

StateRouting􀁺HierarchicalRoutingRoutingAlgorithmBasicsTheroutingalgorithmisthatpartofthenetworklayersoftware

responsiblefordecidingwhichoutputlineanincomingpacketshouldbetransmittedon.Ifthesubnetusesdatagramsinternally,thisdecisionmustb

emadeanewforeveryarrivingdatapacketsincethebestroutemayhavechangedsincelasttime.Ifthesubnetusesvirtualcircuits

internally,routingdecisionsaremadeonlywhenanewvirtualcircuitisbeingsetup.RoutingAlgorithmBasics(2)AlloptimalroutesfromstationA

tootherstationsinthenetwork,jointlyconstituteasinktreeRoutershavetocollaboratetobuildthesinktreeforeachsourcestationordestinationstation.RoutingAlg

orithmBasics(3)MetricsusedforoptimizationDistanceNumberofhopsTimedelayTwomajorclassesofroutingalgorithmsNonadaptiveorStatic

:theroutingtableiscomputedinadvance,off-line,anddownloadedtotherouterswhenthenetworkisbooted.AdaptiveorDynamic:changetheirroutingdecisionstor

eflectchangesinthetopology,andusuallythetrafficaswell.ShortestPathRoutingIdea:buildagraphofthesubnet,witheachnodeofthegraphrepresentingar

outerandeacharcofthegraphrepresentingacommunicationline.Tochoosearoutebetweenagivenpairofrouters,thealgorithmjustfindstheshortestpathbetwe

enthemonthegraph.thelabels(weights)onthearcscouldbecomputedasafunctionofthedistance,bandwidth,averagetraffic,commu

nicationcost,measureddelay,andotherfactors.ShortestPathCriteria:sumoftheweightsalltheway,or,thenumberofhops.Sho

rtestPathRoutingDijkstraAlgorithmBasicIdea:duringeachstep,selectanewlyreachablenodeatthelowestcost,andaddtheedgetothatno

de,tothesinktreerootedatthesourcenodebuiltsofar.FloodingBasicidea:Forwardanincomingpacketacrosseveryoutgoi

ngline,excepttheoneitcamethrough.􀁺Basicproblem:howtoavoid―drowningbypackets‖?􀁺Useahopcounter:afterapackethasbeenforwar

dedacrossNrouters,itisdiscarded.􀁺Besuretoforwardapacketonlyonce(i.e.avoiddirectedcycles).Requiressequencenumberspersou

rcerouter.􀁺Floodselectively:onlyinthedirectionthatmakessense.􀁺Floodingmakessenseonlywhenrobustnessisneeded,e.g.inmilit

aryapplicationsDistanceVectorRoutingBellman-FordorFord-FulkersonalgorithmDistanceVectorRoutingAlgorithms:eachroutermaintainsatable(

i.e,avector)givingthebestknowndistancetoeachdestinationandwhichlinetousetogetthere,whichareupdatedbyexchanginginfor

mationwiththeneighborsperiodically.UpdatingProcess:Takealookatthecoststhatyourdirectneighborsareadvertisingtogetapackett

othedestination.Selecttheneighborwhoseadvertisedcost,addedwiththecosttogettothatneighbor,isthelowest.Advertisetha

tnewcosttotheotherneighbors.InDVR,thereistheproblemofcount-to-infinityinthepresenceofnodecrashes.DVRExam

ple(a)Asubnet.(b)InputfromA,I,H,K,andthenewroutingtableforJLinkStateRoutingLinkStateRouting:broadcastinfoontheentirenetworktopologytoa

llrouters,andleteachofthemcalculateasinktreetotheotherrouters.Eachroutermustdothefollowing:Discoveritsneighbors,learntheirnetworkadd

ress.Measurethedelayorcosttoeachofitsneighbors.Constructapackettellingallithasjustlearned.Sendthispac

kettoallotherrouters.Computetheshortestpathtoeveryotherrouter.MeasuringLineCostJustsendanECHOpacketthrougheachinterface,andmeasuret

heround-tripdelay.That’llgiveyouareasonableestimateoftheactualdelay.Whethertotaketheloadintoaccountwhenmeasuringthedelay?Yes:

thetimershouldbestartedwhentheECHOpacketisqueued.Youmayredirecttrafficinsuchawaythatthealternativerouteisunloaded.No:thetimershouldbes

tartedwhentheECHOpacketreachesthefrontofthequeue.Theshortestpathyouchoosemaybeoverloaded.BuildingLinkStatePacketsThepacketstartswiththei

dentityofthesender,followedbyasequencenumberandage,andalistofdualitems(neighbor,thedelaytoit).Thehardpartiswhento

buildthem,atregularintervalsorwhensomesignificanteventoccurs?Practiceshowsthatonceanhourisoftenenough.DistributingtheLinkStatePacketsUseafloodi

ngalgorithm,anddamthefloodthroughsequencenumbers:allroutersmaintainalistof(source,seqnumber)-pairs.􀁺Tosafeguardagainstolddata,downlinks,etc.ana

geisaddedtoanLSP.Theageisdecrementedonceasecond,andeverytimeitisforwardedbyarouter.Whentheagehitszer

o,theLSPisdiscarded.Toguardagainsterrorsontherouter-routerlines,alllinkstatepacketsareacknowledged.Goodsand

BadsofLSRGoodsGoodconsistencyofeachrouterinformationQuickconvergenceforgoodandbadnewsBadsEachrouterneedlargememorytostoretheinputlin

kstatesofotherroutersThecomputationtimecanbeanissueHierarchicalRoutingProblem:Noroutingalgorithmdiscussedsof

arcanscale:allofthemrequireeachroutertoknowaboutallothers=>toodemandingwithrespecttomemorycapacityandprocessingpower.Gof

orsuboptimalroutesbyintroducinghierarchicalroutingandregions,andseparatealgorithmsforintra-regionandinter-regionrouting.Example:Hierarchica

lRoutingMulticastingroutingMOSPFDVMRPCBTNextdiscussiontopicsMulticastingroutingAdhocroutingBroadcasti

ngroutingMobilehostsroutingCongestionControlAlgorithms􀁺GeneralPrinciplesofCongestionControl􀁺CongestionPreventionPolicies􀁺CongestionControlinVir

tual-CircuitSubnets􀁺CongestionControlinDatagramSubnets􀁺LoadShedding􀁺JitterControlCongestion􀁺Congestion:Whe

ntoomanypacketsarepresent,performancedegrades􀁺Atveryhightraffic,performancecollapsescompletelyandal

mostnopacketsaredelivered.CongestionGeneralPrinciplesofCongestionControlTwogroupsofsolutions:􀁺Openloop:attempttosolvet

heproblembygooddesign,inessence,tomakesureitdoesnotoccurinthefirstplace.􀁺Closedloop:arebasedontheconceptofafeedbackloo

p.Monitorthesystemtodetectwhenandwherecongestionoccurs.Passinformationtowhereactioncanbetaken.Adjustsystemoperationtocorr

ecttheproblem.PolicyCongestionControlinVirtual-CircuitSubnetsHop-by-HopChokePackets􀁺Whenarouterrunsoutofitsresources,it

sendsachokepacketbacktothesourcehost,givingitthedestinationfoundinthepacket.􀁺Whenthesourcehostgetsthechokepacket,itwillslowdownthetrafficse

nttothespecifieddestination.􀁺Hop-by-Hop:thechokepacketaffectseveryhopitpassesthrough.(a)Achokepacketthataffec

tsonlythesource.(b)Hop-by-Hopchokepacket.RandomearlydetectionByhavingroutersdroppacketsbeforethesi

tuationhasbecomehopeless(hencethe''early''inthename),theideaisthatthereistimeforactiontobetakenbeforeitistoolate.Tode

terminewhentostartdiscarding,routersmaintainarunningaverageoftheirqueuelengths.Whentheaveragequeuelengthonsomelineexceedsathreshol

d,thelinkissaidtobecongestionandasmallfractionofthepacketsaredroppedatrandomJitterControlQualityofServiceAstreamofp

acketsfromasourcetoadestinationiscalledaflow.Inaconnection-orientednetwork,allthepacketsbelongingtoa

flowfollowthesameroute;inaconnectionlessnetwork,theymayfollowdifferentroutes.Theneedsofeachflowcanbecharacterizedbyfourprimaryparameters:reli

ability,delay,jitter,andbandwidth.TogetherthesedeterminetheQoS(QualityofService)theflowrequires.TrafficShapingTrafficshapingis

aboutregulatingtheaveragerateofdatatransmission.Thegoalistoallowapplicationstotransmitawidevarietyoftraffi

cthatsuitstheirneeds,includesomebursts.TheLeakyBucketAlgorithmImagineabucketwithasmallholeinthebottom.Nomattertherateatwhichwaterente

rsthebucket,theoutflowisataconstantrate,,whenthereisanywaterinthebucketandzerowhenthebucketisempty.*实现：

-对定长分组的实现：以分组为单位；-对变长分组的实现：采用字节计数法。漏桶算法（续）：*举例：设计算机以25MB/s速率产生数据，路由器长时间的最佳工作速率不超过2MB/s。数据以每秒中有40ms，1MB的突发数据输入。为平稳输出，使用一个ρ=2MB/s，容积C=1MB的漏桶

。a图为漏桶的输入，b图为漏桶的输出。TheTokenBucketAlgorithmTheleakybucketalgorithmenforcesarigidoutputpatternattheaveragerate,nomatterhowburstythetrafficis.For

manyapplications,itisbettertoallowtheoutputtospeedupsomewhatwhenlargeburstsarrive,soamoreflexiblealgori

thmisneeded,preferablyonethatneverlosesdata.Onesuchalgorithmisthetokenbucketalgorithm.通信量整形—令牌桶算法：*实现：-采用分组计数法：设置令牌计数器，每隔ΔT加1，每发送一个分组减1，计数器为0时停止发送。

-采用字节计数法：时钟每隔ΔT令牌计数器加k字节，每发送一个分组减该分组长度。*对突发时间长度的限制：设突发时间长度S秒，令牌桶容量B字节，令牌到达率R字节/秒，最大速率M字节/秒，由B+RS=MS得S=B/(M-R)。通信量整形—令牌桶算法：*对突发长度的限制（续）：例：容量

C分别是250KB、500KB和750KB，ρ=2MB，M=25MB/s。假定当1MB突发数据到达时，令牌桶已满。5.4.2实现高QoS的技术（续）资源预留：•可能被预留资源的种类：-带宽-缓冲区空间-CPU时钟周期AdmissioncontrolAdmissioncontrol：

•确定接收或拒绝一个流并非易事,原因：-由于有些应用可能知道带宽需求，但不知道缓冲区和CPU时钟周期的需求。-有些应用需要更高的容错能力。-有些应用希望讨价还价流的参数。Admissioncontrol•flowspecification(流说明)：-能够准确描述规范化的流参数。

-从源端到目的端沿途路由器可修改这些参数。举例：-令牌桶速率：长时间间隔的平均输入桶的每秒字节数。-令牌桶容量。-峰值数据速率：限制短暂时间间隔发送速率。-最小、最大分组长度：含头部。Packetsscheduling按比例路由：由于路由器一般不

了解整个网络的流量，一种高QoS的方法是根据输出链路能力按相等或比例划分，在多条路径上传输。Packetsscheduling：•公平队列算法：*Nagle算法：-到达分组按分类或流进入各自队列；-轮流从各队列输出，一旦某队列空，

立即从非空队列输出。Packetsscheduling分组调度（续）：•公平队列算法(FIFO)•加权队列算法(WFQ)5.4.2实现高QoS的技术（续）分组调度（续）：•加权公平队列（WFQ）：-对不同的队列设置优先级（即权重）。-按权重比例

发送。5.4.2实现高QoS的技术（续）分组调度（续）：•令牌+WFQ提供可证明的最大队列延时：n条流的令牌桶+WFQ队列模型。b1r1bnrnw1wnInternetworking􀁺HowNetworks

Differ􀁺HowNetworksCanBeConnected􀁺ConcatenatedVirtualCircuits􀁺ConnectionlessInternetworking􀁺Tunneling􀁺FragmentationConnectingNetworksHowNetw

orksDifferHowNetworksCanBeConnected􀁺Repeatersatthephysicallayerforboostingsignals.􀁺Bridgestomaketheinterconnectionatthedatalinklayer.􀁺Mul

tiprotocolroutersforforwarding,andpossiblysplittinguppackets(bridgescan’tdothelatter).􀁺Transportgateways

forinterfacingbetweentwotransportconnections.􀁺Applicationgateways,translatemessagesemantics.ConcatenatedVirtualCirc

uitsConnectionlessinternetworkingHavethenetworklayerofferonlydatagramservices:unreliable,unorderedpacketflow.Mainproblem:Addressing–differentnetwor

ksusecompletelydifferentaddresses,sohowdoIaddressahostinanIPnetworkwhenI’veonlygotSNA?Solution:consider,usingIPasauniversal

networkprotocolTunnelingWecansolvealotoftheinternetworkingproblemswhenwecanassumethatthesourceanddestinationofthesametypeo

fnetworkisconnectedbydifferentnetwork,weneedonlytotunnelpacketsthroughintermediatenetworks.FragmentationFra

gmentation:Differentnetworksmayimposedifferentmaximumpacketsizes.Thismeansthatwemayhavetosplitapacketintosmalleronesw

henforwardingitthroughanetworkwhosemaximumpacketsizeistoosmallWheretoreassemblethefragments?Gateway:Transparentfragmentation􀁺Thedestinationhost

:NontransparentfragmentationTheNetworkLayerintheInternetTheInternetProtocol(IP)TheInternetisacollectionofmanynetwo

rksconnectedtogetherbyabunchofbackbones.ThegluethatholdsthewholeInternettogetheristhenetworklayerprotocol,IP(InternetProtocol).TheIPv4HeaderTheIP

v4Header(2)AddressesIPAddresses(2)Subnets(1)􀁺Allhostsonthesamenetworkmusthavethesamenetworknumber.Thismaycauseasingleorganizationtoacquiresev

eralclassesofaddressesformultipleLANs.􀁺Useasinglenetworkaddressfortheentireorganization,andinternallydividethehosta

ddressspaceintoasubnetaddressandahostid􀁺Toimplementsubnetting,themainrouterneedsasubnetmaskthatindicateCIDR–ClasslessI

nterDomainRoutingCIDR–ExamplesCIDR–AggregateEntriesFormanyroutersoutside194.24.0.0,theonlythingtheyseeisthatt

hereare(atleast)3networkaddressesforwhichpacketsfollowthesameroute.Theseentriescanbeaggregatedintoasingleentry194.24.0.0/19withasinglesubmaskof19

/131/0bits.