This is a queueing discipline that allocates bandwidth in which guarantees are made about latency

2.12.3 Class-Based Weighted Fair Queuing

Weighted fair queuing (WFQ) is a dynamic process that divides bandwidth among queues based on weights. The process is designed to be fair, such that WFQ ensures that all traffic is treated fairly with regard to its weight. Class-Based Weighted Fair Queuing, or CBWFQ, a form of WFQ, provides the ability to reorder packets and control latency at the edge and in the core. By assigning different weights to different service classes, a switch or router can manage buffering and bandwidth for each service class. Because weights are relative and not absolute, underutilized resources can be shared between service classes for optimal bandwidth efficiency. CBWFQ allows application service classes to be mapped to a portion of network link. For example, a QoS class can be configured to occupy, at most, 25 percent of a link. Figure 2.24 provides an example of three service classes provisioned using CBWFQ with the following characteristics:

Class 1, with guaranteed latency and delivery

Class 2, with guaranteed delivery

Class 3, a best-effort service

By separately allocating bandwidth and buffering space, a given class of traffic can have its own characteristics that will result in diverse behaviors between the various traffic classes. Since the shares are relative weights, allocating a large share to Class 1 means that a minimum is guaranteed. If Class 1 is underutilized, the bandwidth will be shared by the remaining classes in proportion to their weights. For CBWFQ, the weight of a packet belonging to a specific class is derived from the bandwidth that is assigned to the class. Therefore, the bandwidth assigned to the packets of a given class determines the order in which packets are sent. All packets are serviced fairly based on weight, and no class of packets may be granted absolute and strict priority. This scheme poses problems for voice traffic, which is largely intolerant to delay, especially variation in delay. For voice traffic, variations in delay introduce irregularities of transmission manifesting as jitter in the heard conversation.

14.8.1 Random Aggregation

The idea behind stochastic fair queuing (SFQ) [McK91] is to employ principle P3a by trading certainty in fairness for reduced state. In this proposal, backbone routers keep a fixed set of flow queues that is affordable, say, 125,000, on which they do, say, DRR. When packets arrive, some set of packet fields (say, destination, source, and the destination and source ports for TCP and UDP traffic) are hashed to a flow queue. Thus assuming that a flow is defined by the set of fields used for hashing, a given flow will always be hashed to the same flow queue. Thus with 250,000 concurrent flows and 125,000 flow queues, roughly 2 flows will share the same flow queue or hash bucket.

Stochastic fair queuing has two disadvantages. First, different backbone routers can hash flows into different groups because routers need to be able to change their hash function if the hash distributes unevenly. Second, SFQ does not allow some flows to be treated differently (either locally within one router or globally across routers) from other flows, a crucial feature for QoS. Thus, SFQ only provides some sort of scalable and uniform bandwidth fairness.

Worst-case fair weighted fair queuing

One of the problems of WFQ is that of “run-ahead.” Queues with many short packets get many transmission opportunities before queues with longer packets get to transmit. In our example in Figure 10-7, Queue 3 transmits its second packet before Queue 2 transmits its first packet. In Bennett and Zhang [16], the authors illustrate with an extensive example this potential unfairness of WFQ. To solve this problem, a modification to WFQ can be made to ensure fairness in the worst case as described [16].

Worst-case fair weighted fair queuing (which is typically abbreviated incorrectly as WF2Q) does not allow transmission of a packet before the time when GPS would have started its transmission. The resulting schedule for our example is shown in Figure 10-7. Note that the second packet of Queue 3 is delayed until after t = 120, which is the packet's start time in GPS.

6 Related Work

We are not aware of any CPU scheduling algorithm that achieves hierarchical partitioning while allowing different schedulers to be used for different applications. However, since a fair scheduling algorithm is the basis for achieving hierarchical partitioning, we discuss other such algorithms proposed in the literature. Most of these algorithms have been proposed for fair allocation of network bandwidth; we have modified their presentation appropriately for CPU scheduling.

