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

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

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

计算机网络TheNetworkLayerTheNetworkLayerTopicsNetworkLayerDesignIssuesStore-and-ForwardPacketSwitchingImplementationofConnectionlessSe

rviceImplementationofConnection-OrientedServiceComparisonofVirtual-CircuitandDatagramSubnetsRoutingAlgorithmsCorrectnessSimplicityRobustne

ssStabilityFairnessOptimalityRoutingAlgorithms􀁺ShortestPathRouting􀁺Flooding􀁺DistanceVectorR

outing􀁺LinkStateRouting􀁺HierarchicalRoutingRoutingAlgorithmBasicsTheroutingalgorithmisthatpartofthenetworklaye

rsoftwareresponsiblefordecidingwhichoutputlineanincomingpacketshouldbetransmittedon.Ifthesubnetusesdatagramsinternally,thisdecis

ionmustbemadeanewforeveryarrivingdatapacketsincethebestroutemayhavechangedsincelasttime.Ifthesubnetusesvirtualcircuitsinternally,ro

utingdecisionsaremadeonlywhenanewvirtualcircuitisbeingsetup.RoutingAlgorithmBasics(2)AlloptimalroutesfromstationAtootherstationsinthenetw

ork,jointlyconstituteasinktreeRoutershavetocollaboratetobuildthesinktreeforeachsourcestationordestinationstation.RoutingAlgor

ithmBasics(3)MetricsusedforoptimizationDistanceNumberofhopsTimedelayTwomajorclassesofroutingalgorithmsNonadaptiveorS

tatic:theroutingtableiscomputedinadvance,off-line,anddownloadedtotherouterswhenthenetworkisbooted.AdaptiveorDynamic:changethe

irroutingdecisionstoreflectchangesinthetopology,andusuallythetrafficaswell.ShortestPathRoutingIdea:buildagraphofth

esubnet,witheachnodeofthegraphrepresentingarouterandeacharcofthegraphrepresentingacommunicationline.Tocho

osearoutebetweenagivenpairofrouters,thealgorithmjustfindstheshortestpathbetweenthemonthegraph.thelabels(weights)onth

earcscouldbecomputedasafunctionofthedistance,bandwidth,averagetraffic,communicationcost,measureddelay,andotherfactors.ShortestP

athCriteria:sumoftheweightsalltheway,or,thenumberofhops.ShortestPathRoutingDijkstraAlgorithmBasicIdea:duringeachstep,selec

tanewlyreachablenodeatthelowestcost,andaddtheedgetothatnode,tothesinktreerootedatthesourcenodebuiltsofar.Floodi

ngBasicidea:Forwardanincomingpacketacrosseveryoutgoingline,excepttheoneitcamethrough.􀁺Basicproblem:howtoavoid―

drowningbypackets‖?􀁺Useahopcounter:afterapackethasbeenforwardedacrossNrouters,itisdiscarded.􀁺Besuretoforwa

rdapacketonlyonce(i.e.avoiddirectedcycles).Requiressequencenumberspersourcerouter.􀁺Floodselectively:onlyinthedirectionthatmakessense.􀁺

Floodingmakessenseonlywhenrobustnessisneeded,e.g.inmilitaryapplicationsDistanceVectorRoutingBellman-FordorF

ord-FulkersonalgorithmDistanceVectorRoutingAlgorithms:eachroutermaintainsatable(i.e,avector)givingthebestknowndistancetoeachdestinationa

ndwhichlinetousetogetthere,whichareupdatedbyexchanginginformationwiththeneighborsperiodically.UpdatingProcess:Takealook

atthecoststhatyourdirectneighborsareadvertisingtogetapackettothedestination.Selecttheneighborwhoseadvertisedcost,addedwiththecosttogettothatne

ighbor,isthelowest.Advertisethatnewcosttotheotherneighbors.InDVR,thereistheproblemofcount-to-infinit

yinthepresenceofnodecrashes.DVRExample(a)Asubnet.(b)InputfromA,I,H,K,andthenewroutingtableforJLinkStateRoutingLinkStateRouting:broadcastinfoontheen

tirenetworktopologytoallrouters,andleteachofthemcalculateasinktreetotheotherrouters.Eachroutermustdothefollowing:Discoveritsneighbors,learnthei

rnetworkaddress.Measurethedelayorcosttoeachofitsneighbors.Constructapackettellingallithasjustlearned.Sendthispackettoallotherrou

ters.Computetheshortestpathtoeveryotherrouter.MeasuringLineCostJustsendanECHOpacketthrougheachinterface,andmeasuretheround

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

etimershouldbestartedwhentheECHOpacketisqueued.Youmayredirecttrafficinsuchawaythatthealternativerouteisunloaded.No:thetimershouldbestar

