BASEL (Buffering Architecture SpEcification Language)

Kirill Kogan, Danushka Menikkumbura, Gustavo Petri, Youngtae Noh, Sergey I. Nikolenko, Patrick EugsterarXiv 2015 · arXiv

Introduction

In modern data center networking, traffic bursts are an unavoidable reality. When packet arrival rates exceed port capacity, buffers must manage the overflow. The logic governing these buffers—determining which packets to admit, drop, or prioritize—is critical for network performance. Traditionally, these architectures are either inflexible hardware implementations or require complex, low-level programming. BASEL (Buffering Architecture SpEcification Language) addresses this gap by providing a high-level, declarative domain-specific language (DSL) for defining sophisticated buffering policies with minimal overhead.

The BASEL Framework

BASEL simplifies buffer management by decomposing complex procedural algorithms into a few core primitives and declarative comparators. The language is built around four primary entities:

  1. Packets: Objects with attributes like size and latency bounds.
  2. Queues: Containers that use procPrio (processing priority) and admPrio (admission priority) comparators.
  3. Ports: Entities that manage sets of queues using schedPrio (scheduling priority).
  4. Buffers: Global entities that manage shared space across multiple queues.

The core innovation is the use of comparators. Instead of coding a full "Longest-Queue-Drop" algorithm, a developer defines a simple Boolean comparison (e.g., q1.currSize > q2.currSize) to resolve congestion.

Comparison of single-queue (a) and multi-queue (b) buffer management logic.

As shown in the figure above, BASEL can express different architectural styles, such as single-queue buffers where packets might be "pushed out" to make room for higher-priority arrivals, or multi-queue systems where drops are handled per-queue.

Evaluation and Results

The authors implemented BASEL on top of Open vSwitch (OVS) and the Linux Traffic Control (TC) subsystem, using B-Tree data structures to maintain packet ordering efficiently. Evaluation was conducted using discrete simulators (NS-2, OMNet++) and a physical 3-node testbed.

Performance and Efficiency

In physical testbeds, the prioritization logic introduced only a 2% to 4% performance degradation compared to standard FIFO queues. This demonstrates that high-level abstraction does not necessarily come at the cost of line-rate performance in software switches.

Theoretical Optimality

A key insight of BASEL is the decoupling of admission priority from processing priority. By setting these independently, researchers can achieve theoretically optimal throughput.

Competitive ratios (OPT/ALG) for various admission and processing priority combinations.

The table above illustrates that while standard FIFO/FIFO approaches have a competitive ratio of O(k), the combination of rsrpt() for admission and srpt() for processing achieves a competitive ratio of 1, reaching optimality.

Conclusion

BASEL provides a powerful abstraction for network engineers to manage the "economic" trade-offs of traffic handling. While currently optimized for software-based virtual switches, future work aims to map these dynamic structures to the more rigid memory constraints of hardware switching ASICs and extend the language for global network-wide policies.

Summary updated

Abstract

Buffering architectures and policies for their efficient management constitute one of the core ingredients of a network architecture. In this work we introduce a new specification language, BASEL, that allows to express virtual buffering architectures and management policies representing a variety of economic models. BASEL does not require the user to implement policies in a high-level language; rather, the entire buffering architecture and its policy are reduced to several comparators and simple functions. We show examples of buffering architectures in BASEL and demonstrate empirically the impact of various settings on performance.
BibTeX
@misc{kogan2015basel,
  author = {Kirill Kogan and Danushka Menikkumbura and Gustavo Petri and Youngtae Noh and Sergey I. Nikolenko and Patrick Eugster},
  title = {{BASEL (Buffering Architecture SpEcification Language)}},
  year = {2015},
  eprint = {1510.04235},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.04235},
}
Figure