共查询到20条相似文献,搜索用时 15 毫秒
1.
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 相似文献
2.
Matching output queueing with a combined input/output-queued switch 总被引:19,自引:0,他引:19
Shang-Tse Chuang Goel A. McKeown N. Prabhakar B. 《Selected Areas in Communications, IEEE Journal on》1999,17(6):1030-1039
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 相似文献
3.
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. 相似文献
4.
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 相似文献
5.
6.
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. 相似文献
7.
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. 相似文献
8.
Giaccone P. Prabhakar B. Shah D. 《Selected Areas in Communications, IEEE Journal on》2003,21(4):546-559
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. 相似文献
9.
在综合现有的一些算法的基础上,提出了一种分层循环(LRR)的调度算法.LRR调度算法采用了两次循环调度,不仅能提供保证速率的服务,而且能提供区分类型的服务,对不同类型的流提供不同的迟延特性,在一定程度上能避免低迟延队列的迟延范围的扩大. 相似文献
10.
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. 相似文献
11.
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 相似文献
12.
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. 相似文献
13.
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. 相似文献
14.
Hyoung-Il Lee Seung-Woo Seo 《Communications Letters, IEEE》2001,5(7):316-318
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 相似文献
15.
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. 相似文献
16.
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). 相似文献
17.
18.
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. 相似文献
19.
Leila Pishdad Hamid R. Rabiee Nasim Mirarmandehi 《Journal of Visual Communication and Image Representation》2010,21(2):167-174
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. 相似文献
20.
本文采用带缓存交叉开关作为核心交换单元,构建了一种空分复用扩展的联合输入/交叉节点/输出排队(SDM-CICOQ)交换结构,从理论上证明了当扩展因子为2时,SDM-CICOQ交换结构可以获得100%的吞吐量,并且能够完全模拟输出排队(OQ)交换结构,从而能够提供服务质量(QoS)保障.本文还给出了一种层次化优先级调度(HPS)方案作为SDM-CICOQ交换结构调度机制的工程设计参考,仿真结果表明采用HPS调度方案SDM-CICOQ交换结构可获得良好的性能. 相似文献