VLSI support for scheduling and buffer management in high speed packet-switched networks

This thesis presents a number of new approaches for designing fast, scalable queuing structures in VLSI for very high speed packet-switched networks. Such queuing structures are necessary for implementing packet buffers in switches and routers that have multi Gigabit-per-second (Gb/s) ports. The thesis addresses the design of two specific queue architectures: balanced parallel multi-input multi-output (MIMO) buffers, and systolic parallel priority queues (PPQ). A methodology for the systematic design of order-preserving parallel MIMO buffers is presented. The MIMO buffer employs an arithmetic-free systolic routing network and bank of parallel FIFO buffers to yield a load-balanced realization with increased bandwidth. Using this methodology we derived scalable parallel buffer structures that can be designed to match the rate of ultra high-speed links using current memory technology that uses moderate clock rates. A small prototype of the MIMO buffer attains a rate of 10.6 Gb/s which is more than adequate to support a Sonet OC- 192 link. The combined use of pipelined architecture and dynamic CMOS circuits resulted in significant reduction in design complexity and substantial performance gains in speed and area. The thesis also addresses a generalization of the priority queue concept to a systolic parallel priority queue (PPQ) which can be scaled to meet the requirements of ultra high-speed links using standard CMOS technology. The PPQ has several applications in implementing real-time fair schedulers or buffer management algorithms in packet routers. The PPQ maintains prioritized access to the data it contains at all times, and the access time to the data is fixed and independent of the PPQ size, i.e. O(l)-time access. The proposed systolic PPQ is rate-adaptive in the sense that the PPQ operates correctly even when the queue input rate and output rate are different. decoupling of the input and output packet flow rates is a distinguishing feature of the PPQ concept because in practice the output rate of the queue is controlled by the available link bandwidth which may vary (or even become zero) independent of the packet arrival rate.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat