Unformatted text preview:

CS 636 Internetworking Ramana Kompella ROUTER ALGORITHMICS Lecture 13: Packet scheduling Some slides courtesy of Nick McKeown 1CS 636 Internetworking 2 A(t) D(t) Cumulative number of departed bits up until time t. time Service process Cumulative number of bits Cumulative number of bits that arrived up until time t. R A(t) D(t) Q(t) Properties ofA(t), D(t):  A(t), D(t) are non-decreasing  A(t) >= D(t)CS 636 Internetworking 3 D(t) A(t) time Q(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). Cumulative number of bitsCS 636 Internetworking 4 1. 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. Fairness Delay GuaranteesCS 636 Internetworking 5 1.1 Mb/s 10 Mb/s 100 Mb/s A B R1 C 0.55 Mb/s 0.55 Mb/s What 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 6 1.1 Mb/s 10 Mb/s 100 Mb/s A B R1 D What is the “fair” allocation? 0.2 Mb/s CCS 636 Internetworking 7 N 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 8 1 W(f1) = 0.1 W(f3) = 10 R1 C W(f4) = 5 W(f2) = 0.5 Round 1: Set R(f1) = 0.1 Round 2: Set R(f2) = 0.9/3 = 0.3 Round 3: Set R(f4) = 0.6/2 = 0.3 Round 4: Set R(f3) = 0.3/1 = 0.3CS 636 Internetworking 9  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 10 1. 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 1 Flow N Classification Scheduling Bit-by-bit round robinCS 636 Internetworking 11 Likewise, flows can be allocated different rates by servicing a different number of bits for each flow during each round. 1 R(f1) = 0.1 R(f3) = 0.3 R1 C R(f4) = 0.3 R(f2) = 0.3 Order 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 12 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 + TRANSPmax Also called “Packetized Generalized Processor Sharing (PGPS)”CS 636 Internetworking 13  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 14  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 m packets, 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 heaps but still costly to implement. 1 2 3 N Packets arriving to egress linecard Calculate Fp Find Smallest Fp Departing packet Egress linecardCS 636 Internetworking 15 100 100 400 400 600 400 150 60 340 50 600 Active packet queues 200 0 0 0 Quantum Size = 200 Step 1: 100 100 400 400 600 400 150 60 340 50 600 Active packet queues 100 200 150 200 Step 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 quantum size for each queue. 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 queueNOSSDAV 2004 Scheduler Deficit Counters Quantum = Q 100 150 Scheduler transmits with prob = 100/250 Quantization between Q-x and Q+P-x Q+P-x Q-xNOSSDAV 2004  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 size Hierarchical round-robin  MDRR: Deficit round-robin + priority CS 636 Internetworking 21 70% 30% 40% 60% 1 1 1 2 2 2 3 3 3 Strict priority 1 1 1 2 3 Alternate priority 1 2 1 3


View Full Document

Purdue CS 63600 - Lecture notes

Download Lecture notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?