交通控制课件

2024/4/17交通控制ComputerNetworksChapter12:CongestioninDataNetworks数据网络中的拥塞WhatIsCongestion?CongestionoccurswhenthenumberofpacketsbeingtransmittedthroughthenetworkapproachesthepackethandlingcapacityofthenetworkCongestioncontrolaimstokeepnumberofpacketsbelowlevelatwhichperformancefallsoffdramaticallyDatanetworkisanetworkofqueuesGenerally80%utilizationiscriticalFinitequeuesmeandatamaybelostQueuesataNode到用户到用户到其他节点到其他节点EffectsofCongestionPacketsarrivingarestoredatinputbuffersRoutingdecisionmadePacketmovestooutputbufferPacketsqueuedforoutputtransmittedasfastaspossibleStatisticaltimedivisionmultiplexingIfpacketsarrivetoofasttoberouted,ortobeoutput,bufferswillfill1.Candiscardpackets2.CanuseflowcontrolCanpropagatecongestionthroughnetworkInteractionofQueuesIdeal

Performance归一化负荷归一化负荷归一化负荷归一化吞吐量迟延网络能力PracticalPerformanceIdealassumesinfinitebuffersandnooverheadBuffersarefiniteOverheadsoccurinexchangingcongestioncontrolmessagesEffectsof

Congestion-

NoControl吞吐率下降原因资源浪费缓冲区存贮容量bufferstoragecapacity线路带宽channelbandwidth缓冲区存贮容量即使线路有富余，分组也无法通过。BSB’AA’

C=10C=1C=1C=10.81.81.1吞吐率重传模型损耗模型线路带宽多路共享信道上常见总线局域网和分组无线网络信道负载很重时：竞争信道的时间多于有效传输数据的时间，从而造成信道容量的极大浪费。Mechanismsfor

CongestionControl隐式显式Backpressure：反压IfnodebecomescongesteditcanslowdownorhaltflowofpacketsfromothernodesMaymeanthatothernodeshavetoapplycontrolonincomingpacketratesPropagatesbacktosourceCanrestricttologicalconnectionsgeneratingmosttrafficUsedinconnectionorientedthatallowhopbyhopcongestioncontrol(e.g.X.25)NotusedinATMnorframerelayOnlyrecentlydevelopedforIPChokePacket：阻流分组ControlpacketGeneratedatcongestednodeSenttosourcenodee.g.ICMPsourcequenchFromrouterordestinationSourcecutsbackuntilnomoresourcequenchmessageSentforeverydiscardedpacket,oranticipatedRathercrudemechanismImplicitCongestionSignaling1.Transmissiondelaymayincreasewithcongestion2.PacketmaybediscardedSourcecandetecttheseasimplicitindicationsofcongestionUsefulonconnectionless(datagram)networkse.g.IPbased(TCPincludescongestionandflowcontrol-seechapter17)UsedinframerelayLAPFExplicitCongestionSignalingNetworkalertsendsystemsofincreasingcongestionEndsystemstakestepstoreduceofferedloadBackwardsCongestionavoidanceinoppositedirectiontopacketrequiredForwardsCongestionavoidanceinsamedirectionaspacketrequiredSOURCENODENODENODEUSERCategoriesofExplicitSignalingBinary—二进制AbitsetinapacketindicatescongestionCreditbased—基于信用值的IndicateshowmanypacketssourcemaysendCommonforendtoendflowcontrolRatebased—基于速率Supplyexplicitdataratelimite.g.ATMTrafficManagement：通信量管理Fairness—公平性Qualityofservice—服务质量MaywantdifferenttreatmentfordifferentconnectionsReservations—预约e.g.ATMTrafficcontractbetweenuserandnetworkCongestionControlinPacketSwitchedNetworksSendcontrolpackettosomeorallsourcenodesRequiresadditionaltrafficduringcongestionRelyonroutinginformationMayreacttooquicklyEndtoendprobepacketsAddstooverheadAddcongestioninfotopacketsastheycrossnodesEitherbackwardsorforwardsLeakyBucketAlgorithm漏桶算法LeakybucketalgorithmLeakybucketalgorithmEachhostisconnectedtothenetworkbyaninterfacecontainingaleakybucketThatisafiniteinternalqueueIfapacketarrivesatthequeuewhenitisfull,thepacketisdiscarded.Asingle-serverqueueingsystemwithconstantservicetimeThiscanbeenforcedbytheinterfacecardorbytheoperatingsystemExampleBucket:C=1MB;ρ=2MB/sHost:ρ=25MB/s;t=40msTokenBucketAlgorithmTheleakybucketalgorithmenforcesarigidoutputpatternattheaveragerate,nomatterhowburstythetrafficis.ThetokenbucketalgorithmallowstheoutputtospeedupsomewhatwhenlargeburstsarriveTheleakybucketholdstokens,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多于分组丢弃主机共享缓冲池节点ATMTrafficManagementHighspeed,smallcellsize,limitedoverheadbitsStillevolvingRequirementsMajorityoftrafficnotamenabletoflowcontrolFeedbackslowduetoreducedtransmissiontimecomparedwithpropagationdelayWiderangeofapplicationdemandsDifferenttrafficpatternsDifferentnetworkservicesHighspeedswitchingandtransmissionincreasesvolatilityLatency/SpeedEffectsATM150Mbps~2.8x10-6secondstoinsertsinglecellTimetotraversenetworkdependsonpropagationdelay,switchingdelayAssumepropagationattwo-thirdsspeedoflightIfsourceanddestinationonoppositesidesofUSA,propagationtime~48x10-3secondsGivenimplicitcongestioncontrol,bythetimedroppedcellnotificationhasreachedsource,7.2x106bitshavebeentransmittedSo,thisisnotagoodstrategyforATMCellDelayVariationForATMvoice/video,dataisastreamofcellsDelayacrossnetworkmustbeshortRateofdeliverymustbeconstantTherewillalwaysbesomevariationintransitDelaycelldeliverytoapplicationsothatconstantbitratecanbemaintainedtoapplicationTimeRe-assemblyofCBRCellsNetworkContributionto