The earliest known fair scheduling algorithm is Weighted Fair Queuing (WFQ) [3]. WFQ was designed to emulate a hypothetical weighted round robin server in which the service received by each thread in a round is infinitesimal and proportional to the weight of the thread. Since threads can only be serviced in quantums at a time, WFQ emulates a hypothetical server by scheduling threads in the increasing order of the finishing times of the quantums of the threads in the hypothetical server. To compute this order, WFQ associates two tags, a start tag and a finish tag, with every quantum of a thread. Specifically, the start tag S(qfj) and the finish tag F(qfj) of quantum qfj are defined as:

(11)S(qfj)=max{υA ((qfj)),F(qfj−1)}j≥1

(12)F(qfj−1)=S(qfj−1)+lfj−1 rfj≥1

where F(qf0) = 0 and υ(t) is defined as the round number that would be in progress at time t in the hypothetical server. Formally, v(t) is defined as:

(13) dυ(t)dt=C∑j∈B(t)rj

where C is the capacity of the CPU measured in instructions/second and B(t) is the set of runnable threads at time t in the hypothetical server. WFQ then schedules quantums in the increasing order of their finish tags. WFQ has several drawbacks for scheduling a CPU:

As demonstrated in [6], WFQ does not provide fairness when the processor bandwidth fluctuates over time. Since fairness in the presence of variation in available CPU bandwidth is crucial for supporting hierarchical partitioning, WFQ is unsuitable for a CPU scheduler in a general purpose operating system.

WFQ requires the length of the quantums to be known a priori. Though the maximum length of the quantum may always be known (as the scheduler can enforce it by preempting a thread), for environments in which the computation requirements are not known precisely, the exact quantum length may not be known. If WFQ assumes the maximum quantum length for scheduling and if the thread uses less than the maximum, the thread will not receive its fair share. On the other hand, if WFQ is modified to reflect the actual length of the execution (by changing the finish tag of a quantum after the end of its execution), then WFQ would have been modified in a non-trivial manner. Though WFQ is known to have bounded fairness, it is not known if the modified algorithm retains its fairness properties.

WFQ requires the computation of v(t), which, in turn, requires simulation of the hypothetical server. This simulation is known to be computationally expensive [4]. In contrast, SFQ computes the start and the finish tags efficiently.

The unfairness of WFQ, as derived in [16], is significantly higher than SFQ.

WFQ provides high delay to low throughput applications. Specifically, it guarantees that quantum qfj will complete execution by:

(14)EAT(qfj)+lfjrf+lmaxC

(15)Δ(qfj)=∑n∈Q ∧n≠flnmaxC+lfjC −lfjrf−lmaxC

Now, if all quantums are of the same lengths, then Δ(qfj) < 0 (i.e., SFQ provides a better delay guarantee) if rf≤1|Q |−1 Since this condition is expected to hold for low throughput applications, we conclude that SFQ provides lower delay to low throughput applications. Since interactive applications are low throughput in nature, this feature of SFQ is highly desirable for CPU scheduling.

Fair Queuing based on Start-time (FQS) was proposed in [7] to make WFQ suitable for CPU scheduling when quantum length may not be known a priori. It computes the start tag and the finish tag of a quantum exactly as in WFQ. However, instead of scheduling quantums in the increasing order of finish tags, it schedules them in the increasing order of start tags. Since quantum length is not required for computing the start tag, it becomes suitable for CPU scheduling. However, its main drawbacks are that: (1) just as WFQ, it is computationally expensive, and (2) it does not provide fairness when the available CPU bandwidth fluctuates over time, and consequently is unsuitable for hierarchical partitioning. Furthermore, it is not known to have any better properties than SFQ.

Self Clocked Fair Queuing (SCFQ), originally proposed in [2] and later analyzed in [4], was designed to reduce the computational complexity of fair scheduling algorithms like WFQ. It achieves efficiency over WFQ by approximating v(t) with the finish tag of the quantum in service at time t. However, since SCFQ also schedules quantums in increasing order of finish tags, it is unsuitable for scheduling CPU in a multimedia operating system. Furthermore, although it has the same fairness and implementation complexity as SFQ, it provides significantly larger delay guarantee than SFQ. Specifically, it increases the maximum delay of quantum qfjbylfjrf [6].

