FoF-R Ant: Ant-Based Survivable Routing Scheme for Shared Path Protection

摘要

This paper proposes a novel framework to solve the survivable routing problem with shared path protection in a distributed control environment. The work mainly concerns how to dynamically determine a protection cycle (i.e., two link-disjoint paths between a source-destination node pair) and allocate spare capacity for a connection establishment request so as to minimize total bandwidth consumption in the network. This is known as the Spare Capacity Allocation (SCA) problem and its resulting Integer Linear Programming (ILP) formulation is known to be NP-hard. This paper tackles the SCA problem using a new matrix-based model and a heuristic algorithm, termed Friend or Foe -Resilient (FoF-R) ant-based routing algorithm. First, a new concept of Resilience Matrix (RM) is introduced to capture the local bandwidth usage information and investigate the relationship between a failed link and other links with protection capacity allocated. Next, based on the special link cost derived from the RM, the novel FoF-R ant-based routing algorithm, which is inspired by the principle of ant colony optimization, is developed to find the optimal protection cycles and explore the sharing ability among protection paths using a headroom-dependent attraction/repulsion function. By keeping a suitable number of mobile agents (i.e., FoF-R ants) in a network to continually and proactively update the RMs, the survivable routing solution for a connection request can be obtained within a reasonable computation time.