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.     

Locally reconfigurable p-cycle networks for dual-failure restoration

p-Cycle reconfiguration methods (for instance complete, incremental, or dynamic-repair) based on the first event adaptive restoration model provide a promising approach for improving the dual-failure restorability characteristics of static p-cycle methods based on the static preplanned restoration model. However, if the reconfiguration process triggered by the first failure is not completed before a second failure occurs, p-cycle reconfiguration methods fail to achieve 100% dual-failure restorability and reduce to the static p-cycle methods which do not take advantage of the spare capacity to be reconfigured. In this study, we propose to use a new restoration model designated as first event locally adaptive restoration model with a coordinated re-restoration effort. This model is aimed to limit the reconfiguration scope to a local p-cycle where the spare capacity is only reconfigured on its straddling links for reducing the reconfiguration overhead (i.e., the average number of reconfigured links during the reconfiguration time.) According to this model, a two-phase locally reconfigurable p-cycle method is proposed. Only the straddling links of the local p-cycle affected by the first failure are reconfigured in the first phase. The second phase is not initialized until the second failure really occurs in the affected local p-cycle. The second phase is to enable the dual-failure restorations with a coordinated re-restoration effort for the first failed link from its original end nodes for any damage that the second failure causes to previously deployed restoration paths. The objective of the proposed method is to maximize the dual-failure restorability within a limited reconfiguration scope. We evaluate the correlation between the normalized spare capacity cost and the dual-failure restorability. The results show that the proposed local reconfiguration heuristic method improves the average dual-failure restorability of the 9n17s and Cost 230 networks by 45.1% and 20.1%, respectively, relative to the static p-cycles method and achieves closely the optimal value obtained using integer linear programming (ILP). Additionally, the spare capacity cost of the proposed local reconfiguration method is smaller than that of previous p-cycle reconfiguration methods in the two test networks.

p2-Cycles: p-Cycles with parasitic protection links

The p-cycle and its Failure Independent Path Protection (FIPP) extension are known to be efficient and agile protection strategies. The p-cycle is pre-configured such that if there is a failure, only the switches at two end nodes need to be reconfigured. In this paper, we extend the p-cycle by allowing cycles to have attached links, called Parasitic Protection Links (PPL), in order to protect paths whose source and destination nodes are not only located on the cycle but also connected by a PPL to the cycle. A p-cycle with PPL is named p²-cycle.We address the unicast service protection problem against single-link failures by using p²-cycle in mesh networks for both static and dynamic traffic scenarios. In the static case, the problem is formulated as an Integer Linear Program (ILP). We further propose two p²-cycle based heuristic algorithms, Strict Routing Protection (SRP) and Flexible Routing Protection (FRP), to address the dynamic traffic case. The numerical results show that the p²-cycle scheme provides better capacity efficiency than the FIPP p-cycle scheme in all the traffic scenarios considered and achieves only less than 1% extra total cost over the optimum in COST239, provided by Shared Backup Path Protection (SBPP) approach when the traffic load is high. We also study the failure recovery performance in terms of average number of switch reconfigurations (NOR), and show that the performance of the p²-cycle becomes much better than that of SBPP and gets close to FIPP as the traffic demand increases. In the dynamic case, both SRP and FRP outperform FIPP p-cycle schemes in terms of blocking probability in most scenarios considered. In general, the p²-cycle protection scheme outperforms the p-cycle based in terms of capacity efficiencies which being slightly slower in terms of traffic recovery speed.     

Efficient optimization of network protection design with <Emphasis Type="Italic">p</Emphasis>-cycles

The purpose of this paper is to consider network survivability designs that utilize the p-cycle, and to propose a novel ILP formulation for capacity design based on network fundamental cycles, as well as the available straddling links. Concepts of visible and hidden straddling links—which are essential components of the model presented herein—are also introduced. The proposed model caters for the case of joint optimization of a p-cycle network that can be solved without enumerating p-cycle candidates. In addition, the complexity of the proposed model is much less than any conventional model dealing with large size networks and suitable for the design of networks having multiple quality of protection (MQoP) service classes using mixed protection techniques.     

