一种基于SRLG条件失败概率限制的保护算法

研究了IP／MPLSover WDM网中，如何建立两条共享风险链路组(SRLG)分离的标记交换(LSP)问题，提出一种新的基于SRLG条件失败概率限制的保护算法。该算法寻找SRLG条件失败概率最小的最短路径作为工作通路的保护通路，既能最大限度地保护用户业务的可靠性要求，同时又能够有效降低全网LSP建立请求的阻塞率。     

Using Shared Risk Link Groups to enhance backup path computation

To cope quickly with all types of failure risks (link, node and Shared Risk Link Group (SRLG)), each router detecting a failure on an outgoing interface activates locally all the backup paths protecting the primary paths which traverse the failed interface. With the observation that upon a SRLG failure, some active backup paths are inoperative and do not really participate to the recovery (since they do not receive any traffic flow), we propose a new algorithm (SRLG structure exploitation algorithm or SSEA) exploiting the SRLG structures to enhance the admission control and improve the protection rate.With our algorithm, more flexibility is provided for the backup path selection since a backup path which protects against the failure of a link belonging to a SRLG does not systematically bypass all the links of that SRLG. Moreover, our algorithm permits to save more bandwidth because it does not allocate the bandwidth for the inoperative backup paths even if they are activated.Simulations show that our algorithm SSEA decreases the ratio of rejected backup paths and, it reduces in distributed environments the average number of messages sent to manage the bandwidth information necessary for the backup path computation.     

Delay-SRLG constrained,backup-shared path protection in WDM networks with sleep scheduling

This paper addresses the Delay-Shared Risk Link Groups (SRLG) constrained path protection problem in green WDM networks with sleep scheduling, and presents a Green Delay-SRLG Constrained Protection (GDSCP) approach. In order to balance the QoS (delay, SRLG reliability, etc.) and energy consumption, the path search algorithm in GDSCP adopts different principles in the search of the primary and backup paths. The choice of the primary path is optimal for the end-to-end delay while minimizing the node awaking to save energy. When necessary, the rarely used backup paths are allowed to go through more sleeping nodes that lead to potential node awaking to ensure the disjoint degree, and thus increase the SRLG reliability of the combined path. Besides the traditional wavelength sharing between backup paths, our approach further encourages paths of different connections to wake up common sleeping nodes to increase the utilization of the reserved node awaking and thus reduce the demand for the new node-state switching in the network. Comparing to the traditional energy-aware schemes, simulations show promising results that GDSCP can obtain significant improvement in terms of increasing the sleeping percentage of the network and reducing the number of node-state switching without sacrificing the performance of blocking rate.     

Two Heuristics for Calculating a Shared Risk Link Group Disjoint Set of Paths of Min-Sum Cost

A shared risk link group (SRLG) is a set of links which share a common risk of failure. Routing protocols in Generalized MultiProtocol Label Switching, using distributed SRLG information, can calculate paths avoiding certain SRLGs. For single SRLG failure an end-to-end SRLG-disjoint path pair can be calculated, but to ensure connection in the event of multiple SRLG failures a set with more than two end-to-end SRLG-disjoint paths should be used. Two heuristic, the Conflicting SRLG-Exclusion Min Sum (CoSE-MS) and the Iterative Modified Suurballes’s Heuristic (IMSH), for calculating node and SRLG-disjoint path pairs, which use the Modified Suurballes’s Heuristic, are reviewed and new versions (CoSE-MScd and IMSHd) are proposed, which may improve the number of obtained optimal solutions. Moreover two new heuristics are proposed: kCoSE-MScd and kIMSHd, to calculate a set of \(k\) node and SRLG-disjoint paths, seeking to minimize its total cost. To the best of our knowledge these heuristics are a first proposal for seeking a set of \(k\, (k>2)\) node and SRLG-disjoint paths of minimal additive cost. The performance of the proposed heuristics is evaluated using a real network structure, where SRLGs were randomly defined. The number of solutions found, the percentage of optimal solutions and the relative error of the sub-optimal solutions are presented. Also the CPU time for solving the problem in a path computation element is reported.     