tedwhentheECHOpacketreachesthefrontofthequeue.Theshortestpathyouchoosemaybeoverloaded.BuildingLinkStatePacketsThepacketstartswithth

eidentityofthesender,followedbyasequencenumberandage,andalistofdualitems(neighbor,thedelaytoit).Thehardpartiswhentobuildthem,atregularintervalsorwhe

nsomesignificanteventoccurs?Practiceshowsthatonceanhourisoftenenough.DistributingtheLinkStatePacketsUseafloodingalgorithm,anddamthefloodthroughse

quencenumbers:allroutersmaintainalistof(source,seqnumber)-pairs.􀁺Tosafeguardagainstolddata,downlinks,etc

.anageisaddedtoanLSP.Theageisdecrementedonceasecond,andeverytimeitisforwardedbyarouter.Whentheagehitszero,theLSPisdiscarded.Toguardagainster

rorsontherouter-routerlines,alllinkstatepacketsareacknowledged.GoodsandBadsofLSRGoodsGoodconsistencyofe

achrouterinformationQuickconvergenceforgoodandbadnewsBadsEachrouterneedlargememorytostoretheinputlinkstatesofotherrou

tersThecomputationtimecanbeanissueHierarchicalRoutingProblem:Noroutingalgorithmdiscussedsofarcanscale:allofthemrequireeachroutertoknowa

boutallothers=>toodemandingwithrespecttomemorycapacityandprocessingpower.Goforsuboptimalroutesbyintroducinghierarchicalroutinga

ndregions,andseparatealgorithmsforintra-regionandinter-regionrouting.Example:HierarchicalRoutingMulticastingroutingMOSPFDVMRPCBTNextdiscus

siontopicsMulticastingroutingAdhocroutingBroadcastingroutingMobilehostsroutingCongestionControlAlgorithms􀁺GeneralPrinciplesofCon

gestionControl􀁺CongestionPreventionPolicies􀁺CongestionControlinVirtual-CircuitSubnets􀁺CongestionControlinDatagramSubnets􀁺LoadShe

dding􀁺JitterControlCongestion􀁺Congestion:Whentoomanypacketsarepresent,performancedegrades􀁺Atveryhightraffic,performancecollapsescompletelyandal

mostnopacketsaredelivered.CongestionGeneralPrinciplesofCongestionControlTwogroupsofsolutions:􀁺Openloop:attempttosolvetheproblembygood

design,inessence,tomakesureitdoesnotoccurinthefirstplace.􀁺Closedloop:arebasedontheconceptofafeedbackloop.Monitorthesystem

todetectwhenandwherecongestionoccurs.Passinformationtowhereactioncanbetaken.Adjustsystemoperationtoc

orrecttheproblem.PolicyCongestionControlinVirtual-CircuitSubnetsHop-by-HopChokePackets􀁺Whenarouterrunsoutofitsresources,itsendsachokepacketback

tothesourcehost,givingitthedestinationfoundinthepacket.􀁺Whenthesourcehostgetsthechokepacket,itwillslowdownthetra

fficsenttothespecifieddestination.􀁺Hop-by-Hop:thechokepacketaffectseveryhopitpassesthrough.(a)Achokepacketthataffectsonlythesource.(b)Hop-by-Ho

pchokepacket.RandomearlydetectionByhavingroutersdroppacketsbeforethesituationhasbecomehopeless(hencethe''early''inthename),theideais

thatthereistimeforactiontobetakenbeforeitistoolate.Todeterminewhentostartdiscarding,routersmaintainaru

nningaverageoftheirqueuelengths.Whentheaveragequeuelengthonsomelineexceedsathreshold,thelinkissaidtobecongestionandasmallfractionofth

epacketsaredroppedatrandomJitterControlQualityofServiceAstreamofpacketsfromasourcetoadestinationiscalledaflow.Inaconnection-orientednetwork

,allthepacketsbelongingtoaflowfollowthesameroute;inaconnectionlessnetwork,theymayfollowdifferentroutes.Theneedsofeachflowcanbecharacterizedbyfourprim

aryparameters:reliability,delay,jitter,andbandwidth.TogetherthesedeterminetheQoS(QualityofService)theflowrequires.Tra

fficShapingTrafficshapingisaboutregulatingtheaveragerateofdatatransmission.Thegoalistoallowapplicationstotransmitawidevarietyoftra

fficthatsuitstheirneeds,includesomebursts.TheLeakyBucketAlgorithmImagineabucketwithasmallholeinthebottom.Nomattertherateat

