Parallel algorithms for time-slot assignment in TDM switching systems
S. Chalasani, A. Varma · IEEE Transactions on Communications · 1993
Presents parallel algorithms for computation of time-slot assignments in time-division multiplex (TDM) switching systems. The algorithms apply to a general class of TDM switching systems called hierarchical switching 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 sequential 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 sequential TSA algorithm runs in O(M/sup 2/.min(N, square root M).min(L, M/sup 2/)) time. The authors first describe an algorithm using L/2 processors with running time O(M/sup 3/ log L) on a PRAM model of computation. They then generalize it to P>