For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Binary Time-Slot Assignment Algorithm for Time-Division Multiplexed (TDM) Hierarchical Switching Systems (HSS)
Boseob KWON Kaoru SEZAKI Young Man KIM Hyunsoo YOON
IEICE TRANSACTIONS on Communications
Publication Date: 1997/05/25
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Satellite Communication
communication networks and services, switching and communication processing, communication software,
Full Text: PDF(755KB)>>
A Time-Division Multiplexed (TDM) Hierarchical Switching System (HSS), proposed by Eng and Acampora , provides any size of bandwidth for a number of subscribers by allocating proper number of time-slots in a frame. In this paper, we present a binary time-slot assignment (TSA) algorithm by which a proper size of time-slots in the frame are allocated to each subscriber so as to meet its bandwidth requests. The time complexity of the proposed algorithm is O(NLlog2 L) in which N is the number of input/output links of the central switch and L is the number of time-slots allotted to each link in the frame. As the authors know, the most efficient algorithm proposed in the literature has time complexity of O(min(L, M2)min(N, M)M2), in which M is the number of subscribers that is larger than N in TDM/HSS system. To give a clear idea of relative efficiency between two algorithms, let us give a typical situation of M = L = O(N2). In this configuration our algorithm makes a significant improvement in time complexity by the order of O(M2/log2M).