Efficient fair queueing algorithms for packet-switched networks

Although weighted fair queueing (WFQ) has been regarded as an ideal scheduling algorithm in terms of its combined delay bound and proportional fairness properties, its asymptotic time complexity increases linearly with the number of sessions serviced by the scheduler, thus limiting its use in high-speed networks. An algorithm that combines the delay and fairness bounds of WFQ with O(1) timestamp computations had remained elusive so far. In this paper we present two novel scheduling algorithms that have O(1) complexity for timestamp computations and provide the same bounds on end-to-end delay and buffer requirements as those of WFQ. The first algorithm, frame-based fair queueing (FFQ), uses a framing mechanism to periodically recalibrate a global variable tracking the progress of work in the system, limiting any short-term unfairness to within a frame period. The second algorithm, starting potential based fair queueing (SPFQ), performs the recalibration at packet boundaries, resulting in improved fairness while still maintaining the O(1) timestamp computations. Both algorithms are based on the general framework of rate-proportional servers (RPSs) introduced by Stiliadis and Varma (see ibid., vol.6, no.2, p.164-74, 1998). The algorithms may be used in both general packet networks with variable packet sizes and in asynchronous transfer mode (ATM) networks     

Dynamic fair scheduling with QoS constraints in multimedia wideband CDMA cellular networks

A class of dynamic fair scheduling schemes based on the generalized processor sharing (GPS) fair service discipline, under the generic name code-division GPS (CDGPS), is proposed for a wideband direct-sequence code-division multiple-access (CDMA) cellular network to support multimedia traffic. The CDGPS scheduler makes use of both the traffic characteristics in the link layer and the adaptivity of the wideband CDMA physical layer to perform fair scheduling on a time-slot by time-slot basis, by using a dynamic rate-scheduling approach rather than the conventional time-scheduling approach. Soft uplink capacity is characterized for designing an efficient CDGPS resource allocation procedure. A credit-based CDGPS (C-CDGPS) scheme is proposed to further improve the utilization of the soft capacity by trading off the short-term fairness. Theoretical analysis shows that, with the C-CDGPS scheme, tight delay bounds can be provided to delay-sensitive traffic, and short-term unfairness can be bounded so that long-term weighted fairness for all users can still be satisfied. Simulation results show that bounded delays, increased throughput, and long-term fairness can be achieved for both homogeneous and heterogeneous traffic.     

Exact GPS Simulation and Optimal Fair Scheduling With Logarithmic Complexity

Generalized processor sharing (GPS) is a fluid scheduling policy providing perfect fairness over both constant-rate and variable-rate links. The minimum deviation (lead/lag) with respect to the GPS service achievable by a packet scheduler is one maximum packet size. To the best of our knowledge, the only packet scheduler guaranteeing the minimum deviation is worst-case fair weighted fair queueing , which requires on-line GPS simulation. Existing algorithms to perform GPS simulation have worst-case computational complexity per packet transmission (being the number of competing flows). Hence, has been charged for complexity too. However it has been proven that the lower bound complexity to guarantee deviation is, yet a scheduler achieving such a result has remained elusive so far. In this paper, we present L-GPS, an algorithm that performs exact GPS simulation with worst-case complexity and small constants. As such it improves the complexity of all the packet schedulers based on GPS simulation. We also present , an implementation of based on L-GPS. has complexity with small constants, and, since it achieves the minimum possible deviation, it does match the aforementioned complexity lower bound. Furthermore, both L-GPS and comply with constant-rate as well as variable-rate links. We assess the effectiveness of both algorithms by simulating real-world scenarios.     

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.     

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.     

On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms

We clarify, extend, and solve a long-standing open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the difference between the time a packet finishes service in a scheduling algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS-relative delay. We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling algorithm that guarantees O(1) GPS-relative delay bound is /spl Omega/(logn). We also discover that, surprisingly, the complexity lower bound remains the same even if the delay bound is relaxed to O(n/sup a/) for 0相似文献   

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.     

Start-time fair queueing: a scheduling algorithm for integratedservices packet switching networks

We present a start-time fair queueing (SFQ) algorithm that is computationally efficient and achieves fairness regardless of variation in a server capacity. We analyze its single server and end-to-end deadline guarantee for variable rate fluctuation constrained (FC) and exponentially bounded fluctuation (EBF) servers. To support heterogeneous services and multiple protocol families in integrated services networks, we present a hierarchical SFQ scheduler and derive its performance bounds. Our analysis demonstrates that SFQ is suitable for integrated services networks since it: (1) achieves low average as well as maximum delay for low-throughput applications (e.g., interactive audio, telnet, etc.); (2) provides fairness which is desirable for VBR video; (3) provides fairness, regardless of variation in server capacity, for throughput-intensive, flow-controlled data applications; (4) enables hierarchical link sharing which is desirable for managing heterogeneity; and (5) is computationally efficient     

