Search

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.

Protected Working Capacity Envelope (PWCE) has been proposed to simplify resource management and traffic control for survivable WDM networks. In a PWCE-based network, part of the link capacity is reserved for accommodating working routes, and the remaining capacity is reserved for backup routes. The shortest path routing is applied in PWCE-based networks. An arrival call is accepted only when each link along the shortest path has a free working channel. Such a working path routing scheme greatly simplifies the call admission control process for dynamic traffic, and it is especially suitable for implementation in a distributed manner among network nodes. In this article, we investigate two protection strategies: Bundle Protection (BP) and Individual Protection (IDP). In BP, only one backup path can be used to protect a failure component, whereas multiple backup paths can be used in IDP. We formulate four mixed integer non-linear programming (MINLP) problems using BP and IDP strategies for single link and single node failure protection. Each model is designed to determine link metrics for shortest working path routing, working and backup channel assignments, and backup path planning. Our objective is to minimize call-blocking probability on the bottleneck link. Since these models are highly non-linear and non-convex, it is difficult to obtain exact global optimal solutions. We propose a Simulated Annealing-based Heuristic (SAH) algorithm to obtain near optimal solutions. This SAH adopts the concepts of simulated annealing as well as the bi-section technique to minimize call-blocking probabilities. To evaluate the performance, we made simulation comparisons between SAH and the unity link weight assignment scheme. The results indicate that SAH can greatly reduce call-blocking probabilities on benchmark and the randomly generated networks.

With quick topology changes due to mobile node movement or signal fading in MANET environments, conventional routing restoration processes are costly to implement and may incur high flooding of network traffic overhead and long routing path latency. Adopting the traditional shortest path tree (SPT) recomputation and restoration schemes used in Internet routing protocols will not work effectively for MANET. An object of the next generation SPT restoration system is to provide a cost-effective solution using an adaptive learning control system, wherein the SPT restoration engine is able to skip over the heavy SPT computation. We proposed a novel SPT restoration scheme, called Cognitive Shortest Path Tree Restoration (CSPTR). CSPTR is designed based on the Network Simplex Method (NSM) and Sensitivity Analysis (SA) techniques to provide a comprehensive and low-cost link failure healing process. NSM is used to derive the shortest paths for each node, while the use of SA can greatly reduce the effort of unnecessary recomputation of the SPT when network topology changes. In practice, a SA range table is used to enable the learning capability of CSPTR. The performance of computing and communication overheads are compared with other two well-known schemes, such as Dijstra's algorithm and incremental OSPF. Results show that CSPTR can greatly eliminate unnecessary SPT recomputation and reduce large amounts of the flooding overheads.

This letter proposes a novel low complexity shortest path tree restoration scheme to address link cost perturbation problem for link state routing in IP Networks. The proposed scheme can reduce the number of unnecessary shortest path tree recomputations and also provides a low-complexity computation when the Shortest Path Tree (SPT) restoration process executes. The proposed scheme has been designed based on the Network Simplex Method (NSM) and Sensitivity Analysis (SA) techniques to perform the optimality test for the current shortest path tree. The computational overhead is compared with various dynamic schemes over six network benchmarks.

To alleviate the impact of network component failures, many fast IP local recovery schemes have been proposed to reroute traffic in the event of failure. Tunnel-based fast IP local recovery is one of the most commonly adopted techniques. In IP-in-IP tunneling, when a failure occurs, the nodes adjacent to a failure are activated to encapsulate and reroute the affected traffic to the endpoint along the shortest path. Once the endpoint receives the affected traffic, it decapsulâtes and delivers the packets to original destination along the shortest path. These shortest paths are computed based on link weights. Therefore the design of link weights for tunnel-based fast IP local recovery is a critical issue. The goal of this paper is to determine a set of link weights in a tunnel-based fast IP local recovery system to jointly achieve: (1) load balance in the normal state (i.e., non-failure state) and (2) protection of any single link failure without incurring link overload during the failure recovery. We first formulate this problem as a mixed integer programming (MIP). Due to the NP-hard property of the MIP, a Simulated Annealing based Tunneling (SATu) scheme is proposed to obtain the solution of the MIP. In SATu, only the nodes adjacent to a failure are activated to encapsulate the affected packets and forward them to endpoint without disturbing regular traffic. Numerical results show that the proposed scheme improves tunnel-based IP fast reroute approach to achieve high rate of fault recovery in protecting single link failures without incurring link congestion in the non-failure state.

