Improved Lower Bounds for Competitive Ratio of Multi-Queue Switches in QoS Networks(<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 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(α/<α-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.
- 一般社団法人電子情報通信学会の論文
- 2005-05-01
著者
-
Itoh Toshiya
Global Scientific Information And Computing Center (gsic) Tokyo Institute Of Technology
-
Itoh Toshiya
Tokyo Inst. Of Technol. Tokyo Jpn
-
Nagumo Takanobu
Department Of Information Processing Tokyo Institute Of Technology
関連論文
- Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length
- FOREWORD (Special Section on Cryptography and Information Security)
- Competitive Analysis of Multi-Queue Preemptive QoS Algorithms for General Priorities(Discrete Mathematics and Its Applications)
- Approximation Algorithms for the Highway Problem under the Coupon Model
- Approximation Preserving Reductions among Item Pricing Problems
- Constructing Families of ε-Approximate k-Wise Independent Permutations(Discrete Mathematics and Its Applications)
- Special Section on Cryptography and Information Security
- A Note on the Relationships among Certified Discrete Log Cryptosystems
- Online Algorithms for Convex Case Capital Investment
- Improved Approximation Lower Bounds for TSP with Distances One and Two
- Improved Lower Bounds for Competitive Ratio of Multi-Queue Switches in QoS Networks(Discrete Mathematics and Its Applications)