CellDelayVariationPacketswitchednetworksQueuingdelaysRoutingdecisiontimeFramerelayAsabovebuttolesserextentATMLessthanframerelayATMprotocoldesignedtominimizeprocessingoverheadsatswitchesATMswitcheshaveveryhighthroughputOnlynoticeabledelayisfromcongestionMustnotacceptloadthatcausescongestionCellDelayVariation

AtTheUNIApplicationproducesdataatfixedrateProcessingatthreelayersofATMcausesdelayInterleavingcellsfromdifferentconnectionsOperationandmaintenancecellinterleavingIfusingsynchronousdigitalhierarchyframes,theseareinsertedatphysicallayerCannotpredictthesedelaysOriginsofCellDelayVariationTrafficandCongestion

ControlFrameworkATMlayertrafficandcongestioncontrolshouldsupportQoSclassesforallforeseeablenetworkservicesShouldnotrelyonAALprotocolsthatarenetworkspecific,norhigherlevelapplicationspecificprotocolsShouldminimizenetworkandendtoendsystemcomplexityTimingsConsideredCellinsertiontimeRoundtrippropagationtimeConnectiondurationLongtermDeterminewhetheragivennewconnectioncanbeaccommodatedAgreeperformanceparameterswithsubscriberTrafficManagementandCongestionControlTechniquesResourcemanagementusingvirtualpathsConnectionadmissioncontrolUsageparametercontrolSelectivecelldiscardTrafficshapingResourceManagementUsingVirtualPathsSeparatetrafficflowaccordingtoservicecharacteristicsUsertouserapplicationUsertonetworkapplicationNetworktonetworkapplicationConcernwith:CelllossratioCelltransferdelayCelldelayvariationConfigurationof

VCCsandVPCsAllocatingVCCswithinVPCAllVCCswithinVPCshouldexperiencesimilarnetworkperformanceOptionsforallocation:AggregatepeakdemandStatisticalmultiplexingConnectionAdmissionControlFirstlineofdefenceUserspecifiestrafficcharacteristicsfornewconnection(VCCorVPC)byselectingaQoSNetworkacceptsconnectiononlyifitcanmeetthedemandTrafficcontractPeakcellrateCelldelayvariationSustainablecellrateBursttoleranceUsageParameterControlMonitorconnectiontoensuretrafficcinformstocontractProtectionofnetworkresourcesfromoverloadbyoneconnectionDoneonVCCandVPCPeakcellrateandcelldelayvariationSustainablecellrateandbursttoleranceDiscardcellsthatdonotconformtotrafficcontractCalledtrafficpolicingTrafficShapingSmoothouttrafficflowandreducecellclumpingTokenbucketTokenBucketATM-ABRTrafficManagementSomeapplications(Web,filetransfer)donothavewelldefinedtrafficcharacteristicsBesteffortsAllowtheseapplicationstoshareunusedcapacityIfcongestionbuilds,cellsaredroppedClosedloopcontrolABRconnectionsshareavailablecapacitySharevariesbetweenminimumcellrate(MCR)andpeakcellrate(PCR)ARBflowlimitedtoavailablecapacitybyfeedbackBuffersabsorbexcesstrafficduringfeedbackdelayLowcelllossFeedbackMechanismsTransmissionratecharacteristics:AllowedcellrateMinimumcellratePeakcellrateInitialcellrateStartwithACR=ICRAdjustACRbasedonfeedbackfromnetworkResourcemanagementcellsCongestionindicationbitNoincreasebitExplicitcellratefieldVariationsinAllowedCell