!_]1に制限された決定性QoS問題に関して,その競合比の下界の解析を行い,任意のα[>!_]1に対して-もしα[>!_]α^*ならば1+/αln((α-1)/α)以上;もし1[>!_]α<α^*ならば1/(1-e^<-γ0>)以上-が成り立つことを示す.ただしα^* [~!~] 1.657でありγ_0は方程式e^<-γ>(1/α+γ)=1-e^γの根とする.またこの結果より,単一優先度決定性QoS問題に関して,その競合比の下界が1.466以上となることが容易に導出される(これは単一優先度決定性QoS問題の競合比に関する既知の下界1.366を改善するものである)." />
Presentation | 2004/3/9 Improved Lower Bounds for Competitive Ratio of Multi-Queue Switches in QoS Networks Toshiya ITOH, Takanobu NAGUMO, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | The recent 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 to 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, and show that for any α[>!_]1, 1+/α ln((α-1) 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Quality of Service (QoS) / Multi-Queue Switch / Multi-Priority Model / Competitive Ratio |
Paper # | COMP2003-89 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 2004/3/9(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Theoretical Foundations of Computing (COMP) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Improved Lower Bounds for Competitive Ratio of Multi-Queue Switches in QoS Networks |
Sub Title (in English) | |
Keyword(1) | Quality of Service (QoS) |
Keyword(2) | Multi-Queue Switch |
Keyword(3) | Multi-Priority Model |
Keyword(4) | Competitive Ratio |
1st Author's Name | Toshiya ITOH |
1st Author's Affiliation | Global Scientific Information and Computing Center, Tokyo Institute of Technology() |
2nd Author's Name | Takanobu NAGUMO |
2nd Author's Affiliation | Department of Computer Science, Tokyo Institute of Technology |
Date | 2004/3/9 |
Paper # | COMP2003-89 |
Volume (vol) | vol.103 |
Number (no) | 723 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |