Access count of this item: 82

Files in This Item:
File Description SizeFormat 
IEICE_tec.rep_COMP2007-26.pdf320.06 kBAdobe PDFView/Open
Title: A Tight Upper Bound on Online Buffer Management for Two-port Shared-Memory Switches
Other Titles: 2ポート共有メモリ型スイッチにおけるオンラインバッファ管理アルゴリズムの厳密な競合比解析
Authors: Kobayashi, Koji M.
Miyazaki, Shuichi  kyouindb  KAKEN_id
Okabe, Yasuo  kyouindb  KAKEN_id
Author's alias: 小林, 浩二
宮崎, 修一
岡部, 寿男
Keywords: Competitive analysis
Shared memory switches
Buffer management
Issue Date: 29-Jun-2007
Publisher: Institute of Electronics, Information and Communications Engineers (IEICE)
Journal title: 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報
Volume: 107
Issue: 127
Start page: 63
End page: 70
Thesis number: COMP2007-26
Abstract: The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarant ee. 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$) po licy is $frac{4M-4}{3M-2}$ in the case of $N=2$, where $N$ is the numbe r of output ports in a switch and $M$ is the size of the buffer. This ma tches the lower bound given by Hahne, Kesselman and Mansour. Also, in th e case of arbitrary $N$, we improve the competitive ratio of $LQD$ from $2-frac{1}{N}$ to $2 - frac{1}{M} min_{K = 1, 2, ..., N}{ lfloor f rac{M}{K} rfloor + K - 1}$.
オンラインバッファ管理問題は, 近年のネットワーク運用における主要な論点となっている QoS(Quality of Service) 保証実現のための, スイッチなどのキュー管理をオンライン問題として定式化した問題であり, 様々なモデルが考案されている. 本論文ではその中の1つである共有メモリ型スイッチを扱ったモデルを取り上げる. 我々は, スイッチの出力ポートの数Nが2であるときに, アルゴリズム Longest Queue Drop ($LQD$) の競合比が $frac{4M-4}{3M-2}$ であることを示した. ここで, Mはスイッチのバッファのサイズである. これは, Hahne らによって示された下限に一致する. また, 任意のNの場合に, $LQD$の競合比を2から $2-frac{1}{N}$ to $2 - frac{1}{M} min_{K = 1, 2, ..., N}{ lfloor f rac{M}{K} rfloor + K - 1}$ に改良した.
Rights: © 2007 IEICE(電子情報通信学会)
Related Link:
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks

Export Format: 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.