マルチアクセス通信のためのグループ化2次元ラウンドロビンスケジューラの提案

概要

論文の詳細を見る
マルチアクセス通信におけるパケットスイッチのスケジューリングを行う機構の一つに, 各入力ポートに出力ポート別のFIFO方式の待ち行列をもつ2DRRスケジューラがある. この2DRRスケジューラは, 高いスループット, フェアネスを達成するが, N入力N出力スイッチに対して, 公平な割当機会を与えるためにはN+1が素数でなければならないという制約がある. また, スケジューリングに要する計算量と記憶容量はO(N^3)である. そこで本論文では, N個の入出力ポートをa_0×…×a_<m-1>(m≧2)に階層化するグループ化2DRRスケジューラを提案する. そして, 本スケジューラにより上述の制約が緩和され, また, a_<m-1>≦N^<1/2>としたとき, 本スケジューラの計算量がO(N^<5/2>)に, 記憶容量がO(N^2)に抑えられることを示す. 最後に, 計算機シミュレーション実験によって, a_<m-1>は4以上に設定すべきであり, その場合, フェアネスなどといった2DRRスケジューラの長所を失うことなく, 2DRR方式と同様の遅延特性をもつことを示す.
1999-04-25