PLR-based heuristic for backup path computation in MPLS networks

To ensure service continuity in networks, local protection pre-configuring the backup paths is preferred to global protection. Under the practical hypothesis of single physical failures in the network, the backup paths which protect against different logical failure risks (node, link and shared risk link group (SRLG)) cannot be active at the same time. Thus, sharing bandwidth between such backup paths is crucial to increase the bandwidth availability.In this article, we focus on the optimal on-line distributed computation of the bandwidth-guaranteed backup paths in MPLS networks. As the requests for connection establishment and release arrive dynamically without knowledge of future arrivals, we choose to use the on-line mode to avoid LSP reconfigurations. We also selected a distributed computation to offer scalability and decrease the LSP setup time. Finally, the optimization of bandwidth utilization can be achieved thanks to the flexibility of the path choice offered by MPLS and to the bandwidth sharing.For a good bandwidth sharing, the backup path computation entities (BPCEs) require the knowledge and maintenance of a great quantity of bandwidth information (e.g. non aggregated link information or per path information) which is undesirable in distributed environments. To get around this problem, we propose here a PLR (point of local repair)-based heuristic (PLRH) which aggregates and noticeably decreases the size of the bandwidth information advertised in the network while offering a high bandwidth sharing. PLRH permits an efficient computation of backup paths. It is scalable, easy to be deployed and balances equitably computations on the network nodes.Simulations show that with the transmission of a small quantity of aggregated information per link, the ratio of rejected backup paths is low and close to the optimum.     

Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures

Failure resilience is a desired feature of the Internet. Most traditional restoration architectures assume single failure assumption, which is not adequate in present day WDM optical networks.Multiple link failure models, in the form of shared risk link groups (SRLG’s) and shared risk node groups (SRNG’s) are becoming critical in survivable optical network design. We classify both of these form of failures under a common scenario of shared risk resource groups (SRRG) failures. We develop graph transformation techniques for tolerating multiple failures arising out of shared resource group (SRRG) failures.Diverse routing in such multi-failure scenario essentially necessitates finding out two paths between a source and a destination that are SRRG disjoint. The generalized diverse routing problem has been proved to be NP-Complete. The proposed transformation techniques however provides a polynomial time solution for certain restrictive failure sets. We study how restorability can be achieved for dependent or shared risk link failures and multiple node failures and prove the validity of our approach for different network scenarios. Our proposed technique is capable of improving the diverse route computation by around 20–30% as compared to approaches proposed in the literature.     

MSDP with ACO: A maximal SRLG disjoint routing algorithm based on ant colony optimization

Failure resilience is a desired feature in communication networks, and different methods can be considered in order to achieve this feature. One of these methods is diverse Routing. In this paper, we are going to suggest a sort of diverse routing algorithm, which can find two maximal shared risk link group (SRLG) disjoint paths between a source and a destination node. This algorithm is based on ant colony optimization algorithm, which consists of three parts. These parts are graph transformation technique, finding two maximal edge-disjoint routes and reverse transformation. The final routes are always maximal SRLG disjoint. Simulation results show the efficiency of the proposed method.     

Traffic recovery time constrained shared sub-path protection algorithm in survivable WDM networks

With the development of real-time applications, the traffic recovery time, which is defined as the duration between the failure occurrence on the working path and the interruptive traffic has been successfully switched to the backup path, has become the basic Quality-of-Service (QoS) requirement in survivable WDM networks. In this paper, we address the problem of shared sub-path protection with considering the constraint of traffic recovery time and propose a new heuristic algorithm called Traffic recovery time Constrained Shared Sub-Path Protection (TC_SSPP) to compute the working path and the Shared-Risk-Link-Group (SRLG)-disjoint backup sub-paths. The main target of our work is to improve the resource utilization ratio and reduce the blocking probability for dynamic network environment. By properly setting the delay parameter for each link and running the Delay Constrained Shortest Path Algorithm (DCSPA) to compute the backup sub-paths, TC_SSPP can effectively guarantee the traffic recovery time. Simulation results show that the proposed TC_SSPP can outperform the traditional algorithms.     

