Back to search

University of British Columbia

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

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
University of British Columbia
Year dc:date
2000

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kazemi-Nia, Mehdi

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/10812

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Kazemi-Nia, Mehdi. VLSI support for scheduling and buffer management in high speed packet-switched networks. doctoral thesis, University of British Columbia, 2000. http://hdl.handle.net/2429/10812