A scheduler ASIC for a programmable packet switch

While the Internet is successful in supporting traditional data-only traffic, an integrated services Internet is inevitable with the emergence of new applications such as voice, video, multimedia, and interactive video conferencing. Such an integrated services network should support a wide range of applications with diverse quality of service requirements and traffic characteristics. Provision for quality of service in packet networks in general, and in the Internet in particular, is the focus of most of the recent developments in switching and routing system design. We designed a generic, single-queue scheduler engine for use in a programmable packet switch/router to handle IP packets, ATM cells, or a combination of both. Comprising 275,000 gates, the 0.35-micron ASIC is incorporated into a prototype programmable packet switch     

A neural-fuzzy system for congestion control in ATM networks

We propose the use of a neural-fuzzy scheme for rate-based feedback congestion control in asynchronous transfer mode (ATM) networks. Available bit rate (ABR) traffic is not guaranteed quality of service (QoS) in the setup connection, and it can dynamically share the available bandwidth. Therefore, congestion can be controlled by regulating the source rate, to a certain degree, according to the current traffic flow. Traditional methods perform congestion control by monitoring the queue length. The source rate is decreased by a fixed rate when the queue length is greater than a prespecified threshold. However, it is difficult to get a suitable rate according to the degree of traffic congestion. We employ a neural-fuzzy mechanism to control the source rate. Through learning, membership values can be generated and cell loss can be predicted from the status of the queue length. Then, an explicit rate is calculated and the source rate is controlled appropriately. Simulation results have shown that our method is effective compared with traditional methods.     

Fuzzy-Based Dynamic Distributed Queue Scheduling for Packet Switched Networks

Addressing the problem of queue scheduling for the packet-switched system is a vital aspect of congestion control. In this paper, the fuzzy logic based decision method is adopted for queue scheduling in order to enforce some level of control for traffic of different quality of service requirements using predetermined values. The fuzzy scheduler proposed in this paper takes into account the dynamic nature of the Internet traffic with respect to its time-varying packet arrival process that affects the network states and performance. Three queues are defined, viz low, medium and high priority queues. The choice of prioritizing packets influences how queues are served. The fuzzy scheduler not only utilizes queue priority in the queue scheduling scheme, but also considers packet drop susceptibility and queue limit. Through simulation it is shown that the fuzzy scheduler is more appropriate for the dynamic nature of Internet traffic in a packet-switched system as compared with some existing queue scheduling methods. Results show that the scheduling strategy of the proposed fuzzy scheduler reduces packet drop, provides good link utilization and minimizes queue delay as compared with the priority queuing (PQ), first-in-first-out (FIFO), and weighted fair queuing (WFQ).     

ATM网络拥塞控制中PID控制器的设计

自适应比特（ABR）业务的流量控制是ATM网络中一种有效的拥塞控制机制和流量管理手段。在大规模的高速网络中，算法的简洁性对优化交换机的性能是至关重要的。尽管二进制ABR流量控制的简洁性具有相当的吸引力，但显式前向拥塞标识（Explicit Forward Congestion Indication,EFCI)算法控制的队列长度和允许信元速率（Allowed Cell Rate,ACR)大幅振荡，降低了链路利用率，严重的影响了交换机的性能，为此有了相对复杂却有效的显式速率反馈机制，在该文中，引入了拥塞的概率判定机制，并运用经典控制理论为拥塞判定概率的实量更新设计了线性的PID控制器，避免了非线性的控制规律可能诱发的系统自激振荡，在PID控制器的参数整定上，因为使用常用处受到限制，进而给出了一种基于确定稳定裕度的参数整定方法，仿真试验表明：二进制流量控制中的PID算法在保持了算法简洁性的前提下，大幅度地抑制了ACR和队列长度的振荡，提高了链路利用率，减小了队列系统引入的时延抖动，为保证ATM网络中的服务质量（Quality of Service,Qos)提供了必要的技术支持。     

Burstiness in broadband integrated networks

