End-to-end survivable broadband networks

Within the EC-sponsored RACE program, the IMMUNE project was established to analyze and specify appropriate strategies for introducing end-to-end survivability into corporate and public broadband networks to support these strategies by proper techniques and evaluation tools, and to demonstrate distributed restoration on PSN (public switched networks) and CPN (customer premises networks) laboratory models. The first objective was to define a set of survivability requirements and metrics to be used in the rest of the project. This has led to the identification of a range of survivability strategy options ann how they can be mapped onto user, service provider and operator requirements. The next step on the road to integral survivability is designing and planning survivable networks, and the evaluation of the restoration and protection mechanisms that will be applied in these networks. An overview is given of this part of the project. Most protection and restoration mechanisms operate within a single network layer and network part, autonomous from network management. The interaction of mechanisms in different network layers or in different network parts, and the role of network management, are discussed. For the demonstration lab models, two techniques have been selected for implementation: a distributed restoration mechanism for a meshed ATM PSN, and a CPN ATM ring protection switching mechanism. These techniques are described and an overview is given of the ongoing activities within the IMMUNE project, with a summary of the status of the demo models     

Design of capacitated survivable networks with a single Facility

In this paper we focus on the single-facility capacitated survivable network design problem. We optimize simultaneously the network topology and the link dimensioning in order to route all traffic commodities according to survivability requirements. The latter are actually expressed in terms of the spare capacity required to address link failures in the context of different rerouting strategies. We present a mixed-integer linear programming model solved by combining several approaches. To tackle the high dimensionality and to separate the continuous and integer variables, we use Benders' decomposition and a cutting-plane approach. Going beyond the proposed method itself, we examine and compare two well-known restoration techniques: local and end-to-end reroutings. Numerous computational results for realistic network instances provide a comparison of these rerouting mechanisms in terms of installed capacities, network density as well as overall costs and CPU time.     

Dimensioning of survivable WDM networks

In this paper routing, planning of working capacity, rerouting, and planning of spare capacity in wavelength division multiplexing (WDM) networks are investigated. Integer linear programming (ILP) and simulated annealing (SA) are used as solution techniques. A complex cost model is presented. The spare capacity assignment is optimized with respect to three restoration strategies. The benefit of wavelength conversion, the choice of the fiber line system, and the influence of cost parameter values are discussed, with respect to the different restoration strategies and solution techniques. Wavelength conversion is found to be of limited importance, whereas tunability at the end points of the connections has substantial benefits     

The design of survivable directed networks

We study a survivable network design problem:the directed network design problem with connectivity constraints (DNCC). Some applications in telecommunications are presented. We discuss two integer linear programming models for DNCC, and relate these. The main body of the paper is a study of DNCC from a polyhedral point of view. We give several classes of nonredundant inequalities for polytopes associated with the problem. A cutting plane algorithm based on the polyhedral results is described and some computational results are given.     

Resource provisioning for survivable WDM networks under a sliding scheduled traffic model

Resource allocation in WDM networks, under both the static and dynamic traffic models have been widely investigated. However, in recent years there has been a growing number of applications with periodic bandwidth demands. Resources for such applications can be scheduled in advance, leading to a more efficient utilization of available network capacity. The setup and teardown times of the scheduled demands may be fixed, or may be allowed to slide within a larger window. A number of optimal integer linear program (ILP) solutions for the first problem (fixed setup/teardown times) have been presented in the literature. In this paper we present two new ILP formulations for the more general sliding scheduled traffic model, where the setup and teardown times may vary within a specified range. We first consider wavelength convertible networks and then extend our model to networks without wavelength conversion. Our ILP formulations jointly optimize the problem of scheduling the demands (in time) and allocating resources for the scheduled lightpaths. The fixed window model can be treated as a special case of our formulations. Our formulations are able to generate optimal solutions for practical sized networks. For larger networks, we have proposed a fast two-step optimization process. The first step schedules the demands optimally in time, so that the amount of overlap is minimized. The second step uses a connection holding time aware heuristic to perform routing and wavelength assignment for the scheduled demands.     

Design of survivable WDM networks using pre-configured protection structures with unrestricted shapes

We propose a novel protection approach for the design of link-protection schemes in survivable Wavelength Division Multiplexing mesh networks by merging the well-known p-cycle- and p-tree-protection structures. So doing, we aim at gathering the advantages of p-cycles in terms of protection capabilities, and of p-trees in terms of protection flexibilities (local re-routing, scalability) in a single protection scheme. As opposed to existing protection schemes based on protection structures with a pre-defined shape, the building blocks of the new scheme are protection structures with unrestricted shapes. Thus, they allow more flexibility in provisioning spare capacity, and provide higher capacity efficiency when compared to the shaped-protection schemes that have been proposed so far. In order to cope with the size of the solution space which includes all the possible protection structures, we propose an efficient and scalable optimization technique in large-scale systems named column generation (CG). In our CG-based optimization approach, the shape of a candidate protection structure is dynamically decided during the optimization process according to a link spare capacity budget. Experimental results on different network instances show that the protection plan resulting from the merging of p-cycle and p-tree structures is, on average, ~15% less capacity redundant and ~15% more reliable than the pure p-cycle one. It also requires, on average, ~30% less protection structures. In addition, those structures provide backup paths ~30% smaller than those of the p-cycle-based scheme.     

