Rate-proportional servers: a design methodology for fair queueingalgorithms

Generalized processor sharing (GPS) has been considered as an ideal scheduling discipline based on its end-to-end delay bounds and fairness properties. Until recently, emulation of GPS in a packet server has been regarded as the ideal means of designing a packet-level scheduling algorithm to obtain low delay bounds and bounded unfairness. Strict emulation of GPS, as required in the weighted fair queueing (WFQ) scheduler, however, incurs a time-complexity of O(N) where N is the number of sessions sharing the link. Efforts in the past to simplify the implementation of WFQ, such as self-clocked fair queueing (SCFQ), have resulted in degrading its isolation properties, thus affecting the delay bound. We present a methodology for the design of scheduling algorithms that provide the same end-to-end delay bound as that of WFQ and bounded unfairness without the complexity of GPS emulation. The resulting class of algorithms, called rate-proportional servers (RPSs), are based on isolating scheduler properties that give rise to ideal delay and fairness behavior. Network designers can use this methodology to construct efficient fair-queueing algorithms, balancing their fairness with implementation complexity     

An efficient ATM network switch scheduling

The problem of allocating network resources to application sessions backlogged at an individual switch has a great impact on the end-to-end delay and throughput guarantees offered by the network. There exists a class of algorithms based on weighted fair queueing (WFQ) for scheduling packets which are work-conserving and they guarantee fairness to the backlogged sessions. These algorithms also apply to ATM networks with a packet equal to a single cell or an ATM block (of fixed size). Bursts are groups of varying numbers of cells. We generalize WFQ to schedule bursts. Our motivation is to derive an adaptive algorithm which generalizes the (fixed size) packet level to a varying size packet level. The new algorithm enhances the performance of the switch service for many important applications. The proposed scheme maintains the work-conserving property, and also provides throughput and fairness guarantees. The worst-case delay bound is also given. We use simulation to study the performance characteristics of our algorithm. Our results demonstrate the efficiency of the new algorithm.     

Fair scheduling with tunable latency: a round-robin approach

Weighted fair queueing (WFQ)-based packet scheduling schemes require processing at line speeds for tag computation and tag sorting. This requirement presents a bottleneck for their implementation at high transmission speeds. We propose an alternative and lower complexity approach to packet scheduling, based on modifications of the classical round-robin scheduler. Contrary to conventional belief, we show that appropriate modifications of the weighted round-robin (WRR) service discipline can, in fact, provide tight fairness properties and efficient delay guarantees to multiple sessions. Two such modifications are described: 1) list-based round robin, in which the server visits different sessions according to a precomputed list which is designed to obtain the desirable scheduling properties; 2) multiclass round robin, a version of hierarchical round robin with controls designed for good scheduling properties. The schemes considered are compared with well-known WFQ schemes and with deficit round robin (a credit-based WRR), on the basis of desirable properties such as bandwidth guarantees, fairness in excess bandwidth sharing, worst-case fairness, and efficiency of latency (delay guarantee) tuning. The scheduling schemes proposed and analyzed here operate with fixed packet sizes, and hence can be used in applications such as cell scheduling in ATM networks, time-slot scheduling on wireless links as in GPRS air interface, etc. A credit-based extension of the proposed schemes to handle variable packet sizes is also possible.     

Solving the trade-off between fairness and throughput: Token bucket and leaky bucket-based weighted fair queueing schedulers

In this article, we present two efficient weighted fair queueing (WFQ) scheduling algorithms leaned on the well-known token bucket and leaky bucket shaping/policing algorithms. The performance of the presented algorithms is compared to those of the state-of-the-art WFQ approximations such as weighted round robin (WRR) and the recently proposed bin sort fair queueing (BSFQ). Our simulation results show that the proposed algorithms provide a better fairness at a lower implementation complexity while simultaneously achieving a comparable network utilization.     

Rate Proportional SCFQ Algorithm for High‐Speed Packet‐Switched Networks

Self‐Clocked Fair Queueing (SCFQ) algorithm has been considered as an attractive packet scheduling algorithm because of its implementation simplicity, but it has unbounded delay property in some input traffic conditions. In this paper, we propose a Rate Proportional SCFQ (RP‐SCFQ) algorithm which is a rate proportional version of SCFQ. If any fair queueing algorithm can be categorized into the rate proportional class and input is constrained by a leaky bucket, its delay is bounded and the same as that of Weighted Fair Queueing (WFQ) which is known as an optimal fair queueing algorithm. RP‐SCFQ calculates the timestamps of packets arriving during the transmission of a packet using the current value of system potential updated at every packet departing instant and uses a starting potential when it updates the system potential. By doing so, RP‐SCFQ can have the rate proportional property. RP‐SCFQ is appropriate for high‐speed packet‐switched networks since its implementation complexity is low while it guarantees the bounded delay even in the worst‐case input traffic conditions.     

