Competitive Buffer Management for Multi-Queue Switches in QoS Networks Using Packet Buffering Algorithms

摘要

The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service) guarantee. We focus on multi-queue switches in QoS networks proposed by Azar et al. To achieve good upper bounds, they introduced so-called "the relaxed model". Also, they showed that if the competitive ratio of the single-queue model is at most c, and if the competitive ratio of the relaxed model is at most c', then the competitive ratio of the multi-queue switch model is cc'. They proved that c'≤ 2, and obtained upper bounds on the competitive ratios for several multi-queue switch models.In this paper, we propose an online algorithm called DS (Dual Scheduling) for the competitive ratio of the relaxed model and obtain some better competitive ratios of the 2-value multi-queue switch model, where the value of packets is restricted to 1 and α(≥ 1). DS uses as subroutine any online algorithms A for the non-preemptive unit-value switch model, which has also been extensively studied. We prove that if the competitive ratio of A is at most c, then thecompetitive ratio of DS is at most (αc(2-c)+c~2-2c+2)/(α(2-c)+c-1), which is strictly better than 2.The followings are a couple of examples of the improvement on the competitive ratios of the 2-value multi-queue switch models using our result: (ⅰ) We have improved the competitive ratio of deterministic algorithms for the non-preemptive 2-value multi-queue switch model from 4 to 3.177 for large enough B, where B is the number of packets each queue can simultaneously store, (ⅱ) We have proved that the competitive ratio of randomized algorithms for the non-preemptive 2-value multi-queue switch model is at most (17)/2-(30)~(1/2) approx= 3.023 for large enough B.