2つのパケットからなるフレーム転送量最大化問題の厳密な競合比解析

概要

論文の詳細を見る
ネットワーク上におけるスイッチのキュー管理は,オンラインバッファ管理問題として定式化されており,多くのモデルが考案されている.我々は,そのモデルの1つである,k(≧2)個のパケットからなるフレーム転送量最大化問題(k-FTM)を扱う.この問題では,データ転送の単位である各フレームをパケットに分割し,転送完了後にフレームを再構成する際の手順に焦点を当てている.各フレームはk個のパケットから構成されており,そのパケットがスイッチ内のFIFOバッファに到着する.1つのフレームを構成するk個のパケットをバッファから転送した場合,そのフレームを再構成することが可能となる.しかし,バッファのサイズは制限されているため,到着したパケットは全てを転送できない場合がある.本問題の目的は,再構成するフレームの数を最大化することである.Kesselmanらは本問題に対して,k=2の場合でさえk-FTMに対する任意のアルゴリズムの競合比は発散することを示している.そこで,入力に制限を加えたk-FTM(k-OFTM)を考え,任意のバッファの大きさB(≧k)に対して,その競合比が高々2kB/⌊B/k⌋+kとなるアルゴリズムを考案し,また,任意のB(≧k)に対して,任意のアルゴリズムの競合比の下限が少なくともB/⌊2B/k⌋であることを示した.我々は,2-OFTMの解析を行い,貧欲なアルゴリズムの競合比が高々3であること,また,任意のアルゴリズムの下限が3であることを示した.
2011-04-15

2つのパケットからなるフレーム転送量最大化問題の厳密な競合比解析

スポンサーリンク

概要

著者

関連論文

スポンサーリンク