Design of packet-fair queuing schedulers using a RAM-based searching engine

H. Jonathan Chao, Yau Ren Jenq, Xiaolei Guo, Cheuk H. Lam

Research output: Contribution to journalArticlepeer-review


The implementation of packet-fair queuing (PFQ) schedulers, which aim at approximating the generalized processor sharing (GPS) policy, is a central issue for providing multimedia services with various quality-of-service (QoS) requirements in packet-switching networks. In the PFQ scheduler, packets are usually time stamped with a value based on some algorithm and are transmitted with an increasing order of the time-stamp values. One of the most challenging issues is to search for the smallest time-stamp value among hundreds of thousands of sessions. In this paper, we propose a novel RAM-based searching engine (RSE) to speed up the searching process by using the concept of hierarchical searching with a tree data structure. The time for searching the smallest time stamp is independent of the number of sessions in the system and is only bounded by the memory accesses needed. The RSE can be implemented with commercial memory and field programmable gate array (FPGA) chips in a cost-effective manner. With the extension of the RSE, we propose a two-dimensional (2-D) RSE architecture to implement a general shaper-scheduler. Other challenging issues, such as time-stamp overflow and aging, are also addressed in the paper.

Original languageEnglish (US)
Pages (from-to)1105-1126
Number of pages22
JournalIEEE Journal on Selected Areas in Communications
Issue number6
StatePublished - Jun 1999

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Design of packet-fair queuing schedulers using a RAM-based searching engine'. Together they form a unique fingerprint.

Cite this