Self-coordinating localized fair queueing in wireless ad hoc networks

Distributed fair queueing in a multihop, wireless ad hoc network is challenging for several reasons. First, the wireless channel is shared among multiple contending nodes in a spatial locality. Location-dependent channel contention complicates the fairness notion. Second, the sender of a flow does not have explicit information regarding the contending flows originated from other nodes. Fair queueing over ad hoc networks is a distributed scheduling problem by nature. Finally, the wireless channel capacity is a scarce resource. Spatial channel reuse, i.e., simultaneous transmissions of flows that do not interfere with each other, should be encouraged whenever possible. In this paper, we reexamine the fairness notion in an ad hoc network using a graph-theoretic formulation and extract the fairness requirements that an ad hoc fair queueing algorithm should possess. To meet these requirements, we propose maximize-local-minimum fair queueing (MLM-FQ), a novel distributed packet scheduling algorithm where local schedulers self-coordinate their scheduling decisions and collectively achieve fair bandwidth sharing. We then propose enhanced MLM-FQ (EMLM-FQ) to further improve the spatial channel reuse and limit the impact of inaccurate scheduling information resulted from collisions. EMLM-FQ achieves statistical short-term throughput and delay bounds over the shared wireless channel. Analysis and extensive simulations confirm the effectiveness and efficiency of our self-coordinating localized design in providing global fair channel access in wireless ad hoc networks.     

Tradeoffs between low complexity, low latency, and fairness with deficit round-robin schedulers

Deficit Round-Robin (DRR) is a scheduling algorithm devised for providing fair queueing in the presence of variable length packets. The main attractive feature of DRR is its simplicity of implementation: in fact, it can exhibit O(1) complexity, provided that specific allocation constraints are met. However, according to the original DRR implementation, meeting such constraints often implies tolerating high latency and poor fairness. In this paper, we first derive new and exact bounds for DRR latency and fairness. On the basis of these results, we then propose a novel implementation technique, called Active List Queue Method (Aliquem), which allows a remarkable gain in latency and fairness to be achieved, while still preserving O(1) complexity. We show that DRR achieves better performance metrics than those of other round-robin algorithms such as Pre-Order Deficit Round-Robin and Smoothed Round-Robin. We also show by simulation that the proposed implementation allows the average delay and the jitter to be reduced.     

Generalized guaranteed rate scheduling algorithms: a framework

In this paper, we define a class of generalized guaranteed rate (GR) scheduling algorithms that includes algorithms which allocate a variable rate to the packets of a flow. We define work-conserving generalized virtual clock, packet-by-packet generalized processor sharing, and self-clocked fair queueing scheduling algorithms that can allocate a variable rate to the packets of a flow. We also define scheduling algorithms suitable for servers where packet fragmentation may occur. We demonstrate that if a class of rate controllers is employed for a flow in conjunction with any scheduling algorithm in GR, then the resulting non-work-conserving algorithm also belongs to GR. This leads to the definition of several non-work-conserving algorithms. We then present a method for deriving the delay guarantee of a network of servers when: (1) different rates are allocated to packets of a flow at different servers along the path and the bottleneck server for each packet may be different, and (2) packet fragmentation and/or reassembly may occur. This delay guarantee enables a network to provide various service guarantees to flows conforming to any specification. We illustrate this by utilizing delay guarantee to derive delay bounds for flows conforming to leaky bucket, exponentially bounded burstiness, and flow specification. Our method for determining these bounds is valid in internetworks and leads to tighter results     

双服务器分组调度算法

分组调度算法对于确保分组交换系统的QoS具有重要意义。时延,公平性,计算复杂度是微量分组度算法的主要指标。本文提出了一种双服务器分组调度算法,该算法在两种不同的工作状态下分别采用两种服务规则决定分组的服务次序。其中一种服务规则用来确保分组的时延,另一种服务规则在时延得到保障的情况下对系统的公平性进行改善,这两种规则计算都不复杂。因此本文提出的算法具有时延低,公平性较好,计算复杂度低的特点。     

