2ポート共有メモリ型スイッチにおけるオンラインバッファ管理アルゴリズムの厳密な競合比解析

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}$ に改良した.