Fifth Asian Test Symposium (ATS'96)
Constructing an Edge-Route Guaranteed Optimal Fault-Tolerant Routing for Biconnected Graphs
Hsinchu, TAIWAN
November 20-November 22
ISBN: 0-8186-7478-4
Consider a graph that corresponds to a communication network in which a limited number of edge and/or node faults might occur. A routing for the network (a fixed path between each pair of nodes) must be chosen without knowing which components might become faulty. The diameter of a surviving route graph, where two nonfaulty nodes are connected by an edge iff there are no faults on the route between them, is considered to be one of the fault-tolerance measures for the routing. In this paper, we show that we can construct a routing for any biconnected graph and an arbitrary fault such that the diameter of its surviving route graph is not greater than two and unlike optimal routings constructed by the previous algorithm, our routing is also provided with the expected feature to routings that every edge is guaranteed to be chosen as the route between its two endpoints.
Index Terms:
Network, Fault tolerance, Routing, Diameter, Distributed computing
Citation:
Yupin Luo, Shiyuan Yang, Dongcheng Hu, "Constructing an Edge-Route Guaranteed Optimal Fault-Tolerant Routing for Biconnected Graphs," ats, pp.123, Fifth Asian Test Symposium (ATS'96), 1996