Virtual topology design and flow routing in optical networks under multihour traffic demand

This article addresses the problem of finding a static virtual topology design and flow routing in transparent optical wavelength division multiplexing networks under a time-varying (multihour) traffic demand. Four variants of the problem are considered, using fixed or dynamically adaptable (meaning variable) flow routing, which can be splittable or unsplittable. Our main objective is to minimize the number of transceivers needed which make up for the main network cost. We formulate the problem variants as exact integer linear programs (ILPs) and mixed ILPs. For larger problem instances, we also propose a family of heuristics based on the concept of domination between traffic matrices. This concept provides the theoretical foundations for a set of techniques proposed to reduce the problem complexity. We present a lower bound to the network cost for the case in which the virtual topology could be dynamically reconfigured along time. This allows us to assess the limit on the maximum possible benefit that could be achieved by using optical reconfigurable equipment. Extensive tests have been conducted, using both synthetically generated and real-traced traffic demands. In the cases studied, results show that combining variable routing with splittable flows obtains a significant, although moderate, cost reduction. The maximum cost reduction achievable with reconfigurable virtual topologies was shown to be negligible compared to the static case in medium and high loads.     

A neurocomputing controller for bandwidth allocation in ATMnetworks

We propose a new neurocomputing call admission control (CAC) algorithm for asynchronous transfer mode (ATM) networks. The proposed algorithm employs neural networks (NNs) to calculate the bandwidth required to support multimedia traffic with multiple quality-of-service (QoS) requirements. The NN controller calculates the bandwidth required percall using on-line measurements of the traffic via its count process, instead of relying on simple parameters such as the peak, average bit rate and burst length. Furthermore, to enhance the statistical multiplexing gain, the controller calculates the gain obtained from multiplexing multiple streams of traffic supported on separate virtual paths (i.e., class multiplexing). In order to simplify the design and obtain a small reaction time, the controller is realized using a hierarchical structure of a bank of small size, parallel NN units. Each unit is a feed-forward back-propagation NN that has been trained to, learn the complex nonlinear function relating different traffic patterns and QoS, with the corresponding received capacity. The reported results prove that the neurocomputing approach is effective in achieving more accurate results than other conventional methods that are based upon mathematical or simulation analysis. This is primarily due to the unique learning and adaptive capabilities of NNs that enable them to extract and memorize rules from previous experience. Evidently such unique capabilities poise NNs to solve many of the problems encountered in the development of a coherent ATM traffic management strategy     

Medium-term centralized virtual-path bandwidth control based ontraffic measurements

The paper presents a centralized virtual path bandwidth (VPB) control scheme for ATM networks which satisfies mainly three specifications: a) optimality during a medium-term control interval, b) fast time response so as to absorb the medium-term traffic fluctuations, and c) easy implementation. The paper mainly points at the impact of direct, on-line traffic measurements on bandwidth control. The control objective is to rearrange the installed bandwidth of the virtual paths according to the offered traffic so as to minimize the maximum call blocking probability of the whole network. Network simulation shows that a sophisticated VPB controller which relies on simple measurements of the offered traffic can substantially improve the performance of an ATM network. The necessary bandwidth rearrangement time is also examined by simulation     

Network planning based on virtual path bandwidth management

Periodical performance evaluation and adaptive resource assignment, already proposed as performance-oriented management, seems to be the most suitable strategy for network planning under demand uncertainty. In this paper, we exploit the inherent capability of ATM networks to rearrange dynamically the already installed resources, and propose performance-oriented management combined with virtual path bandwidth (VPB) control for the planning of the extensions of bandwidth capacities of virtual paths (VPs) and transmission links of the network. We define a large network optimization problem and solve it by a rigorous, analytical procedure. The optimization model comprises specific requirements of the network-planning problem and a bandwidth distribution scheme ensuring network reliability. We reveal the efficiency of the proposed scheme by applying it on a model network, considering two realistic case-studies of network-traffic evolution. We show that in the presence of VPB control: (a) the initial distribution of the total bandwidth to VPs is of no importance, since it can be adaptively rearranged according to the offered traffic, (b) the network is well used and bandwidth investment could be saved, and (c) whenever additional bandwidth must be installed in VPs which have an unanticipated bad grade-of-service, time savings result. We present the network performance in detail, in figures, and compare this with the performance of the network in the absence of VPB control.     

