ON THE COMPUTATIONAL COMPLEXITY OF ROUTING IN FAULTY K-ARY N-CUBES AND HYPERCUBES
Abstract
We equate a routing algorithm in a (faulty) interconnection network whose underlying graph is a k-ary n-cube or a hypercube, that attempts to route a packet from a fixed source node to a fixed destination node, with the sub-digraph of (healthy) links potentially usable by this routing algorithm as it attempts to route the packet. This gives rise to a naturally defined problem, parameterized by this routing algorithm, relating to whether a packet can be routed from a given source node to a given destination node in one of our interconnection networks in which there are (possibly exponentially many) faulty links. We show that there exist such problems that are PSPACE-complete (all are solvable in PSPACE) but that there are (existing and popular) routing algorithms for which the computational complexity of the corresponding problem is significantly easier (yet still computationally intractable).
References
- Theoretical Computer Science 410(50), 5215 (2009), DOI: 10.1016/j.tcs.2009.08.023. Crossref, ISI, Google Scholar
- Journal of Graph Theory 67(1), 69 (2011), DOI: 10.1002/jgt.20514. Crossref, ISI, Google Scholar
-
W. J. Dally and B. Towles , Principles and Practices of Interconnection Networks ( Morgan Kaufmann , San Francisco , 2004 ) . Google Scholar - International Journal of Computer Systems Science and Engineering 12(6), 359 (1997). ISI, Google Scholar
C. J. Glass and L. M. Ni , The turn model for adaptive routing, Proc. of 19th Ann. Int. Symp, on Computer Architecture (ISCA '92) (ACM Press, 1992) pp. 278–287. Google Scholar


