ポート間公平性を考慮した低遅延スケジューリングアルゴリズムの提案

摘要

Head of Line（HoL）ブロッキングを回避する入力バッファ型スイッチとして，各入力ポートにバッファを用意するVirtual Output Queue（VOQ）入力バッファ型スイッチが提案されている．複数のVOQ入力バッファ型スイッチのスケジューリングアルゴリズムが提案されている．代表的なアルゴリズムとして低遅延を実現し，スタベーションを回避するiSLIP，高いポート間公平性をもつTwo-Dimensional Round Robin（2DRR）スケジューリングアルゴリズムがある．本論文では，ポート間公平性をもち，より低遅延なスイッチングを実現することを目的として，VOQ入力バッファ型スイッチに対する階層化スケジューリングアルゴリズムを提案する．N 入力 N 出力スイッチにおいてすべての入出力対のパターンを尽くすことで出力ポートが空いているにもかかわらずパケットが出力されない状態の発生頻度を低減する．N 入力 N 出力スケジューリングを N より小さい単位（ユニットと呼ぶ）に分割して行う．ユニット間の公平性はスイッチングを行う各ユニットの優先順位を逐次ずらすことにより実現する．シミュレーションにより提案スケジューリングアルゴリズムの有効性を評価する．