交通控制

交通控制流量控制(flow)---调节传输速率---端对端、节点对节点拥挤（拥塞congestion）控制---保持网络分组数目不超过某一限度，一旦越过这一界限，性能显著下降。防止死锁（deadlock）---资源（缓冲区buffer）死锁ComputerNetworksChapter12:CongestioninDataNetworks数据网络中的拥塞WhatIsCongestion?CongestionoccurswhenthenumberofpacketsbeingtransmittedthroughthenetworkapproachesthepackethandlingcapacityofthenetworkCongestioncontrolaimstokeepnumberofpacketsbelowlevelatwhichperformancefallsoffdramaticallyDatanetworkisanetworkofqueuesGenerally80%utilizationiscriticalFinitequeuesmeandatamaybelostQueuesataNode到用户到用户到其他节点到其他节点EffectsofCongestionPacketsarrivingarestoredatinputbuffersRoutingdecisionmadePacketmovestooutputbufferPacketsqueuedforoutputtransmittedasfastaspossibleStatisticaltimedivisionmultiplexingIfpacketsarrivetoofasttoberouted,ortobeoutput,bufferswillfill1.Candiscardpackets2.CanuseflowcontrolCanpropagatecongestionthroughnetworkInteractionofQueuesIdealPerformance归一化负荷归一化负荷归一化负荷归一化吞吐量迟延网络能力PracticalPerformanceIdealassumesinfinitebuffersandnooverheadBuffersarefiniteOverheadsoccurinexchangingcongestioncontrolmessagesEffectsofCongestion-NoControl吞吐率下降原因资源浪费缓冲区存贮容量bufferstoragecapacity线路带宽channelbandwidth缓冲区存贮容量即使线路有富余，分组也无法通过。BSB’AA’C=10C=1C=1C=10.81.81.1吞吐率重传模型损耗模型线路带宽多路共享信道上常见总线局域网和分组无线网络信道负载很重时：竞争信道的时间多于有效传输数据的时间，从而造成信道容量的极大浪费。MechanismsforCongestionControl隐式显式Backpressure：反压IfnodebecomescongesteditcanslowdownorhaltflowofpacketsfromothernodesMaymeanthatothernodeshavetoapplycontrolonincomingpacketratesPropagatesbacktosourceCanrestricttologicalconnectionsgeneratingmosttrafficUsedinconnectionorientedthatallowhopbyhopcongestioncontrol(e.g.X.25)NotusedinATMnorframerelayOnlyrecentlydevelopedforIPChokePacket：阻流分组ControlpacketGeneratedatcongestednodeSenttosourcenodee.g.ICMPsourcequenchFromrouterordestinationSourcecutsbackuntilnomoresourcequenchmessageSentforeverydiscardedpacket,oranticipatedRathercrudemechanismImplicitCongestionSignaling1.Transmissiondelaymayincreasewithcongestion2.PacketmaybediscardedSourcecandetecttheseasimplicitindicationsofcongestionUsefulonconnectionless(datagram)networkse.g.IPbased(TCPincludescongestionandflowcontrol-seechapter17)UsedinframerelayLAPFExplicitCongestionSignalingNetworkalertsendsystemsofincreasingcongestionEndsystemstakestepstoreduceofferedloadBackwardsCongestionavoidanceinoppositedirectiontopacketrequiredForwardsCongestionavoidanceinsamedirectionaspacketrequiredSOURCENODENODENODEUSERCategoriesofExplicitSignalingBinary—二进制AbitsetinapacketindicatescongestionCreditbased—基于信用值的IndicateshowmanypacketssourcemaysendCommonforendtoendflowcontrolRatebased—基于速率Supplyexplicitdataratelimite.g.ATMTrafficManagement：通信量管理Fairness—公平性Qualityofservice—服务质量MaywantdifferenttreatmentfordifferentconnectionsReservations—预约e.g.ATMTrafficcontractbetweenuserandnetworkCongestionControlinPacketSwitchedNetworksSendcontrolpackettosomeorallsourcenodesRequiresadditionaltrafficduringcongestionRelyonroutinginformationMayreacttooquicklyEndtoendprobepacketsAddstooverheadAddcongestioninfotopacketsastheycrossnodesEitherbackwardsorforwardsLeakyBucketAlgorithm漏桶算法LeakybucketalgorithmLeakybucketalgorithmEachhostisconnectedtothenetworkbyaninterfacecontainingaleakybucketThatisafiniteinternalqueueIfapacketarrivesatthequeuewhenitisfull,thepacketisdiscarded.Asingle-serverqueueingsystemwithconstantservicetimeThiscanbeenforcedbytheinterfacecardorbytheoperatingsystemExampleBucket:C=1MB;ρ=2MB/sHost:ρ=25MB/s;t=40msTokenBucketAlgorithmTheleakybucketalgorithmenforcesarigidoutputpatternattheaveragerate,nomatterhowburstythetrafficis.ThetokenbucketalgorithmallowstheoutputtospeedupsomewhatwhenlargeburstsarriveTheleakybucketholdstokens,generatedbyaclockattherateofonetokenevery∆Tsec.Tokenbucketalgorithm死锁---deadlock同时等待已经分配的资源获得释放，并且对资源的等待和占用形成环路条件。网络资源：缓冲区三种死锁类型：直接存贮---转发死锁间接存贮---转发死锁重装配死锁直接存贮---转发死锁禁止被单方向占用全部缓冲区NodeANodeB间接存贮---转发死锁NodeBNodeANodeC结构化缓冲池使用规则：1,2,…K,…N表示分组走过的跳数高级可以占用低级缓冲区K类以下缓冲区用完后，到达的所有=K级的分组丢弃N类…K类…2类1类公用缓冲池0类重装配死锁C3C2B4A2B1C1B2B3A1A3A4AFJHKEDCB节点1节点2节点3节点1节点2节点3主机1主机2主机重排序死锁装配缓冲区死锁交通控制的分级跳步级进出口级网络访问级网络访问级会话级ARPANETTraffic--最小分配最大限制总共40个缓冲区每条链路：1输出2输入主机端口10个装配缓冲区剩余共享区，限制如下：输出=8装配缓冲区=20总的存贮转发缓冲区数=20多于分组丢弃主机共享缓冲池节点ATMTrafficManagementHighspeed,smallcellsize,limitedoverheadbitsStillevolvingRequirementsMajorityoftrafficnotamenabletoflowcontrolFeedbackslowduetoreducedtransmissiontimecomparedwithpropagationdelayWiderangeofapplicationdemandsDifferenttrafficpatternsDifferentnetworkservicesHighspeedswitchingandtransmissionincreasesvolatilityLatency/SpeedEffectsATM150Mbps~2.8x10-6secondstoinsertsinglecellTimetotraversenetworkdependsonpropagationdelay,switchingdelayAssumepropagationattwo-thirdsspeedoflightIfsourceanddestinationonoppositesidesofUSA,propagationtime~48x10-3secondsGivenimplicitcongestioncontrol,bythetimedroppedcellnotificationhasreachedsource,7.2x106bitshavebeentransmittedSo,thisisnotagoodstrategyforATMCellDelayVariationForATMvoice/video,dataisastreamofcellsDelayacrossnetworkmus