Input Versus Output Queueing on a Space-Division Packet Switch

Author

Karol, Mark J. ; Hluchyj, Michael G. ; Morgan, Samuel P.

Author_Institution

AT&T Bell Labs.,Holmdel,NJ

Volume

35

Issue

12

fYear

1987

fDate

12/1/1987 12:00:00 AM

Firstpage

1347

Lastpage

1356

Abstract

Two simple models of queueing on an $N \\times N$ space-division packet switch are examined. The switch operates synchronously with fixed-length packets; during each time slot, packets may arrive on any inputs addressed to any outputs. Because packet arrivals to the switch are unscheduled, more than one packet may arrive for the same output during the same time slot, making queueing unavoidable. Mean queue lengths are always greater for queueing on inputs than for queueing on outputs, and the output queues saturate only as the utilization approaches unity. Input queues, on the other hand, saturate at a utilization that depends on $N$ , but is approximately $(2 -\\sqrt {2}) = 0.586$ when $N$ is large. If output trunk utilization is the primary consideration, it is possible to slightly increase utilization of the output trunks-upto $(1 - e^{-1}) = 0.632$ as $N \\rightarrow \\infty$ -by dropping interfering packets at the end of each time slot, rather than storing them in the input queues. This improvement is possible, however, only when the utilization of the input trunks exceeds a second critical threshold-approximately $\\ln (1 +\\sqrt {2}) = 0.881$ for large $N$ .

Keywords

Packet switching; Space-division switching; Buildings; Communication networks; Communication switching; Computer networks; Concurrent computing; Fabrics; Integrated circuit interconnections; Packet switching; Switches; Throughput;

fLanguage

English

Journal_Title

Communications, IEEE Transactions on

Publisher

ieee

ISSN

0090-6778

Type

jour

DOI

10.1109/TCOM.1987.1096719

Filename

1096719