PARALLEL ALGORITHMS FOR TIME-SLOT ASSIGNMENT IN TDM SWITCHING SYSTEMS

We present parallel algorithms for computation of time-slot assignment s in time-division multiplex (TDM) switching systems. The algorithms a pply to a general class of TDM switching systems called hierarchical s witching systems (HSS), which have a three-stage switching structure. The algorithms are based on modeling the time-slot assignment problem as a network-flow problem. Previous algorithms for finding an optimal time-slot assignment in these switching systems are inherently sequent ial and no parallel algorithms are known for this problem. If M is the number of users of the switching system, N is the switch-size, and L is the length of an optimal time-slot assignment, the best-known seque ntial TSA algorithm runs in O(M(2) . min(N, root M) . min(L, M(2))) ti me. We first describe an algorithm using L/2 processors with running t ime O(M(3) log L) on a PRAM model of computation. We then generalize i t to P less than or equal to L/2 processors, with running time O(M(3) log P + M(2) . min(N, root M) . min(L/P, M(2))). An efficient implemen tation of the algorithm on a hypercube multiprocessor with P processor s has the same time-complexity. A massively parallel version of the al gorithm runs in O(M(2) log M log L) time on M L/2 processors. Finally, we discuss how the above algorithms can be applied to the class of SS /TDMA switching systems.