Premium
Cluster fault‐tolerant routing in star graphs
Author(s) -
Gu QianPing,
Peng Shietung
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(200001)35:1<83::aid-net7>3.0.co;2-d
Subject(s) - computer science , star (game theory) , cluster (spacecraft) , fault tolerance , routing (electronic design automation) , distributed computing , mathematics , computer network , mathematical analysis
Fault‐tolerant routing is a key issue in computer/communication networks. We say a network (graph) can tolerate / faulty nodes for a routing problem if after removing at most / arbitrary faulty nodes from the graph the routing paths exist for the routing problem. However, the bound / is usually a worst‐case measure and it is of great interest to find the routing paths when more than / faulty nodes exist. Cluster fault‐tolerant (CFT) routing was proposed as an approach for this purpose. In the CFT routing, we reduce the number of “faults” that a routing problem has to deal with using subgraphs to cover the faulty nodes. In particular, we consider the number and the size (diameter) of faulty subgraphs rather than the number of faulty nodes that a graph can tolerate. In this paper, we show that a subgraph of diameter 2 can be viewed as a single “fault” for the following routing problems in the star graph: Given a source node s and t target nodes t 1 , …, t k , find k node‐disjoint paths from s to t i (1 ≤ i ≤ k ), and given k node pairs ( s 1 , t 1 ), …, ( s k , t k ), find k node‐disjoint paths s i → t i (1 ≤ i ≤ k ). Since a subgraph of diameter 2 of the n ‐dimensional star graph G n may have n nodes, the above result implies that the number of faulty nodes that G n can tolerate is n times larger than the worst‐case measure if the faulty nodes can be covered by certain subgraphs. We also give algorithms which find the paths for the two routing problems. © 2000 John Wiley & Sons, Inc.