Hierarchical packet fair queueing algorithms

We propose to use the idealized hierarchical generalized processor sharing (H-GPS) model to simultaneously support guaranteed real-time, rate-adaptive best-effort, and controlled link-sharing services. We design hierarchical packet fair queueing (H-PFQ) algorithms to approximate H-GPS by using one-level variable-rate PFQ servers as basic building blocks. By computing the system virtual time and per packet virtual start/finish times in unit of bits instead of seconds, most of the PFQ algorithms in the literature can be properly defined as variable-rate servers. We develop techniques to analyze delay and fairness properties of variable-rate and hierarchical PFQ servers. We demonstrate that in order to provide tight delay bounds with an H-PFQ server, it is essential for the one-level PFQ servers to have small worst-case fair indices (WFI). We propose a new PFQ algorithm called WF ²Q+ that is the first to have all the following three properties: (1) providing the tightest delay bound among all PFQ algorithms; (2) having the smallest WFI among all PFQ algorithms; and (3) having a relatively low asymptotic complexity of O(log N). Simulation results are presented to evaluate the delay and link-sharing properties of H-WF²Q+, H-WFQ, H-SFQ, and H-SCFQ     

Soft QoS provisioning using the token bank fair queuing scheduling algorithm

Future-generation wireless packet networks will support multimedia applications with diverse QoS requirements. Much of the research on scheduling algorithms has been focused on hard QoS provisioning of integrated services. Although these algorithms give hard delay bounds, their stringent requirements sacrifice the potential statistical multiplexing performance and flexibility of the packet-switched network. Furthermore, the complexities of the algorithms often make them impractical for wireless networks. There is a need to develop a packet scheduling scheme for wireless packet-switched networks that provides soft QoS guarantees for heterogeneous traffic, and is also simple to implement and manage. This article proposes token bank fair queuing (TBFQ), a soft scheduling algorithm that possesses these qualities. This algorithm is work-conserving and has a complexity of O(1). We focus on packet scheduling on a reservation-based TDMA/TDD wireless channel to service integrated real-time traffic. The TBFQ scheduling mechanism integrates the policing and servicing functions, and keeps track of the usage of each connection. We address the impact of TBFQ on mean packet delay, violation probability, and bandwidth utilization. We also demonstrate that due to its soft provisioning capabilities, the TBFQ performs rather well even when traffic conditions deviate from the established contracts.     

Fair scheduling in wireless packet networks

Fair scheduling of delay and rate-sensitive packet flows over a wireless channel is not addressed effectively by most contemporary wireline fair-scheduling algorithms because of two unique characteristics of wireless media: (1) bursty channel errors and (2) location-dependent channel capacity and errors. Besides, in packet cellular networks, the base station typically performs the task of packet scheduling for both downlink and uplink flows in a cell; however, a base station has only a limited knowledge of the arrival processes of uplink flows. We propose a new model for wireless fair-scheduling based on an adaptation of fluid fair queueing (FFQ) to handle location-dependent error bursts. We describe an ideal wireless fair-scheduling algorithm which provides a packetized implementation of the fluid mode, while assuming full knowledge of the current channel conditions. For this algorithm, we derive the worst-case throughput and delay bounds. Finally, we describe a practical wireless scheduling algorithm which approximates the ideal algorithm. Through simulations, we show that the algorithm achieves the desirable properties identified in the wireless FFQ model     

Time-shift scheduling-fair scheduling of flows in high-speednetworks

We present a scheduling protocol, called time-shift scheduling, to forward packets from multiple input flows to a single output channel. Each input flow is guaranteed a predetermined packet rate and an upper bound on packet delay. The protocol is an improvement over existing protocols because it satisfies the properties of rate-proportional delay, fairness, and efficiency, while existing protocols fail to satisfy at least one of these properties. In time-shift scheduling each flow is assigned an increasing timestamp, and the packet chosen for transmission is taken from the flow with the least timestamp. The protocol features the novel technique of time shifting, in which the scheduler's real-time clock is adjusted to prevent flow timestamps from increasing faster than the real-time clock. This bounds the difference between any pair of flow timestamps, thus ensuring the fair scheduling of flows     

WFQ流量调度算法研究

