Optimal algorithm for scheduling CBR traffic in ATM switches

A non-blocking input buffered ATM switch that supports CBR and ABR traffic using a TDM scheduler frame is considered. A new TDM scheduler algorithm (largest-first) for CBR traffic is compared with four others, based on the evenness of the distribution of unused timeslots in the scheduling frame. An even distribution of unused slots minimises the average latency and jitter for ABR traffic. Simulation results show that largest-first allocation is the best     

Multirate scheduling of VBR video traffic in ATM networks

One of the major attractions of asynchronous transfer mode (ATM) networks for transporting bursty video traffic is its ability to exploit the multiplexing gains of packet switching while providing quality of service guarantees. Unfortunately, most of the multiplexing mechanisms proposed in the literature fail to exploit the multiplexing gains of ATM. We propose a multirate service mechanism that allows a session to be served at different rates at different times. Applications generating bursty data, such as variable bit-rate (VBR) video, can take advantage of multirate service by requesting a high rate of service for brief periods of bursty arrivals and a much lower rate of service for all other times. Consequently, the applications can improve their delay performance without reserving a high bandwidth for the entire duration of the sessions. Furthermore, the scheduler can multiplex the peaks and the lulls in service rates of different sessions and improve the utilization of the system. Using MPEG video traces from a number of applications, we show that multirate servers outperform single-rate PGPS (packet-by-packet generalized processor sharing) servers and CBR (constant bit-rate) servers in terms of number of connections admitted, while providing the same level of service guarantees. We also investigate the performance of multirate service when service quality need not be guaranteed. We refer to this as predictive service. We propose a measurement-based admission control procedure for predictive service, and show that it helps increase the size of the admissible region even further     

Real-time CBR traffic scheduling in IEEE 802.16-based wireless mesh networks

This paper studies packet transmission scheduling for real-time constant-bit-rate (CBR) traffic in IEEE 802.16-based wireless mesh networks. We first formulate and solve the scheduling problem as a binary linear programming problem. The computational complexity of the optimum scheduling solution may prevent it from being implemented in practice. We then propose a heuristic scheme, namely bottleneck first scheduling scheme, where scheduling decisions at stations (base station or subscriber stations) with higher traffic loads are done before those at stations with lower traffic loads. At each station, scheduling decisions for CBR packets with more hops to their destinations are done first. Numerical results show that the proposed scheduling scheme achieves the same capacity as the optimal one while obtaining satisfactory delay performance. Dongmei Zhao received the Ph.D. degree in Electrical and Computer Engineering from the University of Waterloo, Waterloo, Ontario, Canada in June 2002. Since July 2002 she has been with the Department of Electrical and Computer Engineering, McMaster University, Hamilton, Ontario, Canada where she is an assistant professor. Dr. Zhao’s research interests include modeling and performance analysis, quality-of-service provisioning, access control and admission control in wireless networks. Dr. Zhao is a member of the IEEE and a registered Professional Engineer of Ontario. Jun Zou received the B.S. and M. Eng. Degrees from Tianjin University, China in 1999 and 2002, respectively. He worked at Siemens Communication Networks Ltd., Beijing from 2002 to 2004. Currently, he is a Ph.D. student at McMaster University, Canada. His research interests include wireless networking, routing protocols, architecture of next generation networks, network security and their applications in telecommunication industry.     

IFQ:一种新的ATM网络业务调度算法

本文提出了插空公平公队列（ＩＦＱ）调度算法。由于该方法考虑了ＡＴＭ网络中不同种类连接的特性,能充分利用网络资源。理论分析和仿真实验表明,ＩＦＱ算法能为Ｇ连接提供预约带宽保证和确定的时延上界,满足业务的实时传输要求。同时ＩＦＱ调度算法还具有连接独立性特点,能灵活地分配带宽资源。     

Implicit scheduling algorithm for dynamic slot assignment inwireless ATM networks

A novel scheduling algorithm is proposed for the MAC (medium access control) protocol in wireless asynchronous transfer mode networks. The proposed algorithm has been demonstrated to be an effective means of implementing dynamic slot assignment without explicitly transmitting the dynamic parameters for variable bit rate traffic     

The DDTCI switch algorithm for ABR traffic control in ATM networks

