Coordinated Scheduling: A Mechanism for Efficient Multi-Node CommunicationBackground: Priority SchedulingEarliest Deadline FirstMultiple Nodes: Issue 1, Sub-OptimalityMultiple Nodes: Issue 2, Traffic DistortionExisting Solutions to Distortion ProblemGrand ChallengeOur Approach: CoordinationFIFO+ [CSZ92]FIFO+ is a Coordinated SchedulerCoordinated Earliest Deadline First (Similar to [And99,CWM89])Illustration: First Hop (EDF and CNS)Second Hop Without Coordination (EDF)Second Hop With Coordination (CNS) Illustration of Essential Traffic SmoothingPerformance Analysis: CNS vs. GPSVoice Flows 64/32 kb/secCNS vs. EDF (Pareto on-off)Conclusionshttp://www.ece.rice.edu/networksEdward W. Knightly and Chengzhi LiRice Networks GroupCoordinated Scheduling: A Mechanism for Efficient Multi-Node CommunicationEdward W. KnightlyBackground: Priority SchedulingEach packet has a priority indexScheduler selects smallest priority index pkt firstIndex assignment scheme Service Discipline–FIFO: index = arrival_time –Virtual Clock: index = max(arrival_time, prev_index + L/r)Arrival IndexL/rEdward W. KnightlyEarliest Deadline FirstScheduler services packet with smallest deadline = arrival_time + delay_boundEDF is optimal for a single serverArrival IndexδEdward W. KnightlyMultiple Nodes: Issue 1, Sub-OptimalityOver multiple nodes, EDF is not optimal–Locally optimal rules do not achieve global optimum (best end-to-end performance) … Can do betterEdward W. KnightlyMultiple Nodes: Issue 2, Traffic DistortionTraffic can become more bursty downstream–Arrivals previously in now inConsequence: difficult to analyze and efficiently support multi-node QoSNode j Node j+1δ -t t + ItarrivalsI] tδ, - t [ I] t, t [ Edward W. KnightlyExisting Solutions to Distortion Problem1. Reshape trafficHold packets until conform to original pattern2. Isolate flowsLimit distortion by limiting sharing (e.g., guaranteed rate)Problems–Utilization impact of isolation/non-work-conserving–Scalability issues with per-flow operationsNode j Node j+1δ -t t + ItEdward W. KnightlyGrand ChallengeDesign a scheduler with the following propertiesEfficient–achieves high utilization and is work-conservingScalable–without per-flow mechanismsQuality of Service –Provides mechanisms for end-to-end servicesEdward W. KnightlyOur Approach: CoordinationVirtual coordination among servers–Router computes priority index as a function of upstream indexImplications–Late packets upstream have increased priority downstream–Early packets have priorities reduced downstreamEdward W. KnightlyFIFO+ [CSZ92]Servers measure , the average local queueing delay, and actual packet delayFirst node is FIFODownstream priority index is accumulated terms from upstream nodesMulti-node performance gains over WFQ [CSZ92] dd-d d^ d e l a y o f p a c k e t : dm e a n d e l a y a t r o u t e r : d^p r i o r i t y i n d e x + = d - d^ t + d - d^ tEdward W. KnightlyFIFO+ is a Coordinated SchedulerSpecifying scheduler is CNS index assignment δ dkji,k1-ji, δ tki,1ki tkiN o d e 1 N o d e j)d - d(k1-ji,1-ji,h e a d e rp r i o r i t y i n d e xd a t ah e a d e rp r i o r i t y i n d e xd a t ak1-ji,1-ji,kji,d - d δ 0 δ ki,1FIFO at first hopDownstream, relative delay is accumulated, and adjusts priorityEdward W. KnightlyCoordinated Earliest Deadline First (Similar to [And99,CWM89])CEDF uses virtual coordination among servers–Downstream priority index is a function of upstream index (t+5+5 vs. u+5)Late packets upstream have increased priority downstream–Ex. Pkt delayed by 9 has 2nd node index 1 (vs. 5)Early packets have priorities reduced downstream–Ex. Pkt delayed by 1 has 2nd node index 9 (vs. 5) ( t + 5 ) + 5t + 5a r r i v a lt i m e ta r r i v a lt i m e uEdward W. KnightlyIllustration: First Hop (EDF and CNS) 1st hop: priority indexes are the same in CNS and EDFSuppose that the third packet is seriously delayed due to cross traffic0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Packet Arrival EventPacket Departure EventPacket Priority Index5 δ Edward W. KnightlySecond Hop Without Coordination (EDF)At the second hop, the priority indexes depend on the (local/late) arrival times in EDFTraffic distortion is large and propagates downstream0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Packet Arrival EventPacket Departure EventPacket Priority Index5 δ Edward W. KnightlySecond Hop With Coordination (CNS)Illustration of Essential Traffic Smoothing2nd hop: the priority indexes are independent of the (local/late) arrival times in CNSDepartures are narrowly distorted (without reshaping)Theory tightly bounds distortion of essential traffic0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Packet Arrival EventPacket Departure EventPacket Priority Index5 δ Edward W. KnightlyPerformance Analysis: CNS vs. GPSTwo CNS weight assignment schemes:–S-CNS (Simplified CNS)Constant local delay assignment scheme (2 and 6 msec respectively)–G-EDF (Global EDF) [CWM89]Uniform allocation with larger weight at first nodePath for target traffic Path for background trafficServer 1 Server 2 Server 3 Server 4 Server 5 Server 6Edward W. KnightlyVoice Flows 64/32 kb/secAdvantages of coordination–lower end-to-end delay bounds and larger admissible regionsEdward W. KnightlyCNS vs. EDF (Pareto on-off)With 300 flows, reduction in delay form 120 msec to 50 msecEdward W. KnightlyConclusionsCNS provides a framework for coordinated and scalable schedulers–FIFO+, CJVC, GEDF, CEDF, …General
View Full Document
Unlocking...