Improved Lower Bounds for Competitive Ratio of Multi-Queue Switches in QoS Networks

Toshiya ITOH  Takanobu NAGUMO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.5   pp.1155-1165
Publication Date: 2005/05/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.5.1155
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
quality of service (QoS),  multi-queue switch,  multi-priority model,  competitive ratio,  

Full Text: PDF>>
Buy this Article




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 the 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 for each packet. In this paper, we derive lower bounds for the competitive ratio of deterministic multi-queue nonpreemptive QoS problem of priorities 1 and α 1: 1 + /α ln if α α*; 1/(1 - e-τ0) if 1 α < α*, where α* 1.657 and τ0 is a root of the equality that e(1/α + τ)=1 - e. As an immediate result, this shows a lower bound 1.466 for the competitive ratio of deterministic multi-queue nonpreemptive QoS problem of single priority, which slightly improves the best known lower bound 1.366.