Virtual path routing for survivable ATM networks

The advent of high-capacity optical fiber has increased the impact of a network failure in high-speed networks since a large volume of data can be lost even in a short outage. Self-healing algorithms have previosly been proposed to achieve fast restoration from a failure, but their success greatly depends on how traffic is distributed and how spare capacity is dimensioned over the network when a failure happens. Thus, in order to offer better network survivability, it is crucial that a network manager realizes a restorable traffic assignment in response to changing traffic demand and facility network configuration. The authors address the problem of virtual path routing for survivable asynchronous transfer mode (ATM) networks. An algorithm is developed to find a virtual path configuration and bandwidth assignment that minimizes the expected amount of lost flow upon restoration from a network failure. The concept of two-step restoration is introduced to achieve fast restoration as well as optimal reconfiguration. The problem can be formulated as a nonlinear, nonsmooth multicommodity flow problem with linear constraints. A modified flow deviation method is developed to obtain a near-optimal solution, where premature convergence to a nonsmooth point could be avoided by adjusting an optimization parameter. The result of the performance evaluation indicates that the proposed routing scheme can detect the links that are vulnerable to a failure under the current traffic demand pattern and adjust a flow so as to improve the network survivability level     

Migrating sockets-end system support for networking with quality ofservice guarantees

We present an end system architecture designed to support networking with quality of service (QoS) guarantees. The protocol processing component of the architecture, called migrating sockets, has been designed with minimal hidden scheduling which enables accurate determination of the rate requirement of a user application. The end system provides QoS guarantees using: 1) an adaptive rate-controlled scheduler; 2) rate-based flow control on the send side for access to reserved-rate network connections; and 3) a constant overhead active demultiplexing mechanism on the receive side which can be transparently enabled in wide-area TCP/IP internetworking (although it is not restricted to TCP/IP). To achieve efficiency, migrating sockets lets user applications manage network endpoints with minimal system intervention, provides user level protocols read-only access to routing information, and integrates kernel level support previously built for efficient data movement. Migrating sockets is backward compatible with Unix semantics and Berkeley sockets. It has been used to implement Internet protocols such as TCP, UDP, and IP (including IP multicast), and run existing applications such as vic. Migrating sockets has been implemented in Solaris 2.5.1. We discuss our implementation experience, and present performance results of our system running on Sun Sparc and Ultra workstations, as well as Pentium-II desktops     

Exploitation of DWDM for optical packet switching with quality ofservice guarantees

This paper addresses the problem of building optical packet switches that are able to effectively cope with variable length packet traffic and quality of service management, therefore able to support IP traffic. The paper aims at showing that the availability of dense wavelength division multiplexing is crucial. By suitably exploiting the wavelength dimension a multistage fiber delay line buffer can be implemented, with fine granularity and long delay with an architecture of limited complexity. This is necessary to fulfill the buffering requirements of variable length packets. Furthermore, the wavelength domain is proved to be more effective than the time domain to manage different levels of quality of service. Algorithms are presented that are peculiarly designed for this environment showing that they can effectively differentiate the packet loss probability between three priority classes     

Virtual path and link capacity design for ATM networks

A path and link capacity design method for asynchronous transfer mode (ATM) networks using statistical multiplexing of cells is proposed. By developing the design method, the statistical cell multiplexing effect can be exploited to significantly reduce required network resources. The necessary design procedures are identified. A simple and effective policing mechanism is proposed. An analytical method for the evaluation of cell multiplexing characteristics using declared parameters is provided. Path and link capacity design algorithms that use these techniques are proposed. The effectiveness of the proposed design procedure is confirmed by comparing analytical results to those from a computer simulation     

Dynamic call admission control in ATM networks

The authors present dynamic call admission control using the distribution of the number of cells arriving during the fixed interval. This distribution is estimated from the measured number of cells arriving at the output buffer during the fixed interval and traffic parameters specified by users. Call acceptance is decided on the basis of online evaluation of the upper bound of cell loss probability, derived from the estimated distribution of the number of calls arriving. QOS (quality of service) standards can be guaranteed using this control when there is no estimation error. The control mechanism is effective when the number of call classes is large. It tolerates loose bandwidth enforcement and loose policing control, and dispenses with modeling of the arrival processes. Numerical examples demonstrate the effectiveness of this control, and implementation is also discussed     