whichwaterentersthebucket,theoutflowisataconstantrate,,whenthereisanywaterinthebucketandzerowhenthebucketisempty.*实现：-对定长分组的实现：以分组为单位；-对变长分组的实现：采用字

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

漏桶的输出。TheTokenBucketAlgorithmTheleakybucketalgorithmenforcesarigidoutputpatternattheaveragerate,nomatterhowburstythetrafficis.Forman

yapplications,itisbettertoallowtheoutputtospeedupsomewhatwhenlargeburstsarrive,soamoreflexiblealgorithmisneeded,p

referablyonethatneverlosesdata.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时钟周期的需求。-有些应用需要更高的容错能力。-有些应用希望讨价还价流的参数。Admissionco

ntrol•flowspecification(流说明)：-能够准确描述规范化的流参数。-从源端到目的端沿途路由器可修改这些参数。举例：-令牌桶速率：长时间间隔的平均输入桶的每秒字节数。-令牌桶容量。-峰

值数据速率：限制短暂时间间隔发送速率。-最小、最大分组长度：含头部。Packetsscheduling按比例路由：由于路由器一般不了解整个网络的流量，一种高QoS的方法是根据输出链路能力按相等或比例划分，在多条路径上传输。Packetsscheduling：•公平队列算

法：*Nagle算法：-到达分组按分类或流进入各自队列；-轮流从各队列输出，一旦某队列空，立即从非空队列输出。Packetsscheduling分组调度（续）：•公平队列算法(FIFO)•加权队列算法(WFQ)5.4.2实现高QoS

的技术（续）分组调度（续）：•加权公平队列（WFQ）：-对不同的队列设置优先级（即权重）。-按权重比例发送。5.4.2实现高QoS的技术（续）分组调度（续）：•令牌+WFQ提供可证明的最大队列延时：n条流的令牌桶+WFQ队列模型。b1r1bnrnw1wnInternetworking�

�HowNetworksDiffer􀁺HowNetworksCanBeConnected􀁺ConcatenatedVirtualCircuits􀁺ConnectionlessInternetworking􀁺Tunneli

ng􀁺FragmentationConnectingNetworksHowNetworksDifferHowNetworksCanBeConnected􀁺Repeatersatthephysicallayerforboostingsignals.􀁺Bridgest

omaketheinterconnectionatthedatalinklayer.􀁺Multiprotocolroutersforforwarding,andpossiblysplittinguppackets(bridgescan’tdothel

atter).􀁺Transportgatewaysforinterfacingbetweentwotransportconnections.􀁺Applicationgateways,translatemessagesemantics.ConcatenatedVi

rtualCircuitsConnectionlessinternetworkingHavethenetworklayerofferonlydatagramservices:unreliable,unorderedpacketflow.Mainproblem

:Addressing–differentnetworksusecompletelydifferentaddresses,sohowdoIaddressahostinanIPnetworkwhenI’ve

onlygotSNA?Solution:consider,usingIPasauniversalnetworkprotocolTunnelingWecansolvealotoftheinternetworkingproblemswhenwecanassumethatthesourceandde

stinationofthesametypeofnetworkisconnectedbydifferentnetwork,weneedonlytotunnelpacketsthroughintermediatenetworks.FragmentationFragmentation:Differe

ntnetworksmayimposedifferentmaximumpacketsizes.Thismeansthatwemayhavetosplitapacketintosmalleroneswhenforwardingitthrougha

networkwhosemaximumpacketsizeistoosmallWheretoreassemblethefragments?Gateway:Transparentfragmentation􀁺Thedestinationhost:No

ntransparentfragmentationTheNetworkLayerintheInternetTheInternetProtocol(IP)TheInternetisacollectionofmanynetworksconnectedtogetherbyabunchofb

ackbones.ThegluethatholdsthewholeInternettogetheristhenetworklayerprotocol,IP(InternetProtocol).TheIPv4HeaderTheIPv4Header(2)AddressesIPAddress

es(2)Subnets(1)􀁺Allhostsonthesamenetworkmusthavethesamenetworknumber.Thismaycauseasingleorganizationtoacquireseveralclassesof

addressesformultipleLANs.􀁺Useasinglenetworkaddressfortheentireorganization,andinternallydividethehostad

dressspaceintoasubnetaddressandahostid􀁺Toimplementsubnetting,themainrouterneedsasubnetmaskthatindicateCIDR–ClasslessInterDomain

RoutingCIDR–ExamplesCIDR–AggregateEntriesFormanyroutersoutside194.24.0.0,theonlythingtheyseeisthatthereare(atleast)3networkaddressesforwhichpacketsf

ollowthesameroute.Theseentriescanbeaggregatedintoasingleentry194.24.0.0/19withasinglesubmaskof19/131/0bits.