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.
An Efficient Adaptive Routing Algorithm for the Faulty Star Graph
Leqiang BAI Hiroyuki EBARA Hideo NAKANO Hajime MAEDA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1998/08/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
star graph, node-disjoint subgraph, node-disjoint path, fault-tolerance, adaptive routing,
Full Text: PDF(875KB)>>
This paper introduces an adaptive distributed routing algorithm for the faulty star graph. The algorithm is based on that the n-star graph has uniform node degree n-1 and is n-1-connected. By giving two routing rules based on the properties of nodes, an optimal routing function for the fault-free star graph is presented. For a given destination in the n-star graph, n-1 node-disjoint and edge-disjoint subgraphs, which are derived from n-1 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 n-1 node-disjoint paths between two arbitrary nodes, the algorithm can route messages to the destination by finding a fault-free 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 n-1 of the n-star 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.