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

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

Loop-free alternates and not-via addresses: A proper combination for IP fast reroute?

The IETF currently discusses fast reroute mechanisms for IP networks (IP FRR). IP FRR accelerates the recovery in case of network element failures and avoids micro-loops during re-convergence. Several mechanisms are proposed. Loop-free alternates (LFAs) are simple but cannot cover all single link and node failures. Not-via addresses can protect against these failures but are more complex, in particular, they use tunneling techniques to deviate backup traffic. In the IETF it has been proposed to combine both mechanisms to merge their advantages: simplicity and full failure coverage.This work analyzes LFAs and classifies them according to their abilities. We qualitatively compare LFAs and not-via addresses and develop a concept for their combined application to achieve 100% single failure coverage, while using simple LFAs wherever possible. The applicability of existing LFAs depends on the resilience requirements of the network. We study the backup path length and the link utilization for both IP FRR methods and quantify the decapsulation load and the increase of the routing table size caused by not-via addresses. We conclude that the combined usage of both methods has no advantage compared to the application of not-via addresses only.     

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.     

Dynamic load balancing in IP-over-WDM optical burst switching networks

In this paper, we consider the problem of dynamic load balancing in wavelength division multiplexing (WDM)-based optical burst switching (OBS) networks. We propose a load balancing scheme based on adaptive alternate routing aimed at reducing burst loss. The key idea of adaptive alternate routing is to reduce network congestion by adaptively distributing the load between two pre-determined link-disjoint alternative paths based on the measurement of the impact of traffic load on each of them. We develop two alternative-path selection schemes to select link-disjoint alternative paths to be used by adaptive alternate routing. The path selection schemes differ in the way the cost of a path is defined and in the assumption made about the knowledge of the traffic demands. Through extensive simulation experiments for different traffic scenarios, we show that the proposed dynamic load balancing algorithm outperforms the shortest path routing and static alternate routing algorithms.     

LEO卫星网络中的一种分布式路由算法

在LEO卫星网络中，由于卫星高速运动导致的网络拓扑变化和不同卫星覆盖城内流量的非规整性给设计其特殊路由算法带来很大挑战。结合卫星网络的固有特点，本文提出一种基于路径信息压缩的分布式路由算法CPDR（Compressed Path Information based Distributed Routing）。该算法使用分布式分层链路状态收集策略和简洁的路径信息编码机制，能够在不引入额外信令开销基础之上提供多路径路由能力，实现卫星网路中的流量负载平衡、优化网络带宽应用、提高星际链路利用率。     

Comparison of recovery schemes to maximize restorable throughput in multicast networks

Multicast networks have many applications especially in real-time content delivery systems. For high-quality services, users do not expect to witness any interruption; thus, network link failure has to be handled gracefully. In unicast networks there are many approaches for dealing with link failures using backup paths. Recently, Cohen and Nakibly categorized these methods, provided linear programming formulations for optimizing network throughput under the assumption that the paths are splitable, and compared them experimentally. In this work, we take their approach and apply to the multicast failure recovery problem. We propose backup bandwidth allocation algorithms based on linear programs to maximize the throughput, and perform an experimental study on the performance of recovery schemes. We study many recovery schemes in multicast networks and propose a new recovery scheme that performs better than all other recovery scheme except the one that recomputed the whole multicast tree from scratch for each link failure.     

Agent-based load balancing routing for LEO satellite networks

To ensure an intelligent engineering of traffic over entire satellite networks, a distributed routing scheme for low-earth orbit (LEO) satellite networks, agent-based load balancing routing (ALBR), is presented. Two kinds of agents are used. Mobile agents migrate autonomously to explore the path connecting source and destination, to gather inter-satellite link (ISL) cost, identifier and latitude of visited satellites. Meanwhile, stationary agents employ exponential forgetting function to estimate ISL queueing delay, calculate ISL cost using the sum of propagation and queueing delays; evaluate path cost considering satellite geographical position as well as ISL cost, finally update routing items. Through simulations on a Courier-like system, the proposed scheme is shown to achieve better load balancing, and can especially decrease packet loss ratio efficiently, guarantee better throughput and end-to-end delay bound in case of high traffic load. Furthermore, results from the implementation complexity analysis demonstrate that with the aid of agent technology, ALBR has lower on-board computation, storage, signaling requirements than other on-board routing schemes.     

Multicast protection scheme in survivable WDM optical networks

The protection design is a key issue in survivable wavelength division multiplexing (WDM) optical networks. Most researches focused on protecting unicast traffic against the failure of a single network component such as a link or a node. In this paper, we investigate the protection scheme for multicast traffic in meshed WDM optical networks under dual-link failure consideration, and propose a novel protection algorithm called shared segment protection with reprovisioning (SSPR). Through dynamically adjusting link-cost according to the current network state, SSPR establishes a primary light-tree and corresponding link-disjoint backup segments for each multicast connection request. A backup segment can efficiently share wavelength capacity of its working tree or the common resource of other backup segments. Capacity reprovisioning establishes new segments for the vulnerable connections after a link failure and tolerates following link failures. The simulation results show that SSPR not only can make good use of wavelength resources and protect multicast sessions against any single-link failure, but also can greatly improve the traffic restorability in the event of dual-link breakdown.     

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

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

