Routing restorable bandwidth guaranteed connections using maximum 2-route flows

Routing with service restorability is of much importance in Multi-Protocol Label Switched (MPLS) networks, and is a necessity in optical networks. For restoration, each connection has an active path and a link-disjoint backup path. The backup path enables service restoration upon active path failure. For bandwidth efficiency, backups may be shared. This requires that at least the aggregate backup bandwidth used on each link be distributed to nodes performing route computations. If this information is not available, sharing is not possible. Also, one scheme in use for restorability in optical networks is for the sender to transmit simultaneously on the two disjoint paths and for the receiver to choose data from the path with stronger signal. This has the advantage of fast receiver-initiated recovery upon failure but it does not allow backup sharing. In this paper, we consider the problem of efficient dynamic routing of restorable connections when backup sharing is not allowed. Our objective is to be able to route as many connections as possible for one-at-a-time arrivals and no knowledge of future arrivals. Since sharing cannot be used for achieving efficiency, the goal is to achieve efficiency by improved path selection. We show that by using the minimum-interference ideas used for nonrestorable routing, we can develop efficient algorithms that outperform previously proposed algorithms for restorable routing such as routing with the min-hop like objective of finding two disjoint paths with minimum total hop-count. We present two new and efficient algorithms for restorable routing without sharing, and one of them requires only shortest path computations. We demonstrate that both algorithms perform very well in comparison to previously proposed algorithms.     

Routing bandwidth guaranteed paths with local restoration in label switched networks

The emerging multiprotocol label switching (MPLS) networks enable network service providers to route bandwidth guaranteed paths between customer sites. This basic label switched path (LSP) routing is often enhanced using restoration routing which sets up alternate LSPs to guarantee uninterrupted connectivity in case network links or nodes along primary path fail. We address the problem of distributed routing of restoration paths, which can be defined as follows: given a request for a bandwidth guaranteed LSP between two nodes, find a primary LSP, and a set of backup LSPs that protect the links along the primary LSP. A routing algorithm that computes these paths must optimize the restoration latency and the amount of bandwidth used. We introduce the concept of "backtracking" to bound the restoration latency. We consider three different cases characterized by a parameter called backtracking distance D: 1) no backtracking (D=0); 2) limited backtracking (D=k); and 3) unlimited backtracking (D=/spl infin/). We use a link cost model that captures bandwidth sharing among links using various types of aggregate link-state information. We first show that joint optimization of primary and backup paths is NP-hard in all cases. We then consider algorithms that compute primary and backup paths in two separate steps. Using link cost metrics that capture bandwidth sharing, we devise heuristics for each case. Our simulation study shows that these algorithms offer a way to tradeoff bandwidth to meet a range of restoration latency requirements.     

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.     

Link-State-Based Algorithms for Dynamic Routing in All-Optical Networks with Ring Topologies

The increased usage of large bandwidth in optical networks raises the problems of efficient routing to allow these networks to deliver fast data transmission with low blocking probabilities. Due to limited optical buffering in optical switches and constraints of high switching speeds, data transmitted over optical networks must be routed without waiting queues along a path from source to destination. Moreover, in optical networks deprived of wavelength converters, it is necessary for each established path to transfer data from source to destination by using only one wavelength. To solve this NP-hard problem, many algorithms have been proposed for dynamic optical routing like Fixed-Paths Least Congested (FPLC) routing or Least Loaded Path Routing (LLR). This paper proposes two heuristic algorithms based on former algorithms to improve network throughput and reduce blocking probabilities of data transmitted in all-optical networks with regard to connection costs. We also introduce new criteria to estimate network congestion and choose better routing paths. Experimental results in ring networks show that both new algorithms achieve promising performance.     

A novel two-step approach to restorable dynamic QoS routing

