Fast algorithms for restoring survivable spanning connection

The stability of data transmission in the network can be maintained by a survivable spanning connection (SSC), which consists of two not-fully-disjoint spanning trees. Existing works restore the faulty SSC from link failures by regenerating two new not-fully-disjoint spanning trees. However, it takes plenty of recovery time, especially in a large network. This paper aims to fastly restore the faulty SSC by adjusting and updating its faulty spanning trees. A SSC restoration problem is formulated to generate a restored SSC with nearly optimal network survivability and desired bandwidth requirement. To solve the formulated problem, two fast restoration algorithms are proposed to cope with the shared link failure and the unshared link failure, respectively. Simulation results show that, the proposed algorithms can reduce the recovery time by 36.69% and 55.54%, respectively, compared with the existing algorithm. In addition, the proposed algorithms can achieve nearly optimal network survivability.

Automated summary

This study aims to quickly restore the faulty survivable spanning connection (SSC) by adjusting and updating the faulty spanning trees. Two fast restoration algorithms are proposed and simulation results show that they can significantly reduce the recovery time and achieve nearly optimal network survivability.