Fault-tolerant Routing Methods in Bicubes

In this study, we propose three fault-tolerant routing methods in bicubes [1]. To begin with, we design a simple fault-tolerant routing method based on the shortest-path routing algorithm proposed by Okada and Kaneko [2]. We regard this method as the baseline. First, we devised a method, Method 1, in which each node with a message switches to the dept-first search if the distance from the node to the destination node is less than or equal to 3. Next, we proposed a method, Method 2, in which each node with a message excludes the previous node, that is, the node that forwarded the message to the current node, when it selects one of its non-faulty neighbor nodes to forward the message. Finally, we combine the methods, Method 1 and Method 2, to obtain the third one, Method 3. By using the simple fault-tolerant routing method as the baseline, we conducted a computer experiment in 11-, 12-, and 13-dimensional bicubes, BQ
11
, BQ
12
, and BQ
13
, to evaluate the three methods. According to the experimental result, Method 3 showed the best performance and Method 2 did the second best. Method 1 showed slightly better performance than the simple fault-tolerant routing method.