OFF-LINE PERMUTATION ROUTING ON CIRCUIT-SWITCHED FIXED-ROUTING NETWORKS

Circuit-switched fixed routing (CSFR) is an increasingly popular commu nication 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 li near 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 s ubset of paths can be established to run in one pass. In this paper, o ptimal 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 permutat ion in two passes if the model is relaxed to allow for two routing rul es, namely, the so-called e-cube rule and the e-1-cube rule. This comp lexity is reduced to O(N) hypercube-parallel time. Finally, an O(N log 2 N) bipartite-matching-based algorithm will be designed to schedule a ny permutation on p x q meshes/tori in q passes.