Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms

In this paper, we consider the online buffer management problem, which formulates the problem of managing network switches supporting Quality of Service guarantee. We improve competitive ratios of the 2-value multi-queue switch model, where the value of a packet is restricted to 1 or α(≥1). We use a similar approach as Azar and Richter (STOC 2003 and Algorithmica 43(1-2), 2005) did for the multi-value multi-queue switch model. Namely, we show that the competitive ratio of “the relaxed model” of the 2-value multi-queue switch model is at most x=min⁡{c+2−cα(2−c)+c−1,cα}, if the competitive ratio of an online algorithm for the unit-value multi-queue switch model is at most c. Azar and Richter's technique implies that if the competitive ratio of the 2-value single-queue switch model is x′, then the competitive ratio of the 2-value multi-queue switch model is at most xx′. We obtain several results using known c and x′.