Adaptive bandwidth management in ATM networks

A framework for adaptive bandwidth management in ATM based networks is proposed. It is based on a layered approach which includes bandwidth allocation to virtual networks. The central concept of this approach is adaptive estimation of the effective bandwidth required, by connections carried in the network. To achieve reliable results the estimation process takes into account both the traffic source declarations and the connection superposition process measurements on the network links. This is done in an optimization framework provided by estimation theory. A study, based on a linear two-state Kalman filter, shows that the proposed approach provides good adaptation to undeclared changes in traffic parameters and that the network performance is significantly improved when compared to the effective bandwidth allocation based solely on the source parameters declarations. These features allow more relaxed source parameter declarations and at the same time permit less stringent source policing. Thus the two bottlenecks influencing bandwidth management in ATM networks can be significantly widened.     

Design of ATM Networks with Multiple Traffic Classes

In this paper, we propose a new heuristic design algorithm for the virtual path (VP)-based ATM network with multiple traffic classes, in which QoS constraints associated with traffic class are taken into account. The minimum bandwidth of VP required to carry given amount of traffic is obtained by utilizing an equivalent bandwidth concept, and the route of each VP is placed so that the network cost is minimized while the QoS requirement is fulfilled. To evaluate our design algorithm, we consider two kinds of traffic: voice traffic as low speed service and still picture traffic as high speed service. Through numerical examples, we demonstrate that our design method can achieve an efficient use of network resources, which results in providing a cost-effective VP-based ATM network.     

Some approaches to solving a multihour broadband network capacity design problem with single-path routing

In this paper, we consider solution approaches to a multihour combined capacity design and routing problem which arises in the design of dynamically reconfigurable broadband communication networks that uses the virtual path concept. We present a comparative evaluation of four approaches, namely: a genetic algorithm, a Lagrangian relaxation based subgradient optimization method, a generalized proximal point algorithm with subgradient optimization, and, finally, a hybrid approach where the subgradient based method is combined with a genetic algorithm. Our computational experience on a set of test problems of varying network sizes services) shows that the hybrid approach often is the desirable choice in obtaining the minimum cost network while the genetic algorithm based approach has the most difficulty in solving large scale problems. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Variable-bandwidth optical paths: comparison between optical code-labelled path and OCDM path

In a conventional wavelength-routed network, the bandwidth of one wavelength is considered as the minimum granularity for a given connection request. Therefore, no multiple connection requests can be accepted by using a single wavelength simultaneously. This may cause inefficiency in the bandwidth utilization in some cases. In this paper, the focus is on the variable-bandwidth approach called an optical code (OC)-based path to improve this bandwidth utilization. The concept of OC-enabling paths is investigated, which shows its potential in resolving the above granularity problem inherent to the wavelength-routed network. First, two optical paths, called the OC-labeled and OC division multiplexing (OCDM) paths, are proposed. The former is based upon label switching and statistical multiplexing, while the latter is based upon OCDM. Next, OC-label and OCDM optical cross connects are described to support OC-labeled and OCDM paths, respectively. In this paper, a coherent time-spread OC is adopted. A two-state flow-fluid traffic model is addressed and regarded as the general analysis model. Finally, the performances between these proposed paths are qualified and compared, and numerical results show that the OC-labeled path outperforms the OCDM path under short burst duration time, whereas the OCDM path, provides higher flexibility than the OC-labeled path, owing to its independence of burst duration time.     

Broad-band ATM network architecture based on virtual paths

Broadband transport techniques and network architectures based on the virtual path concept are examined. ATM (asynchronous transfer mode) techniques, when coupled with recent technological innovations, are expected to pave the way for future universal transport networks. The virtual path concept, which exploits the ATM's capabilities, is proposed to construct an efficient and economic network. The concept matches current and anticipated technological trends well. Characteristics and implementation techniques of virtual paths are discussed. Advantages of the virtual path concept and its impact on the transport network architecture are demonstrated. The virtual path strategy is also shown to provide efficiently for networks with dynamic reconfiguration capability which will enhance network performance. Some basic analytical results on the dynamic control effects of virtual paths are provided     