For the issue of flow control for Available Bit Rate (ABR) traffic in ATM network,a new improved Explicit Rate (ER) algorithm named Dynamic Double Threshold Congestion Indication (DDTCI) algorithm is presented based on the Explicit Forward Congestion Indication (EFCI) Current Cell Rate (CCR) algorithm and Relative Rate (RR) algorithm. Different from the early ER algorithm, both the high-level and the low-level threshold is dynamically changing according to the state of the bottleneck node. We determinate the congestion state with the information of the two dynamic threshold, and control the cell rate of the source by feed back mechanism. Except for the well performance in both link utilization and fairness in distribution of available bandwidth, the improved algorithm can alleviate the fluctuation of sending rate dramatically. The mechanism is modeled by a fluid model, and the useful expressions are derived.Simulation results show up our conclusion.     

Delay analysis for CBR traffic under static-priority scheduling

We examine the delay performance of packets from constant-bit-rate (CBR) traffic whose delay is affected by non-real-time traffic. The delay performance is analyzed by solving the nD/D/1 queue with vacations. We obtain an exact and closed form solution, hence obviating the need of any approximations or numerical Laplace inversions. We then provide various numerical results for low-bit-rate transmission links, in which packets can experience large delay. From our quantitative evaluation, we conclude that there exists an optimum packet size for a given delay bound. In extremely slow links, such as modem links, transmission control protocol (TCP) packets should be segmented to reduce the CBR delay. We therefore investigate the delay impact of TCP packet sizes as well     

Neural networks for adaptive traffic control in ATM networks

Neural networks (NNs) have several valuable properties for implementing ATM traffic control. The authors present NN-based solutions for two problems arising in connection admission control, affecting the grade of service (GOS) at both the cell and call levels, and propose that neural networks may increase the network throughput and revenue     

Intelligent traffic control for ATM broadband networks

Performance results prove that a neural networks approach achieves better results, simpler and faster, than algorithmic approaches. The focus of this paper is to shed light on how neural networks (NNs) can be used to solve many of the serious problems encountered in the development of a coherent traffic control strategy in ATM networks. The main philosophy that favors neural networks over conventional programming approaches is their learning and adaptive capabilities, which can be utilized to construct adaptive (and computationally intelligent) algorithms for allocation of resources (e.g., bandwidth, buffers), thus providing highly effective tools for congestion control     

ATM SAR处理器发送数据业务的信元调度算法

叙述了ＡＴＭ ＳＡＲ（Ｓｅｇｍｅｎｔａｔｉｏｎ Ａｎｄ Ｒｅａｓｓｅｍｂｌｙ）处理器发送信元的机理,讨论了基于发送调度表的业务成形方式产生的信元时延抖动（Ｃｅｌｌ Ｄｅｌａｙ Ｖａｒｉａｔｉｏｎ,ＣＤＶ）以及信元时延抖动容限（Ｃｅｌｌ Ｄｅｌａｙ Ｖａｒｉａｔｉｏｎ Ｔｏｌｅｒａｎｃｅ,ＣＤＶＴ）,推导了ＣＤＶＴ的计算公式,设计了使最小的信元调度算法ＮＶＳＴ（Ｎｅａｒ Ｖｉｒｔｕａｌ Ｓｄｅｎ Ｔ     

An isochronous and asynchronous traffic scheduling algorithm fordual-star WDM networks

In this paper, based on the concept of wavelength reusing, a new architecture for interconnecting two wavelength division multiplexing (WDM) star networks is proposed. According to this architecture, the problem of scheduling isochronous as well as asynchronous traffic is investigated. The lower bounds for the problem of minimizing the switching duration and the number of switching modes are derived. A transmission scheduling algorithm for the proposed architecture to efficiently reuse the wavelength is also proposed. For only asynchronous traffic, the analytical result shows that the proposed scheduling algorithm produces solutions equal to the lower bounds. For both isochronous and asynchronous traffic, simulation results show that the average switching duration and the average number of switching modes obtained by the proposed algorithm are quite close to the lower bounds. Simulation results also show that given the same number of users and available wavelengths, the solutions (in terms of the average switching duration and the average number of switching modes) obtained by the proposed scheduling algorithm on the dual-star WDM networks are better than the solutions obtained by the two-phase algorithm on the similar dual-star WDM networks     

