For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Self-Protected Spanning Tree Based Recovery Scheme to Protect against Single Failure
IEICE TRANSACTIONS on Communications
Publication Date: 2009/03/01
Online ISSN: 1745-1345
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>>
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.