Tight analysis of priority queuing for egress traffic

Recently, the problems of evaluating performances of switches and routers have been formulated as online problems, and a great amount of results have been presented. In this paper, we focus on managing outgoing packets (called egress traffic) on switches that support Quality of Service (QoS), and analyze the performance of one of the most fundamental scheduling policies Priority Queuing (PQ) using competitive analysis. We formulate the problem of managing egress queues as follows: An output interface is equipped with m queues, each of which has a buffer of size B. The size of a packet is unit, and each buffer can store up to B packets simultaneously. Each packet is associated with one of m priority values αj (1 ≤ j ≤ m), where α1 ≤ α2 ≤ ⋅⋅⋅ ≤ αm  , α1=1,α1=1, and αm=ααm=α and the task of an online algorithm is to select one of m queues at each scheduling step. The purpose of this problem is to maximize the sum of the values of the scheduled packets.For any B and any m, we show that the competitive ratio of PQ   is exactly 2−minx∈[1,m−1]{αx+1∑j=1x+1αj}. That is, we conduct a complete analysis of the performance of PQ   using worst case analysis. Moreover, we show that no deterministic online algorithm can have a competitive ratio smaller than 1+α3+α2+αα4+4α3+3α2+4α+1.