Since broadband integrated networks have to cope with a wide range of bit rates, the notion of burstiness which expresses the irregularity of a flow, has been recognized as a vital question for such networks. In burstiness characterization encountered in the literature, special attention is given to the squared coefficient of variation of interarrival time (Cv²) in a cell arrival process. In order to observe the impact of a bursty flow on a queue, we introduce in this paper a new class of arrival process, the n-stage Markov Modulated Bernoulli Process, MMBP_n, for short, and its peculiar case, the n-stage Hyper-Bernoulli process, denoted by HBP_n. We numerically solve the MMBP_n/D/1/K and we compute in particular the rejection probability and the mean waiting time. For that purpose, a relation between the stationary queue length distribution and arrival time distribution is established. This relation adapts the GASTA equality to the arrival process under consideration. We then discuss the relevance of Cv² for burstiness characterization through an example: the HBP₂/D/1/K queue. We show that Cv² becomes significant only when local overload occurs, i.e., when the arrival rate is momentarily greater than the server rate. The results are then applied to two basic ATM problems: traffic characterization and buffer dimensioning using bursty inputs.     

一种利用ABR业务保证多媒体传输基本质量的方法

在ATM网络中利用可用比特率(ABR)业务支持多媒体传输具有流量管理上的优势.该文提出了利用可用比特率(ABR)业务保证多媒体通讯基本服务质量的机制,并给出相应的支持算法.     

Fast,Fair and Frugal Bandwidth Allocation in ATM Networks

Abstract. ATM networks are used to carry a variety of types of traffic. For some types of traffic, in particular Available Bit Rate (ABR) traffic, the bandwidth of a network is typically insufficient to satisfy the requests of all the sessions, and so some fair allocation scheme must be devised. The ATM Forum, the standards setting body for ATM networks, has specified that the fairness criterion for ABR traffic should be Max-Min Fairness , which intuitively means that raising the bandwidth of any session comes at the expense of some other session of no greater bandwidth. Protocols to allocate bandwidth to sessions in a max-min fair manner are an important part of a network design. For a protocol to be realistic, it must conform to the Resource Management (RM) cell mechanism specified by the ATM Forum. Such RM cells get sent as a constant fraction of all cells sent by the source; however, they have only a few fields. RM cells are the only means of communication allowed from link to link so any reasonable protocol is totally distributed and asynchronous, since the RM cell mechanism does not easily lend itself to synchronization. Finally, RM Cells must be handled very quickly at each link. We call a protocol frugal if at each link it performs O(1) computation per RM cell and uses O(1) space per session. Recently, several frugal RM cell protocols have been proposed for ABR traffic, but none have been shown to converge to the max-min fair state. Protocols that are known to converge in a linear number of maximum round-trip times require RM cell processing that is linear in the number of sessions that go through a link. In this paper we give a frugal RM cell protocol for ABR that matches the convergence time of the fastest known non-frugal protocol. A second type of ABR traffic is the Minimum Cell Rate (MCR) type, where every session can specify a minimum amount of bandwidth. The max-min fair allocation should then respect these MCR requests. We extend our results to give the first frugal RM cell protocol for MCR and achieve a quadratic convergence rate.     

Binary ABR flow control over ATM networks with uncertainty using discrete-time variable structure controller

A binary available bit rate (ABR) scheme based on discrete-time variable structure control (DVSC) theory is proposed to solve the problem of asynchronous transfer mode (ATM) networks congestion in this paper. A discretetime system model with uncertainty is introduced to depict the time-varying ATM networks. Based on the system model, an asymptotically stable sliding surface is designed by linear matrix inequality (LMI). In addition, a novel discrete-time reaching law that can obviously reduce chatter is also put forward. The proposed discrete-time variable structure controller can effectively constrain the oscillation of allowed cell rate (ACR) and the queue length in a router. Moreover, the controller is self-adaptive against the uncertainty in the system. Simulations are done in different scenarios. The results demonstrate that the controller has better stability and robustness than the traditional binary flow controller, so it is good for adequately exerting the simplicity of binary flow control mechanisms.     

Binary ABR flow control over ATM networks with uncertainty using discrete-time variable structure controller

A binary available bit rate （ABR） scheme based on discrete-time variable structure control （DVSC） theory is proposed to solve the problem of asynchronous transfer mode （ATM） networks congestion in this paper. A discrete-time system model with uncertainty is introduced to depict the time-varying ATM networks. Based on the system model, an asymptotically stable sliding surface is designed by linear matrix inequality （LMI）. In addition, a novel discrete-time reaching law that can obviously reduce chatter is also put forward. The proposed discrete-time variable structure controller can effectively constrain the oscillation of allowed cell rate （ACR） and the queue length in a router. Moreover, the controller is self-adaptive against the uncertainty in the system. Simulations are done in different scenarios. The results demonstrate that the controller has better stability and robustness than the traditional binary flow controller, so it is good for adequately exerting the simplicity of binary flow control mechanisms.     