Aiming at minimizing the combined bandwidth cost of a pair of disjoint active and backup paths, a popular approach to designing restorable dynamic quality of service (QoS) routing schemes is based on the integer linear programming (ILP) formulation. Owing to the very different natures of active and backup paths, we found this approach problematic. In this paper, we propose an alternative approach, called two-step restorable QoS routing. In the first step, an active path is found using the widest shortest path (WSP) routing. In the second step, the corresponding backup path is determined using one of the three variants of shortest widest path (SWP) routing: basic SWP, approximate SWP or composite SWP. Combining the two steps, three novel two-step routing algorithms, denoted by SBW, SAW, and SCW, are obtained. Comparing with the best known algorithms, we show that our two-step routing approach yields noticeably lower call blocking probability, shorter active-path length, and additional flexibility of adjusting backup-path length (depending on the SWP variant adopted). Besides, our two-step routing approach gives a much shorter running time than the ILP approach, which makes it more suitable for dynamic routing.     

Achieving fast and bandwidth-efficient shared-path protection

Dynamic provisioning of restorable bandwidth guaranteed paths is a challenge in the design of broad-band transport networks, especially next-generation optical networks. A common approach is called (failure-independent) path protection, whereby for every mission-critical active path to be established, a link (or node) disjoint backup path (BP) is also established. To optimize network resource utilization, shared path protection should be adopted, which often allows a new BP to share the bandwidth allocated to some existing BPs. However, it usually leads the backup paths to use too many links, with zero cost in term of additional backup bandwidth, along its route. It will violate the restoration time guarantee. In this paper, we propose novel integer linear programming (ILP) formulations by introducing two parameters (/spl epsi/ and /spl mu/) in both the sharing with complete information (SCI) scheme and the distributed partial information management (DPIM) scheme. Our results show that the proposed ILP formulations can not only improve the network resource utilization effectively, but also keep the BPs as short as possible.     

A novel shared-path protection algorithm with correlated risk against multiple failures in flexible bandwidth optical networks

In this paper, to decrease the traffic loss caused by multiple link failures, we consider the correlated risk among different connection requests when both the primary and backup paths are routed and assigned spectrum. Therefore, a novel shared-path protection algorithm is developed, named shared-path protection algorithm with correlated risk (SPP_CR), in flexible bandwidth optical networks. Based on the correlated risk, the routing can be diverse and the sharing in backup spectral resource will be restricted by SPP_CR algorithm, then the dropped traffic caused by simultaneous multiple failures between primary and backup path can be efficiently decreased. Simulation results show that, SPP_CR algorithm (i) achieves the higher successful service ratio (SSR) than traditional shared-path protection (SPP), shared-path protection with dynamic load balancing (SPP_DLB) and dedicated path protection (DPP); (ii) makes a better tradeoff in blocking probability, protection ratio (PR), average frequency slots consumed (AFSC) and redundancy ratio (RR) than SPP, SPP_DLB and DPP algorithms.     

Cost Effective Shared Path Protection for WDM Optical Mesh Networks with Partial Wavelength Conversion

In this paper, we study routing and wavelength assignment of connection requests in survivable WDM optical mesh networks employing shared path protection with partial wavelength conversion while 100% restorability is guaranteed against any single failures. We formulate the problem as a linear integer program under a static traffic model. The objective is to minimize the total cost of wavelength-links and wavelength converters used by working paths and protection paths of all connections. A weight factor is used which is defined as the cost ratio of a wavelength converter and a wavelength-link. Depending on the relative cost of bandwidth and wavelength conversion, the optimization objective allows a proper tradeoff between the two. The proposed algorithm, the shortest-widest-path-first (SWPF) algorithm, uses a modified Dijkstra's algorithm to find a working path and a protection path for each connection request in the wavelength graph transformed from the original network topology. When there are multiple candidate paths that have the same minimum total cost, the path along which the maximum number of converters used at each node is minimized is chosen by the SWPF algorithm. We have evaluated the effectiveness of the proposed algorithm via extensive simulation. The results indicate that the performance of the proposed algorithm is very close to that of the optimal solutions obtained by solving the ILP formulation and outperforms existing heuristic algorithms in terms of total number of converters used and the maximum number of converters required at each node in the network. The proposed algorithm also achieves slightly better performance in terms of total cost of wavelength-links and converters used by all connections. We also investigated shared path protection employing converter sharing. The results show that the technique can reduce not only the total number of converters used in the network but also the maximum number of converters required at each node, especially when a large number of converters are needed in the network. In this study, although the ILP formulation is based on static traffic, the proposed algorithm is also applicable to routing dynamic connection requests.     

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.     

