Competitive queue policies for differentiated services

Abstract

We consider the setting of a network providing differentiated services. As is often the case in differentiated services, we assume the packets are tagged as either being high- or low-priority packets. Outgoing links in the network are serviced by a single FIFO queue. Our model gives a benefit of /spl alpha//spl ges/1 to each high-priority packet and a benefit of 1 to each low-priority packet. A queue policy controls which of the arriving packets are dropped and which enter the queue. Once a packet enters the queue it is eventually sent. The aim of a queue policy is to maximize the sum of the benefits of all the packets it delivers. We analyze and compare different queue policies for this problem using the competitive analysis approach, where the benefit of the online policy is compared to the benefit of an optimal offline policy. We derive both upper and lower bounds for the policies we consider, and in most cases our bounds are tight. We believe that competitive analysis gives important insight into the performance of these simple queuing policies.