Dynamic Path Management with Resilience Constraints under Multiple Link Failures in MPLS/GMPLS Networks

Most previous research on MPLS/GMPLS recovery management has focused on efficient routing or signaling methods from single failures. However, multiple simultaneous failures may occur in large-scale complex virtual paths of MPLS/GMPLS networks. In this paper, we present a dynamic MPLS/GMPLS path management strategy in which the path recovery mechanism can rapidly find an optimal backup path which satisfies the resilience constraints under multiple link failure occurrences. We derived the conditions to test the existence of resilience-guaranteed backup path, and developed a decomposition theorem and backup path construction algorithm for the fast restoration of resilience-guaranteed backup paths, for the primary path with an arbitrary configuration. Finally, simulation results are presented to evaluate the performance of the proposed approach.     

MF-DLB: Multimetric forwarding and directed acyclic graph-based load balancing for geographic routing in FANETs

Flying ad hoc network (FANET) comprising unmanned aerial vehicles (UAVs) emerges as a promising solution for numerous military and civil applications. Transferring data collected from the environment to the ground station (GS) is a primary concern for meeting the communication demands of most of these applications. However, the highly mobile UAVs with limited communication range, resulting in frequent topology change and intermittent connectivity, make data routing challenging. In such scenarios, geographic routing is a viable solution due to its scalability and robustness. However, the basic forwarding mechanism of geographic routing favors the neighboring UAV nearest to the destination, impacted substantially by link failures and routing holes in a dynamic environment. Additionally, routing decisions ignoring the current load over UAVs contribute to performance degradation due to the high concentration of data traffic near the GS. Thus, to address these issues, a geographic routing protocol named MF-DLB comprising multimetric forwarding (MF) and a directed acyclic graph-based load balancing (DLB) scheme is proposed to enhance packet forwarding in FANETs. MF takes account of multiple metrics related to connectivity, geographic progress, link lifetime, and residual energy to select the next hop with a stable communication link while effectively bypassing the routing holes. The second scheme, DLB, focuses on proactively maintaining routing paths near GS for load distribution among underutilized nodes to address the congestion problem. Simulations performed in network simulator ns-3 confirm the outperformance of MF-DLB over other related routing schemes in terms of different performance metrics.     

Constructing disjoint paths for failure recovery and multipath routing

Applications such as Voice over IP and video streaming require continuous network service, requiring fast failure recovery mechanisms. Proactive failure recovery schemes have been recently proposed to improve network performance during the failure transients. These proactive failure recovery schemes need extra infrastructural support in the form of routing table entries, extra addresses etc. In this paper, we study if the extra infrastructure support can be exploited to build disjoint paths in those frameworks, while keeping the lengths of the recovery paths close to those of the primary paths. Our evaluations show that it is possible to extend the proactive failure recovery schemes to provide support for nearly-disjoint paths which can be employed in multipath routing for load balancing and QoS.     

On the optimality of field-line routing in massively dense wireless multi-hop networks

We consider the load balancing problem in large wireless multi-hop networks by applying the continuum approximation. The task is to find routes, geometric curves, such that the maximal traffic load in the network is minimized. In finite fixed networks, multi-path routes generally yield a lower congestion and thus allow higher throughput. In contrast, we show that in dense wireless multi-hop networks, the optimal load balancing can be achieved by a destination based single-path routing referred to as field-line routing. This is because any routing can be transformed to the corresponding field-line routing with the same or better performance, by using as paths, the field lines of the so-called destination flow associated with the original routing. The concepts are illustrated with two examples. In the case of a unit disk with unit traffic, the maximal load of 0.389 of a multi-path routing system is reduced to 0.343 by using the field-line routing. Similar improvements are also demonstrated for the unit square.     

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.     

Threshold configuration and routing optimization for PCN-based resilient admission control

Pre-Congestion Notification (PCN) in IP networks uses packet metering and marking within a PCN domain to notify its egress nodes whether link-specific admissible or supportable rate thresholds have been exceeded by high-priority traffic. Based on this information simple admission control and flow termination is implemented. The latter is a new flow control function and useful in case of overload through high priority traffic which can occur in spite of admission control, e.g., when traffic is rerouted in failure cases. Resilient admission control admits only so much traffic that admitted traffic can be rerouted without causing congestion on backup paths in case of a likely failures, e.g., single link failures.We propose algorithms to configure the link-specific PCN rate thresholds such that resources are utilized efficiently and fairly by competing traffic aggregates while meeting resilience constraints. This is done for the single and dual marking PCN architecture whereby the single marking case is more demanding since it requires that the supportable rate is a fixed multiple of the admissible rate on all links within a single PCN domain. Furthermore, we derive objective functions to optimize the underlying routing system for both cases. Our performance results for various network types show that the dual marking PCN architecture leads to significantly better resource efficiency than the single marking PCN architecture.     

