
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Competitive Analysis of MultiQueue Preemptive QoS Algorithms for General Priorities
Toshiya ITOH Noriyuki TAKAHASHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E89A
No.5
pp.11861197 Publication Date: 2006/05/01 Online ISSN: 17451337
DOI: 10.1093/ietfec/e89a.5.1186 Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: quality of service (QoS), multiqueue switches, multipriority, preemption, competitive ratio,
Full Text: PDF>>
Summary:
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 multiqueue preemptive QoS problem with priority between 1/α and 1, i.e., for any α ≥ 1, the algorithm TLH is (31/α)competitive. This is a generalization of known resultsfor the case that packets have only priority 1 (α =1), the algorithm GREEDY (or TLH) is 2competitive; for the case that packets have priorities between 0 and 1 (α = ∞), the algorithm TLH is 3competitive. Then we consider the lower bounds for the competitive ratio of multiqueue preemptive QoS problem with priority between 0 and 1, and show that the competitive ratio of any multiqueue preemptive QoS algorithm is at least 1.514.

