2017年5月
Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms
Theoretical Computer Science
- ,
- ,
- 巻
- 675
- 号
- 開始ページ
- 27
- 終了ページ
- 42
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.tcs.2017.02.014
- 出版者・発行元
- ELSEVIER SCIENCE BV
In this paper, we consider the online buffer management problem, which formulates the problem of managing network switches supporting Quality of Service guarantee. We improve competitive ratios of the 2-value multi-queue switch model, where the value of a packet is restricted to 1 or alpha(>= 1). We use a similar approach as Azar and Richter (STOC 2003 and Algorithmica 43(1-2), 2005) did for the multi-value multi-queue switch model. Namely, we show that the competitive ratio of "the relaxed model" of the 2-value multi-queue switch model is at most x = min{c + 2-c/alpha(2-c)+(c-1), c alpha}, if the competitive ratio of an online algorithm for the unit-value multi-queue switch model is at most c. Azar and Richter's technique implies that if the competitive ratio of the 2-value single-queue switch model is x', then the competitive ratio of the 2-value multi-queue switch model is at most xx'. We obtain several results using known c and x'. (C) 2017 Elsevier B.V. All rights reserved.
- リンク情報
-
- DOI
- https://doi.org/10.1016/j.tcs.2017.02.014
- DBLP
- https://dblp.uni-trier.de/rec/journals/tcs/KobayashiMO17
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000401399700003&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/tcs/tcs675.html#journals/tcs/KobayashiMO17
- ID情報
-
- DOI : 10.1016/j.tcs.2017.02.014
- ISSN : 0304-3975
- eISSN : 1879-2294
- DBLP ID : journals/tcs/KobayashiMO17
- Web of Science ID : WOS:000401399700003