Performance evaluation of p-cycle based protection methods for provisioning of dynamic multicast sessions in mesh WDM networks

Network survivability is crucial to both unicast and multicast traffic. Up to now, extensive research has been done on unicast traffic protection. Recently, due to the rapid growth of multicast applications, such as video-conferencing, high definition television (HDTV), distance learning, and multi-player on-line gaming, the problem of multicast traffic protection has started to draw more research interests. The preconfigured protection cycle (p-cycle) method proposed by Grover offers fast speed in restoration (because p-cycles are pre-cross-connected) and high efficiency in resource utilization (because p-cycles protect both on-cycle and straddling links). So far p-cycles based protection approaches have been intensively studied for unicast traffic protection, but have been rarely investigated for multicast traffic. We propose to apply p-cycles to dynamic protection provisioning of multicast traffic, and evaluate the blocking performance in comparison to other existing multicast protection schemes. We consider three different p-cycle based multicasting protection methods, namely dynamic p-cycle (DpC) design, p-cycle based protected working capacity envelope (PWCE) design, and hybrid DpC and PWCE design. We show that p-cycle-based multicast protection approaches offer much better blocking performance, as compared with other existing multicast protection schemes. The main reasons for the much better blocking performance are attributed to the facts that (i) the selection of p-cycles is independent of the routing of the multicast light trees, (ii) there are no path/segment disjoint constraints between the selected p-cycles and the multicast light trees to be protected, (iii) the selected p-cycles are the most efficient p-cycles.

An overview of p-cycle based optical multicast protection approaches in mesh WDM networks

This paper provides an overview of p-cycle based optical multicast protection approaches for link failure recovery, combined node and link failure recovery, and source failure recovery on top of combined node and link failure recovery. We discuss several recently proposed p-cycle based optical multicast protection approaches, including the link-protecting p-cycle based optical multicast protection approach, the tree-protecting p-cycle based optical multicast protection approach, node-and-link protecting p-cycle based optical multicast protection approach, and flow p-cycle based optical multicast protection approach. They outperform other existing optical multicast protection approaches in both capacity efficiency and recovery speed.     

A heuristic approach to working and spare capacity optimization for survivable anycast streaming protected by p-cycles

Most of previous research in the field of network survivability has been focused on unicast transmissions. However, growing popularity of various concepts following the idea of content-oriented networks has triggered the need to develop new approaches to protect networks with other than unicast flows including multicast and anycast flows. In this paper, we consider the latter case and address the problem of working and spare capacity allocation in networks with anycast streaming, i.e., it is assumed that a set of replica servers is deployed in the network to serve streaming requests. To protect the network we propose to apply p-cycles—a relatively novel survivability approach combining capacity effectiveness of mesh restoration and ring-like restoration speed. To benefit from special properties of anycast flows, we use augmented version of p-cycles called Anycast-Protecting p-Cycles (APpC). We formulate the optimization problem as an ILP (Integer Linear Programming) model further applied to obtain optimal results using the GuRoBi solver. Due to high complexity of this optimization problem, we propose an effective heuristic algorithm based on the Simulated Annealing approach. Several versions of the algorithm are developed and examined—the best method yields on average results only 4.14 % worse than optimal ones. A wide range of experiments is conducted to verify performance of the proposed approach as a function of various network parameters including: p-cycle generator, p-cycle length, number of replica servers, number of clients. Moreover, we evaluate the Anycast-Protecting p-Cycles approach against classical p-cycle.     

p-Cycle Design in Survivable WDM Networks with Shared Risk Link Groups (SRLGs)

