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

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

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

计算机网络TheNetworkLayerTheNetworkLayerTopicsNetworkLayerDesignIssuesStore-and-ForwardPacketSwitchingImplementationofConnectionlessServiceImplem

entationofConnection-OrientedServiceComparisonofVirtual-CircuitandDatagramSubnetsRoutingAlgorithmsCorrectnessSimplicityRobustnessS

tabilityFairnessOptimalityRoutingAlgorithms􀁺ShortestPathRouting􀁺Flooding􀁺DistanceVectorRouting􀁺Li

nkStateRouting􀁺HierarchicalRoutingRoutingAlgorithmBasicsTheroutingalgorithmisthatpartofthenetworklayersoftwareres

ponsiblefordecidingwhichoutputlineanincomingpacketshouldbetransmittedon.Ifthesubnetusesdatagramsinternally,thisdecision

mustbemadeanewforeveryarrivingdatapacketsincethebestroutemayhavechangedsincelasttime.Ifthesubnetusesvirtualcircuitsinternally,routingdecisionsarema

deonlywhenanewvirtualcircuitisbeingsetup.RoutingAlgorithmBasics(2)AlloptimalroutesfromstationAtootherstationsinthene

twork,jointlyconstituteasinktreeRoutershavetocollaboratetobuildthesinktreeforeachsourcestationordestinationstation.Routi

ngAlgorithmBasics(3)MetricsusedforoptimizationDistanceNumberofhopsTimedelayTwomajorclassesofroutingalgori

thmsNonadaptiveorStatic:theroutingtableiscomputedinadvance,off-line,anddownloadedtotherouterswhenthenetworkisbooted.A

daptiveorDynamic:changetheirroutingdecisionstoreflectchangesinthetopology,andusuallythetrafficaswell.ShortestPathRouti

ngIdea:buildagraphofthesubnet,witheachnodeofthegraphrepresentingarouterandeacharcofthegraphrepresentingacommunicationlin

e.Tochoosearoutebetweenagivenpairofrouters,thealgorithmjustfindstheshortestpathbetweenthemonthegraph.thelabels(weights)onthearcscouldb

ecomputedasafunctionofthedistance,bandwidth,averagetraffic,communicationcost,measureddelay,andotherfactors.ShortestPathCri

teria:sumoftheweightsalltheway,or,thenumberofhops.ShortestPathRoutingDijkstraAlgorithmBasicIdea:duringeachstep,selectanewlyreachableno

deatthelowestcost,andaddtheedgetothatnode,tothesinktreerootedatthesourcenodebuiltsofar.FloodingBasicidea:Forwardan

incomingpacketacrosseveryoutgoingline,excepttheoneitcamethrough.􀁺Basicproblem:howtoavoid―drowningb

ypackets‖?􀁺Useahopcounter:afterapackethasbeenforwardedacrossNrouters,itisdiscarded.􀁺Besuretoforwardapacket

onlyonce(i.e.avoiddirectedcycles).Requiressequencenumberspersourcerouter.􀁺Floodselectively:onlyinthedirectionthatmakessen

se.􀁺Floodingmakessenseonlywhenrobustnessisneeded,e.g.inmilitaryapplicationsDistanceVectorRoutingBellman-FordorFord-Fulker

sonalgorithmDistanceVectorRoutingAlgorithms:eachroutermaintainsatable(i.e,avector)givingthebestknowndistancetoeachdestinationandwhichli

netousetogetthere,whichareupdatedbyexchanginginformationwiththeneighborsperiodically.UpdatingProcess:Takealookatthecoststhat

yourdirectneighborsareadvertisingtogetapackettothedestination.Selecttheneighborwhoseadvertisedcost,addedwiththecos

ttogettothatneighbor,isthelowest.Advertisethatnewcosttotheotherneighbors.InDVR,thereistheproblemofcount-to-infinityintheprese

nceofnodecrashes.DVRExample(a)Asubnet.(b)InputfromA,I,H,K,andthenewroutingtableforJLinkStateRoutingLinkState

Routing:broadcastinfoontheentirenetworktopologytoallrouters,andleteachofthemcalculateasinktreetotheotherrouters.Eachroutermu

stdothefollowing:Discoveritsneighbors,learntheirnetworkaddress.Measurethedelayorcosttoeachofitsneighbors.Constructapackettellingallithasjus

tlearned.Sendthispackettoallotherrouters.Computetheshortestpathtoeveryotherrouter.MeasuringLineCostJustsendanECHOpacketthrougheachint

