DocumentCode
1497491
Title
An optimal fault-tolerant routing algorithm for double-loop networks
Author
Liu, Yu-Liang ; Wang, Yue-Li ; Guan, D.J.
Author_Institution
Dept. of Inf. Manage., Nat. Taiwan Univ. of Sci. & Technol., Taipei, Taiwan
Volume
50
Issue
5
fYear
2001
fDate
5/1/2001 12:00:00 AM
Firstpage
500
Lastpage
505
Abstract
A weighted double-loop network can be modeled by a directed graph G(n; h1, h2; w1, w2) with vertex set Zn={0, 1, ..., n-1} and edge set E=E1∪E2, where E1={(u, u+h1 )|u∈Zn}, E2={(u, u+h2)|u∈Zn}. Assume that the weight of each edge in E1 is w1 and the weight of each edge in E 2 is w2. In this paper, we present an optimal routing algorithm on double-loop networks under the case where there is at most one faulty element. Our algorithm is based on the fact that the shortest path from a vertex to any other vertex in a double-loop network is in the L-shape region
Keywords
computational geometry; computer networks; directed graphs; fault tolerant computing; network routing; L-shape region; directed graph; double-loop networks; edge set; optimal fault-tolerant routing algorithm; shortest path; vertex; Communication networks; Fault detection; Fault tolerance; Local area networks; Network topology; Routing; Solids;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.926162
Filename
926162
Link To Document