Online buffer management for transmitting packets with processing cycles

In this study, we consider the model with constant density from a theoretical perspective. We first propose some lower bounds for the problem. Azar and Gilon obtained a 4-competitive algorithm for the online buffer management problem for packets with constant density. Here, we present a (2+1B−1)-competitive algorithm for the case B>1 as well as its generalization to the multi-buffer model. Moreover, we prove that the competitive ratio of a deterministic online algorithm is at least four when the buffer size is one. We also conduct experiments to demonstrate the superior performance of the proposed online algorithm against the previous approach.