Balancing Work and Size with Bounded Buffers

Kirill Kogan, Alejandro López-Ortíz, Sergey Nikolenko, Gabriel Scalosub, Michael Segal

Abstract

We consider the fundamental problem of managing a bounded size queue buffer where traffic consists of packets of varying size, where each packet requires several rounds of processing before it can be transmitted from the queue buffer. The goal in such an environment is to maximize the overall size of packets that are successfully transmitted. This model is motivated by the ever-growing ubiquity of network processors architectures, which must deal with heterogeneously-sized traffic, with heterogeneous processing requirements. Our work addresses the tension between two conflicting algorithmic approaches in such settings: the tendency to favor packets with fewer processing requirements, thus leading to fast contributions to the accumulated throughput, as opposed to preferring packets of larger size, which imply a large increase in throughput at each step. We present a model for studying such systems, and present competitive algorithms whose performance depend on the maximum size a packet may have, and maximum amount of processing a packet may require. We further provide lower bounds on algorithms performance in such settings.

Introduction

In modern networking, routers have evolved into complex "Network Processors" (NPs) that do more than just forward traffic. They perform deep packet inspection, firewalling, and encryption. This evolution introduces a two-dimensional challenge for buffer management:

  1. Heterogeneous Sizes: Packets vary significantly in length (e.g., small ACK packets vs. large video frames).
  2. Heterogeneous Processing: Different packets require different amounts of "work" (CPU cycles). A large packet might be computationally simple, while a small one might be expensive.

When a buffer reaches capacity, the management policy must decide which packets to keep. Prioritizing low processing requirements clears the queue quickly, while prioritizing large packets maximizes the "value" (bytes) of each transmission. This research explores the fundamental tension between work and size in bounded buffers.

System Model and Methods

The authors utilize a slotted-time model to analyze buffer management. Each time slot consists of three distinct phases: transmission of a completed packet, arrival of new packets, and processing of the packet currently at the head of the queue.

The slotted-time model illustrating the sequence of transmission, arrival (including packet drops when the buffer is full), and processing.

Algorithms are evaluated using competitive analysis, which compares an "online" algorithm's performance against an "optimal" offline algorithm that has full knowledge of future arrivals. Two primary management styles are examined:

  • Non-Push-Out (NPO): Packets admitted to the buffer remain until they are either fully processed and transmitted or the buffer is cleared.
  • Push-Out (PO): A newly arrived packet can displace an existing packet if it is deemed "better" according to the priority discipline.

Three priority disciplines are tested within these frameworks: Shortest Remaining Processing Time (SRPT), which focuses on quick wins; Longest Packet (LP), which targets high-value transmissions; and Most Effective Packet (MEP), a hybrid approach prioritizing packets based on the ratio of their size to their processing requirement.

Key Insights

  • The Greed Trap: Simple greedy policies (NPO) perform poorly in worst-case scenarios. Their competitive ratio is tied to the product of maximum size ($L$) and maximum work ($k$), potentially being $kL$ times worse than optimal.
  • The Power of Push-Out: Allowing the buffer to drop partially processed packets in favor of superior ones significantly improves the competitive ratio.
  • MEP as the "Goldilocks" Policy: The MEP policy consistently outperformed SRPT and LP in simulations, balancing the need for throughput with processing efficiency.
  • Throughput vs. Latency: While MEP maximizes total throughput (bytes), the LP policy often reduces average latency by clearing large data volumes, thereby reducing the total number of packets in the queue.

Theoretical Results

The paper establishes formal bounds on the competitive ratios for these policies. The results highlight that SRPT's performance is primarily bounded by packet size ($L$), while LP's performance is bounded by processing cycles ($k$).

Formal scorecard of competitive ratio lower and upper bounds for NPO and PO policies under various priority disciplines.

In simulations using synthetic traces (Markov-modulated Poisson processes), MEP maintained near-optimal performance even under high traffic intensity and significant processing heterogeneity.

Conclusion and Future Work

A key theoretical gap remains: the upper bound for the MEP policy is still an open problem, despite its superior empirical performance. Additionally, while this work focuses on single-core processors ($C=1$), future research could extend these models to multi-core environments where multiple packets are processed in parallel. The lack of real-world traces with per-packet CPU cycle data also presents a challenge for further empirical validation.

Summary updated

Abstract

We consider the fundamental problem of managing a bounded size queue buffer where traffic consists of packets of varying size, where each packet requires several rounds of processing before it can be transmitted from the queue buffer. The goal in such an environment is to maximize the overall size of packets that are successfully transmitted. This model is motivated by the ever-growing ubiquity of network processors architectures, which must deal with heterogeneously-sized traffic, with heterogeneous processing requirements. Our work addresses the tension between two conflicting algorithmic approaches in such settings: the tendency to favor packets with fewer processing requirements, thus leading to fast contributions to the accumulated throughput, as opposed to preferring packets of larger size, which imply a large increase in throughput at each step. We present a model for studying such systems, and present competitive algorithms whose performance depend on the maximum size a packet may have, and maximum amount of processing a packet may require. We further provide lower bounds on algorithms performance in such settings.
BibTeX
@article{kogan2016balancing,
  author = {Kirill Kogan and Alejandro López-Ortíz and Sergey Nikolenko and Gabriel Scalosub and Michael Segal},
  title = {{Balancing Work and Size with Bounded Buffers}},
  journal = {J. Netw. Comput. Appl.},
  year = {2016},
  doi = {10.1016/j.jnca.2016.07.010},
}
Figure