B. Kwon et al., A BINARY TIME-SLOT ASSIGNMENT ALGORITHM FOR TIME-DIVISION MULTIPLEXED(TDM) HIERARCHICAL SWITCHING SYSTEMS (HSS), IEICE transactions on communications, E80B(5), 1997, pp. 770-778
A Time-Division Multiplexed (TDM) Hierarchical Switching System (HSS),
proposed by Eng and Acampora[5], provides any size of bandwidth for a
number of subscribers by allocating proper number of time-slots in a
frame. In this paper. Lye present a binary time-slot assignment(TSA) a
lgorithm by which a proper size of time-slots in the frame are allocat
ed to each subscriber so as to meet its bandwidth requests. The time c
omplexing of the proposed algorithm is O(NL loq(2) L) in which N is th
e number of input/output links of the central switch and L is the numb
er of time-slots allotted to each link in the frame. Rs the authors kn
ow. the most efficient algorithm proposed in the literature has time c
omplexity of O(min(L.M-2).min(N,root M).M-2), in which M is the number
of subscribers that is larger than N in TDM/HSS system. To give a cle
ar idea of relative efficiency between two algorithms, let us give a t
ypical situation of M = L = O(N-2). In this configuration our algorith
m makes a significant improvement in time complexity by the order of O
(M-2/log(2)M).