A method for call admission control in ATM networks with heterogeneous sources

We present a procedure for call admission control for ATM networks. The procedure can be applied to deciding if an additional Virtual Channel (user, source) can be assigned to an end-to-end Virtual Path, or if a link connecting two ATM switches can carry an additional VC. Each source is characterized by its peak rate, mean rate, and cycle length. The objective is to admit as many sources as possible, while meeting a desirable level of cell loss probability. We adapt an effective bandwidth technique to the case where sources do not have to belong to a small number of classes. We do this by suggesting an upper bound for the cell-loss-probability for the case of heterogeneous Markovian on-off sources, and by showing that its computation can be performed in real time by the sending switch, with a reasonable amount of computational and storage resources. We show by simulation that the proposed procedure is effective even for highly bursty source mixes, where it achieves more than 80% of the theoretically possible multiplexing gain.     

Efficient call admission control for heterogeneous services inwireless mobile ATM networks

An efficient call admission control scheme for handling heterogeneous services in wireless ATM networks is proposed. Quality-of-service provisioning of jitter bounds for constant bit rate traffic and delay bounds for variable bit rate traffic is used in the CAC scheme to guarantee predefined QoS levels for all traffic classes. To reduce the forced handoff call dropping rate, the CAC scheme gives handoff calls a higher priority than new calls by reserving an appropriate amount of resources for potential handoff calls. Resource reservation in the CAC scheme makes use of user mobility information to ensure efficient resource utilization. Simulation results show that the proposed CAC scheme can achieve both low handoff call dropping rate and high resource utilization     

Stochastic control of path optimization for inter-switch handoffsin wireless ATM networks

One of the major design issues in wireless ATM networks is the support of inter-switch handoffs. An inter-switch handoff occurs when a mobile terminal moves to a new base station connecting to a different switch. Apart from resource allocation at the new base station, inter-switch handoff also requires connection rerouting. With the aim of minimizing the handoff delay while using the network resources efficiently, the two-phase handoff protocol uses path extension for each inter-switch handoff, followed by path optimization if necessary. The objective of this paper is to determine when and how often path optimization should be performed. The problem is formulated as a semi-Markov decision process. Link cost and signaling cost functions are introduced to capture the tradeoff between the network resources utilized by a connection and the signaling and processing load incurred on the network. The time between inter-switch handoffs follows a general distribution. A stationary optimal policy is obtained when the call termination time is exponentially distributed. Numerical results show significant improvement over four other heuristics     

A call admission control scheme for ATM networks using a simplequality estimate

The authors propose a call admission control scheme based on a method of estimating cell loss quality for individual bursty traffic sources. The estimate is expressed in terms of virtual cell loss probability, which may be defined by two traffic characteristic parameters alone: peak and mean rate. The approach is suitable for the estimation of real cell loss probability in heterogeneous and homogeneous traffic models when burst length is larger than buffer capacity. The concept of virtual cell loss probability is extended to the individual call level so as to be able to estimate the quality of service (QOS) provided to individual calls. A virtual bandwidth method is used to develop a practical call admission control system. Quality is ensured by combining a traffic clustering scheme, with a scheme for assigning individual clusters to subcapacities of a link. Priority levels are presented in terms of the class of QOS required, i.e., deterministic or statistical, and the allocation of virtual bandwidth is discussed in terms of both QOS class and traffic characteristics     

Providing rate guarantees for internet application traffic across ATM networks

