-
- KOBAYASHI Koji
- Graduate School of Informatics, Kyoto University
-
- MIYAZAKI Shuichi
- Academic Center for Computing and Media Studies, Kyoto University The Institute of Electronics, Information and Communication Engineers
-
- OKABE Yasuo
- Academic Center for Computing and Media Studies, Kyoto University The Institute of Electronics, Information and Communication Engineers
この論文をさがす
抄録
The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered. In this paper, we focus on shared memory switches with preemption. We prove that the competitive ratio of the Longest Queue Drop (LQD) policy is 4M-4/3M-2 in the case of N=2, where N is the number of output ports in a switch and M is the size of the buffer. This matches the lower bound given by Hahne, Kesselman and Mansour. Also, in the case of arbitrary N, we improve the competitive ratio of LQD from 2 to 2-1/Mmink=1,2,…,N{[M/k]+K-1}.
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E91-D (8), 2105-2114, 2008
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390001204377755648
-
- NII論文ID
- 10026805230
-
- NII書誌ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用不可