基于速率的反馈拥塞控制的最优化问题研究

基于速率的反馈拥塞控制用于ＡＴＭ网络中可用位速率（ＡＢＲ）流量控制。可用位速率业务需要最优和稳定的流量控制器来保证高的吞吐量和保证网络的稳定性。本文采用线性控制理论来设计基于速率的流量控制器。这个控制器是一个简单的比例控制器,使用品质因数来优化参数。文中证实了最优化控制器对系统参数的最小依赖性。     

ABR流量控制中的变结构控制器

自适应比特(available bit rate,简称ABR)业务的流量控制是ATM网络中一种有效的拥塞控制机制和流量管理手段.在高速的ATM网络中,算法的简洁性在很大程度上决定着交换机的性能.尽管二进制ABR流量控制的简洁性具有相当大的吸引力,但标准的EFCI算法控制的队列长度和允许信元速率(allowed cell rate,简称ACR)却容易出现大幅振荡的现象,这势必会降低链路的利用率,严重影响交换机的性能.进而又有了相对复杂却有效的显式速率反馈机制.在此研究中,以已有的ABR流量控制模型为基础,应用概率拥塞判定机制,并借助鲁棒控制理论中滑模变结构控制器的设计方法,为ABR流量控制设计了一种新的二进制算法,避免了标准EFCI算法中非线性环节诱发的自激振荡,这对于充分发挥二进制流控算法的简洁性以及优化交换机的性能是极为有利的.仿真实验表明:二进制流量控制中的滑模变结构算法大幅度地抑制了ACR和队列的振荡,平滑了由此而引入的时延抖动,为实现ATM网络中的服务质量提供了可靠的实现机制.     

ATM网络传输控制机制研究及进展

ATM网络中的传输控制方法的研究涉及到网络中的服务质量、服务类型。已经提出了许多不同特点的控制机制,主要集中在基于许可证方案和基于速率方案的设计,随着ATM广域网应用和因特网信息浏览的增多,新的研究热点是有速度反馈控制的用于ABR服务类型的传输控制技术。本文进一步研究和讨论ATM网络中所采用拥塞控制策略存在的问题和在当今网络应用考虑的主要因素。     

Design and analysis of a merging algorithm for multipoint-to-point ABR service in ATM networks

In this paper, we propose a merging algorithm, which can provide efficient support for multipoint-to-point ABR service in ATM networks. By forwarding the FRM cells belonging to the VC with the largest FRM-cell arrival rate in a merge point, the proposed algorithm can achieve better link utilization than existing merging algorithms. In addition, the proposed algorithm reduces the number of FRM cells forwarded by a merge point. As a result, it can reduce the control overhead of ABR service. Most importantly, it does not incur extra complexity in switches. We also discuss the impact of different network topologies on our algorithm. Simulation results show that the proposed algorithm is able to achieve better performance while requiring significantly fewer RM cells.     

First-order rate-based flow control with dynamic queue threshold for high-speed wide-area ATM networks

In this paper we present a new rate-based flow control scheme for ATM ABR services and analyze its performance. The proposed algorithm, which we refer to as first-order rate-based flow control (FRFC) is the most simple form of queue-length-based flow control. The asymptotic stability, the steady-state throughput, queue length and fairness, and the transient behavior are analyzed for the case of multiple connections with diverse round-trip delays. We also consider a novel approach to dynamically adjust a queue threshold in the FRFC according to the changes in the available bandwidth, and the arrival and departure of connections. Simulations show that the simple FRFC with dynamic queue threshold (DQT) effectively maintains high throughput, small loss and a desired fairness in these dynamic environments and is a promising solution for ABR flow control in ATM networks.     

A new state space control scheme for Host-Gate Way Rate Control Protocol within intranets using ATM ABR service