The TCP⁄IP protocol suite is the standard requirement for all applications that need to communicate over the Internet. As TCP⁄IP applications are unable to specify the QoS parameters needed for most Asynchronous Transfer Mode (ATM) services, they tend to use the unspecified bit rate (UBR) service category when running across ATM networks. The UBR service utilizes any bandwidth that is left unused by the rest of the ATM services. This has led the ATM Forum's Traffic Management Group to define a new service category called guaranteed frame rate (GFR). GFR is intended to provide minimum cell rate guarantees and fair access to excess bandwidth left over from higher-priority services. This article first presents a tutorial overview of GFR and then presents a survey of the research work that has been carried out toward the design and implementation of associated ATM switch mechanisms.     

Performance analysis for the dynamic virtual path bandwidth control method in ATM networks

Broadband ISDN (integrated services digital network) should provide various kinds of communication services for multimedia traffic, including voice, computer data, still picture and motion video, and an ATM (asynchronous transfer mode) technology is expected to satisfy those demands. In ATM networks, a VP (virtual path) concept is introduced for simplifying the network resource management. However, if the bandwidth of each VP is fixed, it cannot absorb traffic load fluctuation. In this case, it is likely to happen that one VP has no remaining bandwidth while other VPs on the same physical link have free capacities. Another extremity is that a VP is not introduced, and that all VCs along the same physical link share the whole bandwidth of the link. This can achieve an efficient use of the link, but it apparently requires complicated call set-up procedures. In this paper, we propose a new dynamic VP bandwidth control method, in which the bandwidth allocated to each VP is dynamically changed according to traffic fluctuation. More specifically, in the case that multiple VPs are multiplexed on the same link between two nodes, when the utilization of some VP is increased, that VP requests an additional bandwidth. When the traffic load becomes low and the utilization of a VP is decreased, a part of the assigned bandwidth is released. We consider two methods for this purpose; one is the basic method in which the bandwidth increase request is issued after the VP bandwidth is exhausted. The other is the look-ahead method where the bandwidth increase is requested in advance before the bandwidth starvation. An approximate analysis for the above methods is provided, and the validation of its accuracy is assessed by comparing with simulation results. Through numerical examples, we show that our methods can provide performance improvement in terms of call loss probabilities of each VP.     

Source-independent call acceptance procedures in ATM networks

Strategies for connection admission control in asynchronous transfer mode (ATM) networks are considered. Without any Poisson or renewal assumptions, two easily computable upper bounds on the time congestion in a finite buffer are derived. The first upper bound is valid for arbitrary peak and mean-rate-policed sources, whereas the second (and, in principle, tighter) bound is valid for sources of the on/off type. The tightnesses of the bounds are evaluated by a new periodic queuing model taking into account the maximum allowed burst duration. It is concluded that the bounds form a basis for a realization of a simple admission control algorithm. Furthermore, it is pointed out that the derivation of the on/off bound induces a decomposition of the queuing process into a cell-scale contribution and a burst-scale contribution, a decomposition which is superior to traditional Markov modulated approaches both in accuracy, and in offering insight into the queuing process     

Integration of ATM call admission control and link capacity controlby distributed neural networks

An adaptive call admission control using neural networks was recently proposed for asynchronous transfer mode (ATM) communications networks. The author proposes adaptive link capacity control using neural networks. Neural networks are trained to estimate the call loss rate from link capacity and observed traffic, and link capacity assignment is optimized by a random optimization method according to the estimated call loss rate. The integration of adaptive call admission control and adaptive link capacity control yields an efficient ATM traffic control system suitable for multimedia communication services with unknown traffic characteristics. Computer simulation results using a simple network model are also given to evaluate the accuracy and efficiency of the proposed method     

Design of a real-time call admission controller for ATM networks

In this paper, we present a real-time computation algorithm based on the bufferless fluid flow model [Jabbari and Yegenolu, 1992] for call admission control (CAC) on one link of an asynchronous transfer mode (ATM) network with heterogeneous bursty traffic. Cell loss probability is adopted as the measure of quality-of-service (QoS). Our computation algorithm requires a constant memory size and needs only two multiplications and one division to determine whether a connection request can be accepted or not. It is known [Murase et al., 1991], that due to the interference between different types of traffic the individual cell loss probability may not meet the requirement even though the global one does. In this paper, we provide a close upper-bound for individual cell loss probability which can easily be obtained with our computation algorithm. Numerical examples using typical traffic parameters are studied to corroborate the upper-bound. We also compare the performance of the investigated CAC scheme with that of the effective bandwidth technique [Elwalid and Mitra, 1993]     

