Premium
Shortest path routing and fault‐tolerant routing on de Bruijn networks
Author(s) -
Mao JyhWen,
Yang ChangBiau
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(200005)35:3<207::aid-net4>3.0.co;2-f
Subject(s) - equal cost multi path routing , de bruijn sequence , shortest path problem , computer science , private network to network interface , link state routing protocol , k shortest path routing , static routing , multipath routing , path vector protocol , destination sequenced distance vector routing , dynamic source routing , routing (electronic design automation) , computer network , algorithm , routing protocol , mathematics , combinatorics , theoretical computer science , graph
In this paper, we study the routing problem for the undirected binary de Bruijn interconnection network. Researchers have never proposed a shortest path routing algorithm on the undirected binary de Bruijn network. We first propose a shortest path routing algorithm, whose time complexity in the binary de Bruijn network of 2 m nodes is O ( m 2 ). Then, based on our shortest path routing algorithm, we propose two fault‐tolerant routing schemes. It is assumed that at most one node fails in the network. In our schemes, two node‐disjoint paths are found. Our first fault‐tolerant routing algorithm guarantees that one of the two paths is the shortest path, and the other is of length at most m + log 2 m + 4. Our second algorithm can find two node‐disjoint paths with lengths at most m and m + 4, respectively, if the shortest path is not required in the fault‐tolerant routing. © 2000 John Wiley & Sons, Inc.