CS-534: Packet Switch Architecture
Spring 2004
Department of Computer Science
© copyright: University of Crete, Greece

3.2   Multi-Queue Data Structures

[Up - Table of Contents]
[Prev - 3.1 Queueing Arch., HOL]

[3.3 Multicast Queueing - Next]

3.2.1   FIFO Buffer Memories

Single FIFO Queue in a Memory Block: Circular Buffer

Reminder: Circular Array Implementation of FIFO Queue

Multiple FIFO Queues with Statically Partitioned Space for each

Multiple FIFO Queues with Shared Space 1: shifting (impractical)

Multiple FIFO Queues with Shared Space 2: linked lists of blocks

See Exercises 3 for a discussion of how large the segment (block) size should be.

3.2.2   Multiple FIFO Queues Sharing One Memory

Multi-queue buffer memory using linked lists of memory blocks


Enqueue/Dequeue: basic cases

Enqueue/Dequeue: exceptional cases

Cost-performance tradeoffs

For an example of a highly-pipelined implementation of managing multiple linked-list queues, see:

NxtPtr inside data memory: free block preallocation

Reference: A. Nikologiannis, M. Katevenis: "Efficient Per-Flow Queueing in DRAM at OC-192 Line Rate using Out-of-Order Execution Techniques", Proc. IEEE Int. Conf. on Communications (ICC'2001), Helsinki, Finland, June 2001, pp. 2048-2052; http://archvlsi.ics.forth.gr/muqpro/queueMgt.html

Packet size, block size, line rate, queue Op rate

See also exercises 2.3, 2.4, and exercises 3 for discussions on access rate and segment (block) size.

Queue Op rate, free list rate, free list bypass

Dropping a Segment

Dropping a Packet

[Exercises - 4. Linked-List Queues]
[Prev - 3.1 Queueing Arch., HOL]

[3.3 Multicast Queueing - Next]

Up to the Home Page of CS-534
© copyright University of Crete, Greece.
Last updated: 16 Apr. 2004, by M. Katevenis.