IMPLEMENTING ROUTERS WITH A SINGLE STAGE OF BUFFERING

摘要

A Single-Buffered (SB) router is a router where only one stage of shared buffering is sandwiched between two interconnects in comparison of a Combined Input and Output Queued (CIOQ) router where a central switch fabric is sandwiched between two stages of buffering. The first theoretical analysis of SB routers was undertaken by the High-Performance Networking Group (HPNG) of Stanford University with an aim at finding conditions under which a SB router can emulate an ideal shared memory router. Their work deserved full credit, but all of results presented by HPNG appeared to require a Centralized Memory Management Algorithm (CMMA) that was essentially impractical because of the unreasonable processing and communication complexity. In this paper, we attempt to make a scalable high-speed SB router practical by introducing a distributed architecture for SB routers: Virtual Output and Input Queued (VOIQ) shared memory. We show that the resulting VOIQ router can not only eliminate the need for a central memory management scheduler, allowing a full distributed implementation with low complexity of processing and communication, but also provide QoS guarantees and efficiently support variable-length packets. In particular, the hardware implementation of our VOIQ-based router (NDSC SR1880-T series) is illustrated at the end of this paper.