Linear-complexity algorithms for QoS support in input-queuedswitches with no speedup

We present several fast, practical linear-complexity scheduling algorithms that enable provision of various quality-of-service (QoS) guarantees in an input-queued switch with no speedup. Specifically, our algorithms provide per-virtual-circuit transmission rate and cell delay guarantees using a credit-based bandwidth reservation scheme. Our algorithms also provide approximate max-min fair sharing of unreserved switch capacity. The novelties of our algorithms derive from judicious choices of edge weights in a bipartite matching problem. The edge weights are certain functions of the amount and waiting times of queued cells and credits received by a virtual circuit. By using a linear-complexity variation of the well-known stable-marriage matching algorithm, we present theoretical proofs and demonstrate by simulations that the edge weights are bounded. This implies various QoS guarantees or contracts about bandwidth allocations and cell delays. Network management can then provide these contracts to the clients. We present several different algorithms of varied complexity and performance (as measured by the usefulness of each algorithm's contract). While most of this paper is devoted to the study of “soft” guarantees, a few “hard” guarantees can also be proved rigorously for some of our algorithms. As can be expected, the provable guarantees are weaker than the observed performance bounds in simulations. Although our algorithms are designed for switches with no speedup, we also derive upper bounds on the minimal buffer requirement in the output queues necessary to prevent buffer overflow when our algorithms are used in switches with speedup larger than one     

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

The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure and a need to introduce guaranteed qualities-of-service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars instead of shared memory systems; QoS can be provided using weighted-fair queueing (WFQ)-based packet scheduling. Until now, however, the two solutions have been mutually exclusive-all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing or centralized shared memory. This paper demonstrates that a combined input/output-queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet-scheduling algorithms, including WFQ and strict priorities. More precisely, we show that for an N×N switch, a “speedup” of 2-1/N is necessary, and a speedup of two is sufficient for this exact emulation. Perhaps most interestingly, this result holds for all traffic arrival patterns. On its own, the result is primarily a theoretical observation; it shows that it is possible to emulate purely OQ switches with CIOQ switches running at approximately twice the line rate. To make the result more practical, we introduce several scheduling algorithms that with a speedup of two can emulate an OQ switch. We focus our attention on the simplest of these algorithms, critical cells first (CCF), and consider its running time and implementation complexity. We conclude that additional techniques are required to make the scheduling algorithms implementable at a high speed and propose two specific strategies     

Degree-sequenced matching algorithms for input-queued switches

This paper presents a class of algorithms for scheduling packets in input-queued switches. As opposed to previously known algorithms that focus only on achieving high throughput, these algorithms seek to achieve low average delay without compromising the throughput achieved. Packet scheduling in input-queued switches based on the virtual-output-queued architecture is a bipartite graph matching problem wherein ports are represented by vertices and the traffic flows by the edges. The set of matched edges determine the packets that are to be transferred from the input ports to the output ports. Current matching algorithms implicitly prioritize high-degree vertices, i.e., ports with a large number of flows, causing longer delays at ports with a smaller number of flows. Motivated by this observation, we present three matching algorithms based on explicitly prioritizing low-degree vertices and the edges through them. Using both real gateway traffic traces as well as synthetically generated traffic, we present simulation results showing that this class of algorithms achieves a low average delay as compared to other scheduling algorithms of equivalent complexity while still achieving similar throughput. We also show that these algorithms determine the maximum size matching in almost all cases.     

Provisioning QoS features for input-queued ATM switches

A new scheduling algorithm is proposed to improve on existing algorithms designed for input-queued ATM switches. By assigning a session weight according to its queue length normalised by its rate and using maximum weight matching to obtain a match, the proposed algorithm can avoid starvation of slow sessions, thus providing good delay properties as well as fair services, and at the same time reducing traffic burstiness     

在CICQ交换结构下实现分布式的WFQ类加权公平调度算法

传统的基于crossbar的输入排队交换结构在提供良好的QoS方面存在很大的不足,而CICQ(Combined Input and Crosspoint buffered Queuing)交换结构与传统的交换结构相比,不但能在各种输入流下提供接近输出排队的吞吐率,而且能提供良好的QoS支持。该文基于CICQ结构,提出了在输入排队条件下实现基于流的分布式WFQ类分组公平调度算法的方案,并通过仿真验证了这一方案的有效性。     

Achieving stability in networks of input-queued switches

Research has generated many interesting results on scheduling input-queued switches. However, most of this work focuses on a single switch in isolation. We study the problem of scheduling a network of input-queued switches. We consider the longest-queue-first and longest-port-first scheduling policies that are stable for a single switch, and show that they can be unstable even for a fixed traffic pattern in a simple network of eight input-queued switches. Moreover, this result holds regardless of how the traffic sharing the same port-pair is scheduled at each switch. On the positive side, we present a policy, longest-in-network, that is stable in networks of input-queued switches. This result holds even if the traffic pattern is allowed to change over time.     

Switching using parallel input-output queued switches with no speedup

We propose an efficient parallel switching architecture that requires no speedup and guarantees bounded delay. Our architecture consists of k input-output-queued switches with first-in-first-out queues, operating at the line speed in parallel under the control of a single scheduler, with k being independent of the number N of inputs and outputs. Arriving traffic is demultiplexed (spread) over the k identical switches, switched to the correct output, and multiplexed (combined) before departing from the parallel switch. We show that by using an appropriate demultiplexing strategy at the inputs and by applying the same matching at each of the k parallel switches during each cell slot, our scheme guarantees a way for cells of a flow to be read in order from the output queues of the switches, thus, eliminating the need for cell resequencing. Further, by allowing the scheduler to examine the state of only the first of the k parallel switches, our scheme also reduces considerably the amount of state information required by the scheduler. The switching algorithms that we develop are based on existing practical switching algorithms for input-queued switches, and have an additional communication complexity that is optimal up to a constant factor.     

Randomized scheduling algorithms for high-aggregate bandwidth switches

The aggregate bandwidth of a switch is its port count multiplied by its operating line rate. We consider switches with high-aggregate bandwidths; for example, a 30-port switch operating at 40 Gb/s or a 1000-port switch operating at 1 Gb/s. Designing high-performance schedulers for such switches with input queues is a challenging problem for the following reasons: (1) high performance requires finding good matchings; (2) good matchings take time to find; and (3) in high-aggregate bandwidth switches there is either too little time (due to high line rates) or there is too much work to do (due to a high port count). We exploit the following features of the switching problem to devise simple-to-implement, high-performance schedulers for high-aggregate bandwidth switches: (1) the state of the switch (carried in the lengths of its queues) changes slowly with time, implying that heavy matchings will likely stay heavy over a period of time and (2) observing arriving packets will convey useful information about the state of the switch. The above features are exploited using hardware parallelism and randomization to yield three scheduling algorithms - APSARA, LAURA, and SERENA. These algorithms are shown to achieve 100% throughput and simulations show that their delay performance is quite close to that of the maximum weight matching, even when the traffic is correlated. We also consider the stability property of these algorithms under generic admissible traffic using the fluid-model technique. The main contribution of this paper is a suite of simple to implement, high-performance scheduling algorithms for input-queued switches. We exploit a novel operation, called MERGE, which combines the edges of two matchings to produce a heavier match, and study of the properties of this operation via simulations and theory. The stability proof of the randomized algorithms we present involves a derandomization procedure and uses methods which may have wider applicability.     

分层循环调度算法初探

在综合现有的一些算法的基础上,提出了一种分层循环(LRR)的调度算法.LRR调度算法采用了两次循环调度,不仅能提供保证速率的服务,而且能提供区分类型的服务,对不同类型的流提供不同的迟延特性,在一定程度上能避免低迟延队列的迟延范围的扩大.     

Downlink scheduling in a cellular network for quality-of-service assurance

We consider the problem of scheduling data in the downlink of a cellular network over parallel time-varying channels, while providing quality-of-service (QoS) guarantees to multiple users in the network. We design simple and efficient admission control, resource allocation, and scheduling algorithms for guaranteeing requested QoS. In our design, a joint Knopp and Humblet (K&H)/round robin (RR) scheduler, composed of K&H scheduling and RR scheduling, utilizes both multiuser and frequency diversity to achieve capacity gain when delay constraints are loose or moderate. However, for tight delay constraints, an additional reference channel scheduler is required to obtain additional frequency diversity gain. The key advantage of our formulation is that the desired QoS constraints can be explicitly enforced by utilizing the concept of effective capacity.     

A distributed scheduling architecture for scalable packet switches

The continuous growth in the demand for diversified quality-of-service (QoS) guarantees in broadband networks introduces new challenges in the design of packet switches that scale to large switching capacities. Packet scheduling is the most critical function involved in the provision of individual bandwidth and delay guarantees to the switched flows. Most of the scheduling techniques proposed so far assume the presence in the switch of a single contention point, residing in front of the outgoing links. Such an assumption is not consistent with the highly distributed nature of many popular architectures for scalable switches, which typically have multiple contention points, located in both ingress and egress port cards, as well as in the switching fabric. We define a distributed multilayered scheduler (DMS) to provide differentiated QoS guarantees to individual end-to-end flows in packet switches with multiple contention points. Our scheduling architecture is simple to implement, since it keeps per-flow scheduling confined within the port cards, and is suitable to support guaranteed and best-effort traffic in a wide range of QoS frameworks in both IP and ATM networks     

Matching algorithms for three-stage bufferless Clos network switches

Three-stage Clos network switches are an attractive solution for future broadband packet routers due to their modularity and scalability. Most three-stage Clos network switches assume either all modules are space switches without memory (bufferless), or employ shared memory modules in the first and third stages (buffered). The former is also referred to as the space-space-space (S/sup 3/) Clos network switch, while the latter is referred to as the memory-space-memory (MSM) Clos network switch. We provide a survey of recent literature concerning switching schemes in the S/sup 3/ Clos network switch. The switching problem in the S/sup 3/ Clos network switch can be divided into two major parts, namely port-to-port matching (scheduling) and route assignment between the first and third stages. Traditionally, researchers have proposed algorithms to solve these issues separately. Recently, a new class of switching algorithms, called matching algorithms for Clos (MAC), has been proposed to solve scheduling and route assignment simultaneously. We focus on the MAC schemes and show that the new class of algorithms can achieve high performance and maintain good scalability.     

Resource allocation for statistical quality of service provision in buffered crossbar switches

The buffered crossbar switch is a promising switching architecture that plays a crucial role for providing quality of service (QoS) in computer networks. Sufficient amount of resources—bandwidth and buffer space—must be allocated in buffered crossbar switches for QoS provision. Resource allocation based on deterministic QoS objectives might be too conservative in practical network operations. To improve resource utilization in buffered crossbar switches, we study the problem of resource allocation for statistical QoS provision in this paper. First, we develop a model and techniques for analyzing the probabilistic delay performance of buffered crossbar switches, which is described by the delay upper bound with a prescribed violation probability. Then, we determine the required amounts of bandwidth and buffer space to achieve the probabilistic delay objectives for different traffic classes in buffered crossbar switches. In our analysis, we apply the effective arrival envelope to specify traffic load in a statistical manner and characterize switch service capacity by using the service curve technique. Instead of just focusing on one specific type of scheduler, the model and techniques developed in this paper are very flexible and can be used for analyzing buffered crossbar switches with a wide variety of scheduling algorithms. Copyright © 2007 John Wiley & Sons, Ltd.     

Analysis model of multiple input-queued switches with PIMscheduling algorithm

In this letter, we propose a new analysis model of multiple input-queued switches that use the parallel iterative matching (PIM) scheduling algorithm under i.i.d Bernoulli traffic. Compared to the previous analysis models, our approach incurs very low computational complexity while maintaining good accuracy by employing a simple queueing model. Specifically, we model an input queue of the switch as a synchronous Geom/Geom/1/B queue with a service rate which is directly obtained from a PIM scheduling algorithm. We perform the simulation and verify the accuracy of our model     

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.     

Scheduling reserved traffic in input-queued switches: new delay bounds via probabilistic techniques

We consider the problem of providing delay bounds to reserved traffic in high-speed input-queued switches. We assume that the matrix of bandwidth demands is known, and we use the now standard approach of decomposing this matrix into a convex combination of permutation matrices. Our problem, therefore, reduces to the problem of constructing a schedule for these permutation matrices. We derive delay bounds for four algorithms that are based on probabilistic techniques. For each algorithm, we first place tokens randomly in continuous time for each permutation matrix. If the nth token that appears corresponds to permutation matrix M/sub k/, then we schedule matrix M/sub k/ in the nth time slot. The algorithms differ in how the random token processes are defined. For two of the algorithms, we are able to perform a derandomization so as to obtain deterministic schedules. We show through numerical computation that in many situations the resulting delay bounds are smaller than the previously best-known delay bounds of Chang et al. (see Proc. IEEE IWQoS, London, U.K., 1999 and Proc. IEEE INFOCOM, Tel-Aviv, Israel, Mar 2000).     

一种公平输入排队调度算法

输入排队交换结构以其良好的可扩展性被越来越多的高速交换机和路由器所采用。当前的调度算法大都以牺牲公平性来换取最大的吞吐量。但随着对QoS支持的要求增强,适用于输入排队交换结构的高效、公平的调度算法成为迫切需要解决的问题。该文提出了一种具有公平性保证的基于虚服务量的公平调度算法。理论分析和计算机仿真都表明算法在信元时延和公平性方面都能提供较好的保证。算法还具有与iSLIP相同的较低通信开销,以及和iLQF相同的算法复杂度。因此,算法具有较好的实用性。     

Captured-frame eligibility and round-robin matching for input-queued packet switches

A variety of matching schemes for input-queued (IQ) switches that deliver high throughput under traffic with uniform distributions has been proposed. However, there is a need of matching schemes that provide high throughput under several admissible traffic patterns, including those with nonuniform distributions, while keeping implementation complexity low. In this letter, first, we introduce the captured frame concept for matching schemes in IQ switches. Second, we propose a round-robin based matching scheme, uFORM, which uses the proposed concept for cell matching eligibility. We show via simulation that our matching scheme delivers high throughput under several nonuniform traffic patterns, and retains the high performance under uniform traffic that round-robin matching schemes are known to offer.     

A fair optimization scheduling scheme for IEEE 802.16 networks in multimedia applications

IEEE 802.16 networks are designed based on differentiated services concept to provide better Quality of Service (QoS) support for a wide range of applications, from multimedia to typical web services, and therefore they require a fair and efficient scheduling scheme. However, this issue is not addressed in the standard. In this paper we present a new fair scheduling scheme which fulfills the negotiated QoS parameters of different connections while providing fairness among the connections of each class of service. This scheme models scheduling as a knapsack problem, where a fairness parameter reflecting the specific requirements of the connections is defined to be used in the optimization criterion. The proposed scheduler is evaluated through simulation in terms of delay, throughput and fairness index. The results show fairness of the scheduling scheme to all connections while the network guarantees for those connections are fulfilled.     

一种可提供QoS保障的新型交换结构

本文采用带缓存交叉开关作为核心交换单元,构建了一种空分复用扩展的联合输入/交叉节点/输出排队(SDM-CICOQ)交换结构,从理论上证明了当扩展因子为2时,SDM-CICOQ交换结构可以获得100%的吞吐量,并且能够完全模拟输出排队(OQ)交换结构,从而能够提供服务质量(QoS)保障.本文还给出了一种层次化优先级调度(HPS)方案作为SDM-CICOQ交换结构调度机制的工程设计参考,仿真结果表明采用HPS调度方案SDM-CICOQ交换结构可获得良好的性能.