An Experimental Study of New and Known Online Packet Buffering Algorithms

作者：Albers Susanne; Jacobs Tobias^*

来源：Algorithmica, 2010, 57(4): 725-746.

DOI：10.1007/s00453-008-9230-y

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

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.

• 出版日期2010-8