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

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

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

计算机网络TheNetworkLayerTheNetworkLayerTopicsNetworkLayerDesignIssuesStore-and-ForwardPacketSwitchingImplementationofConnectionlessServiceImplementati

onofConnection-OrientedServiceComparisonofVirtual-CircuitandDatagramSubnetsRoutingAlgorithmsCorrectnessSimplicityRobustnessStabilit

yFairnessOptimalityRoutingAlgorithms􀁺ShortestPathRouting􀁺Flooding􀁺DistanceVectorRouting􀁺LinkStat

eRouting􀁺HierarchicalRoutingRoutingAlgorithmBasicsTheroutingalgorithmisthatpartofthenetworklayersoft

wareresponsiblefordecidingwhichoutputlineanincomingpacketshouldbetransmittedon.Ifthesubnetusesdatagramsinte

rnally,thisdecisionmustbemadeanewforeveryarrivingdatapacketsincethebestroutemayhavechangedsincelasttime.Ift

hesubnetusesvirtualcircuitsinternally,routingdecisionsaremadeonlywhenanewvirtualcircuitisbeingsetup.RoutingAlgorith

mBasics(2)AlloptimalroutesfromstationAtootherstationsinthenetwork,jointlyconstituteasinktreeRoutershavetoco

llaboratetobuildthesinktreeforeachsourcestationordestinationstation.RoutingAlgorithmBasics(3)MetricsusedforoptimizationDis

tanceNumberofhopsTimedelayTwomajorclassesofroutingalgorithmsNonadaptiveorStatic:theroutingtableiscomputedinadvance,off-line,anddownl

oadedtotherouterswhenthenetworkisbooted.AdaptiveorDynamic:changetheirroutingdecisionstoreflectchangesinthetopol

ogy,andusuallythetrafficaswell.ShortestPathRoutingIdea:buildagraphofthesubnet,witheachnodeofthegraphrepresentingarouterandeacharcoftheg

raphrepresentingacommunicationline.Tochoosearoutebetweenagivenpairofrouters,thealgorithmjustfindstheshortestpathbetweenthemonthegraph.thelabels

(weights)onthearcscouldbecomputedasafunctionofthedistance,bandwidth,averagetraffic,communicationcost,measureddelay,andotherfactors.ShortestPa

thCriteria:sumoftheweightsalltheway,or,thenumberofhops.ShortestPathRoutingDijkstraAlgorithmBasicIdea:dur

ingeachstep,selectanewlyreachablenodeatthelowestcost,andaddtheedgetothatnode,tothesinktreerootedatthesourcen

odebuiltsofar.FloodingBasicidea:Forwardanincomingpacketacrosseveryoutgoingline,excepttheoneitcamethrough.􀁺Basicproblem

:howtoavoid―drowningbypackets‖?􀁺Useahopcounter:afterapackethasbeenforwardedacrossNrouters,itisdiscarded.􀁺Besuretoforwardapacke

tonlyonce(i.e.avoiddirectedcycles).Requiressequencenumberspersourcerouter.􀁺Floodselectively:onlyinthedirectionthatmakessense.􀁺Floodingma

kessenseonlywhenrobustnessisneeded,e.g.inmilitaryapplicationsDistanceVectorRoutingBellman-FordorFord-

FulkersonalgorithmDistanceVectorRoutingAlgorithms:eachroutermaintainsatable(i.e,avector)givingthebestknowndistancetoeachdestinationandwhi

chlinetousetogetthere,whichareupdatedbyexchanginginformationwiththeneighborsperiodically.UpdatingProcess:Ta

kealookatthecoststhatyourdirectneighborsareadvertisingtogetapackettothedestination.Selecttheneighborwhoseadvertisedcost,addedwiththecostt

ogettothatneighbor,isthelowest.Advertisethatnewcosttotheotherneighbors.InDVR,thereistheproblemofcount-to-inf

inityinthepresenceofnodecrashes.DVRExample(a)Asubnet.(b)InputfromA,I,H,K,andthenewroutingtableforJLinkStateRoutingLinkSt

ateRouting:broadcastinfoontheentirenetworktopologytoallrouters,andleteachofthemcalculateasinktreetotheother

routers.Eachroutermustdothefollowing:Discoveritsneighbors,learntheirnetworkaddress.Measurethedelayorcosttoeachofit

