論文

査読有り
2017年5月

Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms

Theoretical Computer Science
  • Koji M. Kobayashi
  • ,
  • Shuichi Miyazaki
  • ,
  • Yasuo Okabe

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

エクスポート
BibTeX RIS