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.     

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.     

基于关键网络状态的域内路由可用性研究

业界通常采用路由保护方案来提高域内路由可用性.然而已有的路由保护方案存在下面两个方面的问题:a)没有考虑网络中链路的失效概率,同等对待网络中所有的链路,事实上在互联网中,不同链路的失效概率是不同的,因此应该在路由保护方案中考虑链路的失效概率;b)将保护链路的数量作为设计目标,事实上方面某些链路出错的概率非常低,保护这些链路反而会增加开销,而另一方面某些链路出错的概率非常高,需要重点保护这些链路.因此应该将路由可用性作为路由保护方案的设计目标.针对上述两个问题,提出了一种基于关键网络状态的域内路由保护方案(RPBCNS),该算法首先通过链路失效概率计算出所有的关键网络状态,然后在每种关键网络状态下计算节点对之间相应的路径,保证节点对之间路径的多样性,从而使得尽可能多的节点对满足路由可用性需求.仿真实验将RPBCNS算法与主流算法ECMP、DC、path splicing分别在三个真实网络中进行对比,在网络可用性和节点对可用性满足率上RPBCNS的性能明显优于其他三种算法.仿真结果表明,RP-BCNS不仅具有较高的网络可用性,并且能够使得尽可能多的节点对满足路由可用性目标,更符合实时应用的实际需求.     

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.     

Efficient path protection in bi-directional WDM systems

Bi-directional WDM transmission is a technique that allows data to be transmitted simultaneously in both directions of a fiber, with different sets of wavelength channels for each direction. Compared with unidirectional WDM systems, it not only saves the cost of deploying extra fibers, but also allows more flexible bandwidth provisioning. To exploit this flexibility, we investigate path protection schemes for bi-directional WDM transmission systems in this paper. With path protection, a call is accepted if and only if an active data path together with a disjointed backup path can be found in the network. With bi-directional WDM, backup resource sharing in both directions of a fiber is possible. Based on a set of judiciously designed link cost functions, two original path protection schemes are proposed in this paper, BiPro and BiProLP. BiProLP aims at further economizing the hardware cost incurred by BiPro. In contrast to the traditional unidirectional schemes, we show that both BiPro and BiProLP can yield noticeably lower call blocking probability, higher system capacity and shorter active/backup path length.     

节点与链路协同映射的生存性虚拟光网络映射算法

针对弹性光网络中单链路故障问题,提出一种基于匈牙利算法求解链路映射方案的节点与链路协同映射保护算法CMST-HA。将虚拟网络请求的节点与链路分别划分为主动类型与被动类型,把主动类型节点映射至邻接链路频谱资源丰富且邻接节点计算资源充足的物理节点上,在主动链路时使用匈牙利算法求解出最小映射开销方案并完成映射,确定被动节点的映射位置,利用KSP算法为被动链路选择映射路径,在此基础上为虚拟网络请求的最小生成树链路提供备份路径。仿真结果表明,与RVNM、CMST算法相比,CMST-HA算法不仅能够降低虚拟网络请求阻塞率,而且可增加物理网络收益。     

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.     

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

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

基于InfiniBand的多链路mesh/torus大规模并行系统互连网络

在大规模并行系统中,系统级互连网络的设计至关重要.InfiniBand作为一种高性能交换式网络被广泛应用于大规模并行处理系统中.mesh/torus拓扑结构相较于目前普遍应用于InfiniBand网络的胖树拓扑结构拥有更好的性能与可扩展性.尽管如此,研究发现,用传统的mesh/torus拓扑结构构建InfiniBand互连网络存在诸多问题.分析了传统网络拓扑结构的缺陷,并提出了一种基于InfiniBand的多链路mesh/torus互连网络.这种改进型的拓扑结构通过充分利用交换机间的多链路可以获得比传统mesh/torus网络更高的带宽.另外,同时给出了与该网络拓扑结构相配套的高效路由算法.最后,通过网络仿真技术对提出的算法进行了评估,实验结果显示提出的路由算法相较于其他路由算法拥有更好的性能与可扩展性.     

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.     

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.     

