Loss-bounded analysis for differentiated services

Abstract

We consider a network providing Differentiated Services (Diffserv) which allow network service providers to offer different levels of Quality of Service (QoS) to different traffic streams. We focus on loss and first show that only trivial bounds could be obtained by means of traditional competitive analysis. Then we introduce a new approach for estimating loss of an online policy called loss-bounded analysis. In loss-bounded analysis the loss of an online policy are bounded by the loss of an optimal offline policy plus a constant fraction of the benefit of an optimal offline policy. We derive tight upper and lower bounds for various settings of Diffserv parameters using the new loss-bounded model. We believe that loss-bounded analysis is an important technique that may complement traditional competitive analysis and provide new insight and interesting results.