p-Cycle survivable network design under the single link failure assumption has been studied extensively. Shared risk link group (SRLG) is a concept that better reflects the nature of network failures. An SRLG is a set of links that may fail simultaneously because of a common risk they share. The capability of dealing with SRLG failures is essential to network survivability. In this paper, we extend the p-cycle survivable network design from the single link failure model to the single SRLG failure model. An integer linear programming (ILP) formulation that minimizes spare capacity requirement is provided. To avoid enumerating all cycles of a network, we also provide a polynomial-time algorithm to generate a basic candidate p-cycle set that guarantees 100% restorability in case of any single SRLG failure given enough spare capacities. Moreover, we present the SRLG failure detection problem that prevents fast restoration upon an SRLG failure. To solve this problem, we introduce the concept of SRLG-independent restorability, which enables the restoration of each link in a failed SRLG to start immediately without knowing which SRLG has failed. We present an approach to optimal p-cycle design with SRLG-independent restorability and show that it is NP-hard to generate a candidate p-cycle set such that each link can be SRLG-independently restored by at least one cycle in the set.     

Hybrid FRR/p-cycle design for link and node protection in MPLS networks

Survivable MPLS technologies are crucial in ensuring reliable communication services. The fast reroute (FRR) mechanism has been standardized to achieve fast local repair of label switched paths (LSPs) in the event of link or node failures. We present a suite of hybrid protection schemes for MPLS networks that combine the well-known p-cycle method with FRR technology. Whereas with pure FRR backup paths are planned by each node individually, the hybrid schemes employ a set of p-cycles that may be selected using techniques that take a holistic view of the network so as to share protection bandwidth effectively. The hybrid FRR/p-cycle methods are fully RFC 4090-compliant, yet allow network operators to leverage a large existing body of p-cycle design techniques. Numerical results on realistic network topologies indicate that the hybrid approach is successful in combining the advantages of p-cycle design and FRR.     

Intercycle switching (ICS)-based dynamic reconfiguration of p-cycle for dual-failure survivability of WDM networks

Today, the most promising technique used for the survivability of optical transport networks is p-cycle. However, it provides longer restoration path at failure state of the network. The intercycle switching (ICS) is one of the recent approaches that is based on idle p-cycles and is used for shortening the length of restoration path in single-fault model. Utilization of idle p-cycles degrades the inherent dual-failure restorability of single-failure design model of p-cycle, whereas ICS releases the maximum portion of conventional restoration path by utilizing a small segment of the idle p-cycle. Here, the authors proposed a new approach to reconfiguring the released portion of restoration path and unused segment of corresponding idle p-cycle as new cycle(s). In respect of idle p-cycles, the new reconfigured cycle(s) provides more dual-failure restorability in single-failure design of p-cycle. Therefore, the proposed approach mitigates the above-said drawback of ICS and minimizes additional spare capacity requirement for dual-failure survivability.     

Comparison of <Emphasis Type="Italic">p</Emphasis>-cycles and <Emphasis Type="Italic">p</Emphasis>-trees in a unified mathematical framework

As high-speed networks grow in capacity, network protection becomes increasingly important. Recently, following interest in p-cycle protection, the related concept of p-trees has also been studied. In one line of work, a so-called “hierarchical tree” approach is studied and compared to p-cycles on some points. Some of the qualitative conclusions drawn, however, apply only to p-cycle designs consisting of a single Hamiltonian p-cycle. There are other confounding factors in the comparison between the two, such as the fact that, while the tree-based approach is not 100% restorable, p-cycles are. The tree and p-cycle networks are also designed by highly dissimilar methods. In addition, the claims regarding hierarchical trees seem to contradict earlier work, which found pre-planned trees to be significantly less capacity-efficient than p-cycles. These contradictory findings need to be resolved; a correct understanding of how these two architectures rank in terms of capacity efficiency is a basic issue of network science in this field. We therefore revisit the question in a definitive and novel way in which a unified optimal design framework compares minimum capacity, 100% restorable p-tree and p-cycle network designs. Results confirm the significantly higher capacity efficiency of p-cycles. Supporting discussion provides intuitive appreciation of why this is so, and the unified design framework contributes a further theoretical appreciation of how pre-planned trees and pre-connected cycles are related. In a novel further experiment we use the common optimal design model to study p-cycle/p-tree hybrid designs. This experiment answers the question “To what extent can a selection of trees compliment a cycle-based design, or vice-versa?” The results demonstrate the intrinsic merit of cycles over trees for pre-planned protection.     