Localizing link failures in all-optical networks using monitoring tours

In this paper, we introduce the concept of monitoring tours (m-tours) to uniquely localize all possible failures up to k links in all-optical networks. We establish paths and cycles that can traverse the same link at most twice (forward and backward) and call them m-tours. An m-tour is different from other existing schemes such as m-cycle and m-trail, which traverse a link at most once. Closed (open) m-tours start and terminate at the same (distinct) monitor location(s). Each tour is constructed such that any shared risk linked group (SRLG) failure results in the failure of a unique combination of closed and open m-tours. We prove that k-edge connectivity is a sufficient condition to localize all SRLG failures with up to k-link failures when only one monitoring station is employed. We introduce an integer linear program (ILP) and a greedy scheme to find the monitoring locations to uniquely localize any SRLG failures with up to k links. We provide a heuristic scheme to compute m-tours for a given network. We demonstrate the validity of the proposed monitoring method through simulations. We show that our approach using m-tours significantly reduces the number of required monitoring locations compared to previously developed techniques.     

基于优化链路权值的域内路由保护方案

目前,互联网部署的域内链路状态路由协议,如开放最短路径优先(Open Shortest Path First,OSPF)和中间系统到中间系统(Intermediate System-to-Intermediate System,IS-IS),采用被动恢复方案应对网络故障。随着网络的发展,大量的实时应用部署在互联网上,OSPF的收敛时间无法满足这些实时应用对收敛时间的需求。因此,学术界和工业界提出采用路由保护方案来应对网路中出现的故障。然而,已有的路由保护方案存在两个方面的问题:1)默认路径和备份路径的交叉度较高,如LFA；2)为了计算两条交叉度低的路径,对默认路径加以限制,即默认路径不采用最短路径,如Color Tree。为了解决上述两个问题,首先将上述问题归结为整数规划模型,接着利用启发式方法计算近似最优解,最后在实际网络和模拟网络中对所提算法进行了大量实验。实验结果表明,所提算法可以降低默认路径和备份路径的交叉度,极大地提高网络的可用性。     

Efficient techniques and tools for intra‐domain traffic engineering

Intra‐domain routing protocols are based on Shortest Path First (SPF) routing, where shortest paths are calculated between each pair of nodes (routers) using pre‐assigned link weights, also referred to as link metric. These link weights can be modified by network administrators in accordance with the routing policies of the network operator. The operator's objective is usually to minimize traffic congestion or minimize total routing costs subject to the traffic demands and the protocol constraints. However, determining a link weight combination that meets a network operator's objectives is a difficult task. In this paper, we study the link weight optimization problem in intra‐domain networks. This problem is proved to be NP‐hard with hard protocol constraints, e.g., a flow is evenly distributed along the shortest paths between its origin and destination nodes. We present two fast heuristic approaches to generate efficient link metrics for intra‐domain routing. Some promising experimental results are reported.     

SRLG fault localization using nested m-trails

This paper presents a novel technique called nested m-trail method in all-optical mesh networks for failure localization of any shared risk link group (SRLG) with up to d undirected links. The proposed method decomposes the network topology into virtual cycles and trails, in which sets of m-trails that traverse through a common monitoring node (MN) can be obtained. The nested m-trails are used in the monitoring burst (m-burst) framework, in which the MN can localize any SRLG failure by inspecting the optical bursts traversing through it. An integer linear program (ILP) and a heuristic are proposed for the network decomposition, which are further verified by numerical experiments. We show that the proposed method significantly reduces the required fault localization latency compared to the existing methods.     

