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

摘要

オンラインバッファ管理問題は,近年のネットワーク運用における主要な論点となっているQoS (Quality of Service)保証実現のための,スイッチなどのキュー管理をオンライン問題として定式化した問題であり,様々なモデルが考案されている.本論文ではその中の1つである共有メモリ型スイッチを扱ったモデルを取り上げる.我々は,スイッチの出力ポートの数Nが2であるときに、アルゴリズムLongest Queue Policy (LQD)の競合比が(4M-4)/(3M-2)であることを示した。 ここで,Mはスイッチのバッファのサイズである.これは、Hahneらによって示された下限に一致する.また、任意のNの場合に、LQDの競合比を2から2-1/M min_{⌊M/K⌋+K-1}に改良した.