Ad hoc网络中不相关多路由源端寻路算法

路由方案是Ad hoc网络中一个热点研究领域。其中,按需路由算法由于其有效性在带宽受限的Ad hoc网络中得到比较大的发展。然而大部分的按需路由算法,建立并只使用单条路由,当前使用的路径的链路断开时,路由算法必须执行一个路由修复过程。提出了不相关多路由源端路由算法（DMSR）,建立并利用多条最大不相关路由。算法中,中间节点等待一段时间以得到多个路由请求包（RREQ）,然后在这个RREQ中,选择相关性最小的多路径,并将这些信息写入一个RREQ中,并将它广播出去。从仿真结果可以看出本文的算法提高了数据包的正确传输率和业务均衡性。     

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%.     

EONs中一种混合路径专有保护算法

为了降低带宽阻塞率,节约频谱资源,在动态业务到达的弹性光网络(EONs)场景下,不同业务请求的路径状况可能不同,因此不能确定单路径专有保护与带宽分割多路径专有保护的优劣.文章结合单路径专有保护和带宽分割多路径专有保护提出了一种混合路径专有保护(HDPP)算法.该算法利用路径的单位频谱效率和路径跳数计算了k条链路不相关候...     

Path-based routing provisioning with mixed shared protection in WDM mesh networks

In this paper, the authors focus on studying the problem of survivable routing provisioning to prevent single link failure in wavelength-division-multiplexing (WDM) mesh networks, and propose a novel protection scheme called mixed shared path protection (MSPP). With MSPP, the authors define three types of resources: 1) primary resources that can be used by primary paths; 2) spare resources that can be shared by backup paths; and 3) mixed resources that can be shared by both the primary and the backup paths. In the proposed protection scheme, each connection is assigned a primary path and a link disjoint backup path. Differing from pervious protection schemes, MSPP allows some primary paths and backup paths to share the common mixed resources if the corresponding constraints can be satisfied. In this paper, the authors consider three types of path-based protection schemes, i.e., dedicated path protection (DPP), shared path protection (SPP), and MSPP, and evaluate their performance for both the static and the dynamic provisioning problems. Simulation results show that MSPP outperforms DPP and SPP.     

Spare Capacity Allocation in Two-Layer Networks

In this paper we consider the problem of provisioning spare capacity in two-layer backbone networks using shared backup path protection. First, two spare capacity allocation (SCA) optimization problems are formulated as integer linear programming (ILP) models for the cases of protection at the top layer against failures at the bottom layer. The first model captures failure propagation using overlay information between two layers for backup paths to meet diversity requirements. The second model improves bandwidth efficiency by moving spare capacity sharing from the top layer to the bottom layer. This exposes a tradeoff between bandwidth efficiency and extra cross-layer operation. Next, the SCA model for common pool protection is developed to allow spare capacity sharing between two layers. Our previous SCA heuristic technique, successive survivable routing (SSR) is extended for these optimization problems. Numerical results for a variety of networks indicate that the common pool protection is attractive to enhance bandwidth efficiency without loss of survivability and that the SSR heuristic quickly results in near optimal solutions     

IP/MPLS over WDM网中考虑链路 负载平衡的保护设计

利用网络链路资源被占用的部分信息实现保护资源共享,可以极大地改善网络对业务的丢弃性能.这对采用多协议标记交换(MPLS,Multiprotocol Label Switching)技术的IP over WDM网络来说,并不需要太大的代价.基于此,本文提出了在IP over WDM网中考虑通路保护的动态路由算法.对工作通路的选取,算法对选路成本和路由长度作了折衷考虑;而对于保护通路,则对其共享能力和路由长度作了权衡.仿真结果表明,本文算法不管是对业务的丢弃性能,还是对网络的链路负载平衡度,均取得了较满意的结果.     

Restorable dynamic quality of service routing

