AN IMPROVED TIME-SLOT ASSIGNMENT ALGORITHM FOR TDM HIERARCHICAL SWITCHING SYSTEMS

Time-division multiplexed (TDM) hierarchical switching systems (HSS's) were introduced by Eng and Acampora [1]. The best-known algorithm for finding an optimal time slot assignment (TSA) in these switching syst ems runs in O(min(L,M2).M3) time where M is the system size and L is t he length of any optimal TSA [3]. In this correspondence, we present a n improved algorithm that runs in O(min(L,M2).min(N, square-root M). M 2) time for finding an optimal TSA in a hierarchical switching system. Thus, we achieve an O(max(M/N, square-root M)) improvement over the b est-known algorithm.