MPLS VPN动态路径管理算法*

针对标签交换路径的设计与维护问题,提出基于故障恢复模型的MPLS VPN动态路径管理算法。该算法在备份路径设计准则的基础上,测试全连通MPLS VPN中备份路径可用性的条件,利用快速备份路径构造算法,在多故障发生时,自动地构造满足客户故障恢复需求的VPN路径,从而使VPN业务受干扰程度最小。     

MPLS快速重路由多故障恢复算法的研究

传统的MPLS快速重路由技术在面对网络多故障的情况时有许多不足之处,为了更好的解决问题,提出一种新的MPLS快速重路由多故障恢复算法.算法采用Detour路径保护方式,对有不同备份路径经过的链路上的预留带宽资源进行共享管理,并为工作路径建立主、从备份路径.仿真实验结果显示,该算法能够有效减少备份路径上预留带宽资源消耗,对出现多故障的网络进行快速恢复.     

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.     

MPLS故障恢复机制及其仿真研究

对MPLS故障恢复机制进行了研究,分析了各种恢复机制在恢复时机、恢复拓扑、恢复效率、备份路径资源耗费等方面的性能.对NS2进行扩展,设计和实现了支持MPLS故障恢复机制的仿真组件,包括故障检测、故障通告和故障切换功能.故障恢复仿真组件提供了基本MPLS恢复能力,支持多种故障恢复机制,为深入研究MPLS故障恢复方法、优化MPLS恢复算法提供了试验平台.     

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

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

Backup path set selection in ad hoc wireless network using link expiration time

Topological changes in mobile ad hoc networks frequently render routing paths unusable. Such recurrent path failures have detrimental effects on quality of service. A suitable technique for eliminating this problem is to use multiple backup paths between the source and the destination in the network. Most of the proposed on-demand routing protocols however, build and rely on single route for each data session. Whenever there is a link disconnection on the active route, the routing protocol must perform a path recovery process. This paper proposes an effective and efficient protocol for backup and disjoint path set in an ad hoc wireless network. This protocol converges into a highly reliable path set very fast with no message exchange overhead. The paths selection according to this algorithm is beneficial for mobile ad hoc networks, since it produces a set of backup paths with much higher reliability. Simulations are conducted to evaluate the performance of our algorithm in terms of route numbers in the path set and its reliability. In order to acquire link reliability estimates, we use link expiration time (LET) between each two nodes.In another experiment, we save the LET of entire links in the ad hoc network during a specific time period, then use them as a data base for predicting the probability of proper operation of links.Links reliability obtains from LET. Prediction is done by using a multi-layer perceptron (MLP) network which is trained with error back-propagation error algorithm. Experimental results show that the MLP net can be a good choice to predict the reliability of the links between the mobile nodes with more accuracy.     

A subtree-based approach to failure detection and protection for multicast in SDN

Software-defined networking (SDN) has received tremendous attention from both industry and academia. The centralized control plane in SDN has a global view of the network and can be used to provide more effective solutions for complex problems, such as traffic engineering. This study is motivated by recent advancement in SDN and increasing popularity of multicasting applications. We propose a technique to increase the resiliency of multicasting in SDN based on the subtree protection mechanism. Multicasting is a group communication technology, which uses the network infrastructure efficiently by sending the data only once from one or multiple sources to a group of receivers that share a common path. Multicasting applications, e.g., live video streaming and video conferencing, become popular, but they are delay-sensitive applications. Failures in an ongoing multicast session can cause packet losses and delay, which can significantly affect quality of service (QoS). In this study, we adapt a subtree-based technique to protect a multicast tree constructed for OpenFlow switches in SDN. The proposed algorithm can detect link or node failures from a multicast tree and then determines which part of the multicast tree requires changes in the flow table to recover from the failure. With a centralized controller in SDN, the backup paths can be created much more effectively in comparison to the signaling approach used in traditional multiprotocol label switching (MPLS) networks for backup paths, which makes the subtree-based protection mechanism feasible. We also implement a prototype of the algorithm in the POX controller and measure its performance by emulating failures in different tree topologies in Mininet.     

基于资源共享的MPLS组播网络中的路径恢复

MPLS组播网络能快速有效地传输数据，其中的路径恢复机制确保提供持续的网络服务。该文提出了一种基于资源共享的MPLS组播网络中的路径恢复方案，该方案在每条链路的入口处保存一个链路资源使用数据库，使用基于共享资源且提供带宽保证的备份路径计算方法来预先建立备份路径，能优化网络资源的利用并减少切换时延。     

满足指定节点约束的路由算法

