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     

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.     

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

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

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     

A Scalable Packet Sorting Circuit for High-Speed WFQ Packet Scheduling

A novel implementation of a tag sorting circuit for a weighted fair queueing (WFQ) enabled Internet protocol (IP) packet scheduler is presented. The design consists of a search tree, matching circuitry, and a custom memory layout. It is implemented using 130-nm silicon technology and supports quality of service (QoS) on networks at line speeds of 40 Gb/s, enabling next generation IP services to be deployed.     

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.     

基于量子通信的电力业务调度算法

量子通信能够有效提高电力业务传输的可靠性与安全性,但由于量子密钥成码率低,难以满足重要电力业务的加密需求,因此,需要一种队列调度算法对量子通信中的待加密电力业务进行合理调度。提出了一种改进的加权公平队列（weighted fair queuing,WFQ）算法LD-WFQ,算法通过估计待加密数据分组的预计耗时,优先处理即将超时的待加密数据分组,在保持高优先级业务量子加密时延达标率的基础上,有效降低了低优先级业务的量子加密超时率。与WFQ算法进行仿真对比,结果证明了LD-WFQ算法的优越性。     

Matching output queueing with a multiple input/output-queued switch

We have previously proposed an efficient switch architecture called multiple input/output-queued (MIOQ) switch and showed that the MIOQ switch can match the performance of an output-queued switch statistically. In this paper, we prove theoretically that the MIOQ switch can match the output queueing exactly , not statistically, with no speedup of any component. More specifically, we show that the MIOQ switch with two parallel switches (which we call a parallel MIOQ (PMIOQ) switch in this paper) can provide exact emulation of an output-queued switch with a broad class of service scheduling algorithms including FIFO, weighted fair queueing (WFQ) and strict priority queueing regardless of incoming traffic pattern and switch size. To do that, we first propose the stable strategic alliance (SSA) algorithm that can produce a stable many-to-many assignment, and prove its finite, stable and deterministic properties. Next, we apply the SSA algorithm to the scheduling of a PMIOQ switch with two parallel switches, and show that the stability condition of the SSA algorithm guarantees for the PMIOQ switch to emulate an output-queued switch exactly. To avoid possible conflicts in a parallel switch, each input-output pair matched by the SSA algorithm must be mapped to one of two crossbar switches. For this mapping, we also propose a simple algorithm that requires at most 2N steps for all matched input-output pairs. In addition, to relieve the implementation burden of N input buffers being accessed simultaneously, we propose a buffering scheme called redundant buffering which requires two memory devices instead of N physically-separate memories. In conclusion, we demonstrate that the MIOQ switch requires two crossbar switches in parallel and two physical memories at each input and output to emulate an output-queued switch with no speedup of any component.     

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.     

Architectural enhancements for network congestion control applications

Complex network protocols and various network services require significant processing capability for modern network applications. One of the important features in modern networks is differentiated service. Along with differentiated service, rapidly changing network environments result in congestion problems. In this paper, we analyze the characteristics of representative congestion control applications-scheduling and queue management algorithms, and we propose application-specific acceleration techniques that use instruction-level parallelism (ILP) and packet-level parallelism (PLP) in these applications. From the PLP perspective, we propose a hardware acceleration model based on detailed analysis of congestion control applications. In order to get large throughputs, a large number of processing elements (PEs) and a parallel comparator are designed. Such hardware accelerators provide large parallelism proportional to the number of processing elements added. A 32-PE enhancement yields 24/spl times/ speedup for weighted fair queueing (WFQ) and 27/spl times/ speedup for random early detection (RED). For ILP, new instruction set extensions for fast conditional operations are applied for congestion control applications. Based on our experiments, proposed architectural extensions show 10%-12% improvement in performance for instruction set enhancements. As the performance of general-purpose processors rapidly increases, defining architectural extensions (e.g., multi-media extensions (MMX) as in multimedia applications) for general-purpose processors could be an alternative solution for a wide range of network applications.     

智能网中的SCP过载控制研究

