Copyright Hari Balakrishnan, 1998-2005, all rights reserved. Please do n ot redistributewithout permission.LECTURE 8Scheduling for Fairness: FairQueueing and CSFQ! 8.1 IntroductionInthe last lecture, we discussed two ways in which routers can help in congestion control:by signaling congestion, using either packet drops o r marks (e.g., ECN), and by cleverlymanaging its buffers (e.g., using an active queue management scheme like RED). Today,we turn to the third way in which routers can assist in congestion control: scheduling.Specifically, we will first study a particular form of scheduling, called fair queueing (F Q)that achieves (weighted) fair allocation of bandwidth between flows (or betwee n whatevertraffic aggregates one chooses to distinguish between.1While FQ achieves weighted-fairbandwidth allocations, it requires per-flow queueing and per-flow state in each router inthe network. This is often prohibitively expensive. We will also study another scheme,called core-stateless fair queueing (CSFQ), which displays an interesting design where “edge”routers maintain per-flow state whereas “core” routers do not. They use th eir own non-per-flow state complimented with some information reaching them in packet headers(placed by the edge routers) to implement fair allocations. Strictly speaking, CSFQ is not ascheduling mechanism, but a way to achieve fair bandwidth allocation us ing differentialpacket dropping. But because it attempt s to emulate fair queueing, it’s best to discuss thescheme in conjuction with fair queueing .The notes for this lecture are based on two papers:1. A. Demers, S. Keshav, and S. Shenker, “Analysis and Simulation of a Fair Queu eingAlgorithm”, Internetworking: Research and Experience, Vol. 1, No. 1, pp. 3–26, 1990.(Or read ACM SIGCOMM 1989 version.)2. I. Stoica, S. Shenker, H. Zhang, “Core-Stateless Fair Queueing: Achieving Approxi-mately Fair Bandwidth Allocations in High Spee d Network,” in Proc. ACM Sigcomm,September 1998, Vancouver, Canada.1FQ is also known as Packet Generalized Processor Sharing (PGPS), a scheme developed at MIT at about thesame time as FQ was developed at PARC.12 LECTURE 8. SCHEDULING FOR FAIRNESS: FAIR QUEUEING AND CSFQ! 8.2 SchedulingThe fundmental problem solved by a scheduling algorithm running at a router is to an-swer the following question: “Which packet gets sent out next, and when?” The choice ofwhich flow (or flow aggregate; we use the term “flow” to mean one or the other in this lec-ture, unles s mentioned otherwise) is the next one to use an outbound link helps apportionbandwidth betwee n flows. At the same time, a sche duling algorithm can also decide whento send any given packet (or flow’s packet), a choice that can help guarantee (or bound)packet latencies through the router.An important pr actical consideration, perhaps the most important consideration in thedesign of router scheduling algorithms concers state management. The key concern hereis that schemes that maintain per-flow state are not scalable, at least in several router de-signs. This is in stark contrast to buffer management schemes like RED, where the statemaintained by the router is ind ependent o f the number of flows. However, RED does notachieve fair bandwidth allocations amongst flows, whereas good scheduling algorithmscan (precisely because they tend to directly control which flow’s packet gets to use the linknext).It’s also worth appreciating that scheduling for weighted-fair bandwidth allocation andscheduling to provide latency guarantees are actually orthogonal to each other and separa-ble. For instance, one can imagine a hypothetical router that starves a flow for 6 days eachweek and gives extremely high bandwidth for one wh ole day, so t h e flow receives somepre-determined share of bandwidth, but does not receive any latency guarantees. Schedul-ing schemes have be en developed that provide both bandwidth and latency guarantees toflows, although th ey tend to be rather complex and require care in how t h ese requirementsare specified .Broadly speaking, all s chedulers can be divided into two categories: work-conservingand non-work-conserving. The former, of which fair queueing is an example, never keep anoutbound link idle if there is even one packet in the system waiting to use that link. Incontrast, the latter might, for instance to provide delay bounds. Another example of thelatter kind is a strict time-division multiplexing system like the one we saw in Problem 1of Problem Set 1.! 8.2.1 Digression: What happens to a packet in a router?To understand how scheduling fits into the grand scheme of things that happen in a router,it’s wor th understanding (for now, at a high level) all th e different things that go on in arouter. For concreteness, we look at an IP router. The following steps occur on the datapath, which is the term given to the processing that occurs for each packet in the router. Weonly consider unicast packets for now (i.e., no multicast).1. Validation. When a packet arrives, it is validated to check that the IP version numberis correct and that the header checksum is correct.2. Destination lookup. A longest-prefix-match (LPM) lookup is don e on the forwardingtable using the destination IP address as lookup key, to determine which output portto forward the p acke t on. Optionally, an IP source check may also be done t o seeif the port in which this packet is a valid, expected one. This is often used to helpSECTION 8.2. SCHEDULING 3protect against ce r tain denial-of-service (DoS) attacks.3. Classification. Many routers classify a packet using information in th e IP he ader fields(e.g., the “type-of-service” or TOS field, now also called the “differentiated servicescode point” or DSCP) and information in higher layers (e.g., transport protocol type,TCP/UDP port number, etc.). This is also called “layer-4 classification.” The resultof a classification is typ ically a queue that the packet is enqueued o n . In theory, onecan classify packets so each connection (or flow) ge ts its own queue, specified bya unique combination o f source and destination addresses, source and destinationtransport-layer port s, and TOS field, but th is turns out to be prohibitively expensivebecause of the large number of dynamically varying queue s the router needs to keeptrack of. In practice, routers are usually set up with a fixed number of queues, anda network operator can set up classification rules