FoF-R Ant-based Survivable Routing Using Distributed Resilience Matrix

摘要

Fast recovery from failures and overall high utilization of network capacity are two primary goals of network survivability design. Shared backup path protection has been shown to be efficient in terms of capacity utilization, due to the sharing capability among protection paths. However, the resulting Integer Linear Programming (ILP) formulation of the problem is known to be NP-hard. This paper tackles the survivable routing problem using a new distributed matrix-based structure, termed Resilience Matrix (RM), for capturing the local bandwidth usage information. Additionally, a heuristic ant-based routing algorithm, named Friend-or-Foe Resilient (FoF-R), is proposed for finding the optimal protection cycle (i.e., two node-disjoint paths between a source-destination node pair) and for exploring the sharing ability among protection paths using a headroom-dependent attraction and repulsion functions. Simulation results based on the OMNeT++ tool show that the FoF-R scheme with the distributed RM structure is a promising approach to solve the survivable routing problem and it gives a good trade off between solution's optimality and the time needed for finding a solution.