Fault-tolerant routings in Kautz and de Bruijn networks

AbstractWe consider the problem of constructing networks, having a fixed routing, that are highly fault-tolerant. A routing in a network assigns to each ordered pair of nodes a fixed path from one to another. According to Dolev, Halpern, Simons and Strong, a good routing is such that the diameter of the surviving route digraph associated to the routing is small whatever the set of fault is. In this digraph, the nodes are the nonfaulty nodes of the original digraph, two nodes being joined by an arc if and only if there are no faults on the path between them. Dolev, Halpern, Simons and Strong have asked for families of networks admitting such a routing. Here we prove that the families of de Bruijn or Kautz networks satisfy this condition