Analysis of tri-stage memory array for high-speed packet buffers

The speed of high-performance switches and routers is often limited by the bandwidth of commercially available memories. Meanwhile, the rapid growth in network bandwidth accompanied by the slowly increasing memory speed makes the problem even harder over time. There are, in fact, several techniques to build faster memories. However, some are based on the ideas from computer systems, such as parallelism, interleaving and banking, which can hardly be applied directly to packet buffering, while the others like hybrid SRAM-DRAM packet buffers are restricted by the speed of SRAM and inapplicable as the link rate exceeds the speed of SRAM. Motivated by increasing the throughput of packet buffers with only common memory arrays, we present one particular packet buffer architecture called Tri-Stage Memory Array (TSMA) that can speed up the packet buffering and retrieving processes to an arbitrary high speed theoretically. To replenish TSMA, a memory management algorithm called Most Urgent Queue First (MUQF) is also described and analyzed. It is proved that TSMA architecture coupled with MUQF algorithm can guarantee a bounded delay for each packet under any traffic arrival pattern or scheduling algorithm. Moreover, we provide an alternative architecture of TSMA to achieve simple implementation.