FAULT-TOLERANT ROUTINGS IN DOUBLE FIXED-STEP NETWORKS

This paper studies routing vulnerability in loop networks modeled by d ouble fixed step-graphs. A double tired step-graph has its vertices la beled with the integers modulo n and each vertex i is adjacent to the vertices i +/- a(mod n), i +/- b (mod n), where a, b, 1 less than or e qual to \a\,\b\ less than or equal to n - 1, are different integers. A bidirectional and consistent fault-tolerant routing rho of shortest p aths is defined by using a geometrical representation that associates to the graph a tile which periodically tessellates the plane. When som e faulty elements are present in the network, we give a method to obta in p-central vertices, which are vertices that can be used to re-routi ng any communication affected by the faulty elements. This implies tha t 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.