Carry-over round robin: a simple cell scheduling mechanism for ATMnetworks

We propose a simple mechanism named carry-over round robin (CORR) for scheduling cells in asynchronous transfer mode networks. We quantify the operational complexity of CORR scheduling and show that it is comparable to that of a simple round-robin scheduler. We then show that, albeit its simplicity, CORR is very competitive with much more sophisticated and significantly more complex scheduling disciplines in terms of performance. We evaluate the performance of CORR using both analysis and simulation, We derive analytical bounds on the worst case end-to-end delay achieved by a CORR scheduler for different traffic arrival patterns. Using traffic traces from MPEG video streams, we compare the delay performance of CORR with that of packet-by-packet generalized processor sharing (PGPS) and stop-and-go (SG). Our results show that, in terms of delay performance, CORR compares favorably with both PGPS and SG. We also analyze the fairness properties of CORR and show that it achieves near perfect fairness     

提供端到端时延和时延抖动保障的QoS控制

 提出了一类具有最大速率控制的速率保障(Maximum Rate Control-Guaranteed Rate,MRC-GR)算法,可对流同时提供速率保障和最大速率控制.当网络各节点执行MRC-GR算法时,提供了确定网络端到端时延上限和下限的方法,针对服从令牌桶模型和同步单元模型的业务源给出了网络时延上限和下限.针对MRC-GR算法实例——具有最大速率控制的最差情形公平加权公平排队(worst-case fair weighted fair queueing with maximum rate control)调度算法进行仿真实验,仿真结果验证了理论分析.     

SRR: an O(1) time-complexity packet scheduler for flows in multiservice packet networks

We present a novel fair queueing scheme, which we call Smoothed Round Robin (SRR). Ordinary round-robin schedulers are well known for the burstiness of their scheduling output. In order to overcome this problem, SRR codes the weights of the flows into binary vectors to form a Weight Matrix and then uses a Weight Spread Sequence (WSS), which is specially designed to distribute the output more evenly, to schedule packets by scanning a Weight Matrix. By using the WSS and the Weight Matrix, SRR emulates the Generalized Processor Sharing (GPS) well. SRR possesses better short-term fairness and scheduling delay properties in comparison with various existing round-robin schedulers. At the same time, SRR preserves O(1) time complexity by avoiding the time-stamp maintenance employed in various fair queueing schedulers. Simulation and implementation experiments show that SRR provides good mean end-to-end delay for soft real-time services. SRR can be implemented in high-speed networks to provide quality of service due to its simplicity and low time complexity.     

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     

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     

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     

Network delay analysis of a class of fair queueing algorithms

A self-clocked fair queueing (SCFQ) scheme has been proposed by Golestani (see Proc. IEEE INFOCOM, p. 636-636, 1994) as an easily implementable version of fair queueing. In this paper, the worst case network delay performance of a class of fair queueing algorithms, including the SCFQ scheme, is studied. We build upon and generalize the methodology developed by Parekh and Gallager (see ACM/IEEE Trans. Networking, vol.1, no.3, p.344-357, 1993, and vol.2, no.2, p.137-150, 1994) to study this class of algorithms based on the leaky-bucket characterization of traffic. Under modest resource allocation conditions, the end-to-end session delays and backlogs corresponding to this class of algorithms are shown to be bounded. For the SCFQ scheme, these bounds are larger, but practically as good as the corresponding bounds for the PGPS scheme. It is shown that the SCFQ scheme can provide adequate performance guarantees for the delay-sensitive traffic in ATM     

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.     

Efficient delay based scheduling with fairness in multi-hop wireless mesh networks

Some scheduling algorithms have been designed to improve the performance of multi-hop wireless mesh networks (WMNs) recently. However the end-to-end delay is seldom considered as the complexity of multi-hop topology and open wireless shared channel. This article proposes an efficient delay based scheduling algorithm with the concept of buffer-data- hops. Considering the demand satisfaction factor (DSF), the proposed algorithm can also achieve a good fairness performance. Moreover, with the interference-based network model, the scheduling algorithm can maximize the spatial reuse, compared to those graph-based scheduling algorithms. Detailed theoretical analysis shows that the algorithm can minimize the end-to-end delay and make a fair scheduling to all the links.     

The Stratified Round Robin Scheduler: Design, Analysis and Implementation

Stratified Round Robin is a fair-queueing packet scheduler which has good fairness and delay properties, and low quasi-O(1) complexity. It is unique among all other schedulers of comparable complexity in that it provides a single packet delay bound that is independent of the number of flows. Importantly, it is also amenable to a simple hardware implementation, and thus fills a current gap between scheduling algorithms that have provably good performance and those that are feasible and practical to implement in high-speed routers. We present both analytical results and simulations to demonstrate its performance properties     

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.