一种适合低连接度拓扑的集中式保护路由机制

在集中式路由中,由路由控制平台统一计算路由表进行分发,路由器不再具备决策能力,需要预先构建一种具备保护功能的路由机制,使得路由器的下游路径失效后都有立即可用的备份路径,确保报文的最小损失,已有的集中式保护路由机制在低连接度拓扑上保护效果不佳.为了解决该问题,提出了一种适合低连接度拓扑的集中式域内保护路由机制,允许失效处的相邻节点在没有可用路径时将报文返回至其上游节点,由有可用备份路径的上游节点通过备份路径发送,确保单个节点或连接失效后报文的最小损失.证明了为给定拓扑构建最优保护路由的问题是一个NP-hard问题,并且提出了解决该问题的三阶段启发式算法.在各种类型的拓扑中验证了启发式算法的性能.实验结果表明,该方法优于已有保护路由方案.     

Development and research of improved model of multipath adaptive routing in computer networks with load balancing

In modern computer networks, loading and bandwidth of communication links are optimized for providing high-quality service of network traffic, new services and technologies. As a rule, for this task the protocols of dynamic routing based on Dijkstra’s algorithm are used. Protocols of multipath routing for ensuring reliability and accuracy of the provided information allow to divide critical traffic and to execute load balancing along several routes at the same time. The purpose of the work is development and research of the improved multipath adaptive routing model in computer networks with load balancing. In this work, we focused on indicator of jitter optimization between the paved paths and a deviation value of reserve routes from an optimal route. Comparison and estimation of the offered algorithm with some existing approaches, and also modeling and analysis on various topologies of computer networks have been carried out.     

基于决定性能量比例的多径传输技术

多径传输有两种模式：一种是主／备模式，只有在主路径失效之后，其它路径才可以传输数据；另一种是复制模式，数据同时从所有的路径传输。在传感器网络中，这两种模式都没有很好地结合能量节约和负载均衡。本文提出了一种传感器网络中能量敏感负载均衡的多径传榆策略，数据基于决定性能量比例（DER）从源到目标沿着多径传输。这种技术不必定期计算DER，容易实现而且开销较小。本文还提出带有过载避免机制的DER技术（DEROA），用束减少某些关键节点的过多通信量。仿真结果证明，DER可以达到有效传输的目的。     

Lightweight Boolean Network Tomography Based on Partition of Managed Networks

Boolean network tomography is a promising technique to achieve fault management in networks where the existing IP-based troubleshooting mechanism cannot be used. Aiming to apply Boolean network tomography to fault management, a variety of heuristic methods for configuring monitoring trails and paths have been proposed to localize link failures in managed networks. However, these existing heuristic methods must be executed in a centralized server that administers the entire managed network and the methods present scalability problems when applied to large-scale managed networks. Thus, this paper proposes a novel scheme for achieving lightweight Boolean network tomography in a decentralized manner. The proposed scheme partitions the managed network into multiple management areas and localizes link failures independently within each area. This paper also proposes a heuristic network partition method with the aim of efficiently implementing the proposed scheme. The effectiveness of the proposed scheme is verified using typical fault management scenarios where all single-link failures and all dual-link failures are localized by the least number of monitoring paths on predetermined routes. Simulation results show that the proposed scheme can greatly reduce the computational load on the fault management server when Boolean network tomography is deployed in large-scale managed networks. Furthermore, the degradation of optimality in the proposed scheme can be mitigated in comparison with a centralized scheme that utilizes heuristics to reduce the computational load on the centralized server.     

基于逐跳转发方式的单故障路由保护方法

业界提出利用LFA（loop free alternates）方案来应对网络中频繁出现的故障,然而LFA并不能保护网络中所有可能出现的单故障情形。针对上述问题,提出了一种基于逐跳转发方式的单故障路由保护算法SFRPA（single failure routing protection algorithm based on hop by hop forwarding）。SFRPA首先提出了三个无环路备份下一跳选取规则,然后制定了优先级队列的操作规则,最后利用优先级队列和无环路备份下一跳选取规则为所有源目的节点对计算出一个最优的备份下一跳。该算法具有支持逐跳转发、支持增量部署、保护网络中所有可能的单故障情形三个特征。实验结果表明,与经典的路由保护方案LFA、DMPA、TBFH和IAC相比较,SFRPA不仅可以应对网络中所有可能的单故障情形,并且具有较小的路径拉伸度。