Self-Protected Spanning Tree Based Recovery Scheme to Protect against Single Failure

Depeng JIN
Wentao CHEN
Yong LI
Lieguang ZENG

IEICE TRANSACTIONS on Communications   Vol.E92-B    No.3    pp.909-921
Publication Date: 2009/03/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E92.B.909
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network Management/Operation
network recovery,  self-protected spanning tree,  birthday-based link replacing mechanism,  graph theory,  load balancing,  Ethernet,  

Full Text: PDF(601.1KB)>>
Buy this Article

We present a recovery scheme based on Self-protected Spanning Tree (SST), which recovers from failure all by itself. In the recovery scheme, the links are assigned birthdays to denote the order in which they are to be considered for adding to the SST. The recovery mechanism, named Birthday-based Link Replacing Mechanism (BLRM), is able to transform a SST into a new spanning tree by replacing some tree links with some non-tree links of the same birthday, which ensures the network connectivity after any single link or node failure. First, we theoretically prove that the SST-based recovery scheme can be applied to arbitrary two-edge connected or two connected networks. Then, the recovery time of BLRM is analyzed and evaluated using Ethernet, and the simulation results demonstrate the effectiveness of BLRM in achieving fast recovery. Also, we point out that BLRM provides a novel load balancing mechanism by fast changing the topology of the SST.