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.     

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.     

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.     

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.     

一种基于RSVP-TE的MPLS网络FRR机制

快速重路由FRR用于MPLS网络故障时的修复,能够降低故障导致的传输时延和丢包率,保障业务的服务质量,满足网络中有特殊需求的应用。介绍了基于RSVP-TE协议的FRR原理,重点阐述了通过RSVP-TE交互,在MPLS网络中对重要链路或节点预先建立备份路径,检测到链路或节点故障后进行修复的解决方案,给出了具体实现框架,介绍了备份路径的建立过程以及检测故障后的处理过程。介绍了该机制在网络中的典型应用和前景。     

Efficient Distributed Bandwidth Management for MPLS Fast Reroute

As service providers move more applications to their IP/MPLS (multiple protocol label switching ) backbone networks, rapid restoration upon failure becomes more and more crucial. Recently MPLS fast reroute has attracted lots of attention as it was designed to meet the needs of real-time applications, such as voice over IP. MPLS fast reroute achieves rapid restoration by computing and signaling backup label switched path (LSP) tunnels in advance and re-directing traffic as close to failure point as possible. To provide a guarantee of bandwidth protection, extra bandwidth has to be reserved on backup paths. Using path merging technique as described in IETF RFC 4090 only, the network is able to share some bandwidth on common links among backup paths of the same service LSP, i.e., so-called intra-sharing. But no solution is provided on how to share bandwidth among backup paths of different service LSPs, i.e., so-called inter-sharing. In this paper, we provide an efficient distributed bandwidth management solution. This solution allows bandwidth sharing among backup paths of the same and different service LSPs, i.e., both intra-sharing and inter-sharing, with a guarantee of bandwidth protection for any single node/link failure. We also propose an efficient algorithm for backup path selection with the associated signaling extensions for additional information distribution and collection. To evaluate our schemes, we compare them via simulation with the basic MPLS fast reroute proposal, IETF RFC 4090, on two networks. Our simulation results show that using our bandwidth management scheme can significantly reduce restoration overbuild from about 250% to about 100%, and our optimized backup path selection can further reduce restoration overbuild to about 60%.     

MPLS security: an approach for unicast and multicast environments

Multi-Protocol Label Switching (MPLS) network architecture does not protect the confidentiality of data transmitted. This paper proposes a mechanism to enhance the security in MPLS networks by using multi-path routing combined with a modified (k, n) threshold secret sharing scheme. An Internet Protocol (IP) packet entering MPLS ingress router can be partitioned into n shadow (share) packets, which are then assigned to maximally node disjoint paths across the MPLS network. The egress router at the end will be able to reconstruct the original IP packet if it receives any k share packets. The attacker must therefore tap at least k paths to be able to reconstruct the original IP packet that is being transmitted, while receiving k???1 or less of share packets makes it hard or even impossible to reconstruct the original IP packet. In this paper, we consider the multicast case in addition to the unicast. To our best knowledge, no work has been published for MPLS multicast security. We have implemented our model and measured its time complexity on variable packets size.     

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.     

MPLS technology in wireless networks

Recently, there has been increasing demand for Multi-protocol label switching (MPLS) technology in most internet service provider networks. The application of MPLS technology in wireless networking is evolving. Therefore, next generation wireless networks are required to have IP mobility solutions with high reliability, low-latency handoffs, and trustworthy security. In this paper, we propose a novel multi-path mobility scheme for fast handoff to achieve these requirements. The scheme is based on MPLS multi-path forwarding and network coding based on modulo-p Galois finite field GF(p = 2 ⁿ ) arithmetic. The simulation results show that our proposed approach scales well to fulfill fast handoff/handover performance while providing security for transmitted data with minor bandwidth overhead.     

基于IP FRR的MPLS快速重路由实现

随着bIPLS技术的广泛应用,人们对MPLS网络的可靠性要求越来越高,支持MPLS快速重路由的通信设备越来越多。本文主要介绍了如何扩展LDP模块和MPLS模块,以实现基于IPFRR的MPLS快速重路由功能,给出了系统各模块之间的关系、LDP模块对路由模块的路由通知消息的处理流程图以及MPLS模块中转发表项的结构。最后组网测试,证明该扩展设计具有快速重路由功能。     

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.     

An Efficient Rerouting Scheme for MPLS-Based Recovery and Its Performance Evaluation

The path recovery in MPLS is the technique to reroute traffic around a failure or congestion in a LSP. Currently, there are two kinds of model for path recovery: rerouting and protection switching. The existing schemes based on rerouting model have the disadvantage of more difficulty in handling node failures or concurrent node faults. Similarly, the existing schemes based on protection switching model have some difficulty in solving problem such as resource utilization and protection of recovery path. This paper proposes an efficient rerouting scheme to establish a LSP along the least-cost recovery path of all possible alternative paths that can be found on a working path, which is calculated by the upstream LSR that has detected a failure. The proposed scheme can increase resource utilization, establish a recovery path relatively fast, support almost all failure types such as link failures, node failures, failures on both a working path and its recovery path, and concurrent faults. Through simulation, the performance of the proposed scheme is measured and compared with the existing schemes.     

Strategy for protection and restoration of optical paths in WDM backbone networks for next-generation Internet infrastructures