高速包交换电路常常需要为各种不同要求的服务公平地分配带宽,在公平分配带宽的同时还需要满足这些服务的服务质量(QoS)参数.不同QoS需求的业务将被复用到同一条输出链路上,要为它们公平地分配带宽就需要用到各种各样的流量调度算法.加权公平队列(WFQ)是一种常用的流量调度算法.它不仅能保证带宽分配的公平性,而且具有较好的时延性能.文章较为详细地讨论了WFQ算法的基本原理.     

无线网络中的分组调度算法

探讨了将有线网络的分组调度算法引入无线网络需要改进的事项,分析了公平排队算法,建立了一个基本的无线分组调度模型,并综述了一些目前存在的无线分组调度算法。     

A Unified Architecture for the Design and Evaluation of Wireless Fair Queueing Algorithms

Fair queueing in the wireless domain poses significant challenges due to unique issues in the wireless channel such as location-dependent and bursty channel errors. In this paper, we present a wireless fair service model that captures the scheduling requirements of wireless scheduling algorithms, and present a unified wireless fair queueing architecture in which scheduling algorithms can be designed to achieve wireless fair service. We map seven recently proposed wireless fair scheduling algorithms to the unified architecture, and compare their properties through simulation and analysis. We conclude that some of these algorithms achieve the properties of wireless fair service including short-term and long-term fairness, short-term and long-term throughput bounds, and tight delay bounds for channel access.     

Latency-rate servers: a general model for analysis of trafficscheduling algorithms

We develop a general model, called latency-rate servers (ℒℛ servers), for the analysis of traffic scheduling algorithms in broadband packet networks. The behavior of an ℒℛ server is determined by two parameters-the latency and the allocated rate. Several well-known scheduling algorithms, such as weighted fair queueing, virtualclock, self-clocked fair queueing, weighted round robin, and deficit round robin, belong to the class of ℒℛ servers. We derive tight upper bounds on the end-to-end delay, internal burstiness, and buffer requirements of individual sessions in an arbitrary network of ℒℛ servers in terms of the latencies of the individual schedulers in the network, when the session traffic is shaped by a token bucket. The theory of ℒℛ servers enables computation of tight upper bounds on end-to-end delay and buffer requirements in a heterogeneous network, where individual servers may support different scheduling architectures and under different traffic models     

Hardware implementation of fair queuing algorithms for asynchronoustransfer mode networks

Providing quality-of-service guarantees in both cell- and packet-based networks requires the use of a scheduling algorithm in the switches and network interfaces. These algorithms need to be implemented in hardware in a high-speed switch. The authors present a number of approaches to implement scheduling algorithms in hardware. They begin by presenting a general methodology for the design of timestamp-based fair queuing algorithms that provide the same bounds on end-to-end delay and fairness as those of weighted fair queuing, yet have efficient hardware implementations. Based on this general methodology, the authors describe two specific algorithms, frame-based fair queuing and starting potential-based fair queuing, and discuss illustrative implementations in hardware. These algorithms may be used in both cell switches and packet switches with variable-size packets. A methodology for combining a traffic shaper with this class of fair queuing schedulers is also presented for use in network interface devices, such as an ATM segmentation and reassembly device     

一种无时间标记的包调度策略

本文提出一种多队列的包调度算法，该方法在调度的公平性、延时和所需的缓冲空间等性能方面与PGPS，PRPS等调度算法有相同的性能，同时无需对各个到达的数据包记上时间标记，使调度操作更为简单有效。     

Efficient Packet Scheduling Using Channel Adaptive Fair Queueing in Distributed Mobile Computing Systems

In a distributed mobile computing system, an efficient packet scheduling policy is a crucial component to achieve a high utilization of the precious bandwidth resources while satisfying users' QoS (quality of service) demands. An important class of scheduling techniques, namely, the wireless fair queueing algorithms, have been extensively studied recently. However, a major drawback in existing approaches is that the channel model is overly simplified – a two-state channel (good or bad) is assumed. While it is relatively easy to analyze the system using such a simple model, the algorithms so designed are of a limited applicability in a practical environment, in which the level of burst errors is time-varying and can be exploited by using channel adaptive coding and modulation techniques. In this paper, we first argue that the existing algorithms cannot cater for a more realistic channel model and the traditional notion of fairness is not suitable. We then propose a new notion of fairness, which bounds the actual throughput normalized by channel capacity of any two data connections. Using the new fairness definition, we propose a new fair queueing algorithm called CAFQ (Channel Adaptive Fair Queueing), which, as indicated in our numerical studies, outperforms other algorithms in terms of overall system throughput and fairness among error prone connections.