Comparison-Based Buffer Management in QoS Switches

• Published in: Algorithmica 2018-03, Vol.80 (3), p.1073-1092
• Main Authors: Al-Bawani, Kamal, Englert, Matthias, Westermann, Matthias
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Buffers; Competition; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Deadlines; Delay; Electronic devices; FIFO; Lower bounds; Management; Mathematics of Computing; Packet transmission; Quality of service; Quality of service architectures; Scheduling algorithms; Sequences; Special Issue on Theoretical Informatics; Switches; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-017-0393-2

The following online problem arises in network devices, e.g., switches, with quality of service (QoS) guarantees. In each time step, an arbitrary number of packets arrive at a single buffer and only one packet can be transmitted. The differentiated service concept is implemented by attributing each packet with a non-negative value corresponding to its service level. The goal is to maximize the total value of transmitted packets. We consider two models of this problem, the FIFO and the bounded-delay model. In the FIFO model, the buffer can store a limited number of packets and the sequence of transmitted packets has to be a subsequence of the arriving packets. In this model, a buffer management algorithm can reject arriving packets and preempt buffered packets. In the bounded-delay model, the buffer has unbounded capacity, but each packet has a deadline and packets can only be transmitted before their deadlines. Here, a buffer management algorithm determines the packet to be sent in each time step. We study comparison-based buffer management algorithms, i.e., algorithms that make their decisions based solely on the relative order between packet values with no regard to the actual values. This kind of algorithm proves to be robust in the realm of QoS switches. Kesselman et al. (SIAM J Comput 33(3):563–583, 2004 ) present two deterministic comparison-based online algorithms, one for each model, which are 2-competitive. For a long time, it has been an open problem, whether a comparison-based online algorithm exists, in either model, with a competitive ratio below 2. In the FIFO model, we present a lower bound of 1 + 1 / 2 ≈ 1.707 on the competitive ratio of any deterministic comparison-based algorithm and give an algorithm that matches this lower bound in the case of monotonic sequences, i.e., packets arrive in a non-decreasing order according to their values. In the bounded-delay model, we show that no deterministic comparison-based algorithm exists with a competitive ratio below 2. In the special s -uniform case, where the difference between the arrival time and deadline of any packet equals s , we present a randomized comparison-based algorithm that is 5 / 3-competitive.