The focus of quality-of-service routing has been on the routing of a single path satisfying specified QoS constraints. Upon failure of a node or link on the path, a new path satisfying the constraints has to be established. However, resources needed to satisfy the QoS requirements are not guaranteed to be available at the rerouting instant, so QoS is not guaranteed upon failure. Restorable QoS routing, where active and backup paths must be simultaneously set up, has been previously studied. This is mostly motivated by the incorporation of mechanisms to establish QoS guaranteed paths with failure protection in multiprotocol label switching networks. This article describes some previously developed algorithms for dynamic routing of restorable QoS guaranteed paths     

Bandwidth‐guaranteed QoS routing of multiple parallel paths in CDMA/TDMA ad hoc wireless networks

This paper investigates the issues of QoS routing in CDMA/TDMA ad hoc networks. Since the available bandwidth is very limited in ad hoc networks, a QoS request between two nodes will be blocked if there does not exist a path that can meet the QoS requirements, even though there is enough free bandwidth in the whole system. In this paper, we propose a new scheme of using multiple paths between two nodes as the route for a QoS call. The aggregate bandwidth of the multiple paths can meet the bandwidth requirement of the call and the delays of these paths are within the required bound of the call. We also propose three strategies by which to choose a set of paths as the route, namely, shortest path first (SPF), largest bandwidth first (LBF), and largest hop‐bandwidth first (LHBF). Extensive simulations have been conducted to evaluate the performance of the three strategies in comparison with a traditional single path routing algorithm. The simulation results show that the proposed multiple paths routing scheme significantly reduces the system blocking rates in various network environments, especially when the network load is heavy. Copyright © 2005 John Wiley & Sons, Ltd.     

On Achieveing Bandwidth-Aware LSP//spl lambda/SP Multiplexing/Separation in Multi-layer Networks

We present a new traffic engineering (TE) model which is based on QoS rerouting and uses hybrid resilience to improve the recovery performance of multi-layer networks where an MPLS network is layered above an MPlambdaS network. We formulate the rerouting of the LSPs/lambdaSPs as a multi-constrained problem and use its polynomial reduction to find a heuristic solution that can be implemented by standardized constraint-based routing algorithms. This heuristic solution uses a cost-based routing optimization to achieve different network configurations which multiplex/separate bandwidth-aware LSPs/lambdaSPs on the network links. We formulate the resilience upon failure as a multi-objective problem consisting of finding a resilience strategy that minimizes recovery operation time and maximizes the LSP/lambdaSP restorability. A solution to this problem is proposed where a hybrid resilience framework is used to achieve restoration in the MPLS layer to complement path switching in the MPlambdaS layer. We evaluate the performance of the TE model when rerouting the tunnels carrying the traffic offered to a 23- and 31-node networks. Simulation reveals that the hybrid resilience model performs better than classical recovery mechanisms. In terms of restorability, quality of rerouting paths and rerouting stability     

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.     

Lightpath Re-optimization in mesh optical networks

Intelligent mesh optical networks deployed today offer unparalleled capacity, flexibility, availability, and, inevitably, new challenges to master all these qualities in the most efficient and practical manner. More specifically, demands are routed according to the state of the network available at the moment. As the network and the traffic evolve, the lightpaths of the existing demands becomes sub-optimal. In this paper we study two algorithms to re-optimize lightpaths in resilient mesh optical networks. One is a complete re-optimization algorithm that re-routes both primary and backup paths, and the second is a partial re-optimization algorithm that re-routes the backup paths only. We show that on average, these algorithms allow bandwidth savings of 3% to 5% of the total capacity in scenarios where the backup path only is re-routed, and substantially larger bandwidth savings when both the working and backup paths are re-routed. We also prove that trying all possible demand permutations with an online algorithm does not guarantee optimality, and in certain cases does not achieve it, while for the same scenario optimality is achieved through re-optimization. This observation motivates the needs for a re-optimization approach that does not just simply look at different sequences, and we propose and experiment with such an approach. Re-optimization has actually been performed in a nationwide live optical mesh network and the resulting savings are reported in this paper, validating reality and the usefulness of re-optimization in real networks.