共有メモリ型スイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良

摘要

オンラインバッファ管理問題は，近年のネットワーク運用における主要な論点となっているQoS (Quality of Service)保証実現のための，スイッチなどのキュー管理をオンライン問題として定式化した問題であり，様々なモデルが考案されている．本論文ではその中の1つである共有メモリ型スイッチを扱ったモデルを取り上げる．我々は，アルゴリズムLongest Queue Policy (LQD)の競合比の既知の上限を2-1/Nに改良した．ここで，Nはスイッチの出力ポート数である．