Modeling and call admission control algorithm of variable bit ratevideo in ATM networks

The authors propose a new method for the modeling and call admission control (CAC) of variable bit rate video source, which come to the front of ATM networks as hot issues nowadays. First, the modeling of video source is accomplished using the three-state Markov chains including the effects of scene change at which the bit rate of video source is abruptly increased. Also, using two AR models, they improve the defects which an AR model has in modeling a video source. In addition, they represent the analytical model of a video source so that a network manager can acquire the information which is very important in managing the entire networks. CAC is accomplished using the previously defined analytical model. A routing manager calculates the cell loss probability of a chosen VP where a new call is connected so that the routing manager decides whether this new call is accepted or not. This calculation is accomplished through the GB/D/1-S queuing system. Using BIA (bandwidth increasing algorithm), they check whether the calls rejected by the routing manager could be accepted if possible. Finally, the applicable procedures to suitable allocate bandwidth to each VP on a link are presented in detail     

Credit-based flow control for ATM networks

Simulation, analysis, and experiments on switching hardware have shown that for a wide variety of traffic patterns, credit control is fair, uses links efficiently, minimizes delay, and guarantees no cell loss due to congestion. The credit-based mechanism proposed by the authors provides flow control tailored to ATM networks     

Cell‐level/call‐level ATM switch simulator

A B‐ISDN national project in Korea has been carried out to develop a National Information Superhighway since 1992. An ATM switching system has been developed as one of the most important parts in the project, and has been tested in the National Information Superhighway testbed. In this paper, we develop a cell‐level/call‐level ATM switch simulator using cell‐level and call‐level input traffic models for evaluating the ATM switching system. The cell‐level simulator models various cell‐level switching functions such as priority control and multicast, and evaluates the cell‐level performance indices of the ATM switch in terms of cell delay, throughput, and cell loss probability. On the other hand, the call‐level simulator uses call‐level traffic models and evaluates the call blocking rate as a call‐level quality of service (QoS). This revised version was published online in August 2006 with corrections to the Cover Date.     

Self-healing virtual path architecture in ATM networks

ATM network techniques have been actively researched and developed with the goal of realizing B-ISDN. ATM networks can transport signals of various services efficiently and economically, and offer the benefit of enhanced flexibility if the virtual path (VP) concept is adopted. Therefore, the ATM network will provide the infrastructure for B-ISDN. One of the most important themes in B-ISDN is the increased level of network reliability required to to match the high volume of data transmission that will be incurred by the information society and the “mission critical” nature of such data. The authors summarize self-healing network (SHN) schemes they have developed, and discuss problems that must be solved to realize SHN     

A dynamic call admission scheme for VBR traffic in ATM networks

The role of call admission control (CAC) in high-speed networks is to maintain the network utilization at a high level, while ensuring that the quality of service (QoS) requirements of the individual calls are met. We use the term static CAC to describe schemes that always allocate the same bandwidth to a specific group of multiplexed calls, independent of the other traffic sharing the link. Dynamic CAC, on the other hand, denotes a scheme in which the bandwidth allocation to a group of calls sharing a queue is influenced by the traffic in other queues destined for the same outgoing link. We propose a generic dynamic call admission scheme for VBR and ABR traffic whose aim is to reduce the blocking rate for VBR calls at the expense of a higher blocking rate for ABR calls. Our scheme is generic because it builds up on a pre-existing static scheme, e.g., one based on a simple notion of effective bandwidth. Our simple approach results in a significant reduction of the blocking rate for VBR traffic (several orders of magnitude), if the bandwidth requirements of a single call are a reasonably small fraction of the link capacity. At the same time, the deterioration of service for ABR traffic can be contained. This revised version was published online in August 2006 with corrections to the Cover Date.