In the OS context, a randomized fair algorithm, termed lottery scheduling, was proposed in [19]. Due to its randomized nature, lottery scheduling achieved fairness only over large time-intervals. This limitation was later addressed by stride scheduling algorithm [18]. The stride scheduling algorithm is a variant of WFQ and, consequently, has all the drawbacks of WFQ. Furthermore, no theoretical properties of the stride scheduling algorithm are known. Recently, a proportionate share resource allocation algorithm, referred to as Earliest Eligible Virtual Deadline First (EEVDF), has been proposed [17].

Hierarchical partitioning of resource allocation was also proposed in [19] using the abstraction of tickets and currencies. In that framework, a thread is allocated tickets in some currency and the currency, in turn, is funded in terms of tickets of some other currency. The “funding” relationship is such that the value of a ticket in every currency can be translated to a value in the base currency. Every thread then is allocated resources in proportion to the value of its tickets in the base currency using lottery scheduling. This achieves hierarchical partitioning since if a thread becomes inactive, the value of the tickets of the threads that are funded by the same currency increases. This specification of hierarchical partitioning is similar to our scheduling structure. However, the key differences between our framework and the approach of [19] are as follows. First, our framework permits different scheduling algorithms to be employed for different classes of applications, whereas the framework of [19] does not. Second, hierarchical partitioning is achieved in [19] by re-computation of ticket values of every thread that are funded in the same currency or some ancestor of the currency every time a thread gets blocked or exits. This approach not only incurs additional overhead of computing ticket values, but also does not provide any guarantees. Hence, the requirements of hard and soft real-time applications can not be met in this framework. In contrast, our framework achieves hierarchical partitioning through a theoretically sound hierarchical scheduler.

Several other efforts have investigated scheduling techniques for multimedia systems [1, 5, 8, 13]. These scheduling algorithms are complementary to our hierarchical scheduler and can be employed as leaf class scheduler in our framework. Most of these algorithms require precise characterization of resource requirements of a task (such as computation time and period) as well as admission control to achieve predictable allocation of CPU. In contrast, SFQ requires neither of these; it just requires relative importance of tasks (expressed by weights) to be known. It requires admission control only if the applications desire a certain guaranteed minimum CPU bandwidth. Thus, SFQ allows a range of control over CPU allocation: whereas admission control can be used to guarantee a certain minimum CPU allocation to tasks and thus match the performance of the existing algorithms, admission control can be avoided when applications only require relative resource allocation. Such a flexibility is highly desirable in multimedia systems and the lack of it is one of the main disadvantage of existing algorithms. A detailed experimental investigation of the relative merits of these algorithms vis-a-vis SFQ as a leaf class scheduler is the subject of our current research.

Packet Scheduling

If differential treatment is to be provided in the network, then FIFO scheduling, traditionally used in routers, must be replaced by sophisticated queuing disciplines like priority queuing and weighted fair queuing. Priority queuing provides different queues for different traffic types. Every queue has an associated priority in which it is served. Queues with lower priority are served only when there are no packets in all the higher priority queues. One disadvantage of priority queuing is that it might lead to starvation of some low-priority flows.

Weighted fair queuing also has different queues for different traffic classes. Every queue, however, is assigned a certain weight w, and the packets in that queue always get a fraction w/C of the bandwidth, where C is the total link capacity.

4.2.2 Channel-dependent scheduling schemes

Channel-dependent scheduling may be used to take advantage of favorable channel conditions to increase the throughput and system spectral efficiency. Examples of those scheduling algorithms are:

Weighted Fair Queuing (WFQ Scheme): Here, the packets are grouped into various queues. A weight is assigned to each queue which determines the fraction of the total bandwidth available to the queue. The weight may depend on both channel quality and the number of packets in the queue of individual users. It provides balanced resource utilization between fairness and efficiency.

