Shortest path routing and fault-tolerant routing on de Bruijn networks

✍ Scribed by Mao, Jyh-Wen; Yang, Chang-Biau

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 170 KB
• Volume: 35
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(200005)35:3<207::aid-net4>3.0.co;2-f

✦ Synopsis

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 m m nodes is O O O(m m 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 m m + log 2 m m m + 4. Our second algorithm can find two node-disjoint paths with lengths at most m m m and m m m + 4, respectively, if the shortest path is not required in the fault-tolerant routing.