在MPLS或GMPLS网络中,路由算法常常需考虑节点约束条件(即用户可能指定一条端到端路径所必须经过的一些中途节点)。对链路代价值为整数的有向无回路网络,文章提出了一种伪多项式时间算法,用于计算满足指定节点约束的最小代价路径。对一般有向网络,文中给出了一种计算时间及空间上限可调的启发式算法。仿真实验结果表明,所给的启发式算法在网络规模变大时明显优于已知的算法。     

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.     

FDR: fault detection and recovery scheme for wireless sensor networks using virtual grid

Due to autonomous operation and constrained resources, nodes of a wireless sensor network are susceptible to failures. Due to multiple node failures, network topology may change or partition into many disconnected segments causing data/query path breakage. Early detection and recovery of faults is desirable in most scenarios. Also, due to limited battery life of a node, the solution must consume minimum possible energy for prolonged network operation. Hence in this paper, we propose a Fault Detection and Recovery scheme which is an energy efficient fault detection and recovery strategy that achieves minimum data loss by efficiently replacing faulty node on the present route or by finding full or partial alternate paths. Topology is managed by constructing a virtual grid over the entire network which helps in managing dynamically changing network topology easily and makes failure detection and recovery effective. It also helps to create energy efficient path between a source and a sink by finding shortest possible path. Further, nodes’ cooperation is exploited to create certain zones on the data/query path which provides alternate nodes or possible alternate paths if required on some node failures. Thus, scheme achieves fault tolerance and at the same time achieves energy efficiency by always selecting shortest path for data delivery between source and sink. Analytical and simulation study reveals the significant improvement in terms of fault detection and energy conservation over existing similar schemes.     

基于拥塞及内存感知的SD-WAN故障恢复

在软件定义广域网(SD-WAN)中, 链路故障会导致大量丢包, 严重时会引起部分网络瘫痪. 现有的流量工程方法通过在数据平面提前安装备份路径能够加快故障恢复过程, 但在资源受限的情况下难以适应各种网络故障情况, 从而使恢复后的网络性能下降. 为了保证网络在故障恢复之后的性能并减少备份资源的消耗, 本文提出一种基于拥塞及内存感知的主动式故障恢复方案(CAMA), 不仅能够将受影响数据流进行快速重定向, 还能实现负载均衡避免恢复后潜在的链路拥塞. 实验结果表明, 与已有方案相比, CAMA能有效利用备份资源, 在负载均衡上有较好的性能, 且仅需少量备份规则即可覆盖所有单链路故障情况.     

An improved scheme for self-healing in ATM networks

Broadband networks based on ATM technology can carry a large volume of data and can support diverse services like audio, video, and data uniformly. The reliability and availability levels provided by such networks should be very high. Self-healing is an elegant concept in this direction to provide highly reliable networks. A self-healing network can detect failures such as link/node failures and reroute the failed connections automatically using distributed control mechanisms. In this paper, we consider link and node failures including the VP terminating nodes unlike Kawamura and Tokizawa (Self-healing in ATM networks based on virtual path concept, IEEE Journal on Selected Areas in Communications 12 (1) (1994) 120–127). We present here an improved scheme for self-healing in ATM networks based on the concept of backup VPs. The problems we address are: (i) self-healing scheme; and (ii) backup VP routing. Two issues are addressed in the self-healing scheme: (i) backup VP activation protocol; and (ii) dynamic backup VP routing. We propose a new backup VP activation protocol which uses a VC packing strategy which allows the fast and prioritized restoration of critical VCs that were carried by failed VPs. We also propose a distributed dynamic backup VP routing algorithm which reduces the resource contention that may occur when multiple source–destination pairs contend for the routes simultaneously. The objective of the backup VP routing problem is to find a backup VP for each of the working VPs so that the cost of providing the backup is minimized. We propose a heuristic based solution for the backup VP routing problem using the concept of minimum cost shortest paths. We conducted simulation experiments to evaluate the performance of the proposed schemes. The results show that the proposed schemes are effective. Comparison of the results with those of the earlier schemes (R. Kawamura, I. Tokizawa, Self-healing in ATM networks based on virtual path concept, IEEE Journal on Selected Areas in Communications 12 (1) (1994) 120–127; C.J. Hou, Design of a fast restoration mechanism for virtual path-based ATM networks, Proceedings of IEEE INFOCOM’97, Kobe, Japan, April 1997) shows that the proposed schemes perform better.     

基于基本回路的MPLS网络重路由故障恢复机制

研究MPLS网络中的重路由故障恢复机制,提出一种新的计算备用路径的方法,将备用路径的计算分为预处理和在线计算2个过程,给出一种基于基本回路的重路由故障恢复机制(FC-R)。仿真分析表明,FC-R恢复时间较短,可以对抗节点故障或链路故障,大大缩短在线计算时间,减轻节点负担,能够得到性能较优的备用路径,进一步节省网络资源。     

