- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- VLSI support for scheduling and buffer management in...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
VLSI support for scheduling and buffer management in high speed packet-switched networks Kazemi-Nia, Mehdi
Abstract
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.
Item Metadata
Title |
VLSI support for scheduling and buffer management in high speed packet-switched networks
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2000
|
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.
|
Extent |
6750320 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-07-15
|
Provider |
Vancouver : University of British Columbia Library
|
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.
|
DOI |
10.14288/1.0065054
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2000-05
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
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.