Modified Largest Weighted Delay First (M-LWDF): It combines both channel conditions and the state of the queue with respect to delay in making scheduling decisions [12]. It guarantees that the probability of delay packets does not exceed the discarded bound below the maximum allowable packet loss ratio.

Another comparative study of scheduling algorithms for real-time traffic was proposed in [13]. These scheduling algorithms are classified in two types: Fixed Priority Scheduling and Dynamic Priority Scheduling. The Rate Monotonic (RM) and Deadline Monotonic (DM) are fixed priority scheduling. The RM tasks with smaller periods get higher priorities. The DM tasks are assigned priorities according to their deadline. The task with the shortest deadline is assigned the highest priority. The Dynamic Priority Scheduling contains:

The Earliest Deadline First algorithm (EDF), which maintains a list of waiting packets to be executed. This list is sorted by deadline with the first packet having the earliest deadline. The priority of each packet is decided based on the value of its deadline. The task with nearest deadline is given highest priority and it is selected for execution.

The Least Laxity First (LLF) scheme is a dynamic scheduling method. For every task ready to run at the given moment the difference S between the time until deadline D and the remaining computation time C is computed. This difference, called slack or laxity, can be seen as an inverted priority value. The task with the smallest S-value is the one to be executed next. Whenever a task other than the currently running one has the smallest slack, a context switch will occur.

7.6.4 Fairness Optimization

Fairness is an important issue in a multiuser computing environment. There are various kinds of fair policies in the traditional HPC and grid computing, including round-robin [62], proportional resource sharing [63], weighted fair queuing [64], and max-min fairness [65]. In comparison, max-min fairness is the most popular and widely used policy in many existing parallel and distributed systems, such as Hadoop [66], YARN [15], Mesos [16], Choosy [67], and Quincy [68]. Hadoop [66] partitions resources into slots and allocates them fairly across pools and jobs. In contrast, YARN [15] divides resources into containers (ie, a set of various resources like memory and CPU) and tries to guarantee fairness between queues. Mesos [16] enables multiple diverse computing frameworks such as Hadoop and Spark sharing a single system. It proposes a distributed two-level scheduling mechanism called resource offers, which decides how many resources to offer. Each framework decides which resources to accept or which computation to run on them. Choosy [67] extends the max-min fairness by considering placement constraints. Quincy [68] is a fair scheduler for Dryad that achieves a fair scheduling of multiple jobs by formulating it as a min-cost flow problem. In addition to the single-resource fairness, there are some work focusing on multiresource fairness, including DRF [7] and its extensions [69–72].

18.1.3 Toward a Synthesis

In his book The Character of Physical Law, Richard Feynman argues that we have a need to understand the world in “various hierarchies, or levels.” Later, he goes on to say that “all the sciences, and not just the sciences but all the efforts of intellectual kinds, are an endeavor to see the connections of the hierarchies … and in that way we are gradually understanding this tremendous world of interconnecting hierarchies.”

We have divided network algorithmics into two hierarchies: endnode algorithmics and router algorithmics. What are the connections between these two hierarchies? Clearly, we have used the same set of 15 principles to understand and derive techniques in both areas. But are there other unities that can provide insight and suggest new directions?

There are differences between endnode and router algorithmics. Endnodes have large, structured, and general-purpose operating systems that require work arounds to obtain high performance; routers, by contrast, have fairly primitive operating systems (e.g., Cisco IOS) that bear some resemblance to a real-time operating system. Most endnodes’ protocol functions are implemented (today) in software, while the critical performance functions in a router are implemented in hardware. Endnodes compute, routers communicate. Thus routers have no file system and no complex process scheduling.

But there are similarities as well between endnode and router algorithmics.

Copying in endnodes is analogous to the data movement orchestrated by switching in routers.

Demultiplexing in endnodes is analogous to classification in routers.

Scheduling in endnodes is analogous to fair queuing in routers.

