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     

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     

Design of a meta-mesh of chain subnetworks: enhancing theattractiveness of mesh-restorable WDM networking on low connectivitygraphs

We have developed a design refinement to increase the capacity efficiency of span-restorable mesh networks on sparse facility graphs. The new approach views the network as a "meta-mesh of chain subnetworks". This makes the prospect of WDM mesh networking more economically viable than with previous mesh-based designs where the average nodal degree is low. The meta-mesh graph is a homeomorphism of the complete network in which edges are either direct spans or chains of degree-2 nodes. The main advantage is that loop-back-type spare capacity is provided only for the working demands that originate or terminate in a chain and not for the entire flow that crosses a chain. The transiting ("express") flows are entirely mesh-protected within the meta-mesh graph which is of higher average degree and hence efficiency for mesh restoration than the network as a whole. Nodal equipment savings also arise from the grooming of express lightpaths onto the logical chain-bypass span. Only the meta-mesh nodes need optical cross-connect functionality. Other sites use OADMs and/or glassthroughs. The resultant designs comprise a special class of restorable network that is intermediate between pure span restoration and path restoration. Most of the efficiency of path restoration is achieved, but with a span restoration mechanism which is more localized and potentially faster and simpler than path restoration. The concept lends itself to implementation with OADMs having a passive waveband pass-through feature to support the logical chain bypass spans for express lightpaths     

Theoretical underpinnings for the efficiency of restorable networksusing preconfigured cycles (“p-cycles”)

Previous work on restorable networks has shown experimentally that one can support 100% restoration with an optimized set of closed cycles of spare capacity while requiring little or no increase in spare capacity relative to a span-restorable mesh network. This is important and unexpected because it implies that future restoration schemes could be as capacity efficient as a mesh network, while being as fast as ring-based networks because there is no real-time work at any nodes other than the two failure nodes. This paper complements the prior work by giving a greater theoretical basis and insight to support the prior results. We are able to show in a bounding-type of argument that the proposed protection cycles (“p-cycles”) have as high a restoration efficiency as it is possible to expect for any type of preconfigured pattern, and are categorically superior to preconfigured linear segments or trees. We are also able to show that the capacity efficiency of a fully preconfigured p-cycle network has the same well-known lower bound as that of a span restorable mesh network which is cross-connected on-demand. These results provide a theoretical underpinning for the efficiency of p-cycles and confirmation of the experimental observations     

Optimal capacity and flow assignment for self-healing ATM networksbased on line and end-to-end restoration

This paper addresses an optimal link capacity design problem for self-healing asynchronous transfer mode (ATM) networks based on two different restoration schemes: line restoration and end-to-end restoration. Given a projected traffic demand, capacity and flow assignment is jointly optimized to find an optimal capacity placement. The problem can be formulated as a large-scale linear programming. The basis matrix can be readily factorized into an LU form by taking advantage of its special structure, which results in a substantial reduction on the computation time of the revised simplex method. A row generation and deletion mechanism is developed to cope with the explosive number of constraints for the end-to-end restoration-based networks. In self-healing networks, end-to-end restoration schemes have been considered more advantageous than line restoration schemes because of a possible reduction of the redundant capacity to construct a fully restorable network. A comparative analysis is presented to clarify the benefit of end-to-end restoration schemes quantitatively in terms of the minimum resource installation cost. Several networks with diverse topological characteristics as well as multiple projected traffic demand patterns are employed in the experiments to see the effect of various network parameters. The results indicate that the network topology has a significant impact on the required resource installation cost for each restoration scheme. Contrary to a wide belief in the economic advantage of the end-to-end restoration scheme, this study reveals that the attainable gain could be marginal for a well-connected and/or unbalanced network     

一种新的集成自愈技术及其算法

本文首先提出了容量平衡优化（ＣＥＰ）、共享自愈环（ＳＳＲ）和分布式动态自愈网（ＤＳＨ）三者集成的自愈技术,提出了基于最短路由业务量阵（ＳＲＭＴ）的ＳＳＲ空闲容量分配算法,而对于ＤＳＨ,从端到端重选路由和网络资源利用率的观点看,基于通道恢复技术比基于链路恢复技术更有效,本文提出了基于通道恢复的集成自愈设计技术及其算法。数值结果表明：本文提出的集成自愈技术及其算法可有效地节约容量需求。     

Regenerator Placement and Traffic Engineering with Restoration in GMPLS Networks

