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

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

Control and management protocols for survivable optical mesh networks

This paper considers the problem of online provisioning and restoration of sharable, restorable connections in a mesh-based optical network. First, we propose a new framework called distributed path selection with local information (DPLI) and discuss in detail a control and management protocol to set up and tear down connections and determine restoration capacity sharability in a distributed manner. Since only local information is maintained at each node, protocol scalability is not a big concern. Second, we discuss the important problem of the network's ability to quickly recover from element failures. We propose a new rapid restoration signaling that minimizes the service interruption time upon the occurrence of a failure in a network with preplanned restoration paths. The significant contribution of this new algorithm is that the connection restoration time is found to be independent of the restoration path length (i.e., eliminating the effect of the propagation delay), of the accumulation of the switch configuration time along the restoration path, and of the switch configuration waiting time at any particular node when multiple configuration requests arrive simultaneously. We evaluate through simulation experiments the effectiveness of the proposed protocols.     

带有负载均衡机制的网状WDM网络抗毁策略研究

研究了带有负载均衡机制的抗毁网状WDM网络,旨在保证网络具有抗毁能力的同时尽量减少全网光域所使用的资源,即在选择工作路径和保护路径时尽量保证全网的负载均衡。以波长数量最小化为优化目标,建立规划模型分别对多纤网状WDM网络中的共享路径保护和共享链路保护策略进行了研究,同时辅以负载均衡机制对网络资源利用率进一步优化。仿真结果表明,该结构在保证网络抗毁性的同时,能够有效地减少全网总体所需的波长数,降低网络成本。     

Incremental survivable network design with topology augmentation in SDH/SONET mesh networks

An incremental capacity allocation with topology augmentation problem is investigated in this article to maximize the service restorability in SDH/SONET mesh networks. To tackle the optimal design problem, two schemes are proposed, i.e., minimal backup path provisioning with topology augmentation (MBPP-TA), and global path pair provisioning with topology augmentation (GPPP-TA). Both schemes are formulated as integer linear programming (ILP) models, and are implemented using the proposed two-step linear programming (LP) approaches. Numerical results show that the two-step LP approaches achieve better solutions with significantly less execution time than the direct ILP approach. Moreover, results show that GPPP-TA provides better solutions than MBPP-TA at the cost of longer computation time.     

Incremental survivable network design against node failure in SDH/SONET mesh networks

Network survivability is becoming more and more important for the plenty of information each single fiber carries. Extra network resources are needed to increase network survivability level. In this paper, we investigate the problem of how to augment the network topology with adding new links and allocate spare capacity to maximize the service restorability against node failures in SDH/SONET mesh networks. A scheme called maximal node-disjoint backup paths provisioning with topology augmentation is proposed to tackle the problem, and another scheme called globally optimized path provisioning with topology augmentation, which allows adjusting the existing working paths of network flows, is investigated to optimize the augmented network globally. Both schemes are formulated as mixed integer linear programming models. Furthermore, heuristic algorithms are investigated to be implemented in software. Three algorithms, i.e., added links searching method, successive maximal survivable routing method, and random sequence routing convergence method, are designed and compared. Simulation results show the effectiveness of the algorithms.     

Inter group shared protection (I-GSP) for survivable WDM mesh networks

This paper focuses on the survivable routing problem in WDM mesh networks where the objective is to minimize the total number of wavelengths used for establishing working and protection paths in the WDM networks. The past studies for survivable routing suffers from the scalability problem when the number of nodes/links or connection requests grows in the network. In this paper, a novel path-based shared protection framework, namely inter group shared protection (I-GSP), is proposed where the traffic matrix can be divided into multiple protection groups (PGs) based on specific grouping policy. Optimization is performed on these PGs such that sharing of protection wavelengths is considered not only inside a PG, but between the PGs. Simulation results show that I-GSP based integer linear programming model, namely, ILP-II solves the networks in a reasonable amount of time for which a regular integer linear programming formulation, namely, ILP-I becomes computationally intractable. For most of the cases the gap between the optimal solution and the ILP-II stays within 6%. The proposed ILP-II model yields a scalable solution for the capacity planning in the survivable optical networks based on the proposed I-GSP protection architecture.     

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     

Approximating optimal spare capacity allocation by successive survivable routing

The design of survivable mesh based communication networks has received considerable attention in recent years. One task is to route backup paths and allocate spare capacity in the network to guarantee seamless communications services survivable to a set of failure scenarios. This is a complex multi-constraint optimization problem, called the spare capacity allocation (SCA) problem. This paper unravels the SCA problem structure using a matrix-based model, and develops a fast and efficient approximation algorithm, termed successive survivable routing (SSR). First, per-flow spare capacity sharing is captured by a spare provision matrix (SPM) method. The SPM matrix has a dimension the number of failure scenarios by the number of links. It is used by each demand to route the backup path and share spare capacity with other backup paths. Next, based on a special link metric calculated from SPM, SSR iteratively routes/updates backup paths in order to minimize the cost of total spare capacity. A backup path can be further updated as long as it is not carrying any traffic. Furthermore, the SPM method and SSR algorithm are generalized from protecting all single link failures to any arbitrary link failures such as those generated by Shared Risk Link Groups or all single node failures. Numerical results comparing several SCA algorithms show that SSR has the best trade-off between solution optimality and computation speed.     

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     

A novel survivable routing algorithm for shared segment protection in mesh WDM networks with partial wavelength conversion

In this paper, a survivable routing algorithm is proposed for shared segment protection (SSP), called optimal self-healing loop allocation (OSHLA), which dynamically allocates spare capacity for a given working lightpath in mesh wavelength-division-multiplexing (WDM) networks with partial wavelength conversion capability. Two novel graph transformation approaches, namely graph of cycles and wavelength graph of paths, are introduced to solve this problem, in which the task of survivable routing is formulated as a series of shortest path searching processes. In addition to an analysis on the computation complexity, a suite of experiments is conducted to verify OSHLA on four networks with different topologies and traffic loads. We find that the blocking probability and computation complexity are dominated by the upper bound on the length of the working and protection segments. Comparison is made between OSHLA and four other reported schemes in terms of blocking probability. The results show that OSHLA can achieve the lowest blocking probability under the network environment of interest. We conclude that OSHLA provides a generalized framework of survivable routing for an efficient implementation of SSP in mesh WDM partial wavelength convertible networks. With OSHLA, a compromise is initiated by manipulating the upper bound on the length of working and protection segments such that the best performance-computation complexity gain can be achieved.     

Stability and sensitivity for congestion control in wireless mesh networks with time varying link capacities

A critical challenge for wireless mesh networks is the design of efficient transport protocols that provide high bandwidth utilization and desired fairness in the multi-hop, wireless environment. While extensive efforts have been devoted to providing optimization based, distributed congestion control schemes for efficient bandwidth utilization and fair allocation in both wireline and wireless networks, a common assumption therein is fixed link capacities. This unfortunately will limit the application scope in wireless mesh networks where channels are ever changing. In this paper, we explicitly model link capacities to be time varying and investigate congestion control problems in multi-hop wireless networks. In particular we propose a primal–dual congestion control algorithm which is proved to be trajectory stable in the absence of feedback delay. Different from system stability around a single equilibrium point, trajectory stability guarantees the system is stable around a time varying reference trajectory. Moreover, we obtain sufficient conditions for the scheme to be locally stable in the presence of delay. Our key technique is to model time variations of capacities as perturbations to a constant link. Furthermore, to study the robustness of the algorithm against capacity variations, we investigate the sensitivity of the control scheme and through simulations to study the tradeoff between stability and sensitivity.     

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.     

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.     

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.     

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