Competitive Analysis of Buffer Policies with SLA Commitments

Boaz Patt-Shamir, Gabriel Scalosub, and Yuval Shavitt

Abstract:

We consider an abstraction of the problem of managing buffers where traffic is subject to service level agreements (SLA). In our abstraction of SLAs, some packets are marked as “committed” and the others are marked as “excess.” The service provider must on one hand deliver all committed packets, and on the other hand can get extra revenue for any excess packet delivered. We study online algorithms managing a buffer with limited space, whose task is to decide which packets should be delivered and which should be dropped. Using competitive analysis, we show how to utilize additional buffer space and link bandwidth so that the number of excess packets delivered is comparable to the best possible by any off-line algorithm, while guaranteeing that no committed packet is ever lost.