loading...
Constructing an Edge-Route Guaranteed Optimal Fault-Tolerant Routing for Biconnected Graphs
Hsinchu, TAIWAN November 20-November 22
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ATS.1996.555148Fifth Asian Test Symposium (ATS'96)
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Yupin Luo, Tsinghua University
Shiyuan Yang, Tsinghua University
Dongcheng Hu, Tsinghua University
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
Usage of this product signifies your acceptance of the Terms of Use.