ON f-WISE ARC FORWARDING INDEX AND WAVELENGTH ALLOCATIONS IN FAULTY ALL-OPTICAL HYPERCUBES

摘要

Motivated by the wavelength division multiplexing in all-optical networks, we consider the problem of finding an optimal (with respect to the least possible number of wavelengths) set of f + 1 internally node disjoint dipaths connecting all pairs of distinct nodes in the binary r-dimensional hypercube, where 0 ≤ f < r. This system of dipaths constitutes a routing protocol that remains functional in the presence of up to f faults (of nodes and/or links). The problem of constructing such protocols for general networks was mentioned in [1]. We compute precise values of f-wise arc forwarding indexes and give (describe dipaths and color them) nearly optimal all-to-all f-fault tolerant protocols for the hypercube network. Our results generalize corresponding results from [1,4,14].