In this paper, we study regenerator placement and traffic engineering of restorable paths in generalized multiprotocol label switching (GMPLS) networks. Regenerators are necessary in optical networks in order to cope with transmission impairments. We study a network architecture where regenerators are placed only at selected nodes for decreasing cost of regeneration. We propose two heuristic algorithms for optimum placement of these regenerators. Performances of these algorithms in terms of required number of regenerators and computational complexity are evaluated. In this network architecture with sparse regeneration, off-line computation of working and restoration paths is studied for traffic engineering with path rerouting as the restoration scheme. We study two approaches for selecting working and restoration paths from a set of candidate paths and formulate each method as an integer linear programming (ILP) problem. A traffic uncertainty model is developed in order to compare these methods based on their robustness with respect to changing traffic patterns. Traffic engineering methods are compared based on number of additional demands resulting from traffic uncertainties that can be carried over the network. Proposed heuristic regenerator placement algorithms are also evaluated from a traffic engineering point of view.     

Architecture for restorable call allocation and fast VP restorationin mesh ATM networks

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     

Fast restoration of ATM networks

Asynchronous transfer mode (ATM) is now well recognized as the fundamental switching and multiplexing technique for future broadband ISDN. As these networks will be increasingly relied upon for providing a multitude of integrated voice, data, and video services, network reliability is a key concern. There are several intrinsic features of ATM networks that could potentially be exploited to provide improved restoration techniques, beyond those established for synchronous transfer mode (STM) networks, such as digital cross-connect restoration or self-healing rings. These features include ATM cell level error detection, inherent rate adaptation and nonhierarchical multiplexing. The authors explore the use of these features in developing fast restoration strategies for ATM networks. In particular, they address: (1) ATM error detection capabilities for enhanced failure detection, (2) network rerouting strategies, (3) spare capacity allocation, and (4) network control architecture and related implementation aspects. Their findings suggest that fast network span failure detection and bandwidth-efficient rerouting capabilities can be combined to develop restoration strategies for ATM networks with significantly greater performance-cost ratios when compared to existing STM network restoration strategies     

Design of Translucent Optical Networks: Partitioning and Restoration

We discuss the problem of designing translucent optical networks composed of restorable, transparent subnetworks interconnected via transponders. We develop an integer linear programming (ILP) formulation for partitioning an optical network topology into subnetworks, where the subnetworks are determined subject to the constraints that each subnetwork satisfies size limitations, and it is two-connected. A greedy heuristic partitioning algorithm is proposed for planar network topologies. We use section restoration for translucent networks where failed connections are rerouted within the subnetwork which contains the failed link. The network design problem of determining working and restoration capacities with section restoration is formulated as an ILP problem. Numerical results show that fiber costs with section restoration are close to those with path restoration for mesh topologies used in this study. It is also shown that the number of transponders with the translucent network architecture is substantially reduced compared to opaque networks.     

Extending the p-cycle concept to path segment protection for span and node failure recovery

The paper introduces an extension to the method of p-cycles for network protection. The p-cycle concept is generalized to protect path segments of contiguous working flow, not only spans that lie on the cycle or directly straddle the p-cycle. The original span protecting use of the p-cycle technique is extend to include path protection or protection of any flow segment along a path. It also gives an inherent means of protecting working flows that transit a failed node. We use integer linear programming to study the new concept and determine its inherent capacity requirements relative to prior p-cycle designs and other types of efficient mesh-survivable networks. Results show that path-segment-protecting p-cycles ("flow p-cycles") have capacity efficiency near that of the shared backup path-protection (SBPP) scheme currently favored for optical networking. Because its protection paths are fully preconnected and because it protects path segments (not entire paths), it has the potential for both higher speed and higher availability than SBPP. We also develop capacity optimization models to support 100% restoration of transiting flows through failed nodes. Only a very small additional spare capacity is needed to achieve both 100% span and intermediate node-failure restorabilities, and a very high transiting traffic restorability can be accomplished for node failure restorability given spare capacity only for span-failure protection. An immediate practical application is to suggest the use of flow p-cycles to protect transparent optical express flows through a regional network.     

Two dynamic reconfiguration approaches for optimizing the restoration path length in p-cycle protection network

