CS 636 InternetworkingCS 636 InternetworkingRamana KompellaROUTER ALGORITHMICSLecture 24: Packet schedulingSome slides courtesy of Nick McKeown1CS 636 Internetworking 2Simple deterministic model of a queueA(t)D(t)Cumulative number of departed bits up until time t.timeService processCumulativenumber of bitsCumulative number of bits that arrived up until time t.RA(t)D(t)Q(t)Properties ofA(t), D(t):A(t), D(t) are non-decreasingA(t) >= D(t)CS 636 Internetworking 3D(t)A(t)timeQ(t)d(t)Queue occupancy: Q(t) = A(t) - D(t).Queueing delay, d(t), is the time spent in the queue by a bit that arrived at time t, (assuming that the queue is served FCFS/FIFO). Simple Deterministic ModelCumulativenumber of bitsCS 636 Internetworking 4The problems caused by FIFO queues in routers1. In order to maximize its chances of success, a source has an incentive to maximize the rate at which it transmits. 2. (Related to #1) When many flows pass through it, a FIFO queue is “unfair” – it favors the most greedy flow.3. It is hard to control the delay of packets through a network of FIFO queues.FairnessDelay GuaranteesCS 636 Internetworking 5Fairness1.1 Mb/s10 Mb/s100 Mb/sABR1C0.55Mb/s0.55Mb/sWhat is the “fair” allocation: (0.55Mb/s, 0.55Mb/s) or (0.1Mb/s, 1Mb/s)?e.g. an http flow with a given(IP SA, IP DA, TCP SP, TCP DP)CS 636 Internetworking 6Fairness1.1 Mb/s10 Mb/s100 Mb/sABR1DWhat is the “fair” allocation?0.2 Mb/sCCS 636 Internetworking 7Max-Min FairnessA common way to allocate flowsN flows share a link of rate C. Flow f wishes to send at rate W(f), and is allocated rate R(f).1. Pick the flow, f, with the smallest requested rate.2. If W(f)<C/N, then set R(f) = W(f).3. If W(f) >C/N, then set R(f) = C/N.4. Set N = N – 1. C = C – R(f).5. If N>0 goto 1.CS 636 Internetworking 81W(f1) = 0.1W(f3) = 10R1CW(f4) = 5W(f2) = 0.5Max-Min FairnessAn exampleRound 1: Set R(f1) = 0.1Round 2: Set R(f2) = 0.9/3 = 0.3Round 3: Set R(f4) = 0.6/2 = 0.3Round 4: Set R(f3) = 0.3/1 = 0.3CS 636 Internetworking 9Max-Min Fairness How can an Internet router “allocate” different rates to different flows?  First, let’s see how a router can allocate the “same” rate to different flows…CS 636 Internetworking 10Fair Queueing1. Packets belonging to a flow are placed in a FIFO. This is called “per-flow queueing”.2. FIFOs are scheduled one bit at a time, in a round-robin fashion. 3. This is called Bit-by-Bit Fair Queueing.Flow 1Flow NClassification SchedulingBit-by-bit round robinCS 636 Internetworking 11Weighted Bit-by-Bit Fair QueueingLikewise, flows can be allocated different rates by servicing a different number of bits for each flow during each round. 1R(f1) = 0.1R(f3) = 0.3R1CR(f4) = 0.3R(f2) = 0.3Order of service for the four queues:… f1, f2, f2, f2, f3, f3, f3, f4, f4, f4, f1,…Also called “Generalized Processor Sharing (GPS)”CS 636 Internetworking 12Packetized Weighted Fair Queueing (WFQ)Problem: We need to serve a whole packet at a time.Solution: 1. Determine what time a packet, p, would complete if we served flows bit-by-bit. Call this the packet’s finishing time, F.2. Serve packets in the order of increasing finishing time.Theorem: Packet p will depart before F + TRANSPmaxAlso called “Packetized Generalized Processor Sharing (PGPS)”CS 636 Internetworking 13Intuition behind Packetized WFQ Consider packet p that arrives and immediately enters service under WFQ. Potentially, there are packets Q = {q, r, …} that arrive after p that would have completed service before p under bit-by-bit WFQ. These packets are delayed by the duration of p’s service. Because the amount of data in Q that could have departed before p must be less than or equal to the length of p, their ordering is simply changed Packets in Q are delayed by a maximum length of p.(Detailed proof in Parekh and Gallager)CS 636 Internetworking 14Implementation of WFQ There may be hundreds to millions of flows; the linecard needs to manage a FIFO per flow.  The finishing time must be calculated for each arriving packet, Packets must be sorted by their departure time. Naively, with mpackets, the sorting time is O(logm). In practice, this can be made to be O(logN), for N active flows: Sorting can be efficiently implemented in hardware using multi-way heaps123NPackets arriving to egress linecardCalculateFpFind Smallest FpDeparting packetEgress linecardCS 636 Internetworking 15Deficit Round Robin (DRR)An O(1) approximation to WFQ100100400 4006004001506034050600Active packet queues200000Quantum Size = 200Step 1: 100100400 4006004001506034050600Active packet queues100200150200Step 2,3,4:  It appears that DRR emulates bit-by-bit FQ, with a larger “bit”. So, if the quantum size is 1 bit, does it equal FQ? (Answer is No). It is easy to implement Weighted DRR using a different quantumsize for each queue.Deficit Round Robin Provides excellent bandwidth guarantees One major problem:◦ Poor delay bounds Implementation complexity◦ Need to skip a lot of queues to find next active queue◦ We can use an active list for maintaining this ◦ However, it can lead to inactive queues not accumulating their fair share.CS 636 Internetworking 16NOSSDAV 2004 State Overheads :◦ Queuing Overheads : Maintaining quantum allocations per queue Storing queue heads and tails◦ Scheduling Overheads :  Maintaining Active list of queues to schedule Maintaining Deficit Counters per queueImplementation of DRRNOSSDAV 2004Randomized DRR [Kompella,Varghese04]SchedulerDeficit CountersQuantum = Q100150Scheduler transmits with prob = 100/250Quantization between Q-x and Q+P-xQ+P-x Q-xNOSSDAV 2004State reduction achieved by Randomized DRR Randomized Rounding eliminates the deficit counter per-queue For 64000 queues, ◦ a reduction of about 1Mbit of high speed SRAM◦ a reduction of two memory accesses, one read and one write (of the deficit counters) Achieves average throughput fairness similar to DRRNOSSDAV 2004 If S is total service received by a backlogged queue with Quantum Q Standard Deviation  Chernoff Bounds : For fixed packet sizeStatistical Properties..Exp[S]  Q.n (n is the number of rounds)XP2nPr[X X n(Qmod P)]  eY2/ 3Extensions to Round-robin Hierarchical round-robin MDRR: Deficit round-robin + priorityCS 636 Internetworking 2170%30%40%60%1 1 12 2 2 3 3 3Strict priority1 1 1 2 3Alternate priority1