As a failure occurs, the affected traffic is quickly rerouted to backup paths for a network performing a fast protection scheme. Such a prompt reaction is aimed to reduce the damages caused by a failure. However, in some cases, the rerouted traffic may cause congestion along the backup paths which would lead to more packet losses than purely discarded affected flows. In this paper, we propose a load-balanced fast local protection scheme called Non-Weighted Interface Specific Routing (NISR) for determining the working and backup routing tables of IP routers. We jointly consider protection switching time, network survivability, and traffic load distribution together in the proposed scheme. In NISR, once a failure occurs, only the nodes adjacent to a failure divert affected traffic to backup paths. This local reaction process guarantees fast protection switching and reduces failure recovery time. Unlike the conventional IP routing, our approach relaxes the shortest path routing in computing working and backup routing tables. Most importantly, each interface in a router has its own routing tables. Combining the interface specific routing with the shortest path relaxation provides greater routing flexibility to enhance network survivability and load balancing. We formulate this as a mixed integer programming problem in which the traffic load on the most congested link is to be minimized. Since this problem is intractable by its NP-hard nature, we further decompose it into several sub-problems which are solved optimally and their solutions combined to provide a solution to the original problem. We perform experiments on some benchmark networks and compare the proposed scheme to several well-known schemes (including LFA, ECMP, OSPF, and NLB) on survivability ratio, link load distribution, and average path length for both normal and failure states. Through numerical results, we delineate that the proposed scheme achieves a sub-optimal solution, which is better for its high survivability and load balancing at the expense of slightly raising the average path hop count.

In order to reduce the greenhouse effects and environmental pollution, energy saving has become important in designing next the generation networks. Shutting down the network devices carrying light loads and redirecting the traffic flows to other routes is a way to decrease network energy consumption. Since traffic demands among node pairs vary in different time periods, the energy efficient network design is to determine the optimal network topologies for them. However, in current IP network, flows are governed by shortest path routing, thus purely determining the network topology is not enough. A set of link weight metric has to be derived in company with the network topology such that the flows on the active links can meet the physical capacity constraints. Although applying adaptive network topology could save energy consumption, however, the lack of stringent synchronization among routers would cause undesired loops during the transient period of topology changes. Removing routing images inconsistent among routers to prevent loops is a critical issue in energy efficient network and this issue is still not yet considered in the green network design. In this paper, we propose a comprehensive approach that determines network topology and link metric for each time period. Traffic engineering is considered in our design such that flows going on the energy aware network are within a predetermined percentage of the link capacity such that no congestion occurs in a statistical manner. To avoid accurate synchronization among routers, we propose using RFC 4915 Multi-Topology Routing, to resolve the transient loop problem. By controlling the update sequence in MTR, there is no transient loop during the period of topology changes. We formulate an integer linear programming to jointly determine this multi-topology and link weight assignment problem. Due to its NP-hard property, we propose an efficient algorithm, termed Lagrangean Relaxation and Harmonic Series (LR&HS) heuristic. Numerical results demonstrate that the proposed LR&HS approach outperforms the other approaches on four benchmark networks and provides up to 35%–50% energy saving in our experimental cases.

In this paper, we propose a non-weighted load balanced fast local protection scheme for survivable IP networks. Unlike conventional shortest path based routing, we relax shortest path constraints in computing working and backup routes to achieve load balancing purposes. Once a failure occurs, those nodes adjacent to the failure point use their backup routing tables to achieve fast local failure recovery. Only the affected traffic is diverted to bypass a failure. The approach adopts failure set concept such that the proposed scheme can be used to handle various kinds of scenarios including single link, single node or even shared risk link group (SRLG) failure. We formulate this problem as a mixed integer linear programming (MILP) to minimize the traffic load on the most congested link. Since this problem is not tractable by its NP-hard property, we further decompose it into several sub-problems. Each sub-problem is solved optimally and the original problem is approximated by combining the solutions of those sub-problems. We perform experiments on benchmark networks and compare the proposed scheme to well-known schemes on survivability, path lengths and link load distribution for normal and rerouted states. Through numerical results and comparisons, we delineate that the proposed approach achieves a sub-optimal solution, which is profoundly to its high survivability and load balancing at the expense of slightly longer average path hop count.