On surviving dual-link failures in path protected optical WDM mesh networks

In this paper, we investigate the problem of enhancing dual-failure restorability in path protected mesh-restorable optical Wavelength Division Multiplexed (WDM) networks. Recent studies have demonstrated the need to survive simultaneous dual-link failures and have also provided solutions for handling such failures. A key finding of these early efforts is that designs providing complete (i.e. 100%) protection from all dual-failures need almost triple the spare capacity compared to a system that protects against all single-link failures. However, it has also been shown that systems designed for 100% single-link failure protection can provide reasonable protection from dual-link failures [M. Clouqueur, W. Grover, Mesh-restorable networks with 74 enhanced dual-failure restorability properties, in: Proc. SPIE OPTICOMM, Boston, MA, 2002, pp. 1-12]. Thus, the motivation for this work is to develop a hybrid mechanism that provides maximum (close to 100%) dual-failure restorability with minimum additional spare capacity.The system architecture considered is circuit-switched with dynamic arrival of sessions requests. We propose an adaptive mechanism, which we term active protection, that builds upon a proactive path protection model (that provides complete single-failure restorability), and adds dynamic segment-based restoration to combat dual-link failures. The objective is to optimize network survivability to dual-link failures while minimizing additional spare capacity needs. We also propose a heuristic constraint-based routing algorithm, which we term best-fit, that aids backup multiplexing among additional spare paths towards this goal. Our findings indicate that the proposed active protection scheme achieves close to complete (100%) dual-failure restorability with only a maximum of 3% wavelength-links needing two backups, even at high loads. Moreover, at moderate to high loads, our scheme attains close to 16% improvement over the base model that provides complete single-failure restorability. Also, the best-fit routing algorithm is found to significantly assist backup multiplexing, with around 15%-20% improvement over first-fit at all loads. The segment-based restoration algorithm reiterates the importance of utilizing wavelength converters in protection and is seen to provide around 15%-20% improvement over link restoration especially at moderate to high loads.     

Robust FIPP p-cycles against dual link failures

We propose a new generic flow formulation for Failure-Independent Path-Protecting (FIPP) p-cycles subject to multiple failures. While our new model resembles the decomposition model formulation proposed by Orlowski and Pioro (Networks, 2011) in the case of classical shared path protection, its originality lies in its adaptation to FIPP p-cycles. When adapted to that last pre-configured pre-cross connected protection scheme, the bandwidth sharing constraints must be handled in a different way in order to take care of the sharing along the FIPP p-cycles. It follows that, instead of a polynomial-time solvable pricing problem as in the model of Orlowski and Pioro (Networks, 2011), we end up with a much more complex pricing problem, which has an exponential number of constraints due to some subtour elimination constraints. Consequently, in order to efficiently solve the pricing problem, we consider: (i) a hierarchical decomposition of the original pricing problem; (ii) heuristics in order to go around the large number of constraints in the pricing problem. Performance evaluation is made in the case of FIPP p-cycles subject to dual failures. For small to medium size networks, the proposed model remains fairly scalable for increasing percentages of dual failures, and requires much less bandwidth than p-cycle protection schemes (ratio varies from 2 to 4). For larger networks, heuristics are required in order to keep computing times reasonable. In the particular case of single link failures, it compares very favorably (5 to 10 % of bandwidth saving) to the previously proposed column generation ILP model of Rocha, Jaumard and Stidsen (Telecommun. Syst., 2012).     

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.     

Route optimization in mobile ATM networks

