On Packet Switch Design

Growth in communication network capacity has been fueled by rapid advances in fiber-optic transmission technologies. In contrast, growth in the capacity of switching and routing nodes has grown
at a much slower pace, to the point where they are currently the bottlenecks that limit network capacity. The maximum capacity (throughput) a packet switch can achieve is largely determined by its architecture. It is widely recognized that conventional architectures cannot be scaled to implement the multi-terabit/s fabrics that will soon be required. Therefore, the problem this dissertation addresses is that of scalable high-capacity packet switches with a strong focus on performance.

First, a comprehensive overview of current packet-switch architectures is given, in which the pros and cons of existing approaches are identified. The main contribution of this dissertation is the introduction and evaluation of a novel architecture that combines the strengths of input-queued switches using virtual output queuing (VOQ) and shared-memory output-queued switches. When compared to purely input-queued switches or combined switches with a limited speed-up, the need for centralized arbitration is removed, whereas when compared to traditional purely output-buffered switches the proposed architecture requires only a relatively small amount of costly output buffers. Performance of the proposed architecture is shown to be high and robust under a wide variety of traffic patterns, particularly when compared with existing architectures. A detailed study on the implementation aspects of the proposed architecture demonstrates its feasibility.

A VOQ-based multicast approach that integrates unicast and multicast queuing and scheduling disciplines is introduced, and is shown to outperforms the existing dedicated-multicast-queue approaches by far, and a straightforward, inexpensive implementation is described.

Finally, a method to support long packets is introduced. Because these long packets have to share resources in the switch (the output queues and the shared memory), deadlocks can occur if no precautions are taken. We demonstrate how a suitable modification of the flow-control mechanism can eliminate all possible deadlocks in the presence of both unicast and multicast traffic, as well as with multiple traffic priorities. To assess its complexity, a possible implementation is described in detail.

This dissertation* has been performed in the context of the PRIZMA project (the IBM family of high-speed packet-switch chips). Its main role within this project has been system-level modeling and simulation. The main contributions in this context are that it has greatly increased understanding of the proposed system in terms of system-level architecture and performance, and, as a direct result of this increased insight, has paved the way for further architectural improvements.

*PhD Thesis, Eindhoven University of Technology, The Netherlands, 2001.