OBM: Optimal Shared Packet Buffer Management in Switches
To better utilize the switch memory for packet buffering, the packet buffer in datacenter switches is shared across all switch ports. As a result, the buffer sharing algorithm is extremely critical to the performance of datacenter switches and networks. Previous work has shown that push-out algorithms for buffer sharing achieve much higher throughput than drop-tail algorithms. However, switches today still implement drop-tail algorithms, as it is extremely challenging to implement push-out operations at the line rate of datacenter switches. In this paper, we present OBM, a new system for managing shared packet buffers in network switches based on the best-known online push-out algorithm for buffer sharing called the Longest Queue Drop (LQD). OBM makes two key contributions. First, OBM extends the classic LQD algorithm by making it priority-aware for packet admission and push-out, without sacrificing LQD's throughput guarantee. Second, OBM makes LQD-based push-out practical to implement on modern switches, by proposing a novel hardware pipeline and tree-based switching interconnect that can perform push-out operations at line rate with low latency and low hardware resource usage. We synthesize the OBM's design on both an FPGA and an ASIC compiler. Our prototype of the OBM switch is both high performance and consumes nominal hardware resources. Using large-scale network simulations, we show that OBM not only significantly outperforms state-of-the-art drop-tail and push-out buffer management schemes, but also matches the performance of ideal albeit impractical LQD for a single priority class while significantly outperforming it for multiple priority classes.