The distributed robust traffic controller for ATM networks

We propose an approach to design a distributed rate‐based traffic controller to flow‐regulate the best‐effort service (e.g. ABR) traffic and guaranteed service traffic through an ATM switch. The controller is distributed among the source nodes and has a very simple structure. Its local controller at each source node is open‐loop stable and only requires the knowledge of the buffer occupancy at the bottleneck switch. We show that this controller is fair and is not sensitive to the change of VCs over time. It does not have oscillation and can achieve a high utilization. Copyright © 2001 John Wiley & Sons, Ltd.     

Traffic classification and scheduling in ATM networks

Virtual paths (VPs) are an integral part of the resource management and control hierarchy of ATM (asynchronous transfer mode) networks. To improve the utilization of network resources and facilitate management and control, source types are organized into traffic classes. Each traffic class is transported by its own virtual path subnetwork. In this paper, we consider issues related to the design of traffic classes. We consider an ATM switch node to which cells arrive from a diverse set of source types. Traffic classes are assumed to be served according to a weighted round robin policy, while cells belonging to a given traffic class are served in first-come-first-served order. We consider the problem of determining the optimal set of traffic classes. Under suitable simplifying assumptions, it is shown that the above problem can be modeled as a set-partitioning problem. The structure of the problem at hand is then exploited to develop an efficient heuristic. Several examples are given to illustrate the developed methodology.Supported partially through NSF Grant NCR-891447 and AT&T Grant 5-23690.     

PERFORMANCE ANALYSIS OF LEAKY BUCKET ALGORITHM WITH BURSTY TRAFFIC INPUT IN ATM NETWORKS

A bursty traffic model is introduced in this paper to describe the statistical characteristics of packet video. The performance of leady bucket algorithm with bursty traffic input is analyzed. The influences of various parameters on QOS (Quality of Service) are investigated. The analysis shows that although the loss probability decreases through expanding the buffer capacity, the delay and delay jitter increase, whose effect on QOS will not be negligible.     

A hybrid analysis/simulation for ATM performance with application to quality-of-service of CBR traffic

A discrete time queueing model for the performance of an ATM system is analyzed using matrix analytic methods. Time is segmented into slots with each slot equal to the transmission time of one ATM cell. The ATM system is modeled as a single server queue with Markovian arrivals and service time equal to one slot. The arrival process includes as a special case the superposition of on-off sources, possibly heterogeneous. The queueing model is of the M/G/1 type. By exploiting the structure of the M/G/1 type Markov chain, the complexity of the solution to the problem is reduced to only the inversion of a 2×2 matrix irrespective of the size of the Markov chain. This simplification allows us to investigate Constant Bit Rate (CBR) traffic performance (or quality-of-service) issues through a hybrid analysis/simulation approach. Specifically, we analyze the impact of on-off background traffic on the probability of consecutive cell losses, cell delay variation, and traffic shaper or playback buffer underflow and overflow probabilities of CBR traffic sources.     

An iterative cell scheduling algorithm for ATM input-queued switchwith service class priority

An iterative cell scheduling algorithm for asynchronous transfer mode (ATM) input-queued switch with service class priority is proposed in this paper. At inputs of the switch the VC's or VP's are discriminated into classes of services and in each class an iterative round robin matching scheduler is provided. A performance analysis is carried out by simulation and the results show a very promising ATM switch for the proposed algorithm     

WFQ流量调度算法研究

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

A traffic measurement method and its application for cell lossprobability estimation in ATM networks

Focuses on how to determine a set of parameters describing cell arrival stream characteristics and how to evaluate the accuracy of these measurements. Since a cell arrival stream is both correlated and bursty, the autocorrelation characteristics between the number of arriving cells in two adjacent intervals are analyzed, and then the time interval is determined for which the autocorrelation may be neglected. It is also shown that this set of parameters can represent the first and approximately second moment statistics during any interval. A method of estimating cell loss probability through the use of a queuing model that has an input process is presented. The input process is determined from the set of parameters that describe the characteristics of the source. In order to verify the accuracy, a brief simulation study is carried out