erface,andmeasuretheround-tripdelay.That’llgiveyouareasonableestimateoftheactualdelay.Whethertotaketheloadintoaccountwhenmeasuringthedel

ay?Yes:thetimershouldbestartedwhentheECHOpacketisqueued.Youmayredirecttrafficinsuchawaythatthealternativerouteisunloaded.No:thetim

ershouldbestartedwhentheECHOpacketreachesthefrontofthequeue.Theshortestpathyouchoosemaybeoverloaded.BuildingLinkStatePack

etsThepacketstartswiththeidentityofthesender,followedbyasequencenumberandage,andalistofdualitems(neighbor,thedelaytoit).Thehardpar

tiswhentobuildthem,atregularintervalsorwhensomesignificanteventoccurs?Practiceshowsthatonceanhourisoftenenough.Distributingth

eLinkStatePacketsUseafloodingalgorithm,anddamthefloodthroughsequencenumbers:allroutersmaintainalistof(source,seqnumber)-pairs.􀁺Tosafegua

rdagainstolddata,downlinks,etc.anageisaddedtoanLSP.Theageisdecrementedonceasecond,andeverytimeitisforwardedbyarouter.Whentheagehitszero,the

LSPisdiscarded.Toguardagainsterrorsontherouter-routerlines,alllinkstatepacketsareacknowledged.GoodsandB

adsofLSRGoodsGoodconsistencyofeachrouterinformationQuickconvergenceforgoodandbadnewsBadsEachrouterneedlargememorytostoretheinputli

nkstatesofotherroutersThecomputationtimecanbeanissueHierarchicalRoutingProblem:Noroutingalgorithmdiscussedsofarcanscale:allo

fthemrequireeachroutertoknowaboutallothers=>toodemandingwithrespecttomemorycapacityandprocessingpower.Goforsuboptimalrou

tesbyintroducinghierarchicalroutingandregions,andseparatealgorithmsforintra-regionandinter-regionrouting.Example:Hierarch

icalRoutingMulticastingroutingMOSPFDVMRPCBTNextdiscussiontopicsMulticastingroutingAdhocroutingBroadcastingroutingMobilehosts

routingCongestionControlAlgorithms􀁺GeneralPrinciplesofCongestionControl􀁺CongestionPreventionPolicies􀁺CongestionControlinVirt

ual-CircuitSubnets􀁺CongestionControlinDatagramSubnets􀁺LoadShedding􀁺JitterControlCongestion􀁺Congestion:Whent

oomanypacketsarepresent,performancedegrades􀁺Atveryhightraffic,performancecollapsescompletelyandalmostnopacketsaredelivered.Conge

stionGeneralPrinciplesofCongestionControlTwogroupsofsolutions:􀁺Openloop:attempttosolvetheproblembygooddesign,inessenc

e,tomakesureitdoesnotoccurinthefirstplace.􀁺Closedloop:arebasedontheconceptofafeedbackloop.Monitorthesystemtodetectwhenandwherecon

gestionoccurs.Passinformationtowhereactioncanbetaken.Adjustsystemoperationtocorrecttheproblem.PolicyCongestionContro

linVirtual-CircuitSubnetsHop-by-HopChokePackets􀁺Whenarouterrunsoutofitsresources,itsendsachokepacketbacktothesourcehost,givingitth

edestinationfoundinthepacket.􀁺Whenthesourcehostgetsthechokepacket,itwillslowdownthetrafficsenttothespecifieddestination.􀁺Hop-by-Hop:thechokepa

cketaffectseveryhopitpassesthrough.(a)Achokepacketthataffectsonlythesource.(b)Hop-by-Hopchokepacket.Randomearlyde

tectionByhavingroutersdroppacketsbeforethesituationhasbecomehopeless(hencethe''early''inthename),theideaistha

tthereistimeforactiontobetakenbeforeitistoolate.Todeterminewhentostartdiscarding,routersmaintainarunningaverageoft

heirqueuelengths.Whentheaveragequeuelengthonsomelineexceedsathreshold,thelinkissaidtobecongestionandasmallfr

actionofthepacketsaredroppedatrandomJitterControlQualityofServiceAstreamofpacketsfromasourcetoadestin

ationiscalledaflow.Inaconnection-orientednetwork,allthepacketsbelongingtoaflowfollowthesameroute;inaconnectionlessnetwork,theymayfo

