Competitive Analysis of Buffer Policies With SLA Commitments

Overview

This paper considers an abstraction of the problem of managing buffers where traffic is subject to service level agreements (SLA). 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. Using competitive analysis, they have shown 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 arriving committed packet is ever dropped. Simulations of such traffic (alone and combined with additional best-effort traffic) show that the performance of the algorithm is in fact much better than analytical guarantees.