This paper proposes and analyzes a strategy for protection and restoration of optical paths in wavelength division multiplexing (WDM) networks for next-generation Internet infrastructure. Assuming a network model in which a multiprotocol label switching (MPLS) layer is overlaid on top of a WDM layer, and a segregation of the traffic on a wavelength basis, the strategy is based on a network dimensioning aiming at: 1) the support of different types of traffic, relating to different service categories; 2) the guarantee that all the wavelength paths carrying mission-critical services (with stringent quality of service requirements) are protected against failure; and 3) the possibility of restoring a large amount of wavelength paths carrying Internet best-effort services, i.e., low-priority (LP) preemptible traffic with no QoS requirements. The reference network scenario is an overlay model in which the optical network interacts with an MPLS network with a separated control plane; the optical network manages its resources to better serve the traffic coming from the MPLS network. Two path protection schemes, namely, disjoint path (DP) and single-link basis (SLB), and a link protection mechanism, namely, local repair (LP), are investigated. Furthermore, the paper considers both the case of using wavelength conversion in the optical nodes and the case in which wavelength conversion is not used at all. The analysis compares the performance of the different strategies in terms of the percentage of optical paths carrying LP traffic not served by the optical network after a failure and of the dimensions of the optical nodes for all the schemes. The analysis reveals that the proposed approach allows the restoration of a large amount of best-effort traffic with a reasonable increase of network redundancy.     

Performance evaluation of software-defined clustered-optical access networking for ubiquitous data center optical interconnection

In recent years, p-cycles have been widely investigated for survivability of WDM networks. They provide fast recovery speed such as ring and capacity efficiency as mesh survivability schemes. However, restoration paths are very long, which causes excessive latency and intolerable physical impairments. On the other hand, nowadays, a wide set of applications require an optical path with almost no delay. The existing approaches, namely loopbacks removal and inter-cycle switching, provide a significant reduction in the restored path, but even then a number of restored paths remain many times longer than the working path lengths. In this paper, we propose a network partitioning-based approach to control the length of each restored path as per delay sustainability of time critical applications. The basic idea of the work is to partition the network into domains and construct the p-cycles for each domain independently. The domain wise construction of p-cycles restricts their length, which consequently reduces the length of restored paths. Here, we introduce a new concept where the selected border nodes are overlapped among adjacent domains to cover inter-domain spans of the network as a domain span in order to ensure their survivability through domain p-cycles. Simulation results show that the proposed solution is good enough to control the restored path length with small augmentation in redundancy of spare capacity as compared to optimal design of p-cycles. More importantly, it enhances the dual failure restorability significantly.     

A new approach for fast segment‐based protection in WDM mesh networks

We propose a new approach for developing segment‐based schemes for protection against single link/node failure in wavelength division multiplexing (WDM) mesh networks. In the proposed approach, every request is allocated a pair of link disjoint but most coupled primary and backup paths. Two paths are said to be most coupled if they share the maximum number of end nodes of some existing requests. Coupled paths reduce the total number of hops need to be traversed by a failure signal and, hence, potentially reduces the overall recovery time. We show that the problem of finding a pair of disjoint and most coupled paths is NP‐complete. Accordingly, we propose an efficient and fast protection algorithm called SPXP—Segment Pre‐Cross‐Connected Protection, to allocate disjoint and most coupled paths. The proposed SPXP algorithm reduces the recovery time by ensuring that backup resources are pre‐configured along each backup segment and, hence, is readily available upon a failure. Simulation results for different incremental traffic models and network topologies show that, for most cases, the proposed SPXP exhibits better performance in terms of blocking probability, resource usage, and recovery time compared with existing protection schemes. Copyright © 2010 John Wiley & Sons, Ltd.     

An efficient column generation design method of p-cycle-based protected working capacity envelope

The protected working capacity envelope (PWCE) concept was proposed by Grover (2004) in order to simplify network operations and management in survivable wavelength division multiplexing (WDM) networks. In this paper, we focus on the design of PCWE and investigate a new design method based on column generation (CG) for designing survivable WDM networks based on p-cycle PWCE. Proposed design algorithms for PWCE and p-cycle proceed in two steps: A first step where a large (sometimes huge) number of cycles is enumerated followed by a second step where the selection of the most promising p-cycles is made with the help of combinatorial optimization tools. In this paper, we develop a new (single-step) method based on large scale optimization tools, that is, CG techniques, where the generation of cycles is dynamic and embedded within the optimization process. The key advantage of CG techniques is that no a priori cycle enumeration step is required ahead of the optimization process: The generation of the relevant cycles, only one or few at a time, is embedded in the optimization process. We conducted intensive computational experiments to compare the performances of our CG algorithms with four other algorithms in the literature. The different algorithms were compared with regard to several design metrics and running time. Results obtained in the experiments on five different network instances show that the CG-based algorithm outperforms by far all proposed algorithms in the literature, both with respect to the scalability (much smaller computing times for large network instances) and also with respect to the quality of the solutions.     

Network Design and Cost Optimization for Label Switched Multilayer Photonic IP Networks

Dealing with the explosive increase in the amount of Internet traffic requires high-speed and huge capacity Internet protocol (IP) backbone networks. Existing IP backbone networks are constructed using point-to-point wavelength-division-multiplexing (WDM) transmission systems, where all the wavelengths are terminated link-by-link, so that rather expensive optical/electrical conversions are necessary at every node. In these systems, since every IP packet is routed at each intermediate node based on the header information, a header processing bottleneck will occur when the node input traffic exceeds several hundreds of gigabits per second. In order to mitigate these problems, an optical cross-connect (OXC) function that employs wavelength routing of the optical paths (OPs) will provide an effective solution. This paper proposes a network design method where electrical and photonic multiprotocol label switching (MPLS) technologies are used; the network is referred to as a photonic IP network. We first propose new algorithms that minimize the network cost in a multilayered network comprising electrical label switched paths (LSPs) and optical LSPs (optical paths that are controlled using the MPLS mechanism). The particular point of the proposed algorithms is that they include different cost minimization scenarios appropriate for the different OLSP provisioning conditions that are chosen as the first step in the design stage. The effectiveness of the proposed algorithms and the benefits of the OLSPs are quantitatively evaluated through various simulations.