llowdifferentroutes.Theneedsofeachflowcanbecharacterizedbyfourprimaryparameters:reliability,delay,jitter,andbandwidth.Togetherthesedetermin

etheQoS(QualityofService)theflowrequires.TrafficShapingTrafficshapingisaboutregulatingtheaveragerateofdatatransmission.Thegoalistoallowapplication

stotransmitawidevarietyoftrafficthatsuitstheirneeds,includesomebursts.TheLeakyBucketAlgorithmImagineabucketwithasmallh

oleinthebottom.Nomattertherateatwhichwaterentersthebucket,theoutflowisataconstantrate,,whenthereisanyw

aterinthebucketandzerowhenthebucketisempty.*实现：-对定长分组的实现：以分组为单位；-对变长分组的实现：采用字节计数法。漏桶算法（续）：*举例：设计算机以25MB/s速率产生数据，路由器长时间的最佳工作速率不超过2MB/s。数据以每秒中

有40ms，1MB的突发数据输入。为平稳输出，使用一个ρ=2MB/s，容积C=1MB的漏桶。a图为漏桶的输入，b图为漏桶的输出。TheTokenBucketAlgorithmTheleakybucketalg

orithmenforcesarigidoutputpatternattheaveragerate,nomatterhowburstythetrafficis.Formanyapplications,itisbettertoallowtheoutputtospeedupsomewha

twhenlargeburstsarrive,soamoreflexiblealgorithmisneeded,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的技术（续）资源预留：•可能被预留资源的种类：-带宽-缓冲区空间-C

PU时钟周期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􀁺HowNetworksDiffer􀁺HowNetworksCanBeConnected􀁺ConcatenatedVirtualCircuits􀁺ConnectionlessInternetworking

􀁺Tunneling􀁺FragmentationConnectingNetworksHowNetworksDifferHowNetworksCanBeConnected􀁺Repeatersatthephysicallayerforboostingsignals.􀁺

Bridgestomaketheinterconnectionatthedatalinklayer.􀁺Multiprotocolroutersforforwarding,andpossiblysplittinguppackets(bridgescan’tdothelatter).

􀁺Transportgatewaysforinterfacingbetweentwotransportconnections.􀁺Applicationgateways,translatemessagesemantics.ConcatenatedVirt

ualCircuitsConnectionlessinternetworkingHavethenetworklayerofferonlydatagramservices:unreliable,unorderedpack

etflow.Mainproblem:Addressing–differentnetworksusecompletelydifferentaddresses,sohowdoIaddressahostinanIPnetworkwhenI’veonlygot

SNA?Solution:consider,usingIPasauniversalnetworkprotocolTunnelingWecansolvealotoftheinternetworkingproblemswhenwecanassumethatthesourcea

nddestinationofthesametypeofnetworkisconnectedbydifferentnetwork,weneedonlytotunnelpacketsthroughintermedi

atenetworks.FragmentationFragmentation:Differentnetworksmayimposedifferentmaximumpacketsizes.Thismeansthatwemayhavetosplitapacketintosmalleroneswh

enforwardingitthroughanetworkwhosemaximumpacketsizeistoosmallWheretoreassemblethefragments?Gateway:Transparentfragmentation􀁺Thedesti

nationhost:NontransparentfragmentationTheNetworkLayerintheInternetTheInternetProtocol(IP)TheInternetisacollectionofmanynetworksconnectedtogetherbya

bunchofbackbones.ThegluethatholdsthewholeInternettogetheristhenetworklayerprotocol,IP(InternetProtocol)

.TheIPv4HeaderTheIPv4Header(2)AddressesIPAddresses(2)Subnets(1)􀁺Allhostsonthesamenetworkmusthavethesamenetwork

number.ThismaycauseasingleorganizationtoacquireseveralclassesofaddressesformultipleLANs.􀁺Useasinglenet

workaddressfortheentireorganization,andinternallydividethehostaddressspaceintoasubnetaddressandahosti

d􀁺Toimplementsubnetting,themainrouterneedsasubnetmaskthatindicateCIDR–ClasslessInterDomainRoutingCIDR–Exam

plesCIDR–AggregateEntriesFormanyroutersoutside194.24.0.0,theonlythingtheyseeisthatthereare(atleast)3networkaddressesforwhich

packetsfollowthesameroute.Theseentriescanbeaggregatedintoasingleentry194.24.0.0/19withasinglesubmasko

f19/131/0bits.