交通管理的概念、问题与挑战课件

1、Traffic managementConcepts, Issues and ChallengesS. KeshavCornell UniversityACM SIGCOMM 97, CannesSeptember 15th 199711/14/961An exampleExecutive participating in a worldwide videoconferenceProceedings are videotaped and stored in an archiveEdited and placed on a Web siteAccessed later by others Dur

2、ing conferenceSends email to an assistantBreaks off to answer a voice callWhat this requiresFor videosustained bandwidth of at least 64 kbpslow loss rateFor voicesustained bandwidth of at least 8 kbpslow loss rateFor interactive communicationlow delay ( S/a, user is worse off! (reflects time wasted)

3、Assumes linear decrease in utilityS and a can be experimentally determinedSocial welfareSuppose 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 increasin

4、g the utility of one user must necessarily 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 profitExampleAssumeSingle switch,

5、 each user imposes load 0.4 As utility: 4 - dBs 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 util

6、ity, but may pay less for service Some economic principlesA single network 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 u

7、ser requirements BUT need to know what users want (signaling)For typical utility functions, welfare increases more than linearly with increase in capacityindividual users see smaller overall fluctuationscan increase welfare by increasing capacityPrinciples appliedA single wire that carries both voic

8、e and data is more efficient than separate wires for voice and dataADSLIP 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

9、 somehow mark and isolate low-delay trafficThe two campsCan increase 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 so

10、me traffic, we need to give all traffic low delay, even if it doesnt need itBut, perhaps, we can use the money spent on traffic management to increase capacityWe will study traffic management, assuming that it matters!Traffic classesNetworks should match offered service to source requirements (corre

11、sponds 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 offeringsTraffic cl

12、asses - detailsA 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

13、 multiplayer gamesBest-effortsend and prayclosed-loop flow controle.g. email, net newsTraffic subclasses (roadmap)ATM Forum based on sensitivity to bandwidthGS CBR, VBRBEABR, UBRIETFbased on sensitivity to delayGSintolerant tolerantBEinteractive burstinteractive bulkasynchronous bulkATM Forum GS sub

14、classesConstant Bit Rate (CBR)constant, cell-smooth trafficmean and peak rate are the samee.g. telephone call evenly sampled and uncompressedconstant bandwidth, variable qualityVariable Bit Rate (VBR)long term average with occasional burststry to minimize delaycan tolerate loss and higher delays tha

15、n CBRe.g. compressed video or audio with constant quality, variable bandwidthATM Forum BE subclassesAvailable Bit Rate (ABR)users get whatever is availablezero loss if network signals (in RM cells) are obeyedno guarantee on delay or bandwidthUnspecified Bit Rate (UBR)like ABR, but no feedbackno guar

16、antee on losspresumably cheaperIETF GS subclassesTolerant GSnominal mean delay, but can tolerate “occasional” variationnot specified what this means exactlyuses controlled-load service book uses older terminology (predictive)even at “high loads”, admission control assures a source that its service “

17、does not suffer”it really is this imprecise!Intolerant GSneed a worst case delay boundequivalent to CBR+VBR in ATM Forum modelIETF BE subclassesInteractive burstbounded asynchronous service, where bound is qualitative, but pretty tighte.g. paging, messaging, emailInteractive bulkbulk, but a human is

18、 waiting for the resulte.g. FTPAsynchronous bulkjunk traffice.g netnewsSome points to ponderThe only thing out there is CBR and asynchronous bulk!These are application requirements. There are also organizational requirements (link sharing)Users needs QoS for other things too!billingprivacyreliabilit

19、y and availabilityTime scalesSome actions are taken once per calltell network about 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 v

20、ery rapidly,during the data transferschedulingpolicing and regulationTraffic management mechanisms must deal with a range of traffic classes at a range of time scalesSummary of mechanisms at each time scaleLess than one round-trip-time (cell-level)Scheduling and buffer managementRegulation and polic

21、ingPolicy routing (datagram networks)One or more round-trip-times (burst-level)Feedback flow controlRetransmissionRenegotiationOutlineEconomic principlesTraffic classesMechanisms at each time scaleFaster than one RTTscheduling and buffer managementregulation and policingpolicy routingOne RTTSessionD

22、ay Weeks to monthsSome open problemsScheduling and buffer management11/14/9630OutlineWhat is scheduling?Why we need itRequirements of a scheduling disciplineFundamental choicesScheduling best effort connectionsScheduling guaranteed-service connectionsPacket drop strategiesSchedulingSharing always re

23、sults in contentionA scheduling discipline resolves contention: whos next?Key to fairly sharing resources and providing performance guaranteesComponentsA scheduling discipline does two things:decides service ordermanages queue of service requestsExample:consider queries awaiting web serverscheduling

24、 discipline decides service orderand also if some query should be ignoredWhere?Anywhere where contention may occurAt every layer of protocol stackUsually studied at network layer, at output queues of switchesOutlineWhat is schedulingWhy we need itRequirements of a scheduling disciplineFundamental ch

25、oicesScheduling best effort connectionsScheduling guaranteed-service connectionsPacket drop strategiesWhy do we need one?Because future applications need itRecall that we expect two types of future applicationsbest-effort (adaptive, non-real time)e.g. email, some types of file transferguaranteed ser

26、vice (non-adaptive, real time)e.g. packet voice, interactive video, stock quotesWhat can scheduling disciplines do?Give different users different qualities of serviceExample of passengers waiting to board a planeearly boarders spend less time waitingbumped off passengers are lost!Scheduling discipli

27、nes can allocatebandwidthdelaylossThey also determine how fair the network isOutlineWhat is schedulingWhy we need itRequirements of a scheduling disciplineFundamental choicesScheduling best effort connectionsScheduling guaranteed-service connectionsPacket drop strategiesRequirementsAn ideal scheduli

28、ng disciplineis easy to implementis fairprovides performance boundsallows easy admission control decisionsto decide whether a new flow can be allowedRequirements: 1. Ease of implementationScheduling discipline has to make a decision once every few microseconds!Should be implementable in a few instru

29、ctions or hardwarefor hardware: critical constraint is VLSI spaceWork per packet should scale less than linearly with number of active connectionsRequirements: 2. FairnessScheduling discipline allocates a resourceAn allocation is fair if it satisfies min-max fairnessIntuitivelyeach connection gets n

30、o more than what it wantsthe excess, if any, is equally sharedABCABCTransfer half of excessUnsatisfied demandFairness (cont.)Fairness is intuitively a good ideaBut it also provides protectiontraffic hogs cannot overrun othersautomatically builds firewalls around heavy usersFairness is a global objec

31、tive, but scheduling is localEach endpoint must restrict its flow to the smallest fair allocationDynamics + delay = global fairness may never be achievedRequirements: 3. Performance boundsWhat is it?A way to obtain a desired level of serviceCan be deterministic or statisticalCommon parameters areban

32、dwidthdelaydelay-jitter lossBandwidthSpecified 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 peak ratePeak is measured over a small intervalAverage is asymptote as intervals in

33、crease without boundDelay and delay-jitterBound on some parameter of the delay distribution curveReqments: 4. Ease of admission controlAdmission control needed to provide QoSOverloaded resource cannot guarantee performanceChoice of scheduling discipline affects ease of admission control algorithmOut

34、lineWhat is schedulingWhy we need itRequirements of a scheduling disciplineFundamental choicesScheduling best effort connectionsScheduling guaranteed-service connectionsPacket drop strategiesFundamental choices1. Number of priority levels2. Work-conserving vs. non-work-conserving3. Degree of aggrega

35、tion4. Service order within a levelChoices: 1. PriorityPacket is served from a given priority level only if no packets exist at higher levels (multilevel priority with exhaustive service)Highest level gets lowest delayWatch out for starvation!Usually map priority levels to delay classesLow bandwidth

36、 urgent messagesRealtimeNon-realtime PriorityChoices: 2. Work conserving vs. non-work-conservingWork conserving discipline is never idle when packets await serviceWhy bother with non-work conserving?Non-work-conserving disciplinesKey conceptual idea: delay packet till eligibleReduces delay-jitter =

37、fewer buffers in networkHow to choose eligibility time?rate-jitter regulatorbounds maximum outgoing ratedelay-jitter regulatorcompensates for variable delay at previous hopDo we need non-work-conservation?Can remove delay-jitter at an endpoint insteadbut also reduces size of switch buffersIncreases

38、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 biggest problemChoices: 3. Degree of aggregationMore aggregationless statecheaper s

39、maller VLSIless to advertiseBUT: less individualizationSolutionaggregate to a class, members of class have same performance requirementno protection within classChoices: 4. Service within a priority levelIn order of arrival (FCFS) or in order of a service tagService tags = can arbitrarily reorder qu

40、eueNeed to sort queue, which can be expensiveFCFSbandwidth hogs win (no protection)no guarantee on delaysService tagswith appropriate choice, both protection and delay bounds possibleOutlineWhat is schedulingWhy we need itRequirements of a scheduling disciplineFundamental choicesScheduling best effo

41、rt connectionsScheduling guaranteed-service connectionsPacket drop strategiesScheduling best-effort connectionsMain requirement is fairnessAchievable using Generalized processor sharing (GPS)Visit each non-empty queue in turnServe infinitesimal from eachWhy is this fair?How can we give weights to co

42、nnections?More on GPSGPS 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: work(I,a,b) = # bits transmitted for connection I in time a,bAbsolute fa

43、irness bound for discipline SMax (work_GPS(I,a,b) - work_S(I, a,b)Relative fairness bound for discipline SMax (work_S(I,a,b) - work_S(J,a,b)What next?We cant implement GPSSo, lets see how to emulate itWe want to be as fair as possibleBut also have an efficient implementationWeighted round robinServe

44、 a packet from each non-empty queue in turnUnfair if packets are of different length or weights are not equalDifferent weights, fixed packet sizeserve more than one packet per visit, after normalizing to obtain integer weightsDifferent weights, variable size packetsnormalize weights by mean packet s

45、izee.g. weights 0.5, 0.75, 1.0, mean packet sizes 50, 500, 1500normalize weights: 0.5/50, 0.75/500, 1.0/1500 = 0.01, 0.0015, 0.000666, normalize again 60, 9, 4Problems with Weighted Round RobinWith variable size packets and different weights, need to know mean packet size in advanceCan be unfair for

46、 long periods of timeE.g.T3 trunk with 500 connections, each connection has mean packet length 500 bytes, 250 with weight 1, 250 with weight 10Each packet takes 500 * 8/45 Mbps = 88.8 microsecondsRound time =2750 * 88.8 = 244.2 msWeighted Fair Queueing (WFQ)Deals better with variable size packets an

47、d weightsGPS is fairest disciplineFind the finish time of a packet, had we been doing GPSThen serve packets in order of their finish timesWFQ: first cutSuppose, in each round, the server served one bit from each active connectionRound number is the number of rounds already completedcan be fractional

48、If a packet of length p arrives to an empty queue when the round number is R, it will complete service when the round number is R + p = finish number is R + pindependent of the number of other connections!If a packet arrives to a non-empty queue, and the previous packet has a finish number of f, the

49、n the packets finish number is f+pServe packets in order of finish numbersA catchA queue may need to be considered non-empty even if it has no packets in ite.g. packets of length 1 from connections A and B, on a link of speed 1 bit/secat time 1, packet from A served, round number = 0.5A has no packe

50、ts in its queue, yet should be considered non-empty, because a packet arriving to it at time 1 should have finish number 1+ p A connection is active if the last packet served from it, or in its queue, has a finish number greater than the current round numberWFQ continuedTo sum up, assuming we know t

51、he current round number RFinish number of packet of length pif arriving to active connection = previous finish number + pif arriving to an inactive connection = R + p(How should we deal with weights?)To implement, we need to know two things:is connection active?if not, what is the current round numb

52、er?Answer to both questions depends on computing the current round number (why?)WFQ: computing the round numberNaively: round number = number of rounds of service completed so farwhat if a server has not served all connections in a round?what if new conversations join in halfway through a round?Rede

53、fine round number as a real-valued variable that increases at a rate inversely proportional to the number of currently active connectionsthis takes care of both problems (why?)With this change, WFQ emulates GPS instead of bit-by-bit RRProblem: iterated deletionA sever recomputes round number on each

54、 packet arrivalAt any recomputation, the number of conversations can go up at most by one, but can go down to zero= overestimationTrickuse previous count to compute round numberif this makes some conversation inactive, recomputerepeat until no conversations become inactiveRound number# active conver

55、sationsWFQ implementationOn packet arrival:use source + destination address (or VCI) to classify it and look up finish number of last packet served (or waiting to be served)recompute round numbercompute finish numberinsert in priority queue sorted by finish numbersif no space, drop the packet with l

56、argest finish numberOn service completionselect the packet with the lowest finish numberAnalysisUnweighted case:if GPS has served x bits from connection A by time tWFQ would have served at least x - P bits, where P is the largest possible packet in the networkWFQ could send more than GPS would = abs

57、olute fairness bound PTo reduce bound, choose smallest finish number only among packets that have started service in the corresponding GPS system (WF2Q)requires a regulator to determine eligible packetsEvaluationProslike GPS, it provides protectioncan obtain worst-case end-to-end delay boundgives us

58、ers incentive to use intelligent flow control (and also provides rate information implicitly)Consneeds per-connection stateiterated deletion is complicatedrequires a priority queueOutlineWhat is schedulingWhy we need itRequirements of a scheduling disciplineFundamental choicesScheduling best effort

59、connectionsScheduling guaranteed-service connectionsPacket drop strategiesScheduling guaranteed-service connectionsWith best-effort connections, goal is fairnessWith guaranteed-service connectionswhat performance guarantees are achievable?how easy is admission control?We now study some scheduling di

60、sciplines that provide performance guaranteesWFQTurns out that WFQ also provides performance guaranteesBandwidth boundratio of weights * link capacitye.g. connections with weights 1, 2, 7; link capacity 10connections get at least 1, 2, 7 units of b/w eachEnd-to-end delay boundassumes that the connec