IEICE TRANSACTIONS on Fundamentals
Competitive Analysis of Multi-Queue Preemptive QoS Algorithms for General Priorities
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 multi-queue preemptive QoS problem with priority between 1/α and 1, i.e., for any α ≥ 1, the algorithm TLH is (3-1/α)-competitive. This is a generalization of known results--for the case that packets have only priority 1 (α =1), the algorithm GREEDY (or TLH) is 2-competitive; for the case that packets have priorities between 0 and 1 (α = ∞), the algorithm TLH 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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.5 pp.1186-1197
- Publication Date
- 2006/05/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e89-a.5.1186
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Toshiya ITOH, Noriyuki TAKAHASHI, "Competitive Analysis of Multi-Queue Preemptive QoS Algorithms for General Priorities" in IEICE TRANSACTIONS on Fundamentals,
vol. E89-A, no. 5, pp. 1186-1197, May 2006, doi: 10.1093/ietfec/e89-a.5.1186.
Abstract: 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 TLH is (3-1/α)-competitive. This is a generalization of known results--for the case that packets have only priority 1 (α =1), the algorithm GREEDY (or TLH) is 2-competitive; for the case that packets have priorities between 0 and 1 (α = ∞), the algorithm TLH 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.5.1186/_p
Copy
@ARTICLE{e89-a_5_1186,
author={Toshiya ITOH, Noriyuki TAKAHASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Competitive Analysis of Multi-Queue Preemptive QoS Algorithms for General Priorities},
year={2006},
volume={E89-A},
number={5},
pages={1186-1197},
abstract={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 TLH is (3-1/α)-competitive. This is a generalization of known results--for the case that packets have only priority 1 (α =1), the algorithm GREEDY (or TLH) is 2-competitive; for the case that packets have priorities between 0 and 1 (α = ∞), the algorithm TLH 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.},
keywords={},
doi={10.1093/ietfec/e89-a.5.1186},
ISSN={1745-1337},
month={May},}
Copy
TY - JOUR
TI - Competitive Analysis of Multi-Queue Preemptive QoS Algorithms for General Priorities
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1186
EP - 1197
AU - Toshiya ITOH
AU - Noriyuki TAKAHASHI
PY - 2006
DO - 10.1093/ietfec/e89-a.5.1186
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2006
AB - 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 TLH is (3-1/α)-competitive. This is a generalization of known results--for the case that packets have only priority 1 (α =1), the algorithm GREEDY (or TLH) is 2-competitive; for the case that packets have priorities between 0 and 1 (α = ∞), the algorithm TLH 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.
ER -
English