sneighbors.Constructapackettellingallithasjustlearned.Sendthispackettoallotherrouters.Computetheshortestpathtoeveryotherrouter.

MeasuringLineCostJustsendanECHOpacketthrougheachinterface,andmeasuretheround-tripdelay.That’llgiveyouareasona

bleestimateoftheactualdelay.Whethertotaketheloadintoaccountwhenmeasuringthedelay?Yes:thetimershouldb

estartedwhentheECHOpacketisqueued.Youmayredirecttrafficinsuchawaythatthealternativerouteisunloaded.No:thetimershouldbestartedwhentheE

CHOpacketreachesthefrontofthequeue.Theshortestpathyouchoosemaybeoverloaded.BuildingLinkStatePacketsThepacketstartswiththeidentityofthesender,follow

edbyasequencenumberandage,andalistofdualitems(neighbor,thedelaytoit).Thehardpartiswhentobuildthem,atregularintervalsorwhensomesignifica

nteventoccurs?Practiceshowsthatonceanhourisoftenenough.DistributingtheLinkStatePacketsUseafloodingalgorithm,anddamthefloodthroughseq

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

Theageisdecrementedonceasecond,andeverytimeitisforwardedbyarouter.Whentheagehitszero,theLSPisdiscarded.Toguardagainster

rorsontherouter-routerlines,alllinkstatepacketsareacknowledged.GoodsandBadsofLSRGoodsGoodconsistencyofeachrouterinformationQu

ickconvergenceforgoodandbadnewsBadsEachrouterneedlargememorytostoretheinputlinkstatesofotherroutersThecomputationtime

canbeanissueHierarchicalRoutingProblem:Noroutingalgorithmdiscussedsofarcanscale:allofthemrequireeachroutertoknowaboutallothers=>toodemandingwit

hrespecttomemorycapacityandprocessingpower.Goforsuboptimalroutesbyintroducinghierarchicalroutingandregions,andsepa

ratealgorithmsforintra-regionandinter-regionrouting.Example:HierarchicalRoutingMulticastingroutingMOSPFDVMRPCBTNextdiscussiontopicsMu

lticastingroutingAdhocroutingBroadcastingroutingMobilehostsroutingCongestionControlAlgorithms􀁺GeneralPrincipleso

fCongestionControl􀁺CongestionPreventionPolicies􀁺CongestionControlinVirtual-CircuitSubnets􀁺CongestionControlinDatagramSubnets􀁺LoadShedd

ing􀁺JitterControlCongestion􀁺Congestion:Whentoomanypacketsarepresent,performancedegrades􀁺Atveryhightraffic

,performancecollapsescompletelyandalmostnopacketsaredelivered.CongestionGeneralPrinciplesofCongestio

nControlTwogroupsofsolutions:􀁺Openloop:attempttosolvetheproblembygooddesign,inessence,tomakesureitdoesnotoccurinthefirstplace.􀁺Closedloop:arebas

edontheconceptofafeedbackloop.Monitorthesystemtodetectwhenandwherecongestionoccurs.Passinformationtowhereactioncanbetaken.Adjusts

ystemoperationtocorrecttheproblem.PolicyCongestionControlinVirtual-CircuitSubnetsHop-by-HopChokePackets􀁺Whenarouterruns

outofitsresources,itsendsachokepacketbacktothesourcehost,givingitthedestinationfoundinthepacket.􀁺Whenthesourcehostgetsthechokepacket,itw

illslowdownthetrafficsenttothespecifieddestination.􀁺Hop-by-Hop:thechokepacketaffectseveryhopitpasses

through.(a)Achokepacketthataffectsonlythesource.(b)Hop-by-Hopchokepacket.RandomearlydetectionByhavingroutersdroppackets

beforethesituationhasbecomehopeless(hencethe''early''inthename),theideaisthatthereistimeforactiontobetakenbeforeitistoolate.Todeterminewhent

ostartdiscarding,routersmaintainarunningaverageoftheirqueuelengths.Whentheaveragequeuelengthonsomeline

exceedsathreshold,thelinkissaidtobecongestionandasmallfractionofthepacketsaredroppedatrandomJitterCont

rolQualityofServiceAstreamofpacketsfromasourcetoadestinationiscalledaflow.Inaconnection-orientednetwork,allthepack

