Search

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 x x ′ . We obtain several results using known c and x ′ . [ABSTRACT FROM AUTHOR]