In this paper, a new control strategy based on Host-Gate Way Rate Control Protocol is proposed for intranet congestion management. A more sophisticated optimal control algorithm based on a state space approach will be proposed via using the Available Bit Rate (ABR) service of an Asynchronous Transfer Mode (ATM) backbone network. The stability of the proposed control algorithm will be analyzed and the benefits of the algorithm are investigated thoroughly. Simulations confirm that the proposed new algorithm will produce lower queue level variance at the gateway. This implies that smaller buffers can fulfill the requirement for a given loss probability. Moreover, the queue level variance is less sensitive to variations in the ABR bandwidth model. This is true even when a self-similar long-range dependent trace is used to represent the ABR bandwidth in simulations, which is encouraging in view of the known self-similar nature of both LAN traffic and compressed video streams that will be sharing the ATM network.     

Tiny Tera: a packet switch core

Describes Tiny Tera: a small, high-bandwidth, single-stage switch. Tiny Tera has 32 ports switching fixed-size packets, each operating at over 10 Gbps (approximately the Sonet OC-192e rate, a telecom standard for system interconnects). The switch distinguishes four classes of traffic and includes efficient support for multicasting. We aim to demonstrate that it is possible to use currently available CMOS technology to build this compact switch with an aggregate bandwidth of approximately 1 terabit per second and a central hub no larger than a can of soda. Such a switch could serve as a core for an ATM switch or an Internet router. Tiny Tera is an input-buffered switch, which makes it the highest bandwidth switch possible given a particular CMOS and memory technology. The switch consists of three logical elements: ports, a central crossbar switch, and a central scheduler. It queues packets at a port on entry and optionally prior to exit. The scheduler, which has a map of each port's queue occupancy, determines the crossbar configuration every packet time slot. Input queueing, parallelism, and tight integration are the keys to such a high-bandwidth switch. Input queueing reduces the memory bandwidth requirements: When a switch queues packets at the input, the buffer memories need run no faster than the line rate. Thus, there is no need for the speedup required in output-queued switches     

Stability, queue length, and delay of deterministic and stochasticqueueing networks

We present two types of stability problems: 1) conditions for queueing networks that render bounded queue lengths and bounded delay for customers, and 2) conditions for queueing networks in which the queue length distribution of a queue has an exponential tail with rate &thetas;. To answer these two types of stability problems, we introduce two new notions of traffic characterization: minimum envelope rate (MER) and MER with respect to &thetas;. We also develop a set of rules for network operations such as superposition, input-output relation of a single queue, and routing. Specifically, we show that: 1) the MER of a superposition process is less than or equal to the sum of the MER of each process, 2) a queue is stable in the sense of bounded queue length if the MER of the input traffic is smaller than the capacity, 3) the MER of a departure process from a stable queue is less than or equal to that of the input process, and 4) the MER of a routed process from a departure process is less than or equal to the MER of the departure process multiplied by the MER of the routing process. Similar results hold for MER with respect to &thetas; under a further assumption of independence. For single class networks with nonfeedforward routing, we provide a new method to show that similar stability results hold for such networks under the first come, first served policy. Moreover, when restricting to the family of two-state Markov modulated arrival processes, the notion of MER with respect to &thetas; is shown to be equivalent to the recently developed notion of effective bandwidth in communication networks     

基于ABR业务的自适应广义预测流量控制策略

针对ABR业务传输存在大时延的情况，设计了一种自适应广义预测（GPC）流量控制器；该算法实现简单，适合计算机控制系统实现．在大时延ATM网络中具有实际应用价值；仿真结果表明，该算法能够快速有效地调节ABR分组发送速率和缓冲区排队队列。提高链路利用率，有效地克服了时延影响。     

Scheduling and admission control policies: A case study for ATM

Scheduling mechanisms and admission policies play an important role in optimising resource allocation in networks offering integrated services. The scheduler mediates the low-level contention for service between cells of different classes, while admission control regulates the acceptance or blocking of incoming traffic on a connection-by-connection basis. These two levels of control are of course closely related in the sense that if too much traffic is allowed to enter the network by an overly lax admission control policy, then no scheduler will be able to provide the requested Quality of Service (QoS) for all traffic classes. A functioning admission control is a prerequisite for any guarantee of cell-level QoS while its merit is to guarantee QoS efficiently and fairly. We focus on an ATM switch to demonstrate these principles.