《交通管理的概念、问题与挑.ppt》由会员分享，可在线阅读，更多相关《交通管理的概念、问题与挑.ppt（230页珍藏版）》请在三一办公上搜索。
1、Traffic managementConcepts,Issues and Challenges,S.KeshavCornell UniversityACM SIGCOMM 97,CannesSeptember 15th 1997,An example,Executive participating in a worldwide videoconferenceProceedings are videotaped and stored in an archiveEdited and placed on a Web siteAccessed later by others During confe
2、renceSends email to an assistantBreaks off to answer a voice call,What this requires,For videosustained bandwidth of at least 64 kbpslow loss rateFor voicesustained bandwidth of at least 8 kbpslow loss rateFor interactive communicationlow delay(100 ms one-way)For playbacklow delay jitterFor email an
3、d archivingreliable bulk transport,What if,A million executives were simultaneously accessing the network?What capacity should each trunk have?How should packets be routed?(Can we spread load over alternate paths?)How can different traffic types get different services from the network?How should eac
4、h endpoint regulate its load?How should we price the network?These types of questions lie at the heart of network design and operation,and form the basis for traffic management.,Traffic management,Set of policies and mechanisms that allow a network to efficiently satisfy a diverse range of service r
5、equestsTension is between diversity and efficiencyTraffic management is necessary for providing Quality of Service(QoS)Subsumes congestion control(congestion=loss of efficiency),Why is it important?,One of the most challenging open problems in networkingCommercially importantAOL burnoutPerceived rel
6、iability(necessary for infrastructure)Capacity sizing directly affects the bottom lineAt the heart of the next generation of data networksTraffic management=Connectivity+Quality of Service,Outline,Economic principlesTraffic classesTime scalesMechanisms Some open problems,Basics:utility function,User
7、s are assumed to have a utility function that maps from a given quality of service to a level of satisfaction,or utilityUtility functions are private informationCannot compare utility functions between usersRational users take actions that maximize their utilityCan determine utility function by obse
8、rving preferences,Example,Let u=S-a tu=utility from file transferS=satisfaction when transfer infinitely fastt=transfer timea=rate at which satisfaction decreases with timeAs transfer time increases,utility decreasesIf t S/a,user is worse off!(reflects time wasted)Assumes linear decrease in utilityS
9、 and a can be experimentally determined,Social welfare,Suppose network manager knew the utility function of every userSocial Welfare is maximized when some combination of the utility functions(such as sum)is maximizedAn economy(network)is efficient when increasing the utility of one user must necess
10、arily decrease the utility of anotherAn economy(network)is envy-free if no user would trade places with another(better performance also costs more)Goal:maximize social welfaresubject to efficiency,envy-freeness,and making a profit,Example,AssumeSingle switch,each user imposes load 0.4 As utility:4-d
11、Bs utility:8-2dSame delay to both usersConservation law0.4d+0.4d=C=d=1.25 C=sum of utilities=12-3.75 CIf Bs delay reduced to 0.5C,then As delay=2CSum of utilities=12-3CIncrease in social welfare need not benefit everyoneA loses utility,but may pay less for service,Some economic principles,A single n
12、etwork that provides heterogeneous QoS is better than separate networks for each QoSunused capacity is available to othersLowering delay of delay-sensitive traffic increased welfare can increase welfare by matching service menu to user requirements BUT need to know what users want(signaling)For typi
13、cal utility functions,welfare increases more than linearly with increase in capacityindividual users see smaller overall fluctuationscan increase welfare by increasing capacity,Principles applied,A single wire that carries both voice and data is more efficient than separate wires for voice and dataA
14、DSLIP Phone Moving from a 20%loaded10 Mbps Ethernet to a 20%loaded 100 Mbps Ethernet will still improve social welfareincrease capacity whenever possibleBetter to give 5%of the traffic lower delay than all traffic low delayshould somehow mark and isolate low-delay traffic,The two camps,Can increase
15、welfare either bymatching services to user requirements orincreasing capacity blindlyWhich is cheaper?no one is really sure!small and smart vs.big and dumbIt seems that smarter ought to be betterotherwise,to get low delays for some traffic,we need to give all traffic low delay,even if it doesnt need
16、 itBut,perhaps,we can use the money spent on traffic management to increase capacityWe will study traffic management,assuming that it matters!,Outline,Economic principlesTraffic classesTime scalesMechanisms Some open problems,Traffic classes,Networks should match offered service to source requiremen
17、ts(corresponds to utility functions)Example:telnet requires low bandwidth and low delay utility increases with decrease in delaynetwork should provide a low-delay serviceor,telnet belongs to the low-delay traffic classTraffic classes encompass both user requirements and network service offerings,Tra
18、ffic classes-details,A basic division:guaranteed service and best effortlike flying with reservation or standbyGuaranteed-serviceutility is zero unless app gets a minimum level of service qualitybandwidth,delay,lossopen-loop flow control with admission controle.g.telephony,remote sensing,interactive
19、 multiplayer gamesBest-effortsend and prayclosed-loop flow controle.g.email,net news,GS vs.BE(cont.),Degree of synchronytime scale at which peer endpoints interactGS are typically synchronous or interactiveinteract on the timescale of a round trip timee.g.telephone conversation or telnetBE are typic
20、ally asynchronous or non-interactiveinteract on longer time scalese.g.EmailSensitivity to time and delayGS apps are real-timeperformance depends on wall clockBE apps are typically indifferent to real timeautomatically scale back during overload,Traffic subclasses(roadmap),ATM Forum based on sensitiv
21、ity to bandwidthGS CBR,VBRBEABR,UBR,IETFbased on sensitivity to delayGSintolerant tolerantBEinteractive burstinteractive bulkasynchronous bulk,ATM Forum GS subclasses,Constant Bit Rate(CBR)constant,cell-smooth trafficmean and peak rate are the samee.g.telephone call evenly sampled and uncompressedco
22、nstant bandwidth,variable qualityVariable Bit Rate(VBR)long term average with occasional burststry to minimize delaycan tolerate loss and higher delays than CBRpressed video or audio with constant quality,variable bandwidth,ATM Forum BE subclasses,Available Bit Rate(ABR)users get whatever is availab
23、lezero loss if network signals(in RM cells)are obeyedno guarantee on delay or bandwidthUnspecified Bit Rate(UBR)like ABR,but no feedbackno guarantee on losspresumably cheaper,IETF GS subclasses,Tolerant GSnominal mean delay,but can tolerate“occasional”variationnot specified what this means exactlyus
24、es controlled-load service book uses older terminology(predictive)even at“high loads”,admission control assures a source that its service“does not suffer”it really is this imprecise!Intolerant GSneed a worst case delay boundequivalent to CBR+VBR in ATM Forum model,IETF BE subclasses,Interactive burs
25、tbounded asynchronous service,where bound is qualitative,but pretty tighte.g.paging,messaging,emailInteractive bulkbulk,but a human is waiting for the resulte.g.FTPAsynchronous bulkjunk traffice.g netnews,Some points to ponder,The only thing out there is CBR and asynchronous bulk!These are applicati
26、on requirements.There are also organizational requirements(link sharing)Users needs QoS for other things too!billingprivacyreliability and availability,Outline,Economic principlesTraffic classesTime scalesMechanisms Some open problems,Time scales,Some actions are taken once per calltell network abou
27、t traffic characterization and request resourcesin ATM networks,finding a path from source to destinationOther actions are taken during the call,every few round trip timesfeedback flow controlStill others are taken very rapidly,during the data transferschedulingpolicing and regulationTraffic managem
28、ent mechanisms must deal with a range of traffic classes at a range of time scales,Summary of mechanisms at each time scale,Less than one round-trip-time(cell-level)Scheduling and buffer managementRegulation and policingPolicy routing(datagram networks)One or more round-trip-times(burst-level)Feedba
29、ck flow controlRetransmissionRenegotiation,Summary(cont.),Session(call-level)SignalingAdmission controlService pricingRouting(connection-oriented networks)DayPeak load pricingWeeks or monthsCapacity planning,Outline,Economic principlesTraffic classesMechanisms at each time scaleFaster than one RTTsc
30、heduling and buffer managementregulation and policingpolicy routingOne RTTSessionDay Weeks to monthsSome open problems,Scheduling and buffer management,Outline,What is scheduling?Why we need itRequirements of a scheduling disciplineFundamental choicesScheduling best effort connectionsScheduling guar
31、anteed-service connectionsPacket drop strategies,Scheduling,Sharing always results in contentionA scheduling discipline resolves contention:whos next?Key to fairly sharing resources and providing performance guarantees,Components,A scheduling discipline does two things:decides service ordermanages q
32、ueue of service requestsExample:consider queries awaiting web serverscheduling discipline decides service orderand also if some query should be ignored,Where?,Anywhere where contention may occurAt every layer of protocol stackUsually studied at network layer,at output queues of switches,Outline,What
33、 is schedulingWhy we need itRequirements of a scheduling disciplineFundamental choicesScheduling best effort connectionsScheduling guaranteed-service connectionsPacket drop strategies,Why do we need one?,Because future applications need itRecall that we expect two types of future applicationsbest-ef
34、fort(adaptive,non-real time)e.g.email,some types of file transferguaranteed service(non-adaptive,real time)e.g.packet voice,interactive video,stock quotes,What can scheduling disciplines do?,Give different users different qualities of serviceExample of passengers waiting to board a planeearly boarde
35、rs spend less time waitingbumped off passengers are lost!Scheduling disciplines can allocatebandwidthdelaylossThey also determine how fair the network is,Outline,What is schedulingWhy we need itRequirements of a scheduling disciplineFundamental choicesScheduling best effort connectionsScheduling gua
36、ranteed-service connectionsPacket drop strategies,Requirements,An ideal scheduling disciplineis easy to implementis fairprovides performance boundsallows easy admission control decisionsto decide whether a new flow can be allowed,Requirements:1.Ease of implementation,Scheduling discipline has to mak
37、e a decision once every few microseconds!Should be implementable in a few instructions or hardwarefor hardware:critical constraint is VLSI spaceWork per packet should scale less than linearly with number of active connections,Requirements:2.Fairness,Scheduling discipline allocates a resourceAn alloc
38、ation is fair if it satisfies min-max fairnessIntuitivelyeach connection gets no more than what it wantsthe excess,if any,is equally shared,A,B,C,A,B,C,Transfer half of excess,Unsatisfied demand,Fairness(cont.),Fairness is intuitively a good ideaBut it also provides protectiontraffic hogs cannot ove
39、rrun othersautomatically builds firewalls around heavy usersFairness is a global objective,but scheduling is localEach endpoint must restrict its flow to the smallest fair allocationDynamics+delay=global fairness may never be achieved,Requirements:3.Performance bounds,What is it?A way to obtain a de
40、sired level of serviceCan be deterministic or statisticalCommon parameters arebandwidthdelaydelay-jitter loss,Bandwidth,Specified as minimum bandwidth measured over a prespecified intervalE.g.5Mbps over intervals of 1 secMeaningless without an interval!Can be a bound on average(sustained)rate or pea
41、k ratePeak is measured over a small intervalAverage is asymptote as intervals increase without bound,Delay and delay-jitter,Bound on some parameter of the delay distribution curve,Reqments:4.Ease of admission control,Admission control needed to provide QoSOverloaded resource cannot guarantee perform
42、anceChoice of scheduling discipline affects ease of admission control algorithm,Outline,What is schedulingWhy we need itRequirements of a scheduling disciplineFundamental choicesScheduling best effort connectionsScheduling guaranteed-service connectionsPacket drop strategies,Fundamental choices,1.Nu
43、mber of priority levels2.Work-conserving vs.non-work-conserving3.Degree of aggregation4.Service order within a level,Choices:1.Priority,Packet is served from a given priority level only if no packets exist at higher levels(multilevel priority with exhaustive service)Highest level gets lowest delayWa
44、tch out for starvation!Usually map priority levels to delay classesLow bandwidth urgent messagesRealtimeNon-realtime,Priority,Choices:2.Work conserving vs.non-work-conserving,Work conserving discipline is never idle when packets await serviceWhy bother with non-work conserving?,Non-work-conserving d
45、isciplines,Key conceptual idea:delay packet till eligibleReduces delay-jitter=fewer buffers in networkHow to choose eligibility time?rate-jitter regulatorbounds maximum outgoing ratedelay-jitter regulatorcompensates for variable delay at previous hop,Do we need non-work-conservation?,Can remove dela
46、y-jitter at an endpoint insteadbut also reduces size of switch buffersIncreases mean delaynot a problem for playback applicationsWastes bandwidthcan serve best-effort packets insteadAlways punishes a misbehaving sourcecant have it both waysBottom line:not too bad,implementation cost may be the bigge
47、st problem,Choices:3.Degree of aggregation,More aggregationless statecheaper smaller VLSIless to advertiseBUT:less individualizationSolutionaggregate to a class,members of class have same performance requirementno protection within class,Choices:4.Service within a priority level,In order of arrival(
48、FCFS)or in order of a service tagService tags=can arbitrarily reorder queueNeed to sort queue,which can be expensiveFCFSbandwidth hogs win(no protection)no guarantee on delaysService tagswith appropriate choice,both protection and delay bounds possible,Outline,What is schedulingWhy we need itRequire
49、ments of a scheduling disciplineFundamental choicesScheduling best effort connectionsScheduling guaranteed-service connectionsPacket drop strategies,Scheduling best-effort connections,Main requirement is fairnessAchievable using Generalized processor sharing(GPS)Visit each non-empty queue in turnSer
50、ve infinitesimal from eachWhy is this fair?How can we give weights to connections?,More on GPS,GPS is unimplementable!we cannot serve infinitesimals,only packetsNo packet discipline can be as fair as GPSwhile a packet is being served,we are unfair to othersDegree of unfairness can be boundedDefine:w
