This paper presents an architecture for restorable call allocation and fast virtual path (VP) restoration in mesh ATM networks. In this architecture, virtual working and spare capacities needed for call allocation and restoration are reserved and released dynamically on a call-by-call basis at the time of call admission and termination. This obviates the need for advance assignment of spare and working capacities. To shorten the call processing delay, this is done in a parallel-distributed fashion. To provide restorable call allocation, parallel-distributed call processing algorithms of sender-chooser type are suggested. The algorithms integrate, on the call level, virtual bandwidth allocation, virtual spare-capacity assignment, and fixed, alternate, or state-dependent routing. Each routing scheme leads to a particular tradeoff between call processing complexity, call setup delay, and bandwidth efficiency. For each pair of nodes, two sets of VPs are provisioned. The first, working VP (WVP) set, is used for call allocation during the normal operation. The second, spare VP (SVP) set, is used for WVP restoration in the event of failures of network elements. Each SVP protects a preassigned subset of the node pair's WVPs. Each SVP is selected to be link/node disjoint from the WVPs that it is assigned to protect. This assures a protection of the WVP set by a small number of SVPs. Since SVPs are preset and appropriate virtual spare capacities are reserved in advance, the architecture guarantees full restorability and provides very fast restoration. The restoration is done on the VP level in a self-healing manner. The suggested architecture requires only local information to be maintained at each node.

We present the architecture for burst level congestion control (BLCC) in ATM networks which is well suited for bursty self-similar traffic. The architecture is based upon pre-planned virtual path (PVP) set and preassigned maximal permitted route rates (MPR). The PVP set and MPR are engineered to meet QoS requirements of multi-service demand. The suggested burst level control maintains the maximal rate of cell admission on any PVP below its MPR. This is done at each PVP's source node by regulating bursts admission and by reserving the burst peak rate for each admitted burst. The reservation can be performed very fast since it is done at PVP's source node without any communication with other nodes. The MPR and PVP set are adjusted in a relatively slow, for instance hourly, timeframe adapting to the changes in the demand. The paper also presents an efficient technique for multiclass QoS engineering of burst admission that can be applied to engineer networks with large number of nodes and service classes.

This paper presents an architecture for restorable call allocation and fast virtual path (VP) restoration in mesh ATM networks. In this architecture, virtual working and spare capacities needed for call allocation and restoration are reserved and released dynamically on a call-by-call basis at the time of call admission and termination. The architecture does not require advance assignment of spare and working capacities. To shorten the call processing delay, this is done in a parallel-distributed fashion. To provide restorable call allocation, parallel-distributed call processing algorithms of the sender-chooser type are suggested. The algorithms integrate on the call level virtual bandwidth allocation, virtual spare capacity assignment with fixed, alternate, or state-dependent routing. Each routing scheme leads to a particular tradeoff between call processing complexity, call setup delay, and bandwidth efficiency. For each pair of nodes, two sets of VPs are provisioned. The first is a working VP (WVP) set, to be used for call allocation during the normal operation. The second is a spare VP (SVP) set, to be used for VP restoration in the event of failure of network elements (NE). Each SVP protects a preassigned subset of the node pair WVPs. Each SVP is selected to be link/node disjoint from the WVPs that it is assigned to protect. This assures protection of the WVP set by a small number of SVPs. Since SVPs are preset and appropriate virtual spare capacities are reserved in advance, the architecture guarantees full restorability and provides very fast restoration. The restoration is done on the VP level in a self-healing manner. The suggested architecture requires only local information to be maintained at each node.

In this paper, we consider the problem of multicommodity flows in a ring network. Using necessary and sufficient conditions to ensure feasible linear and integral flows in the network, and the special structure of the ring topology, we construct efficient algorithms to route all the demands.

This paper presents a new scheme for real-time bandwidth allocation and path restoration (BARS) in mesh networks via SONET wideband digital cross-connect systems (WDCSs) in response to demand and load dynamics and link and/or node failure(s). The scheme dynamically maximizes bandwidth allocation while ensuring full service restorability. Since the physical network capacity is limited, sometime not all the demand can be accommodated under the full restorability requirement. This demand in SONET BARS is rejected fairly at the network boundary even if capacity for allocation is available. Bandwidth allocation and fair demand admission are optimized jointly under the full restorability requirements. The implementation of SONET WDCS does not need excessive storage. An efficient parallel algorithm for solving the optimization problem is also presented. The algorithm produces superior spare capacity assignments compared to the results in the literature.

The authors study how to expand capacity of the local access network to meet projected demand over a given planning horizon at minimum cost. The alternatives for capacity expansion include both copper cable and digital multiplexer. They show how the problem can be modeled as an integer programming problem; however, the size of the problem for a typical network and the discontinuous cost structure of the expansion facilities preclude the use of a general purpose integer programming code to solve it. A decomposition approach that takes advantage of the structure of the problem and allows the problem to be solved in a reasonable amount of time is proposed. The solution methods described have been implemented and computational results are discussed. The algorithm forms a part of the network planning system NETCAP that has been in use since 1989.>

An investigation to determine the minimum cost capacity expansion plan for the outside plant network to meet projected demand over a given planning horizon is presented. It is shown how the problem can be modeled as an integer programming problems; however, the size of the problem for a typical network precludes the use of a general-purpose integer programming code. A decomposition approach that takes advantage of the structure of the problem and allows the problem to be solved in a reasonable amount of time is proposed. The solution methods have been implemented and computational results are presented.>

Consideration is given to the optimal circuit routing problem in an existing circuit-switched network. The objective is to find circuit routing which accommodates a given circuit demand while maximizing the residual capacity of the network. In addition, the cost of accommodating the circuit demand should not exceed a given amount. Practical considerations require that a solution be robust to the variations in circuit demand and cost. The objective function for the optimal circuit routing problem is not a smooth one. In order to overcome the difficulties of nonsmooth optimization, the objective function is approximated by smooth concave functions. The optimization algorithm for the circuit routing problem is obtained as a limiting case of the sequence of optimal routing strategies for the corresponding smooth convex optimization problems, and the proof of its convergence to the optimal solution is given. An approach to calculating the optimal multicommodity flow is presented. The optimization algorithm efficiently handles networks with a large number of commodities, satisfies the robustness requirements, and can be used to solve circuit routing problems for large networks.>

A network optimization model (NOM) that provides a tool for performance analysis and optimal design of a broad class of routing strategies is presented. It can evaluate and optimize both static and dynamic, local and global routing strategies. The tool is applicable to both packet-switched and circuit-switched networks. NOM software is based on original modeling methods and optimization algorithms. It is user-friendly and menu-driven, and has extensive 'what if' capabilities. NOM can be used for performance evaluation of existing routing strategy and for optimal routing design for a given performance criterion. As a performance evaluation tool, for a given network topology, link and node capacities, point-to-point demand matrix, and routing strategy, NOM models the routing and computes important characteristics of network performance. As a routing optimization tool, for a given network topology, link and node capacities, point-to-point demand matrix, and performance criterion, NOM generates the optimal routing, and computes important characteristics of network performance. The current Telenet local dynamic routing strategy is compared with a set of optimal routing strategies designed for various performance criteria.>