Protecting multicast services in optical internet backbones

Many applications in the future Internet will use the multicasting service mode. Since many of these applications will generate large amounts of traffic, and since users expect a high level of service availability, it is important to provision multicasting sessions in the future Internet while also providing protection for multicast sessions against network component failures. In this paper we address the multicast survivability problem of using minimum resources to provision a multicast session and its protection paths (trees) against any single-link failure. We propose a new, and a resource efficient, protection scheme, namely, Segment-based Protection Tree (SPT). In SPT scheme, a given multicast session is first provisioned as a primary multicast tree, and then each segment on the primary tree is protected by a multicast tree instead of a path, as in most existing approaches. We also analyze the recovery performance of SPT and design a reconfiguration calculation algorithm to compute the average number of reconfigurations upon any link failure. By extending SPT to address dynamic traffic scenarios, we also propose two heuristic algorithms, Cost-based SPT (CB_SPT) and Wavelength-based SPT (WB_SPT). We study the performance of the SPT scheme in different traffic scenarios. The numerical results show that SPT outperforms the best existing approaches, optimal path-pair-based shared disjoint paths (OPP_SDPs). SPT uses less than 10% extra resources to provision a survivable multicast session over the optimal solution and up to 4% lower than existing approaches under various traffic scenarios and has an average number of reconfigurations 10–86% less than the best cost efficient approach. Moreover, in dynamic traffic cases, both CB_SPT and WB_SPT achieves overall blocking probability with 20% lower than OPP_SDP in most network scenarios.     

Heuristic algorithms for designing self-repairing protection trees in mesh networks

Protection trees have been used in the past for restoring multicast and unicast traffic in networks in various failure scenarios. In this paper we focus on shared self-repairing trees for link protection in unicast mesh networks. Shared protection trees have been proposed as a relatively simple approach that is easy to reconfigure and could provide sub-second restoration times with sub-optimal redundancy requirement. The self-repairing nature of this class of protection trees may make them an attractive option for cases where dynamic changes in network topology or demand may occur. In this paper, we present heuristic algorithms to design a self-repairing protection tree for a given network. We study the restorability performance of shared trees and examine the limitations of such schemes in specific topologies, such as cases where long node chains exist. Using extensive simulations with thousands of randomly generated network graphs. We compare redundancy and average backup path length of shared protection trees with optimal tree designs and non-tree designs. We also apply our algorithms to the problem of designing the protection tree in a pre-designed fixed-capacity network, and study the performance of shared protection trees in this scenario under different network loads and link utilization levels.     

Energy-efficient forwarding in wireless sensor networks

For maximizing the energy efficiency in a wireless network, we propose two forwarding schemes termed single-link and multi-link energy-efficient forwarding that tradeoff delivery ratios against energy costs. Multi-link forwarding improves the network performance substantially by addressing multiple receivers at once during the packet forwarding process. If the first forwarding node does not receive a packet correctly, other nodes may act as backup nodes and perform the forwarding instead. By means of mathematical analyses, we derive how the energy efficiency of a forwarding path can be computed and how a forwarding tree is established. Routing cycles are explicitly taken into account and prevented by means of sequence numbers. Simulations and real-world experiments provide a comparison to other reference strategies, showing a superior performance of our forwarding scheme in terms of energy efficiency.     

Protection based on backup radios and backup fibers for survivable Fiber-Wireless (FiWi) access network