MULTICAST ROUTING SCHEMES IN ATM

In this study, we investigate the problem of accommodating multicast traffic in ATM networks, with emphasis on the virtual path (VP) environment. We propose a network structure called “virtual copy network” that is suitable for multicast communication and connection setup scheme, taking into account the VP environment. With our technique, we can expect statistical multiplexing gain in accommodating multiple multicast traffic streams over a VP. Also, we propose two multicast routing algorithms (the CNR-LH algorithm and the improved CNR-LH algorithm) for an ATM network environment. In these algorithms, in addition to determining an adequate route, the exact corresponding VPs on the route are also obtained. We examine the efficiency of the algorithms by demonstrating their basic characteristics using computer simulations.     

Modified least loaded routing in virtual path based ATM networks

We consider a Virtual Path (VP) based ATM network supporting multiple traffic classes with heterogeneous traffic characteristics. Using simple FIFO scheduling policy at the ATM multiplexer, we assume that all traffic require identical end‐to‐end quality of service (QoS) requirement. The concept of effective bandwidth is used to determine the required bandwidth to guarantee the specified QoS requirement. We study the problem of using dynamic routing to VP‐based ATM networks by transforming it into an equivalent multi‐rate circuit‐switched network problem. To further simplify the analysis, we restrict the choice of path to single‐link and two‐link routes. We propose a dynamic routing algorithm based on the Least Loaded Routing (LLR) with packing. Simulation results are used to compare the performance of this algorithm with other dynamic routing schemes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Design and Configuration of Reconfigurable ATM Networks with Unreliable Links

This paper considers a problem of configuring both physical backbone and logical virtual path (VP) networks in a reconfigurable asynchronous transfer mode (ATM) network where links are subject to failures. The objective is to determine jointly the VP assignment, the capacity assignment of physical links and the bandwidth allocation of VPs, and the routing assignment of traffic demand at least cost. The network cost includes backbone link capacity expansion cost and penalty cost for not satisfying the maximum throughput of the traffic due to link failures or insufficient link capacities. The problem is formulated as a zero-one non-linear mixed integer programming problem, for which an effective solution procedure is developed by using a Lagrangean relaxation technique for finding a lower bound and a heuristic method exploited for improving the upper bound of any intermediate solution. The solution procedure is tested for its effectiveness with various numerical examples.     

Toward a broadband congestion control strategy

The congestion control problem in asynchronous transfer mode (ATM) based broadband networks is defined. In general, a suitable set of congestion controls will include features for admission control, buffer and queue management, traffic enforcement, and reactive control. The leading alternatives for each of these congestion control features are summarized. An approach for choosing the best of these alternatives is presented, and a reasonable set of such alternatives that captures the increased utilization due to statistical multiplexing is suggested. It uses separate and static bandwidth pools for each service category; a statistical multiplexing gain determined for each bandwidth pool that supports a variable-bit-rate (VBR) service category; traffic enforcement on a virtual circuit basis using a leaky bucket algorithm with parameters set to accommodate anticipated levels of cell transfer delay variation; and multilevel loss priorities as well as a reactive control for appropriate VBR service categories based on multithreshold traffic enforcement and explicity congestion notification     

Comparison of virtual path bandwidth assignment and routing methods

The virtual path (VP) can simplifyAtm network management by minimizing connection routing and admission costs, and by facilitating the layered control of resources. However, fully exploiting these advantages may lead to a large number of relatively low capacity virtual paths travelling on each physical link. If each VP is treated as a separate unit, as is commonly assumed, low path capacities will lead to low network utilisation. This paper carefully examines the trade-off between simplification through traffic separation and improved efficiency due to traffic consolidation. We review existing vp bandwidth assignment and control techniques, and propose a new vp tagging control method. A comparison shows that by permitting resource sharing between paths it is possible to influence significantly the trade-off between simplified network management and multiplexing gain from traffic consolidation.     

Restoration strategies and spare capacity requirements inself-healing ATM networks