This paper presents an algorithm for optimizing the route of a connection that becomes suboptimal due to operations such as handoffs and location-based reroutes, and applies this algorithm to the handoff management problem in mobile ATM (Asynchronous Transfer Mode) networks based on the PNNI (Private Network-to-Network Interface) standard. The route optimization algorithm uses hierarchical route information of the connection and summarized topology and loading information of the network to determine a “crossover node” such that adjusting the connection from that crossover node results in an optimally routed connection. Handoff management schemes that perform local rerouting of connections have been proposed in order to support fast handoffs. These methods result in suboptimally routed connections. In this paper, we demonstrate how this route optimization algorithm can be used to optimize the route of a connection after such a handoff is executed, as the second phase of a two-phase handoff scheme. This route optimization procedure can also be executed as part of the handoff procedure resulting in a one-phase handoff scheme. Applying this route optimization algorithm, we propose two one-phase schemes, the one-phase optimal scheme and the one-phase minimal scheme. A comparative performance analysis of one- and two-phase handoff schemes is presented. Measures of comparison are handoff latency and the amount of network resources used by a connection. Handoff latency in the one-phase optimal scheme is greater than that in the two-phase schemes, and handoff latency in the one-phase minimal scheme is smaller than that in the two-phase schemes. The one-phase methods show a significant increase in efficiency of the connection compared to the two-phase methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

Capacity Optimization for Surviving Double-Link Failures in Mesh-Restorable Optical Networks

Most research to date in survivable optical network design and operation, focused on the failure of a single component such as a link or a node. A double-link failure model in which any two links in the network may fail in an arbitrary order was proposed recently in literature [1]. Three loop-back methods of recovering from double-link failures were also presented. The basic idea behind these methods is to pre-compute two backup paths for each link on the primary paths and reserve resources on these paths. Compared to protection methods for single-link failure model, the protection methods for double-link failure model require much more spare capacity. Reserving dedicated resources on every backup path at the time of establishing primary path itself would consume excessive resources. Moreover, it may not be possible to allocate dedicated resources on each of two backup paths around each link, due to the wavelength continuous constraint. In M. Sridharan et al., [2,3] we captured the various operational phases in survivable WDM networks as a single integer programming based (ILP) optimization problem. In this work, we extend our optimization framework to include double-link failures. We use the double-link failure recovery methods available in literature, employ backup multiplexing schemes to optimize capacity utilization, and provide 100% protection guarantee for double-link failure recovery. We develop rules to identify scenarios when capacity sharing among interacting demand sets is possible. Our results indicate that for the double-link failure recovery methods, the shared-link protection scheme provides 10–15% savings in capacity utilization over the dedicated link protection scheme which reserves dedicated capacity on two backup paths for each link. We provide a way of adapting the heuristic based double-link failure recovery methods into a mathematical framework, and use techniques to improve wavelength utilization for optimal capacity usage.     

Dynamic establishment of restorable connections using -cycle protection in WDM networks

Dynamic establishment of restorable connections in WDM networks is an important problem that has received much study. We propose a dynamic restorable connection establishment scheme that uses p-cycles to protect a connection’s working lightpath. For a given connection request, our scheme first computes a working lightpath and then computes a set of p-cycles to protect the links on the working lightpath so that the connection can survive any single link failure. The key advantage of the proposed scheme is that it enables fast failure recovery while requiring very simple online computation at connection establishment time. Our scheme consists of three components for connection establishment: offline computation of primary cycles, online computation of the working lightpath, and online computation of p-cycles for working lightpath protection. Our scheme also includes a connection teardown procedure that computes and releases all p-cycles that are no longer needed. Simulation study shows that our scheme significantly outperforms an existing p-cycle-based dynamic restorable connection establishment scheme.     

Protection Schemes for IP-over-WDM Networks: Throughput and Recovery Time Comparison

