
For FullText 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.

An Efficient Adaptive Routing Algorithm for the Faulty Star Graph
Leqiang BAI Hiroyuki EBARA Hideo NAKANO Hajime MAEDA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E81D
No.8
pp.783792 Publication Date: 1998/08/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: star graph, nodedisjoint subgraph, nodedisjoint path, faulttolerance, adaptive routing,
Full Text: PDF(875KB)>>
Summary:
This paper introduces an adaptive distributed routing algorithm for the faulty star graph. The algorithm is based on that the nstar graph has uniform node degree n1 and is n1connected. By giving two routing rules based on the properties of nodes, an optimal routing function for the faultfree star graph is presented. For a given destination in the nstar graph, n1 nodedisjoint and edgedisjoint subgraphs, which are derived from n1 adjacent edges of the destination, can be constructed by this routing function and the concept of Breadth First Search. When faults are encountered, according to that there are n1 nodedisjoint paths between two arbitrary nodes, the algorithm can route messages to the destination by finding a faultfree subgraphs based on the local failure information (the status of all its incident edges). As long as the number f of faults (node faults and/or edge faults) is less than the degree n1 of the nstar graph, the algorithm can adaptively find a path of length at most d+4f to route messages successfully from a source to a destination, where d is the distance between source and destination.