In Fiber-Wireless (FiWi) access network, the optical back-end is vulnerable to the network component failure due to its tree topology. Any failure at the optical back-end may cause huge data loss. Thus, the survivability in FiWi is an important issue, especially the protection for the optical back-end. Some works propose to protect the optical back-end in FiWi by means of the wireless rerouting in the wireless front-end. However, these works cannot guarantee that there are always the available wireless paths for the traffic rerouting. In this paper, we divide the failures at the optical back-end into ONU-level failure and OLT-level failure according to the failure severity. To tolerate the ONU-level failure, we allocate each ONU a partner ONU and establish the wireless-backup-path between them by deploying backup radios on the traversed wireless routers. To tolerate the OLT-level failure, we cluster all segments in the network and place the backup fibers among the segments in each cluster to establish the protection ring. Thus, each pair of segments in the same cluster can backup for each other along the optical-backup-paths on the protection ring. We propose the heuristic algorithms to minimize the cost of backup radios and the cost of backup fibers. The simulation results demonstrate that the proposed algorithms are effective in enhancing the survivability of FiWi, while requiring less cost than the previous works.     

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.     

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.     

Energy-aware IP traffic engineering with shortest path routing

Internet energy consumption is rapidly becoming a critical issue due to the exponential traffic growth and the rapid expansion of communication infrastructures worldwide. We address the problem of energy-aware intra-domain traffic engineering in networks operated with a shortest path routing protocol. We consider the problem of switching off (putting in sleep mode) network elements (links and routers) and of adjusting the link weights so as to minimize the energy consumption as well as a network congestion measure. To tackle this multi-objective optimization problem with priority (first minimize the energy consumption and then the network congestion), we propose a Mixed Integer Linear Programming based algorithm for Energy-aware Weights Optimization (MILP-EWO). Our heuristic exploits the Interior Gateway Protocol Weight Optimization (IGP-WO) algorithm for optimizing the OSPF link weights so as to minimize the total cost of link utilization. The computational results obtained for eight real network topologies and different types of traffic matrices show that it is possible to switch off a substantial number of nodes and links during low and moderate traffic periods, while guaranteeing that network congestion is low enough to ensure service quality. The proposed approach is also validated on two networks of emulated Linux routers.     

Estimation of the available bandwidth ratio of a remote link or path segments

Available bandwidth is usually sensitive to network anomalies such as physical link failure, congestion, and DDoS attack. Thus, real-time available bandwidth information can be used to detect network anomalies. Many schemes have been proposed to estimate the end-to-end available bandwidth or end-to-end capacity. However, the problem of estimating the available bandwidth for a specific remote link has not been investigated in detail yet. We propose a new scheme to estimate the available bandwidth ratio of a remote link or remote path segments, a group of consecutive links, without deploying our tool at the remote nodes. The scheme would be helpful in accurately pinpointing anomalous links. Two streams of ICMP timestamp packets are sent to both end nodes of a target link according to a Poisson process, and the available bandwidth ratio for the target link is estimated based on the measured packet delay. Since the proposed scheme needs not incur a short-term congestion, unlike conventional end-to-end available bandwidth estimation mechanisms, the intrusiveness is low and the proposed scheme overcomes the limitation of conventional approaches, inability to probe the links beyond the tight link with the minimum available bandwidth. The performance of the proposed scheme is evaluated by ns-2 simulation.     

Link stability estimation based on link connectivity changes in mobile ad-hoc networks

Link stability issue is significant in many aspects, especially for the route selection process in mobile ad-hoc networks (MANETs). Most previous works focus on the link stability in static environments, with fixed sampling windows which are only suitable for certain network topologies. In this paper, we propose a scheme to estimate the link stability based on link connectivity changes, which can be performed on the network layer, without the need of peripheral devices or low layer data. We adopt a variable sized sampling window and propose a method to estimate the link transition rates. The estimation scheme is not restricted to specific network topologies or mobility models. After that, we propose a routing method which adjusts its operating mode based on the estimated link stability. Simulation results show that the proposed scheme can provide correct estimation in both stationary and non-stationary scenarios, and the presented routing protocol outperforms conventional routing schemes without link stability estimation.