一种基于分段共享的预测式错误恢复机制

In MPLS/GMPLS networks, a range of restoration schemes will be required to support trade-offs between service interruption time and network resource utilization. Although, the tradition protectionbased and reservation-based recovery schemes exist some merits,but they can not provide a good trade-offs. In this paper,we propose a Prognostic Segment-based Sharing Recovery Mechanism(PSSRM)for restoration of connection over shared bandwidth in a fully distributed GMPLS architecture. PSSRM can use QoS constraints such as bandwidth and recovery time to obtain the good trade-offs of recovery time and resource efficiency.     

一种基于多路径的传感器网络安全数据传输机制

本文针对传感器网络提出了一种基于多路径的安全数据传输方案,通过在多条路径上分发数据,达到增强机密性和鲁棒性的目的。针对数据机密性,设计基于异或计算的编码方式,使得攻击者解析任何数据片段的难度等同于攻占所有的K条路径。针对传输的鲁棒性,设计了数据分发算法以及备份与校验相结合的容错模式,实现了容忍多条路径失效的数据传输,并且具有适度的数据冗余、理想的路径利用率以及快速的数据恢复能力。     

Joint coverage and link utilization for fast IP local protection

To mitigate the impact of failures, many IP Fast Local Recovery (IPFLR) schemes have been proposed to reroute traffic in the events of failures. However, the existing IPFLR schemes either aimed to find the alternate backup routes to protect failures, or focused on balancing the traffic load routed on the backup routes. Furthermore, in Internet, flows are often managed by shortest path routing, and therefore purely determining the backup routing paths is not sufficient in protecting the error-prone networks. In this paper, we propose a Simulated Annealing based Load balancing and Protection (SALP) scheme to determine link weights for balancing link utilization in the non-failure state and simultaneously construct backup routing tables for protecting any single link failure in IP networks. In our proposed scheme, the two most significant issues, (1) load balancing and (2) coverage, are jointly considered to recover the network operation from single link failures. In the proposed scheme, upon a failure, only the nodes adjacent to a failure are activated to divert affected traffic to backup paths without disturbing regular traffic. Numerical results delineate that the proposed scheme achieves high coverage rate and load balancing at the expense of slightly increasing the entries of backup routing table.     

TRIDENT: An automated approach to traffic engineering in IP/MPLS over ASON/GMPLS networks

This paper addresses the problem of designing a capacity management/traffic engineering procedure for an IP/MPLS over ASON/GMPLS scenario. We suggest TRIDENT, a procedure whose main goal is to dynamically provide the bandwidth required to transport through an ASON the MPLS–LSPs already established at the IP/MPLS client network. TRIDENT relies on automatically triggering demands to set up or tear down the ASON switched connections, and it is based on monitoring and predicting the offered traffic at the interfaces between the IP (MPLS) and the ASON layers. TRIDENT allows providing automatic Bandwidth on Demand (BoD) and it counteracts potential congestion at the client network. Its merits are evaluated by simulation results and it has also been experimentally tested.     

GMPLS技术研究

GMPLS是MPLS的扩展,旨在解决多种组网技术的流量工程问题。为了探讨当前应用GMPLS时存在的问题及其解决方案,分析了GMPLS架构及研究现状,通过对MPLS协议应用于光纤网时存在的问题的分析,得出了GMPLS协议MPLS协议的改进点。指出了GMPLS中亟待解决的问题并提出了自己的见解。     

A New Fast Backup Method for Bidirectional Multicast Traffic in MPLS Networks: Control Plane Procedures and Evaluation by Simulations

Bidirectional multicast mechanisms are used to support multi-point to multi-point (MP2MP) traffic such as video-conferencing. These mechanisms are deployed today in multi-protocol label switching (MPLS) networks using the connectionless mode in which traffic engineering (TE) features such as bandwidth reservation and fast reroute in case of link and/or node failure are not defined. Indeed, TE procedures are defined in MPLS for unicast and multicast point-to-multipoint (P2MP) traffic only. Hence, MP2MP traffic that requires TE procedures is carried out using a full mesh of P2P or P2MP paths. Similarly, a full mesh of P2P and P2MP backup paths should be predefined in order to fast reroute traffic in case of a node failure. This leads to a major scalability problem since MPLS TE paths incur heavy overhead burden on MPLS nodes (CPU and memory). In this paper, we emphasize on fast reroute procedures using MP2MP TE paths. In particular, we define the control plane procedures that should be established. In addition, we present a simulation study that demonstrates the scalability amelioration when using MP2MP TE paths for fast rerouting instead of full mesh P2P and/or P2MP paths.