Differentiated QoS for survivable WDM optical networks

Optical networks based on WDM technology have become a promising solution to realize transport networks that can meet the ever-increasing demand for bandwidth. As WDM networks carry a huge volume of traffic, maintaining a high level of survivability is an important and critical issue. The. development of GMPLS switching technology led to the direct integration of IP and WDM. In these IP-over-WDM networks different applications/end users need different levels of fault tolerance and differ in how much they are willing to pay for the service they get. The current trend in network development is moving toward a unified solution providing support for voice, data, and various multimedia services. Therefore, it imperative that WDM networks incorporate fault tolerance to single or multiple component failures, protection bandwidth, recovery time, and recovery granularity besides resource utilization and call acceptance ratio. This article presents a survey of various methods that have been proposed for providing service differentiation in survivable WDM networks and discuss their performance. Such methods are broadly classified under various paradigms such as differentiated reliability, R-connections, quality of protection, and quality of recovery.     

Assigning spare capacities in mesh survivable networks

This paper analyses one key issue of designing reliable networks: assignment of spare capacities in transmission networks. The spare capacities are optimized to facilitate the restoration of single failures. This problem can be formulated as an integer linear program and approximated by its continuous relaxation. This model is based on arc-path formulation especially efficient for dealing with end-to-end rerouting and providing appreciable economies in comparison with local rerouting. The main idea of our method resides in a linear programming decomposition, which permits us to solve problems for medium and large networks. Our approach could be applicable to both STM and ATM-based networks. This method was tested successfully on medium and large DCS-meshed networks and some numerical examples are given to illustrate its performances in terms of CPU time and ratio of optimality. This revised version was published online in June 2006 with corrections to the Cover Date.     

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     

SONET ring applications for survivable fiber loop networks

Synchronous optical network (SONET) self-healing rings (SHR) are studied in the loop environment. SONET SHR architectures for loop feeder networks are discussed, focusing on three possible dual central office (CO) architectures for fiber loop networks, using SONET SHRs to reduce network costs and provide network service survivability. These architectures reflect an integrated planning concept for SONET networks that eliminates the boundary between the access network and the inter-office network. It is shown that the use of SONET SHRs makes it easy to evolve to a protected dual CO access architecture. Economic and survivability studies are discussed. The economic studies show that using the ring approach yields significant advantages over the traditional diverse protection approach in terms of cost and survivability, especially for the dual CO architectures     

Satellite communications networks

The evolution of satellite communication systems over the past two decades from simple point-to-point links with unique subcarrier-defined paths between points to today's multipoint, satellite-switched, multi-satellite networks tying together hundreds of earth stations, and transmitting voice and data increasingly in the time domain is considered. Examples of the methods used to manage network resources efficiently through terrestrial control and monitoring of information flow together with on-board switching are given. These examples are choosen mostly from the INTELSAT experience which will soon include a sixth generation of space segment. The paper concludes with a discussion of the future directions of satellite network development made possible by the technology being planned for NASA's Advanced Communications Technology Satellite. This design anticipates the needs of both high-volume trunking and thin-route service.     

New options and insights for survivable transport networks

This article is devoted to a selection of recent topics in survivable networking. New ideas in capacity design and ring-to-mesh evolution are given, as well as a systematic comparison of the capacity requirements of several mesh-based schemes showing how they perform over a range of network graph connectivity. The work provides new options and insights to address the following questions. How does one evolve from an existing ring-based network to a future mesh network? If the facilities graph is very sparse, how can mesh efficiency be much better than rings? How do the options for mesh protection or restoration rank in capacity requirements? How much is efficiency increased if we enrich our network connectivity? We also outline p-cycles, showing this new concept can realize ring-like speed with meshlike efficiency. The scope is limited to conveying basic ideas with an understanding that they could be further adapted for use in IP or DWDM layers with GMPLS-type protocols or a centralized control plane     

WDM抗毁网状网络中的业务量疏导算法

研究具有抗毁能力的WDM网状网中的业务量疏导设计问题，提出几种以网络吞吐量为优化目标的启发式算法，并通过计算机仿真分析，证实了基于最大化资源利用率的算法具有很好的性能。     

Computing blocking probabilities in survivable WDM optical networks

One of the most important performance measurements in wavelength-division multiplexing (WDM) networks is the call blocking probability. In this paper, we present an approximate analytical method to evaluate the blocking probabilities in survivable WDM networks with dynamically arriving connection requests. Our approach utilizes the wavelength independence whereby WDM network can be regarded as an aggregation of disjoint single wavelength sub-networks with a common physical topology. In each single wavelength sub-network, we derive the calculation of the blocking probability from an exact analysis. We assume dedicated protection with fixed routing and either first-fit or random wavelength assignment. Simulation results demonstrate the accuracy of the proposed method.     