This paper studies the capacity and flow assignment problem arising in the design of self-healing asynchronous transfer mode (ATM) networks using the virtual path concept. The problem is formulated here as a linear programming problem which is solved using standard methods. The objective is to minimize the spare capacity cost for the given restoration requirement. The spare cost depends on the restoration strategies used in the network. We compare several restoration strategies quantitatively in terms of spare cost, notably: global versus failure-oriented reconfiguration, path versus link restoration, and state-dependent versus state-independent restoration. The advantages and disadvantages of various restoration strategies are also highlighted. Such comparisons provide useful guidance for real network design. Further, a new heuristic algorithm based on the minimum cost route concept is developed for the design of large self-healing ATM networks using path restoration. Numerical results illustrate that the heuristic algorithm is efficient and gives near-optimal solutions for the spare capacity allocation and flow assignment for tested examples     

Efficient support for client/server applications over heterogeneousATM networks

We present a new network design problem that is applicable for designing virtual paths (VPs) in an asynchronous transfer mode (ATM) network to efficiently support client/server applications. We present several alternatives for the solution, compare their properties, and focus on a novel “greedy” solution, which we prove to optimize certain important criteria (namely, the network overhead for a request/response and the utilization of bandwidth and routing table resources). We also present simulation results that demonstrate the performance and scalability of our solution. In addition, we propose a new efficient bandwidth allocation scheme which is tailored for client/server applications over ATM networks     

Resource management with virtual paths in ATM networks

A virtual path connection (VPC) is a labelled path which can be used to transport a bundle of virtual channel connections (VCCs) and to manage the resources used by these connections. The virtual network is organized as a collection of VPCs which form a VPC, or logical, overlay network. If the VPCs are permanent or semi-permanent and have reserved capacity, establishing new VCCs requires simple connection admission decisions at the VPC terminators of existing VPCs. This would enable faster connection establishment since transit nodes are not involved in the connection setup. The virtual path concept also allows the possibility of segregating traffic types according to quality of service requirements. However, the extent to which VPC provisioning is able to improve network efficiency is dependent on the resource management decisions that determine the VPC topology and capacity allocations. The article surveys resource management using virtual paths in an ATM network. Of interest are techniques which modify the VPC topology and capacity assignments in order to adapt to changing traffic conditions and possible network failures. The resource management activities employed to facilitate such adaptation can be categorized by the timescale on which they operate. On the shortest timescale are strategies for dynamically making minor changes to the VPC topology or capacity assignments. On a somewhat longer timescale are strategies for making more widespread modifications to the VPC overlay network. This would be appropriate for traffic changes based on time of day and for recovering from network failures. Finally, on an even longer timescale, strategies may be employed to design a general VPC overlay network, to be used at startup or after major network upgrades. Solutions to VPC resource management for each of these timescales are discussed     

Internetting LAN's and MAN's to B-ISDN's for connectionless trafficsupport

One of the challenges in the interconnection of LANs and MANs to asynchronous transfer mode (ATM) networks is the support of connectionless traffic in the ATM network. A commonly proposed strategy consists of maintaining a thin, low bandwidth virtual path (VP) between each pair of gateways and requesting more bandwidth whenever a burst comes in from the LAN or MAN. Unfortunately, this strategy places a heavy burden on the ATM control processors; furthermore, it is overly conservative in the use of bandwidth. An alternative solution is proposed: on the-fly tranmission of bursts without prior bandwidth reservation. The key conditions for this scheme to work are the use of the cell loss priority (CLP) bit in the ATM cell header and the knowledge of available bandwidth on the path through bandwidth advertising. An on-the-fly strategy for connectionless traffic is described and is compared with a bandwidth renegotiation strategy     

Omega network-based ATM switch with neural network-controlledbypass queueing and multiplexing

Multistage interconnection networks (MINs) have long been studied for use in switching networks. Since they have a unique path between source and destination and the intermediate nodes of the paths are shared, internal blocking can cause very poor throughput. This paper proposes a high throughput ATM switch consisting of an Omega network with a new form of input queues called bypass queues. We also improve the switch throughput by partitioning the Input buffers into disjoint buffer sets and multiplexing several sets of nonblocking cells within a time slot, assuming that the routing switch operates only a couple of times faster than the transmission rate. A neural network model is presented as a controller for cell scheduling and multiplexing in the switch. Our simulation results under uniform traffic show that the proposed approach achieves almost 100% of potential switch throughput