Pi-PIFO: A scalable pipelined PIFO memory management architecture

Quality of service (QoS) provisioning is rapidly becoming an assumed attribute of core packet switching systems. Substantial work has been focused on designing algorithms which offer strict QoS guarantees under a broad range of traffic scenarios. The majority of these scheduling algorithms can be realized utilizing push-in-first-out (PIFO) queues, which are characterized by allowing packets to enter the queue at arbitrary locations while departures occur from the head of line position only. Although the PIFO queueing mechanism has received attention, it is generally considered impractical from a hardware implementation perspective. This is due primarily to the computational complexity involved in placing arriving packets in a generic PIFO queue. The iPIFO memory management scheme has been proposed in which additional data structures are employed to facilitate the realization of PIFO queues. While iPIFO does overcome some of the complexities involved in implementing PIFO queueing, it relies on the existence of a high-speed memory device which supports a large number of concurrent read and write operations. Such assumption substantially limits scalability. This paper introduces Pi-PIFO, a pipelined PIFO queuing memory management architecture, which requires modest memory bandwidth, with sub-linear dependency on the queue size (N), thereby overcoming the limitations previously associated with realizing PIFO queueing. Moreover, the logic complexity of the architecture is O(log N), rendering the approach highly scalable with respect to switch port densities and speeds.