A Binary Time-Slot Assignment Algorithm for Time-Division Multiplexed (TDM) Hierarchical Switching Systems (HSS)

Boseob KWON; Kaoru SEZAKI; Young Man KIM; Hyunsoo YOON

A Binary Time-Slot Assignment Algorithm for Time-Division Multiplexed (TDM) Hierarchical Switching Systems (HSS)

Boseob KWON, Kaoru SEZAKI, Young Man KIM, Hyunsoo YOON

Full Text Views

0

Cite this

Summary :

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, 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(NLlog₂ 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, M²)min(N, M)M²), 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(N²). In this configuration our algorithm makes a significant improvement in time complexity by the order of O(M²/log₂M).

Publication: IEICE TRANSACTIONS on Communications Vol.E80-B No.5 pp.770-778

Publication Date: 1997/05/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Satellite Communication

Cite this

Copy

Boseob KWON, Kaoru SEZAKI, Young Man KIM, Hyunsoo YOON, "A Binary Time-Slot Assignment Algorithm for Time-Division Multiplexed (TDM) Hierarchical Switching Systems (HSS)" in IEICE TRANSACTIONS on Communications, vol. E80-B, no. 5, pp. 770-778, May 1997, doi: .
Abstract: 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, 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(NLlog₂ 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, M²)min(N, M)M²), 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(N²). In this configuration our algorithm makes a significant improvement in time complexity by the order of O(M²/log₂M).
URL: https://global.ieice.org/en_transactions/communications/10.1587/e80-b_5_770/_p

Copy

@ARTICLE{e80-b_5_770,
author={Boseob KWON, Kaoru SEZAKI, Young Man KIM, Hyunsoo YOON, },
journal={IEICE TRANSACTIONS on Communications},
title={A Binary Time-Slot Assignment Algorithm for Time-Division Multiplexed (TDM) Hierarchical Switching Systems (HSS)},
year={1997},
volume={E80-B},
number={5},
pages={770-778},
abstract={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, 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(NLlog₂ 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, M²)min(N, M)M²), 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(N²). In this configuration our algorithm makes a significant improvement in time complexity by the order of O(M²/log₂M).},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - A Binary Time-Slot Assignment Algorithm for Time-Division Multiplexed (TDM) Hierarchical Switching Systems (HSS)
T2 - IEICE TRANSACTIONS on Communications
SP - 770
EP - 778
AU - Boseob KWON
AU - Kaoru SEZAKI
AU - Young Man KIM
AU - Hyunsoo YOON
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E80-B
IS - 5
JA - IEICE TRANSACTIONS on Communications
Y1 - May 1997
AB - 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, 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(NLlog₂ 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, M²)min(N, M)M²), 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(N²). In this configuration our algorithm makes a significant improvement in time complexity by the order of O(M²/log₂M).
ER -