@article{DAVYDOW2021107942,
title = {Competitive buffer management for packets with latency constraints},
journal = {Computer Networks},
volume = {189},
pages = {107942},
year = {2021},
issn = {1389-1286},
doi = {https://doi.org/10.1016/j.comnet.2021.107942},
url = {https://www.sciencedirect.com/science/article/pii/S1389128621000839},
author = {Alex Davydow and Pavel Chuprikov and Sergey I. Nikolenko and Kirill Kogan},
keywords = {Packets with deadlines, Buffer management, Competitive analysis},
abstract = {Modern datacenters are increasingly required to deal with latency-sensitive applications. Incorporation of multiple traffic characteristics (e.g., packet values and required processing requirements) significantly increases the complexity of buffer management policies. In this context two major questions arise: how to represent the latency in desired objectives and how to provide guarantees for buffer management policies that would hold across a wide variety of traffic patterns. In this work, we consider a single queue buffering architecture, where every incoming packet is prepended with intrinsic value, required processing, and slack (offset from the arrival time during which this packet should be transmitted); the buffer size is implicitly bounded by slack values. Our goal is to maximize a total transmitted value (weighted throughput). In these settings, we study worst-case performance guarantees of the proposed online algorithms by means of competitive analysis whose effectiveness is compared versus an optimal clairvoyant offline algorithm. We show non-constant general lower bounds that hold for arbitrary slack values and for slacks that are additively separated from processing requirements; for the case of a multiplicative separation, we present a novel buffer management policy SPQ (stack with priority queue) and show that it is at most 3-competitive. Our theoretical results are supported by a comprehensive evaluation study on CAIDA traces.}
}