This article presents a novel protection approach using Generalized Multi-Protocol Label Switching (GMPLS). This strategy provides protection at the Wavelength Division Multiplexing (WDM) layer, meaning that all Internet Protocol Label-Switched Path (IP LSPs) nested inside a lightpath are protected in an aggregated way. It uses resources efficiently since spare capacity of working primary lightpaths can be used for backup purposes whenever necessary. The IP and WDM layers are treated together as a single integrated network from a control plane point of view, so that network state information from both layers can be used. Besides discussing the strategy proposed and the key features of GMPLS that will allow its implementation, we mathematically formulate the maximum throughput problem. Thereafter, we propose and compare heuristic algorithms for IP-over-WDM networks using three protection approaches: WDM lightpath protection, IP LSP protection, and the proposed protection scheme. Their throughputs and recovery times are analyzed and compared. Our results show that, for a representative mesh network, the proposed aggregated protection scheme presents better protection efficiency and good scalability properties when compared with the other two schemes.     

Dynamic Establishment of Segmented Protection Paths in Single and Multi-Fiber WDM Mesh Networks

Wavelength division multiplexed (WDM) networks are matured to provide, scalable data centric infrastructure, capable of delivering flexible, value added, high speed and high bandwidth services directly from the optical (WDM) layer. But, providing fault-tolerance at an acceptable level of overhead in these networks has become a critical problem. This is due to the size of the current and future networks and diverse quality of service (QoS) requirements for multimedia and mission critical applications. Several distributed real-time applications require communication services with fault-tolerance apart from guaranteed timeliness at acceptable levels of overhead. Several methods exist in the literature which attempt to guarantee recovery in a timely and resource efficient manner. These methods are centered around a priori reservation of network resources called spare resources along a protection path. This protection path is usually routed from source to destination along a totally link disjoint path from primary path. This paper considers the problem of routing and wavelength assignment (RWA) in wavelength routed WDM optical networks. In particular, we propose an efficient algorithm to select routes and wavelengths to establish dependable connections (D-connections), called segmented protection paths. Our algorithm does not insist on the existence of totally disjoint paths to provide full protection. We present experimental results which suggest that our scheme is attractive enough in terms of average call acceptance ratio, spare wavelength utilization, and number of requests that can be satisfied for a given number of wavelengths assuming that the requests come one at time, and wavelengths are assigned according to fixed ordering. Furthermore, the results suggest that our scheme is practically applicable for medium and large sized networks, which improves number of requests that can be satisfied and helps in providing better QoS guarantees such as bounded failure recovery time and propagation delays without any compromise on the level of fault-tolerance for a given number of wavelengths and fibers. We conduct extensive simulation experiments to evaluate the effectiveness of the proposed scheme on different networks and compare with existing methods.This work was supported by the Department of Science and Technology, New Delhi, India. An earlier version of this paper was presented at Opticomm 2002 conference, July 29-August 2, Boston, USA.     

Dynamic proxy tree-based data dissemination schemes for wireless sensor networks

In wireless sensor networks, efficiently disseminating data from a dynamic source to multiple mobile sinks is important for the applications such as mobile target detection and tracking. The tree-based multicasting scheme can be used. However, because of the short communication range of each sensor node and the frequent movement of sources and sinks, a sink may fail to receive data due to broken paths, and the tree should be frequently reconfigured to reconnect sources and sinks. To address the problem, we propose a dynamic proxy tree-based framework in this paper. A big challenge in implementing the framework is how to efficiently reconfigure the proxy tree as sources and sinks change. We model the problem as on-line constructing a minimum Steiner tree in an Euclidean plane, and propose centralized schemes to solve it. Considering the strict energy constraints in wireless sensor networks, we further propose two distributed on-line schemes, the shortest path-based (SP) scheme and the spanning range-based (SR) scheme. Extensive simulations are conducted to evaluate the schemes. The results show that the distributed schemes have similar performance as the centralized ones, and among the distributed schemes, the SR scheme outperforms the SP scheme.