Other than packet classification, where the analogy is more exact, it may seem that the other correspondences are a little stretched. However, these analogies suggest the following potentially fruitful directions.

Switch-based endnode architectures: The analogy between copying and switching, and the clean separation between I/O and computation in a router, suggests that this may also be a good idea for endnodes. More precisely, most routers have a crossbar switch that allows parallel data transfers using dedicated ASICs or processors; packets meant for internal computation are routed to a separate set of processors. While we considered this briefly in Chapter 2, we did not consider very deeply the implications for endnode operating systems.

By dedicating memory bandwidth and processing to I/O streams, the main computational processors can compute without interruptions, system calls, or kernel thread, because I/O is essentially serviced and placed in clean form by a set of I/O processors (using separate memory bandwidth that does not interfere with the main processors) for use by the computational processors when they switch computational tasks. With switch-based bus replacements such as Infiniband, and the increasing use of protocol offload engines such as TCP chips, this vision may be realizable in the near future. However, while the hardware elements are present, there is need for a fundamental restructuring of operating systems to make this possible.

Generalized endnode packet classification: Although there seems to be a direct correspondence between packet classification in endnodes (Chapter 8) and packet classification in routers (Chapter 12), the endnode problem is simpler because it works only for a constrained set of classifiers, where all the wildcards are at the end. Router classifiers, on the other hand, allow arbitrary classifiers, requiring more complicated algorithmic machinery or CAMs.

It seems clear that if early demultiplexing is a good idea, then there are several possible definitions of a path (flow in router terminology), other than a TCP connection. For example, one might want to devote resources to all traffic coming from certain subnets or to certain protocol types. Such flexibility is not allowed by current classifiers, such as BPF and DPF (Chapter 8). It may be interesting to study the extra benefits provided by more general classifiers in return for the added computational burden.

Fair queuing in endnodes: Fair queuing in routers was originally invented to provide more discriminating treatment to flows in times of overload and (later) to provide quality of service to flows in terms of, say, latency. Both these issues resonate in the endnode environment. For example, the problem of receiver livelock (Chapter 6) requires discriminating between flows during times of overload. The use of early demultiplexing and separate IP queues per flow in lazy receiver processing seems like a first crude step toward fair queuing. Similarly, many endnodes do real-time processing, such as running MPEG players, just as routers have to deal with the real-time constraints of, say, voice-over-IP packets.

Thus, a reasonable question is whether the work on fair schedulers in the networking community can be useful in an operating system environment. When a sending TCP is scheduling between multiple concurrent connections, could it use a scheduling algorithm such as DRR for better fairness? At a higher level, could a Web server use worst-case weighted fair queuing to provide better delay bounds for certain clients? Some work following this agenda has begun to appear in the operating system community, but it is unclear whether the question has been fully explored.

So far, we have suggested that endnodes could learn from router design in overall I/O architecture and operating system design. Routers can potentially learn the following from endnodes.

Fundamental Algorithms: Fundamental algorithms for endnodes, such as selection, buffer allocation, CRCs, and timers, are likely to be useful for routers, because the router processor is still an endnode, with very similar issues.

More Structured Router Operating Systems: While the internals of router operating systems, such as Cisco’s IOS and Juniper’s JunOS, are hidden from public scrutiny, there is at least anecdotal evidence that there are major software engineering challenges associated with such systems as time progresses (leading to the need to be compatible with multiple past versions) and as customers ask for special builds. Perhaps routers can benefit from some of the design ideas behind existing operating systems that have stood the test of time.

While protection may be fundamentally unnecessary (no third-party applications running on a router), how should a router operating system be structured for modularity? One approach to building a modular but efficient router operating system can be found in the router plugins system [DDPP98] and the Click operating system [KMea00].

Vertically Integrated Routers: The components of an endnode (applications, operating system, boxes, chips) are often built by separate companies, thus encouraging innovation. The interface between these components is standardized (e.g., the API between applications and operating system), allowing multiple companies to supply new solutions. Why should a similar vision not hold for routers some years from now when the industry matures? Currently, this is more of a business than a technical issue because existing vendors do not want to open up the market to competitors. However, this was true in the past for computers and is no longer true; thus there is hope.