本文首先对Ｃａｌｌａｇｐ、Ｐｅｒｃｅｎｔ和漏梭算法进行了比较,得出了漏桶算法健壮性强适用于ＳＳＰ限制呼叫的结论。通过对过载控制框架的描述,提出了一种基于动态调整的控制算法用于ＳＣＰ过载控制。最后将算法进行扩展,使其满足不同的公平性条件,并适合在多业务环境各执行。模拟结果表明此算法具有较好的有效好性和公平性。     

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.     

Fair queueing algorithm with rate independent delay for ATMnetworks

A new scheduling algorithm based on self-clocked fair queueing is proposed. The algorithm employs an array of sorting bins for managing the virtual finishing time of connections and uses token buckets as a behaviour-indicator. It remedies the drawbacks of existing fair queueing algorithms and is able to reserve bandwidth to connections while guaranteeing a class-dependent and rate-independent delay for behaving connections     

A topology-independent wireless fair queueing model in ad hoc networks

Fair queueing of rate and delay-sensitive packet flows in a shared-medium, multihop wireless network is challenging due to the unique design issues. These issues include: 1) spatial contention among transmitting flows in a spatial locality, as well as spatial reuse of bandwidth through concurrent flow transmissions in different network locations; 2) conflicts between ensuring fairness and maximizing spatial channel reuse; and 3) the distributed nature of ad hoc fair queueing. In this paper, we propose a new topology-independent fair queueing model for a shared-medium ad hoc network. Our fairness model ensures coordinated fair channel access among spatially contending flows, while seeking to maximize spatial reuse of bandwidth. We describe packetized algorithms that realize the fluid fairness model with analytical performance bounds. We further design a distributed implementation which approximates the ideal centralized algorithm. We present simulations and analysis on the performance of our proposed algorithms.     

Bursty ATM user traffic allowed by a jitter tolerant leaky bucket and its impact on link utilization

In a network based on the asynchronous transfer mode (ATM), quality of service requirements have to be met even in the presence of users who send traffic as bursty as the policing device allows. For peak cell rate policing with a jitter tolerant leaky bucket, a periodic maximally bursty traffic pattern allowed by the leaky bucket is derived. The impact of this kind of bursty user traffic on the cell loss performance of the remaining sources is investigated by introducing, solving and applying the queueing model Geo(n) + P/D/1/K, where P stands for ‘periodic’. Taking bursty user traffic into account, it is shown that the maximal jitter or cell delay variation allocated to the user and tolerated by the leaky bucket is an important parameter for link utilization. The results help to answer the question under which conditions a shaping function is needed in conjunction with the usage parameter control function.     

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     

一种新的基于GPS的分组公平调度器

GPS(通用处理器共享)是一种调度算法流模型,WFQ(加权公平排队)、WF²Q(最差情形公平加权公平排队)等调度算法都是基于对GPS的模拟.本文证明了WFQ、WF²Q等算法并不是P-GPS(基于分组的GPS),也就不能保证P-GPS的时延及服务特性.此外,本文提出了正确的P-GPS的分组公平调度器模型.     

利用基于测量的WFQ实现比例区分服务模型及其性能分析

本文首先介绍了比例区分服务模型的定义以及现有的两种实现算法BPR和WTP,然后定量地分析了WFQ算法在系统负荷和业务负载分布变化时的性能变化,得出了其本身具有一定的抗突发能力.提出了一种基于测量的可变权值的WFQ调度算法,最后通过仿真,将它与BPR,WTP和WFQ进行了比较.仿真结果证明基于测量的WFQ在业务负载正常分布的情况下性能比WFQ更好,且抗高等级突发的能力更强.     

用户系统基于流的QoS调度

Diff-Serv网与用户系统之间有服务等级协议，有必要对用户系统的分组流进行合理调度，以确保定购的服务等级上速率、突发比特量等符合协议要求。进行合理调度还有有效分配带宽好处。基于流的排队(FBQ)在加权公平分享带宽的同时起到流量整形(traffic shaping)的作用，比较适合这种调度要求。但FBQ对带宽利用率不够高，本文在FBQ分类结构基础上通过新颖的分配令牌参数和虚拟时钟的方法构建新的分级调度算法，保留FBQ优点但提高带宽利用率。