パケット損失を防止するスケジューリングアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
現在のネットワーク通信におけるパケットロスはルータでバッファが足りなくなるのが原因である。本稿では、ルータでオンラインスケジューラがm本のキューからパケットをスケジューリングする際に、どれだけバッファがあればパケットロスを防げるかを調べる。少ないバッファ量でパケットロスを防ぐには最大キュー長を小さく抑える必要があり、この新しい問題を我々はBalanced Scheduling Problem(BSP)と名付けた。BSPはタスクが負のコストを持つことを許す新しい負荷分散問題である。オンラインスケジューリングアルゴリズムの評価は、パケットロスを起こさない最適オフラインアルゴリズムの何倍のバッファがあればパケットロスが起きないかという競合比を使って行った。その結果、(1)いかなる決定的/確率的アルゴリズムもΩ(log m)-competitiveより良くない、(2)GREEDYアルゴリズムはΟ(log m)-competitiveを達成し、ほぼ最適となるという結果を得た。
- 一般社団法人情報処理学会の論文
- 2001-07-27