We are already seeing router chips being manufactured by semiconductor companies. However, a great aid to progress would be a standardized router operating system that is serious and general enough for production use by several, if not all, router companies.1 Such a router operating system would have to work across a range of router architectures, just as operating systems span a variety of multiprocessor and disk architectures.

Once this is the case, perhaps there is even a possibility of “applications” that run on routers. This is not as far-fetched as it sounds, because there could be a variety of security and measurement programs that operate on a subset of the packets received by the router. With the appropriate API (and especially if the programs are operating on a logged copy of the router packet stream), such applications could even be farmed out to third-party application developers. It is probably easy to build an environment where a third-party application (working on logged packets) cannot harm the main router functions, such as forwarding and routing.

6.9 Fair queuing

Computing and communication on a cloud are intimately related. Therefore, it should be no surprise that the first algorithm we discuss can be used for scheduling packet transmission as well as threads. Interconnection networks allow cloud servers to communicate with one another and with users. These networks consist of communication links of limited bandwidth and switches/routers/gateways of limited capacity. When the load exceeds its capacity, a switch starts dropping packets because it has limited input buffers for the switching fabric and for the outgoing links, as well as limited CPU cycles.

A switch must handle multiple flows and pairs of source-destination endpoints of the traffic. Thus, a scheduling algorithm has to manage several quantities at the same time: the bandwidth, the amount of data each flow is allowed to transport; the timing when the packets of individual flows are transmitted; and the buffer space allocated to each flow. A first strategy to avoid network congestion is to use a FCFS scheduling algorithm. The advantage of the FCFS algorithm is a simple management of the three quantities: bandwidth, timing, and buffer space. Nevertheless, the FCFS algorithm does not guarantee fairness; greedy flow sources can transmit at a higher rate and benefit from a larger share of the bandwidth.

To address this problem, a fair queuing algorithm proposed in [252] requires that separate queues, one per flow, be maintained by a switch and that the queues be serviced in a round-robin manner. This algorithm guarantees the fairness of buffer space management, but does not guarantee fairness of bandwidth allocation. Indeed, a flow transporting large packets will benefit from a larger bandwidth (see Figure 6.8).

The fair queuing (FQ) algorithm in [102] proposes a solution to this problem. First, it introduces a bit-by-bit round-robin (BR) strategy; as the name implies, in this rather impractical scheme a single bit from each queue is transmitted and the queues are visited in a round-robin fashion. Let R(t) be the number of rounds of the BR algorithm up to time t and Nactive( t) be the number of active flows through the switch. Call tia the time when the packet i of flow a , of size Pia bits arrives, and call Sia and Fia the values of R(t) when the first and the last bit, respectively, of the packet i of flow a are transmitted. Then,

(6.28)Fia=Sia+ PiaandSia=maxFi-1a,Rtia.

The quantities R(t), Nactive (t), Sia, and Fia depend only on the arrival time of the packets, tia, and not on their transmission time, provided that a flow a is active as long as

(6.29)R(t)⩽Fiawheni=maxj|tia⩽t.

The authors of [102] use for packet-by-packet transmission time the following nonpreemptive scheduling rule, which emulates the BR strategy: The next packet to be transmitted is the one with the smallest Fia. A preemptive version of the algorithm requires that the transmission of the current packet be interrupted as soon as one with a shorter finishing time, Fia, arrives.

A fair allocation of the bandwidth does not have an effect on the timing of the transmission. A possible strategy is to allow less delay for the flows using less than their fair share of the bandwidth. The same paper [102] proposes the introduction of a quantity called the bid, Bia, and scheduling the packet transmission based on its value. The bid is defined as

(6.30)B ia=Pia+maxFi-1a,Rtia -δ,

with δ a nonnegative parameter. The properties of the FQ algorithm, as well as the implementation of a nonpreemptive version of the algorithms, are analyzed in [102].