Multiple link failure recovery in survivable optical networks

Survivability is of critical importance in high-speed optical communication networks. A typical approach to the design of survivable networks is through a protection scheme that pre-determines and reserves backup bandwidth considering single/double link failure scenarios. In this article, a greedy algorithm is presented to reserve backup bandwidth considering multiple (F > 2) link (SRLG) failure scenarios. A bandwidth-saving joint selection scheme of working and protection paths is presented for protection against random multiple-link failures under dynamic traffic. Simulation shows that the algorithm can achieve maximum sharing of backup bandwidth for protection against random multiple-link failure with significant amount of bandwidth saving.     

Availability of survivable Valiant load balancing (VLB) networks over optical networks

Valiant load balancing (VLB) network has been proposed as a capacity-efficient solution to handle highly dynamic traffic in future backbone networks. In this paper, we study the availability of VLB networks that are overlaid over an optical infrastructure. The main challenges in such a context arise from the unique routing and protection scheme that goes beyond the definition of conventional connection-level service availability as well as the logical link failure correlation that prohibits the use of traditional analytical methods. We propose a network-level availability model to compute the probability that a VLB network is congestion-free under all traffic patterns. Numerical results show that with a proper truncation level, our calculation on availability can be accelerated significantly by generating tight lower and upper bounds. Our main finding is that physical link sharing in a two-layer setting degrades the network availability drastically by several orders of magnitude due to the full mesh requirement for VLB networks, and may remove the capacity efficiency advantage of VLB networks.     

Value optimization of survivable multilayer IP/MPLS-over-WSON networks

Network operators are willing to provide a range of services in the hope of maximizing their profits: from the highly available connectivity services for key business customers to the unprotected or even best effort services for residential customers. These services are being provided through IP/multiprotocol label switching (MPLS) over wavelength-switched optical networks (WSON) networks. Such multilayer network enables the application of optimal load balancing between the packet and the optical layer, optimizing both the cost of the packet layer and the utilization of the WSON. To provide highly available services, redundant network resources need to be added to the network providing survivability against failures; generally speaking, the higher the survivability degree, the higher both the capital and the operational expenditures (CAPEX and OPEX, respectively) of the network. In this work, we design networks to meet specific availability objectives considering single failures in optical links, IP/MPLS nodes, and optoelectronic ports. The benefits of the designed networks are evaluated from an economic perspective defining costs and revenues models and using Net Present Value as a metric to evaluate future cash flows after an investment. To this end, CAPEX and OPEX, including power consumption and maintenance, and penalties as a consequence of service level agreement breaches are considered. Exhaustive numerical results on several reference network scenarios demonstrate how the value of the network can be maximized by tuning availability objectives.     

Optimal design and evaluation of survivable WDM transport networks

This paper proposes an optimal design scheme for survivable wavelength-division multiplexing (WDM) transport networks in which fast restoration can be achieved by using predetermined restoration paths that are independent of failure locations and which have one to one correspondence with working paths. Integer programming-based design problems are formulated to optimally determine working and their corresponding restoration paths, the number of fibers in each span, and the number of optical cross connects (OXCs) in each node. In these optimization problems, total facility cost, which includes not only transmission cost but also cross connection, is minimized. This design scheme can handle the dedicated/shared allocation of spare resources and several parameters, such as the maximum available number of wavelengths per fiber Ω, the matrix size of each OXC, and cross-connection to transmission cost-coefficient ratio γ. Total fiber length, the total number of OXCs, etc., are evaluated from obtained design results for these options and parameters. Numerical examples show that the dependency of total fiber length and the total number of OXCs on γ is relatively small, and cross-connection to transmission cost ratios (γ times the total number of OXCs divided by total fiber length) in the dedicated and shared cases are almost the same for each combination of γ and Ω     

Optimized design of survivable MPLS over optical transport networks

In this paper we study different options for the survivability implementation in MPLS over Optical Transport Networks (OTNs) in terms of network resource usage and configuration cost. We investigate two approaches to the survivability deployment: single-layer survivability, where some recovery mechanism (e.g. protection or restoration) is implemented in a single network layer and multilayer survivability, where recovery is implemented in multiple network layers. The survivable MPLS over OTN design is implemented as a static network optimization problem and incorporates various methods for spare capacity allocation (SCA) to reroute disrupted traffic.The comparative analysis between the single layer and the multilayer survivability shows the influence of the traffic granularity on the survivability cost: for high-bandwidth LSPs, close to the optical channel capacity, the multilayer survivability outperforms the single layer one, whereas for low-bandwidth LSPs the single-layer survivability is more cost-efficient. For the multilayer survivability we demonstrate that by mapping efficiently the spare capacity of the MPLS layer onto the resources of the optical layer one can achieve up to 22% savings in the total configuration cost and up to 37% in the optical layer cost. Further savings (up to 9%) in the wavelength use can be obtained with the integrated approach to network configuration over the sequential one; however, this is at the increase in the optimization problem complexity. These results are based on a cost model with current technology pricing and were obtained for networks targeted to a nationwide coverage.