Performance Analysis of a Growable Architecture for Broadband Packet (ATM) Switching.

A growable architecture for broadband packet (ATM) switching, consisting of a memoryless, self-routing interconnect fabric and modest-size packet switch modules, was recently proposed by Eng, Karol, and Yeh. In this memorandum, we examine the performance of this architecture. Because the architecture attains the best possible delay-throughput performance if the packet switch modules use output queueing, we focus on the cell loss probability. There are two sources of cell loss in the switch. First, cells are dropped if too many simultaneous arrivals are destined to a group of output ports. Second, because a simple, distributed path-assignment controller is used for speed and efficiency, cells are dropped when the controller cannot "schedule" a path through the switch. We compute an upper bound on the cell loss probability for arbitrary (nonuniform) patterns of independent cell arrivals, possibly including isochronous circuit connections, and show that both sources of cell loss can be made negligibly small. For example, to guarantee less than 10 sup -9 cell loss probability, this growable architecture requires packet switch modules of dimension 47 times 16, 45 times 16, 42 times 16, and 39 times 16 for 100%, 90%, 80%, and 70% traffic loads, respectively. The analytic techniques we use to bound the cell loss probabilities are applicable to other output queueing architectures.