Previous [1] [2] [3] [4] [5] 6 [7 ] [8 ]

Journal of Inforamtion Science and Engineering, Vol.8 No.4, pp.603-620 (December 1992)
A High-Throughput Cell Scheduling Algorithm
for Delay-Sensitive Traffic
in Broadband Switching Systems*

Wen-Tsuen Chen, Huai-Jen Liu and Yeong-Tsong Tsay
Department of Computer Science
National Tsing Hua University
Hsin-Chu, Taiwan 30043, R.O.C.

In this paper, we consider the output contention problem with the objective of increasing the throughput for asynchronous fransfer mode (ATM) switching systems with delay-sensitive traffic. We propose a cell scheduling algorithm to increase the throughput of a switching system. The maximum throughput is increased by up to 0.949. The efficiency, (output trunk utilization)/(input trunk utilization), is almost equal to 100%, and it is independent of the switch size and the traffic load. The cell scheduling algorithm is also shown to be able to provide high throughput not only for delay-sensitive traffic but also for traffic which can tolerate longer queueing delay. The mean cell waiting time of delay-sensitive traffic is reduced. That is, delay-sensitive traffic is transmitted as soon as possible. In previous works, the switching network usually has consisted of a sorting network followed by a routing network. However, in the switching system implemented with our cell scheduling algorith, it is sufficient for a sorting network to establish input/output paths through it simultaneously without conflicts, and it is not necessary to append a routing network to a sorting network. With our cell scheduling algorithm, it is impossible for any out-of -sequence cells to be received by the destinations on an input/output path. This, in turn, leads to the design of simpler protocols for the synchronization of real-time services such as voice and video communications. Consequently, our algorithm may offer an effective alternative for an ATM switching system.

Keywords: output contention, bandwidth allocation, cell scheduling, broadband integrated services digital network (BISDN), asynchronous transfer modde (ATM), ATM switching, sorting network, routing network

Received April 20, 1992; revised January 6, 1993.
Communicated by Jin-Fu Chang.
*A preliminary version of this paper was presented in the IEEE INFOCOM'92 Conference, Florence, Italy, May 1992.
This work was supported by the National Science Council, Taiwan, R.O.C., under grant NSC80-0408-E-007-10.