On the speedup required for work-conserving crossbar switches

This paper describes the architecture for a work-conserving server using a combined I/O-buffered crossbar switch. The switch employs a novel algorithm based on output occupancy, the lowest occupancy output first algorithm (LOOFA), and a speedup of only two. A work-conserving switch provides the same throughput performance as an output-buffered switch. The work-conserving property of the switch is independent of the switch size and input traffic pattern. We also present a suite of algorithms that can be used in combination with LOOFA. These algorithms determine the fairness and delay properties of the switch. We also describe a mechanism to provide delay bounds for real-time traffic using LOOFA. These delay bounds are achievable without requiring output-buffered switch emulation     

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.     

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     

RED分组丢弃算法性能研究

 本文研究了在ATM交换机上实现的RED算法的性能.在固定有效带宽、时变有效带宽情况下和同种、异种业务环境下,研究了RED算法的通过率、公平性和时延等性能.经研究表明:RED算法有必要与EPD算法相结合,构成RED+EPD算法.采用RED+EPD算法的ATM交换机通过控制平均排队长度,有效地减小了交换机的平均排队时延.通过与其他分组丢弃算法进行性能比较表明:采用RED+EPD算法的ATM交换机,可提供比EPD算法略高的通过率,更好的公平性和更低的排队时延,能较好地支持具有时延要求的业务.     

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     

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     

WFQ流量调度算法研究

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

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     

The UniMIN switch architecture for large-scale ATM switches

A general expansion architecture is proposed that can be used in building large-scale switches using any type of asynchronous transfer mode (ATM) switch. The proposed universal multistage interconnection network (UniMIN) switch is composed of a buffered distribution network (DN) and a column of output switch modules (OSMs), which can be any type of ATM switch. ATM cells are routed to their destination using a two-level routing strategy. The DN provides each incoming cell with a self-routing path to the destined OSM, which is the switch module containing the destination output port. Further routing to the destined output port is performed by the destination OSM. Use of the channel grouping technique yields excellent delay/throughput performance in the DN, and the virtual FIFO concept is used for implementing the output buffers of the distribution module without internal speedup. We also propose a “fair virtual FIFO” to provide fairness between input links while preserving cell sequence. The distribution network is composed of one kind of distribution module which has the same size as the OSM, regardless of the overall switch size N. This gives good modular scalability in the UniMIN switch. Performance analysis for uniform traffic and hot-spot traffic shows that a negligible delay and cell loss ratio in the DN can be achieved with a small buffer size, and that DN yields robust performance even with hot-spot traffic. In addition, a fairness property of the proposed fair virtual FIFO is shown by a simulation study     

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.     

An Improved Round Robin Packet Scheduler for Wireless Networks

Scheduling algorithms are important components for providing quality-of-service (QoS) guarantees in wireless networks. The design of such algorithms need to take into account bursty errors and location-dependent channel capacity that are characteristics of wireless networks. In this paper, a new scheduling algorithm for packet cellular networks, wireless deficit round robin (WDRR), is proposed. WDRR is a round robin scheduler that has low implementation complexity and offers a low delay bound, tight fairness index, and good isolation property. In error-prone channels, the algorithm provides short-term fairness among sessions that perceive a clean channel, long-term fairness among all sessions, ability to meet specified throughput objectives for all sessions, and graceful service degradation among sessions that received excess service. Both analysis and simulation are used to verify the WDRR properties.     

Credit-based fair queueing (CBFQ): a simple service-schedulingalgorithm for packet-switched networks

This paper proposes a simple rate-based scheduling algorithm for packet-switched networks. Using a set of counters to keep track of the credits accumulated by each traffic flow, the bandwidth share allocated to each flow, and the size of the head-of-line (HOL) packets of the different flows, the algorithm decides which flow to serve next. Our proposed algorithm requires on average a smaller complexity than the most interesting alternative ones while guaranteeing comparable fairness, delay, and delay jitter bounds. To further reduce the complexity, a simplified version (CBFQ-F) of the general algorithm is also proposed for networks with fixed packet lengths, such as ATM, by relaxing the fairness bound by a negligibly small amount     

HSDPA分组调度算法与小区吞吐率研究

分组调度是HSDPA的核心技术之一,对网络性能有重要影响。在HSDPA分组调度功能和实现的基础上,重点分析对比3种典型分组调度算法原理及其对系统的影响,并通过实际测试验证,明确了不同调度算法对小区吞吐率的影响。结论:MAXCI算法下能够得到最大的系统吞吐量,公平性最差;RR算法公平性最好,系统资源利用率最低,吞吐率最小;EPF算法既考虑了用户的公平性,也能从一定程度上保证比较高的系统吞吐量,是一种实用的调度方法。     

Analysis of input and output queueing for nonblocking ATM switches

A switch model for ATM networks is analyzed. Its interconnection network is internally nonblocking and is provided with dedicated input and output queues, one per switch inlet and one per switch outlet. The switch operates with an internal speed-up: more than one packet per slot can be transferred from the head-of-line positions of the input queues to each output queue by the interconnection network. Two different operation modes are considered for the interaction between input and output queues: backpressure mode and queue loss mode. The analytical model developed for the evaluation of the switch performance under random traffic assumes an infinite size for the switch, arbitrary values for input and output queue size, as well as for the speed-up factor. Switch throughput, packet delay and loss performance are evaluated and the analytical model accuracy is assessed using computer simulation results     