Selecting shorter alternate paths for tunnel-based IP Fast ReRoute in linear time

IP Fast ReRoute (IPFRR) has received increasing attention as a means to effectively shorten traffic disruption under failures. A major approach to implementing IPFRR is to pre-calculate backup paths for nodes and links. However, it may not be easy to deploy such an approach in practice due to the tremendous computational overhead. Thus, a light-weight IPFRR scheme is desired to effectively provide cost-efficient routing protection. In this paper, we propose a Fast Tunnel Selection (FTS) approach to achieve tunnel-based IPFRR. FTS approach can find an effective tunnel endpoint before complete computation of entire SPT and thus effectively reduce computation overhead. Specially, we propose two FTS algorithms to provide protection for networks with symmetric and asymmetric link weights. We simulate FTS with topologies of different sizes. The results show that FTS approach reduces more than 89% computation overhead compared to the existing approaches, and achieves more than 99% average link protection rate and more than 90% average node protection rate. Moreover, FTS approach achieves less than 15% path stretch, which is better than the existing approaches.     

基于故障链路资源分离的电力光缆备用路由资源配置方法

为了保障电网远程调度通道的可靠性,同时提高光缆网络资源的利用效率,基于共享备份通道保护方法耗费资源量大、阻塞率高等问题,提出一种基于故障链路组分离的资源配置方法,在构建保护通道时,根据所形成的资源链路组进行保护资源的配置管理,将主路由、备用路由的资源进行标记,采用分组配置方式提升备用通道的利用效率,从而实现主用工作路由资源的节省.最后,针对不同的网络仿真场景对所提出的方法进行验证,并对性能指标进行了理论分析.     

Models for optimal survivable routing with a minimum number of hops: comparing disaggregated with aggregated models

Given an undirected network with link capacities and a set of commodities with known demands, this paper addresses the problem of determining D (with D=2, 3, 4) hop‐constrained node disjoint paths for each commodity while minimizing the average or the maximum number of hops. These paths are defined according to two survivability mechanisms ? Path Diversity and Path Protection, the latter guaranteeing total demand protection in the event of n failures (with n<D). We study these problems in the context of a traffic engineering task over pre‐dimensioned networks where the real traffic demands are inevitably different from the estimated traffic demands that were assumed in the network dimensioning task. We present two classes of ILP models, disaggregated and aggregated, for both problems, study the relationship between their linear programming relaxations and compare their effectiveness through a set of computational experiments. The results show that, in practice, there is no gain in using the disaggregated models.     

多协议标签交换流量工程隧道实时监测方法——MTRM

针对现有工作无法实时动态监测多协议标签交换(MPLS)流量工程(TE)隧道状态变化的问题,提出了一种MPLS TE隧道实时监测方法--MTRM。在网络中植入被动采集探针以采集OSPF-TE信令,以此为基础构建网络模型,使用隧道路径实时监测算法进行实时的隧道路径计算,最终实现动态监测。仿真实验在15个节点的MPLS网络中进行。结果表明,MTRM能够在5s之内监测到隧道变化,准确率超过90%。这种MPLS TE隧道实时监测方法,大大降低了MPLS网络管理和流量工程实施的难度,具有广阔的应用前景。     

基于SRLG不相关陷阱避免算法的研究

在光网络通信中,计算路由常常会出现共享风险链路组(SRLG)分离和"陷阱"问题。针对这种现象,提出了一种基于SRLG不相关的陷阱避免算法,并采用阿尔卡特朗讯公司的光网络规划工具1356NT进行验证。实验结果表明,与传统路由算法相比,该算法不但缩短了恢复时间,还有效提高了网络连接的可靠性和网络资源的利用率。     

An efficient critical protection scheme for intra-domain routing using link characteristics

