Competitive Analysis of Multi-Queue Preemptive QoS Algorithms for General Priorities(<Special Section>Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
The recent burst growth of the Internet use overloads networking systems and degrades the quality of communications, e.g., bandwidth loss, packet drops, delay of responses, etc. To overcome such degradation of communication quality, the notion of Quality of Service (QoS) has received attention in practice. In general, QoS switches have several queues and each queue has several slots to store arriving packets. Since network traffic changes frequently, QoS switches need to control arriving packets to maximize the total priorities of transmitted packets, where the priorities are given by nonnegative values and correspond to the quality of service required to each packet. In this paper, we first derive the upper bounds for the competitive ratio of multi-queue preemptive QoS problem with priority between 1/α and 1, i.e., for any α≥1, the algorithm T_<LH> is (3-1/α)-competitive. This is a generalization of known results-for the case that packets have only priority 1 (α=1), the algorithm G_<REEDY> (or T_<LH>) is 2-competitive; for the case that packets have priorities between 0 and 1 (α=∞), the algorithm T_<LH> is 3-competitive. Then we consider the lower bounds for the competitive ratio of multi-queue preemptive QoS problem with priority between 0 and 1, and show that the competitive ratio of any multi-queue preemptive QoS algorithm is at least 1.514.
社団法人電子情報通信学会の論文
2006-05-01