Fair and efficient scheduling for UMTS forward link

This paper presents two scheduling algorithms, MWF²Q+ and MDRR, for multiple classes of service over the same spectrum in the forward link of the UMTS network. These scheduling algorithms can allocate bandwidth in proportion to weights of flows sharing the channel, and assign OVSF code to backlogged flows on a frame‐by‐frame basis. The MWF²Q+ algorithm has better fairness properties while the MDRR algorithm requires less computational complexity and space complexity. The fairness properties of these scheduling algorithms are analysed in this paper. Our simulation results show that these two algorithms support multiple traffic sources with heterogeneous rate guarantees while fully utilizing the system bandwidth. The impact of self‐similar traffic is also addressed in our simulations. Copyright © 2005 John Wiley & Sons, Ltd.     

The pi-persistent protocol for unidirectionalbroadcast bus networks

A protocol for multiaccess communication over unidirectional bus networks is proposed, and its performance capabilities are determined. Under this protocol, time is slotted with a slot equaling a packet's transmission time. A station with a packet to send persists in transmitting its packet in an empty slot with probability p_i until it is successful. Three criteria for fairness in selection of the p_i are modeled using Markov chains, which are solved to obtain the proper p_i that satisfy each fairness criterion. Unlike previous studies of unidirectional bus networks, stations are allowed to buffer more than one packet. The average packet delay for this protocol is bounded, and the maximum achievable throughput approaches unity with increasing buffer size. Further, the protocol provides better delay versus throughput behavior for fixed packet lengths than previous round-robin schemes, its performance is insensitive to bus characteristics, and it appears to be particularly well suited for fiber-optic network applications requiring long distances and high bandwidths. Simulation results that confirm the predicted performance are included     

Engineering ATM networks for congestion avoidance

With the combination of telecommunication, entertainment and computer industries, computer networking is adopting a new method called Asynchronous Transfer Mode (ATM) networking. Congestion control plays an important role in the effective and stable operation of ATM networks. Traffic management concerns with the design of a set of mechanisms which ensure that the network bandwidth, buffer and computational resources are efficiently utilized while meeting the various Quality of Service (QoS) guarantees given to sources as part of a traffic contract. In this paper, the most widely recognized congestion control schemes for ABR service are investigated. Some of these schemes show either lack of scalability or fairness while other well‐behaved schemes may require a highly complex switch algorithm that is unsuitable for implementation in cell‐switching high‐speed ATM networks. A new and improved congestion control scheme is proposed to support the best‐effort ABR traffic. This algorithm provides the congestion avoidance ability with high throughput and low delay, in addition to achieving the max–min fairness allocation. This revised version was published online in June 2006 with corrections to the Cover Date.     

A local fairness algorithm for gigabit LAN's/MAN's with spatialreuse

The authors present an algorithm to provide local fairness for ring and bus networks with spatial bandwidth reuse. Spatial bandwidth reuse can significantly increase the effective throughput delivered by the network. The proposed algorithm can be applied to any dual ring or bus architecture such as MetaRing. In the dual bus configuration, when transporting ATM cells, the local fairness algorithm can be implemented using two generic flow control (GFC) bits in the ATM cell header. In the performance it is shown that this local fairness algorithm can exploit the throughput advantage offered by spatial bandwidth reuse better than a global fairness algorithm. This is accomplished because it ensures fair use of network resources among nodes that are competing for the same subset of links, while permitting free access to noncongested parts of the network. The performance advantage of the local fairness scheme is demonstrated by simulating the system under various traffic scenarios and comparing the results to that of the MetaRing SAT-based global fairness algorithm. It is also shown that under certain traffic patterns, the performance of this algorithm achieves the optimal throughput result predicted by the known Max-Min fairness definition     

Quality‐of‐service guarantees architecture with weighted fair shaping

Weighted Fair Queuing (WFQ), conducted for each flow at ATM nodes, is effective for ensuring fairness among differently behaving flows, and for preventing incremental delay as cells are transmitted through multiple nodes. Implemented thus in accordance with rates assigned to flows and actual cell transmission conditions, WFQ is known as “shaping”. This paper proposes a new installable algorithm that dynamically adapts WFQ to each of multiple flows. The Quality‐of‐Service (QoS) guaranteed by this algorithm is also explained. This revised version was published online in June 2006 with corrections to the Cover Date.     

TCP/IPoverATM的性能研究

 本文讨论将传统的TCP拥塞控制机制和CIPOA用于采用ER(FB)算法和EFCI(CCR)算法的ATM网络时可用比特率业务(ABR)和未确定比特率业务(UBR)的性能.仿真结果表明,无论在缓冲区的需求、带宽分配的公平性、吞吐量和链路利用率方面ABR业务的TCP性能均明显优于UBR业务.对于较简单的网络模型ER(FB)算法的TCP性能优于EFCI(CCR)算法,更优于传统的EFCI算法.