In recent years, there are substantial demands to reduce packet loss on the Internet. Among the proposed schemes, finding backup paths in advance is considered to be an effective method to reduce the reaction time. Very commonly, a backup path is chosen to be the most disjoint path from the primary path, or on the network level, a backup path is computed for each link (e.g., IPFRR). The validity of this straightforward choice is based on two things. The first thing is all the links may have the equal likelihood to fail; the second thing is, facing the high protection requirement today, it just looks weird to have links not protected or to share links between the primary and backup paths. Nevertheless, many studies have confirmed that the individual vulnerability of the links on the Internet is far from being equal. In addition, we have observed that full protection schemes (In this paper, full protection schemes means schemes (1) in which backup path is a most disjoint path from the primary path; or (2) which compute backup path for each link.) may introduce high cost (e.g., computation).In this paper, we argue that such approaches may not be cost-efficient and therefore propose a novel critical protection scheme based on link failure characteristics. Firstly, we analyze the link failure characteristics based on real world traces of CERNET2 (China Education and Research NETwork 2). The analysis results clearly show that the failure probabilities of the links in CERNET2 backbone are heavy-tailed, i.e., a small set of links causing most of the failures. Based on this observation, we find out two key parameters which strongly impact link criticality and propose a critical protection scheme for both single link failure situation and multi-link failure situation. We carefully analyze the implementation details and overhead for backup path schemes of the Internet today; the problem is formulated as an optimization problem to guarantee the routing performance and minimize the backup cost. This cost is special as it involves computational overhead. Based on this, we propose a novel Critical Protection Algorithm which is fast itself for both the single link failure and the multi-link failure versions. A comprehensive set of evaluations with randomly generated topologies, real world topologies and the real traces from CERNET2, shows that our scheme gains significant achievement over full protection in both single link failure situation and multi-link failure situation. It costs only about 30–60% of the full protection cost when the network relative availability increment is 90% of the full protection scheme.     

Redundant multicast routing in multilayer networks with shared risk resource groups: Complexity,models and algorithms

This paper presents a redundant multicast routing problem in multilayer networks that arises from large-scale distribution of realtime multicast data (e.g., Internet TV, videocasting, online games, stock quotes). Since these multicast services commonly operate in multilayer networks, the communications paths need to be robust against a single router or link failure as well as multiple such failures due to shared risk link groups (SRLGs). The main challenge of this multicast is to ensure the service availability and reliability using a path protection scheme, which is to find a redundant path that is SRLG-disjoint (diverse) from each working path. The objective of this problem is, therefore, to find two redundant multicast trees, each from one of the two redundant sources to every destination, at a minimum total communication cost whereas two paths from the two sources to every destination are guaranteed to be SRLG-diverse (i.e., links in the same risk group are disjoint). In this paper, we present two new mathematical programming models, edge-based and path-based, for the redundant multicast routing problem with SRLG-diverse constraints. Because the number of paths in path-based model grows exponentially with the network size, it is impossible to enumerate all possible paths in real life networks. We develop three approaches (probabilistic, non-dominated and nearly non-dominated) to generate potentially good paths that may be included in the path-based model. This study is motivated by emerging applications of internet-protocol TV service, and we evaluate the proposed approaches using real life network topologies. Our empirical results suggest that both models perform very well, and the nearly non-dominated path approach outperforms all other path generation approaches.     

Two-link failure protection in WDM mesh networks with p-cycles

In WDM networks, it is important to protect connections against link failures due to the high bandwidth provided by a fiber link. Although many p-cycle based schemes have been proposed for single-link failure protection, protection against two-link failures have not received much attention. In this paper, we propose p-cycle based protection schemes for two-link failures. We formulate an ILP model for the p-cycle design problem for static traffic. We also propose two protection schemes for dynamic traffic, namely SPPP (Shortest Path Pair Protection) and SFPP (Short Full Path Protection). Simulation results show that SFPP is more capacity efficient than SPPP under incremental traffic. Under dynamic traffic, SPPP has lower blocking than SFPP when the traffic load is low and has higher blocking than SFPP when the traffic load is high.