p-cycle is one of the most promising technique of span protection in optical transport networks with mesh-like efficiency and ring-like speed. Longer p-cycle provides better efficiency in term of spare capacity, but longer restored path increases end-to-end propagation delay, which reduces the reliability of the restored network. Hence, minimization of restoration path is a critical issue in p-cycle based protection network. In this paper, two new dynamic reconfiguration approaches namely inter-cycles switching (ICS) and local restoration paths (LRP) are discussed to reduce the length of restored paths in existing optimal spare capacity design of p-cycle. Both proposed approaches are meant to utilize the idle p-cycles thus significantly reducing the path length. This reduction in restored path length also releases the redundant spare capacity.     

Improved Quasi-Path Restoration in Mesh Networks

Restoration of disrupted traffic is critical in today's high-speed self-healing telecommunication networks. A restoration scheme dynamically discovers alternate paths bypassing the failed component. This paper presents an (online) improved quasi-path restoration (IQPR) scheme. IQPR is derived from the two-commodity max-flow algorithm. The running time complexity of IQPR is O(|V|³). Therefore, IQPR is computationally more efficient and more scalable than path restoration (PR). IQPR is faster (in restoration speed) and less complex than PR, and more economical (in spare capacity requirement) than link restoration (LR). Thus, it provides a good alternative to PR when quick restoration of disrupted traffic is desired. The (offline) spare capacity planning problem deals with the allocation of spare capacity to each link in the network, such that the spare capacity requirement is minimized, while guaranteeing the desired level of restoration in the event of a link failure. The spare capacity allocation problems for LR, original quasi-path restoration (OQPR), IQPR, link-disjoint path restoration (LDPR) and PR are formulated as integer linear programming problems. Numerical results illustrate that the restoration schemes studied can be sorted from the least efficient to the most efficient (in the spare capacity requirement) in the following order: LR, OQPR, IQPR, LDPR and PR. The experimental analysis shows that network topology and demand patterns have a significant impact on the spare capacity savings offered by one scheme over the other. Merits and demerits of these schemes are also discussed.     

A highly efficient path-restoration protocol for management ofoptical network transport integrity

Distributed path restoration based on optical cross-connects can provide highly capacity-efficient real-time restoration for WDM-based optical networking. However, to obtain an assured restoration level with the theoretically very low amounts of spare capacity that path restoration allows, one must solve, or closely approximate a solution to, the integer multicommodity maximum flow (MCMF) problem, MCMF is, however a hard combinatorial optimization problem due to what is called the “mutual capacity” aspects of the problem: which of many competing origin-destination pairs should be allowed paths over the finite spares on each span? Integer MCMF is further complicated by the nonunimodular nature of the problem, i.e., fractional flows are forbidden but would arise if solved by linear programming. This paper presents a heuristic principle that tests well against integer programming solutions of MCMF routing. The heuristic is first characterized in a centralized program, then adapted for use in a distributed path restoration protocol. In all test cases, the protocol obtains over 97% of the paths found in an optimal MCMF solution in the same network. Via OPNET simulation it is also predicted that the protocol will run in well under 2 seconds which means it could be used directly in real-time, or in distributed prefailure self-planning, for restoration. The significance is that network operators could aggressively optimize their spare capacity, toward theoretical minimums, while still assuring 100% restorability     

Connection Availability Analysis of Shared Backup Path-Protected Mesh Networks

Dual-span failures dominate the system unavailability in a mesh-restorable network with full restorability to single-span failures. Traditional availability analysis based on reliability block diagrams is not suitable for survivable networks with shared spare capacity. Therefore, a new concept is proposed to facilitate the calculations of connection availability. A U.S. network consisting of 19 nodes and 28 spans yielding 171 bidirectional connections is investigated. We find that networks with shared backup path protection can have average connection unavailabilities of the same order of magnitude as those with dedicated automatic protection switching, however, with a much better capacity efficiency. The proposed method can exactly calculate the unavailability of a specific connection with known restoration details or the average connection performance without any restoration details by presuming the dual-span failures to be the only failure mode and an arbitrary allocation rule of spare capacity     

Optimized design and availability analysis of large-scale shared backup path protected networks

Traditional integer linear programming model for shared backup path networks allows only one working route and one backup route per demand and does not scale well. By introducing multiple working routes and backup routes, the traditional multi-flow model solves in a faster manner. This paper seeks improvements on the traditional multi-flow model and develops an algorithm to assess availability for multi-flow shared backup path protection models. Experiments on 165 networks testify that the newly proposed model is 51% faster on average with similar total cost and overall network availability, compared with the traditional multi-flow model. All the networks in this paper are designed to be 100% single-failure restorable, and major findings regarding these networks include: (1) total cost of assigning backup capacity to each span dwindles away with increasing network average nodal degree; (2) network availability first rises then falls as network average nodal degree increases; and (3) when network scale increases, network availability decreases with fluctuations. The results found are explained with two case studies in this paper.     

