仮想出力キューイング

ヘッドオブラインブロッキングに対処するネットワーク技術

仮想出力キューイング（VOQ ）は、特定のネットワークスイッチアーキテクチャで使用される技術であり、すべてのトラフィックを単一のキューに保持するのではなく、出力可能な場所ごとに個別のキューを維持する。これは、ヘッドオブラインブロッキングと呼ばれる一般的な問題に対処します。^[1]

説明

VOQでは、各入力ポートの物理バッファは、各出力ポートごとに個別の仮想キューを維持します。したがって、出力ポートの輻輳は、その特定の出力ポートの仮想キューのみをブロックします。同じ物理バッファ内の、異なる（輻輳していない）出力ポート宛てのパケットは、別の仮想キューに格納されるため、引き続き処理されます。従来の設定では、輻輳した出力ポート宛てのパケットがブロックされると、物理バッファ全体がブロックされ、結果としてヘッドオブラインブロッキングが発生していました。

VOQは効果的なスケジューリングアルゴリズムを用いることで100%のスループット性能を達成できることが実証されています。^[要出典]このスケジューリングアルゴリズムは、入力から出力へのパケットのサイクルごとの高速マッピングを実現できるはずです。VOQメカニズムは、 VOQを持たないクロスバースイッチよりもはるかに高いスループットを提供します。

高速VOQの設計と実装のためのアルゴリズムは数多く存在します。例えば、ニック・マッキーオンとスタンフォード大学のグループは1997年に設計を発表しました。^[2]

サービス品質と優先順位は同時代の文献に見られる拡張である。^[3]

VOQスケジューリングはしばしば「調停」（同時アクセスの希望を解決すること）と呼ばれますが、パケットの順序付け（「パケットスケジューリング」）はVOQ調停に続く追加のタスク^[4]です。

参考文献

^ Goudreau, Mark W.; Kolliopoulos, Stavros G.; Rao, Satish B. (2000). 「入力キュー型スイッチのスケジューリングアルゴリズム：ランダム化手法と実験的評価」. Proceedings IEEE INFOCOM 2000. コンピュータ通信会議. 第19回IEEEコンピュータ・通信学会合同会議 (カタログ番号00CH37064) . 第3巻. pp. 1634– 1643. CiteSeerX 10.1.1.42.5126 . doi :10.1109/INFCOM.2000.832562. ISBN 978-0-7803-5880-5. S2CID 11834666。
^ McKeown, Nick ; Izzard, Martin ; Mekkittikul, Adisak ; Ellersick, Bill ; Horowitz, Mark (1997). 「Tiny Tera: a packet switch core」(PDF) . IEEE Micro . 17 : 26–33 . arXiv : cs/9810006 . doi :10.1109/40.566194. S2CID 1909255.
^ Schoenen, Rainer; Post, Guido; Sander, Gerald (1999). 「100%スループットを実現する入力キュー型スイッチの優先アービトレーション」IEEE ATM Workshop '99 Proceedings (Cat. No. 99TH8462) . pp. 253– 258. CiteSeerX 10.1.1.668.8621 . doi :10.1109/ATM.1999.786865. ISBN 978-4-88552-164-5. S2CID 14749858。
^ Schoenen, Rainer; Hying, Roman (1999). 「仮想出力キュースイッチ向け分散セルスケジューリングアルゴリズム」.ユニバーサルサービスのためのシームレスな相互接続. グローバル電気通信会議. GLOBECOM'99. (カタログ番号99CH37042) . 第2巻. pp. 1211– 1215. CiteSeerX 10.1.1.29.4129 . doi :10.1109/GLOCOM.1999.829963. ISBN 978-0-7803-5796-9. S2CID 1649478。

[1] Goudreau, Mark W.; Kolliopoulos, Stavros G.; Rao, Satish B. (2000). 「入力キュー型スイッチのスケジューリングアルゴリズム：ランダム化手法と実験的評価」. Proceedings IEEE INFOCOM 2000. コンピュータ通信会議. 第19回IEEEコンピュータ・通信学会合同会議 (カタログ番号00CH37064) . 第3巻. pp. 1634– 1643. CiteSeerX 10.1.1.42.5126 . doi :10.1109/INFCOM.2000.832562. ISBN 978-0-7803-5880-5. S2CID 11834666。

[2] McKeown, Nick ; Izzard, Martin ; Mekkittikul, Adisak ; Ellersick, Bill ; Horowitz, Mark (1997). 「Tiny Tera: a packet switch core」(PDF) . IEEE Micro . 17 : 26–33 . arXiv : cs/9810006 . doi :10.1109/40.566194. S2CID 1909255.

[3] Schoenen, Rainer; Post, Guido; Sander, Gerald (1999). 「100%スループットを実現する入力キュー型スイッチの優先アービトレーション」IEEE ATM Workshop '99 Proceedings (Cat. No. 99TH8462) . pp. 253– 258. CiteSeerX 10.1.1.668.8621 . doi :10.1109/ATM.1999.786865. ISBN 978-4-88552-164-5. S2CID 14749858。

[4] Schoenen, Rainer; Hying, Roman (1999). 「仮想出力キュースイッチ向け分散セルスケジューリングアルゴリズム」.ユニバーサルサービスのためのシームレスな相互接続. グローバル電気通信会議. GLOBECOM'99. (カタログ番号99CH37042) . 第2巻. pp. 1211– 1215. CiteSeerX 10.1.1.29.4129 . doi :10.1109/GLOCOM.1999.829963. ISBN 978-0-7803-5796-9. S2CID 1649478。