Fault-tolerant routings in double fixed-step networks

AbstractThis paper studies routing vulnerability in loop networks modeled by double fixed step-graphs. A double fixed step-graph has its vertices labeled with the integers modulo n and each vertex i is adjacent to the vertices i ± a (modn), i ± b (mod n), where a, b, 1 ⩽ ¦a¦, ¦b¦⩽ n − 1, are different integers. A bidirectional and consistent fault-tolerant routing p of shortest paths is defined by using a geometrical representation that associates to the graph a tile which periodically tessellates the plane. When some faulty elements are present in the network, we give a method to obtain p-central vertices, which are vertices that can be used to re-routing any communication affected by the faulty elements. This implies that the diameter of the corresponding surviving route graph is optimum. On the other hand, the set of vertices or edges that can fail, given a p-central vertex, is characterized