Browse Prior Art Database

Automatic Recovery From Failure for Address Independent Networks

IP.com Disclosure Number: IPCOM000034834D
Original Publication Date: 1989-Apr-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 1 page(s) / 13K

Publishing Venue

IBM

Related People

Philips, TK: AUTHOR

Abstract

Disclosed is an algorithm that allows address independent networks configured on a tree [1] to automatically reconfigure themselves after the failure of a node or a link. The key to the scheme is the observation that every connected undirected graph possesses one or more spanning trees, and consequently supports an address independent routing [1]. An address independent network may therefore be configured on an undirected (or bidirectional) network of point-to-point links that contains one or more redundant links by first finding a spanning tree in a distributed manner, and then routing messages along this spanning tree using a predetermined address independent routing.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 1

Automatic Recovery From Failure for Address Independent Networks

Disclosed is an algorithm that allows address independent networks configured on a tree [1] to automatically reconfigure themselves after the failure of a node or a link. The key to the scheme is the observation that every connected undirected graph possesses one or more spanning trees, and consequently supports an address independent routing [1]. An address independent network may therefore be configured on an undirected (or bidirectional) network of point-to-point links that contains one or more redundant links by first finding a spanning tree in a distributed manner, and then routing messages along this spanning tree using a predetermined address independent routing. If the failure of a node or a link can be sensed by adjacent nodes, then the network can be made self-repairing, in that the failure of a component can be used to trigger a rerunning of the spanning tree algorithm. Note that such a network is maximally reliable; as long as the surviving portion of the network is connected, a spanning tree exists and will be found.

The procedure described above may be codified into an algorithm as follows: 1. Initialization: Run distributed spanning tree algorithm.
2. Route messages in an address independent manner. 3. If failure of link sensed, go to 1. A number of algorithms to find minimal spanning trees [2,3] are known. These algorithms assume the edges of the graph to be weighted, and they find the spanning tree for which the sum of the weights of all the tree edges is m...