交通控制課件

2024/4/17交通控制ComputerNetworksChapter12:CongestioninDataNetworks數(shù)據(jù)網(wǎng)絡(luò)中的擁塞WhatIsCongestion?CongestionoccurswhenthenumberofpacketsbeingtransmittedthroughthenetworkapproachesthepackethandlingcapacityofthenetworkCongestioncontrolaimstokeepnumberofpacketsbelowlevelatwhichperformancefallsoffdramaticallyDatanetworkisanetworkofqueuesGenerally80%utilizationiscriticalFinitequeuesmeandatamaybelostQueuesataNode到用戶到用戶到其他節(jié)點到其他節(jié)點EffectsofCongestionPacketsarrivingarestoredatinputbuffersRoutingdecisionmadePacketmovestooutputbufferPacketsqueuedforoutputtransmittedasfastaspossibleStatisticaltimedivisionmultiplexingIfpacketsarrivetoofasttoberouted,ortobeoutput,bufferswillfill1.Candiscardpackets2.CanuseflowcontrolCanpropagatecongestionthroughnetworkInteractionofQueuesIdeal

Performance歸一化負(fù)荷歸一化負(fù)荷歸一化負(fù)荷歸一化吞吐量遲延網(wǎng)絡(luò)能力PracticalPerformanceIdealassumesinfinitebuffersandnooverheadBuffersarefiniteOverheadsoccurinexchangingcongestioncontrolmessagesEffectsof

Congestion-

NoControl吞吐率下降原因資源浪費緩沖區(qū)存貯容量bufferstoragecapacity線路帶寬channelbandwidth緩沖區(qū)存貯容量即使線路有富余，分組也無法通過。BSB’AA’

C=10C=1C=1C=10.81.81.1吞吐率重傳模型損耗模型線路帶寬多路共享信道上常見總線局域網(wǎng)和分組無線網(wǎng)絡(luò)信道負(fù)載很重時：競爭信道的時間多于有效傳輸數(shù)據(jù)的時間，從而造成信道容量的極大浪費。Mechanismsfor

CongestionControl隱式顯式Backpressure：反壓IfnodebecomescongesteditcanslowdownorhaltflowofpacketsfromothernodesMaymeanthatothernodeshavetoapplycontrolonincomingpacketratesPropagatesbacktosourceCanrestricttologicalconnectionsgeneratingmosttrafficUsedinconnectionorientedthatallowhopbyhopcongestioncontrol(e.g.X.25)NotusedinATMnorframerelayOnlyrecentlydevelopedforIPChokePacket：阻流分組ControlpacketGeneratedatcongestednodeSenttosourcenodee.g.ICMPsourcequenchFromrouterordestinationSourcecutsbackuntilnomoresourcequenchmessageSentforeverydiscardedpacket,oranticipatedRathercrudemechanismImplicitCongestionSignaling1.Transmissiondelaymayincreasewithcongestion2.PacketmaybediscardedSourcecandetecttheseasimplicitindicationsofcongestionUsefulonconnectionless(datagram)networkse.g.IPbased(TCPincludescongestionandflowcontrol-seechapter17)UsedinframerelayLAPFExplicitCongestionSignalingNetworkalertsendsystemsofincreasingcongestionEndsystemstakestepstoreduceofferedloadBackwardsCongestionavoidanceinoppositedirectiontopacketrequiredForwardsCongestionavoidanceinsamedirectionaspacketrequiredSOURCENODENODENODEUSERCategoriesofExplicitSignalingBinary—二進(jìn)制AbitsetinapacketindicatescongestionCreditbased—基于信用值的IndicateshowmanypacketssourcemaysendCommonforendtoendflowcontrolRatebased—基于速率Supplyexplicitdataratelimite.g.ATMTrafficManagement：通信量管理Fairness—公平性Qualityofservice—服務(wù)質(zhì)量MaywantdifferenttreatmentfordifferentconnectionsReservations—預(yù)約e.g.ATMTrafficcontractbetweenuserandnetworkCongestionControlinPacketSwitchedNetworksSendcontrolpackettosomeorallsourcenodesRequiresadditionaltrafficduringcongestionRelyonroutinginformationMayreacttooquicklyEndtoendprobepacketsAddstooverheadAddcongestioninfotopacketsastheycrossnodesEitherbackwardsorforwardsLeakyBucketAlgorithm漏桶算法LeakybucketalgorithmLeakybucketalgorithmEachhostisconnectedtothenetworkbyaninterfacecontainingaleakybucketThatisafiniteinternalqueueIfapacketarrivesatthequeuewhenitisfull,thepacketisdiscarded.Asingle-serverqueueingsystemwithconstantservicetimeThiscanbeenforcedbytheinterfacecardorbytheoperatingsystemExampleBucket:C=1MB;ρ=2MB/sHost:ρ=25MB/s;t=40msTokenBucketAlgorithmTheleakybucketalgorithmenforcesarigidoutputpatternattheaveragerate,nomatterhowburstythetrafficis.ThetokenbucketalgorithmallowstheoutputtospeedupsomewhatwhenlargeburstsarriveTheleakybucketholdstokens,generatedbyaclockattherateofonetokenevery?Tsec.Tokenbucketalgorithm死鎖---deadlock同時等待已經(jīng)分配的資源獲得釋放，并且對資源的等待和占用形成環(huán)路條件。網(wǎng)絡(luò)資源：緩沖區(qū)三種死鎖類型：

直接存貯---轉(zhuǎn)發(fā)死鎖

間接存貯---轉(zhuǎn)發(fā)死鎖

重裝配死鎖

直接存貯---轉(zhuǎn)發(fā)死鎖禁止被單方向占用全部緩沖區(qū)NodeANodeB

間接存貯---轉(zhuǎn)發(fā)死鎖NodeBNodeANodeC結(jié)構(gòu)化緩沖池使用規(guī)則：1,2,…K,…N表示分組走過的跳數(shù)高級可以占用低級緩沖區(qū)K類以下緩沖區(qū)用完后，到達(dá)的所有<=K級的分組丟棄N類…K類…2類1類公用緩沖池0類

重裝配死鎖C3C2B4A2B1C1B2B3A1A3A4AFJHKEDCB節(jié)點1節(jié)點2節(jié)點3節(jié)點1節(jié)點2節(jié)點3主機1主機2主機重排序死鎖裝配緩沖區(qū)死鎖交通控制的分級跳步級進(jìn)出口級網(wǎng)絡(luò)訪問級網(wǎng)絡(luò)訪問級會話級ARPANETTraffic--最小分配最大限制總共40個緩沖區(qū)每條鏈路：1輸出2輸入主機端口10個裝配緩沖區(qū)剩余共享區(qū)，限制如下：輸出<=8裝配緩沖區(qū)<=20總的存貯轉(zhuǎn)發(fā)緩沖區(qū)數(shù)<=20多于分組丟棄主機共享緩沖池節(jié)點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