etsbelongingtoaflowfollowthesameroute;inaconnectionlessnetwork,theymayfollowdifferentroutes.Theneedsofeachflowcanbecharacteriz

edbyfourprimaryparameters:reliability,delay,jitter,andbandwidth.TogetherthesedeterminetheQoS(Quality

ofService)theflowrequires.TrafficShapingTrafficshapingisaboutregulatingtheaveragerateofdatatransmission.

Thegoalistoallowapplicationstotransmitawidevarietyoftrafficthatsuitstheirneeds,includesomebursts.TheLeakyBuc

ketAlgorithmImagineabucketwithasmallholeinthebottom.Nomattertherateatwhichwaterentersthebucket,theoutflowisataconstantrate,,

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

佳工作速率不超过2MB/s。数据以每秒中有40ms，1MB的突发数据输入。为平稳输出，使用一个ρ=2MB/s，容积C=1MB的漏桶。a图为漏桶的输入，b图为漏桶的输出。TheTokenBucketAlgorithmThe

leakybucketalgorithmenforcesarigidoutputpatternattheaveragerate,nomatterhowburstythetrafficis.Formanyapplications,itisbettertoa

llowtheoutputtospeedupsomewhatwhenlargeburstsarrive,soamoreflexiblealgorithmisneeded,preferablyonethatneverlose

sdata.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•flowspecifi

cation(流说明)：-能够准确描述规范化的流参数。-从源端到目的端沿途路由器可修改这些参数。举例：-令牌桶速率：长时间间隔的平均输入桶的每秒字节数。-令牌桶容量。-峰值数据速率：限制短暂时间间隔发送速率。-最小、最大分组长度：含头部。Pa

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

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

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

atenatedVirtualCircuits􀁺ConnectionlessInternetworking􀁺Tunneling􀁺FragmentationConnectingNetworksHowNetworksDifferHowNet

worksCanBeConnected􀁺Repeatersatthephysicallayerforboostingsignals.􀁺Bridgestomaketheinterconnectionatthedatalinklayer.􀁺Multiproto

colroutersforforwarding,andpossiblysplittinguppackets(bridgescan’tdothelatter).􀁺Transportgatewaysforinterfacingbetweentwotr

ansportconnections.􀁺Applicationgateways,translatemessagesemantics.ConcatenatedVirtualCircuitsConnectionlessinter

networkingHavethenetworklayerofferonlydatagramservices:unreliable,unorderedpacketflow.Mainproblem:Addressing–differen

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

networkprotocolTunnelingWecansolvealotoftheinternetworkingproblemswhenwecanassumethatthesourceanddestinatio

nofthesametypeofnetworkisconnectedbydifferentnetwork,weneedonlytotunnelpacketsthroughintermediatenetworks.Fra

gmentationFragmentation:Differentnetworksmayimposedifferentmaximumpacketsizes.Thismeansthatwemayhavetosplitapacketintosmalleroneswhenforwardingi

tthroughanetworkwhosemaximumpacketsizeistoosmallWheretoreassemblethefragments?Gateway:Transparentfragmentation􀁺The

destinationhost:NontransparentfragmentationTheNetworkLayerintheInternetTheInternetProtocol(IP)TheInternetisacollectionofmanyne

tworksconnectedtogetherbyabunchofbackbones.ThegluethatholdsthewholeInternettogetheristhenetworklayerprotocol,IP(InternetProtocol).TheIPv4Header

TheIPv4Header(2)AddressesIPAddresses(2)Subnets(1)􀁺Allhostsonthesamenetworkmusthavethesamenetworknumber.Thismaycauseasingleorganization

toacquireseveralclassesofaddressesformultipleLANs.􀁺Useasinglenetworkaddressfortheentireorganization,andinternallydividethehostaddressspaceint

oasubnetaddressandahostid􀁺Toimplementsubnetting,themainrouterneedsasubnetmaskthatindicateCIDR–ClasslessInt

erDomainRoutingCIDR–ExamplesCIDR–AggregateEntriesFormanyroutersoutside194.24.0.0,theonlythingtheyseeisthat

thereare(atleast)3networkaddressesforwhichpacketsfollowthesameroute.Theseentriescanbeaggregatedintoasingleentry194.24.0.

0/19withasinglesubmaskof19/131/0bits.