Buffer management problems
Lea Epstein, R. vanStee · 2004
In recent years, there has been a lot of interest in Quality of Service (QoS) networks. In regular IP networks, packets are indistinguishable and in case of overload any packet may be dropped. In a commercial environment, it is much more preferable to allow better service to higher-paying customers or customers with critical requirements. The idea of Quality of Service guarantees is that packets are marked with values which indicate their importance. This naturally leads to decision problems at network switches when many packets arrive and overload occurs. In this paper, we give an overview of several models that have been studied in this area from an online perspective. These models differ by restrictions such as bounded delay, bounded size of queue etc. We first present results for a single buffer in Section 1 and then for multiple buffers in Section 2. This paper is not meant as a comprehensive survey of the work in this area. There are many more variations of these problems that have been studied, for instance, multiple output buffers [14]. Our goal was merely to give a taste of this problem area, and we hope you enjoy it. 1 Single buffer We consider a QoS buffering system that is able to hold B packets. Time is slotted. At the beginning of a time step a set of packets (possibly empty) arrives and at the end of the time step a single packet may