Off‐line permutation routing on circuit‐switched fixed‐routing networks
Abdou S. Youssef · Networks · 1993
Abstract Circuit‐switched fixed routing (CSFR) is an increasingly popular communication model wherein there is between every source—destination pair a single path that is system‐determined by a fixed‐routing rule. This paper studies the new problem of off‐line permutation scheduling on linear arrays, rings, hypercubes, and 2‐dimensional arrays, assuming the CSFR model. Optimal permutation scheduling involves finding a minimum number of subsets of nonconflicting source—destination paths. Every subset of paths can be established to run in one pass. In this paper, optimal permutation scheduling on linear arrays is shown to be linear, and on rings, NP‐complete. On hypercubes, the problem is NP‐complete. However, we will give an O(N log N) algorithm that routes any permutation in two passes if the model is relaxed to allow for two routing rules, namely, the so‐called e‐cube rule and the e−1‐cube rule. This complexity is reduced to O(N) hypercube‐parallel time. Finally, an O(N log2 N) bipartite‐matching‐based algorithm will be designed to schedule any permutation on p × q meshes/tori in q passes. © 1993 by John Wiley & Sons, Inc.