Dependence of network capacity requirements on the allowable flowconvergence overloads in ATM backup VP restoration

Work on capacity design for VP restoration in ATM has to date either been heuristic in nature or has treated the capacity design problem in a 1 for 1 VP replacement manner that is essentially the same as for STM path restorable networks. However, the inherently statistical nature of the traffic in ATM should allow formulation of a backup VP restoration capacity design that permits a controlled maximum of convergent flow overloads on spans during restoration. Results show that significant capacity savings can be obtained relative to STM if ATM restoration is allowed even modest restoration overload factors. We give an integer program formulation permitting controlled exploitation of this intrinsic difference between ATM and STM transport and present results showing the significant capacity benefits motivating this approach     

Availability analysis of span-restorable mesh networks

The most common aim in designing a survivable network is to achieve restorability against all single span failures, with a minimal investment in spare capacity. This leaves dual-failure situations as the main factor to consider in quantifying how the availability of services benefit from the investment in restorability. We approach the question in part with a theoretical framework and in part with a series of computational routing trials. The computational part of the analysis includes all details of graph topology, capacity distribution, and the details of the restoration process, effects that were generally subject to significant approximations in prior work. The main finding is that a span-restorable mesh network can be extremely robust under dual-failure events against which they are not specifically designed. In a modular-capacity environment, an adaptive restoration process was found to restore as much as 95% of failed capacity on average over all dual-failure scenarios, even though the network was designed with minimal spare capacity to assure only single-failure restorability. The results also imply that for a priority service class, mesh networks could provide even higher availability than dedicated 1+1 APS. This is because there are almost no dual-failure scenarios for which some partial restoration level is not possible, whereas with 1+1 APS (or rings) there are an assured number of dual-failure scenarios for which the path restorability is zero. Results suggest conservatively that 20% or more of the paths in a mesh network could enjoy this ultra-high availability service by assigning fractional recovery capacity preferentially to those paths upon a dual failure scenario     

Shared-Risk Logical Span Groups in Span-Restorable Optical Networks: Analysis and Capacity Planning Model

In an optical transport network distinct logical groups of lightwave channels between neighboring OXC nodes (called spans) may sometimes be realized over a common physical resource such as a duct or conduit, and hence share a common cause of failure. This is closely related to the concept of shared risk on individual channels or links, called SRLGs, which is relevant to pre-planned path protection schemes with shared capacity on backup paths. But when considering span-restorable networks, shared risk over logical spans (not individual channels) is the corresponding issue of concern. This work considers several aspect of how such shared-risk span groups (SRSG) affect the protection capacity design and other aspects of span-restorable mesh networks. We provide a model for capacity planning any span-restorable network in the presence of a known set of such shared-risk spans and study the relationship between capacity requirements and the number and placement of such situations. This provides guidelines as to how many SRSGs can be sustained before the capacity penalty becomes severe and methods to diagnose which of them are the most limiting to overall protection efficiency. One finding of interest is that if a given percentage of all possible dual-failure combinations incident to a common node are allowed for in the design, then nearly the same percentage of other dual-span failure combinations (any two spans in the network) will also be restorable. We also show that designing a network to withstand even a small number of multi-span co-incident spared-risk span groups will yield a significant improvement in overall dual-failure restorability and hence also in network availability.Presented at Optical Networking and Communications Conference (Opti Comm 2002), Boston, MA, USA, July-August 2002.     

Capacity planning providing 100 % survivability against double-link failures for WDM Networks

Survivability is always a key concern in WDM optical transport networks as failures may result in large amount of traffic disruption and significant degradation of network performance. In this paper, we investigate the capacity planning problem against double-link failures considering wavelength—continuity constraint. Our objective is to minimize the resource consumption when guaranteeing connection request 100 % survivability. We propose two efficient approaches: (1) the New Static Preplanned Path Protection (NSPPP); (2) the New Dynamic Rerouting (NDR). In NSPPP, we present a new backup resource sharing rule to compress the spare capacity. In NDR, only the working path of connection request is necessary to be given, and the rerouting path can be dynamically found on the network after double-link failures. Compared to previous algorithms, our proposed two capacity planning approaches can efficiently solve double-link failures problem of WDM networks, also obtain higher resource utilization ratio and lower network resource.