Fault Tolerant Routings In Some All-optical Networks

An all-optical network can be modelled as a symmetric directed graph G, i.e., if an arc (u,v)∈A(G) then (v,u)∈ A(G). We use R_f(G) to denote an f-fault tolerant routing of G and π(R_f(G)) to denote the maximum load on its arcs induced by the routing R_f(G).The f-tolerant arc-forwarding index π_f(G) of G is defined to be .We say that a routing R_f(G) is optimal if its load achieves the f-tolerant arc-forwarding index π_f(G); and it is balanced if the difference between loads of any two arcs is at most one. We say that an optimal balanced routing R_f(G) is leveled if each of its subroutings is also optimal and balanced.In this paper, we first construct an f-fault tolerant routings for K_{n,m}, where K_{n,m} is the complete n-partite graph with each partition part containing exactly m vertices and where, n is a prime power. In particular, if m = 2 or n = 3, these routings are shown to be leveled and, consequently, the corresponding π_f indexes for these graphs are determined. We also construct the leveled f-fault tolerant routings for hypercube Q_n, folded hypercube FH(n) and product graph K_n ×K_n, respectively. Furthermore, the corresponding π_f indexes of these graphs are given.