An experimental study of new and known online packet buffering algorithms

Susanne Albers, Tobias Jacobs

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


We present the first experimental study of online packet buffering algorithms for network switches. We consider a basic scenario in which m queues of size B have to be maintained so as to maximize the packet throughput. For this model various online algorithms with competitive factors ranging between 2 and 1.5 were developed in the literature. We first develop a new 2-competitive online algorithm, called HSFOD, which is especially designed to perform well under real-world conditions. In our experimental study we have implemented all the proposed algorithms, including HSFOD, and tested them on packet traces from benchmark libraries. We have evaluated the experimentally observed competitiveness, the running times, memory requirements and actual packet throughput of the strategies. The tests were executed for varying values of m and B as well as varying switch speeds. It shows that greedy-like strategies and HSFOD perform best in practice.

Original languageEnglish
Pages (from-to)725-746
Number of pages22
Issue number4
StatePublished - Aug 2010
Externally publishedYes


  • Algorithm engineering
  • Network switch
  • Online algorithm
  • Packet buffering
  • Performance analysis


Dive into the research topics of 'An experimental study of new and known online packet buffering algorithms'. Together they form a unique fingerprint.

Cite this