# 相互結合網 ## 定義 相互結合網(interconnection network)とは、複数の入力端子と出力端子の間でパケットを中継する固定サイズのスイッチ群を、有向グラフとして構造化した通信ネットワークのことである。頂点はスイッチ(または入出力端子)、辺は配線を表し、パケットは入力端子からスイッチを経由して指定された出力端子へ届けられる。設計目標は入出力の対応を表す置換 `π` を実現するルーティング問題を解くことであり、その良し悪しは次の4指標で評価される: (1) **直径(diameter)** — 最短経路ルーティングでの最悪遅延、(2) **スイッチ数(switch count)** — ネットワークを構成する固定サイズスイッチの総数、(3) **レイテンシ(latency)** — ある基準(輻輳最小化など)で選んだルーティングの最長経路長、(4) **輻輳(congestion)** — 単一スイッチを通過する経路本数の最大値(ルーティング問題ごとに輻輳最小のルーティングを選んだ上でのmaximin)。この4指標を同時に最適化するネットワークは存在せず、トポロジ設計は本質的にトレードオフの選択である。代表的なトポロジには、経路が一意で直径・スイッチ数は小さいが輻輳が壊滅的な**完全二分木**、輻輳を2に抑える代わりにスイッチ数が`N^2`に爆発する**2次元アレイ**、両者を折衷する**バタフライネット**、そしてバタフライを2つ背中合わせに繋いでスイッチ数と直径をおよそ2倍にする代償に輻輳を1まで消し去る**Beneš ネット**がある。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 10 Communication Networks]] §10.2〜§10.9) 計算機アーキテクチャの実務的な設計論では、相互結合網は接続する装置数と距離スケールに応じてOCN(オンチップ)・SAN(システム/ストレージエリア)・LAN・WANの4領域に分類され、あらゆる領域に共通する4つの設計機能——**トポロジ**(どの経路がありうるか)・**ルーティング**(そのうちどれが許容されるか)・**アービトレーション**(経路がいつ使えるか)・**スイッチング**(経路がどう割り当てられるか)——によって記述される。トポロジはスイッチを終端装置に分散配置する**直接網**(メッシュ・トーラス・ハイパーキューブ)と、外部にスイッチファブリックを集約する**間接網**(crossbar・多段相互接続網)に大別され、後者はcrossbarのN²規模のスイッチコストをNlogN規模へ削減する代償にブロッキングを生む。パケットが有限資源への巡回的待ち合わせに陥る**デッドロック**は、資源に部分順序を課しつつ適応的な経路選択の余地を残す**仮想チャネル**(Duato's protocolなど)によって、経路の適応性を保ったまま回避できる。(Source: [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Appendix F Interconnection Networks]] §F.1, §F.3〜§F.5) ## 横断的知見 - **多段スイッチングネットワークという同じ対象を、組合せ論的指標と運用指標という異なる評価軸で捉える2つのソース**: 本概念の直接の出典である[[@2015__MIT__Mathematics for Computer Science - Chapter 10 Communication Networks]]は、輻輳=単一スイッチを通過する経路本数の最大値という離散数学的な指標で相互結合網を評価し、Beneš ネットが輻輳1を達成することを2彩色問題への帰着という証明技法で厳密に示す。一方、既存の[[データセンターネットワークトポロジ]]([[@2008__SIGCOMM__A Scalable Commodity Data Center Network Architecture]]ほか)は、同じく多段スイッチングネットワークであるFat-Tree/Closトポロジを、二分帯域幅・過剰購読比・商用スイッチのコスト効率という運用上の指標で評価する。同じ「入出力端子群を固定サイズスイッチの多段構成でどう結ぶか」という設計問題に対し、教科書は数学的最適性(輻輳の理論限界)を、実運用ソースは経済性・実装可能性を主眼に置いており、両者は補完的な評価軸を提供する。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 10 Communication Networks]], [[@2008__SIGCOMM__A Scalable Commodity Data Center Network Architecture]]) - **多段非閉塞ネットワークの起源はいずれも電話交換機**: 本章のBeneš ネットは1960年代にBell研究所のVáclav E. Benešが考案したものであり(Source: ch.10 §10.9)、既存[[データセンターネットワークトポロジ]]が記録するClosネットワークは1953年にCharles Closが電話交換機向けに設計したものである(Source: [[@2022__SpeakerDeck__Clos Network Topology 再入門]])。両者はともに1950〜60年代の電話交換トラフィック理論を起源とし、数十年後にそれぞれ独立に計算機科学の教科書とデータセンター設計の系譜へ受け継がれた点で共通する。ただし本章はBeneš ネットとClosネットワークの数学的な同値性・関係そのものには触れておらず、この対応は2つのソースを突き合わせて初めて見える系譜上の並行性の指摘にとどまる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 10 Communication Networks]], [[@2022__SpeakerDeck__Clos Network Topology 再入門]]) - **BenešネットはClosネットワークの中間段を再帰的に2×2まで分割した極限形であり、両者の対応関係は工学系教科書側に明示されている**: 本ページの既存の未解決の問いは、「Beneš ネットがClosネットワークの特殊ケースといえるか」を離散数学の教科書単独では確認できないとしていた。[[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Appendix F Interconnection Networks]] §F.4はこの対応を直接記述する——3段Clos網の多重経路性を中間段スイッチに再帰的に適用し、すべてのスイッチを2×2まで縮小すると、2(log₂N)−1段のBeneš網が得られ、これは再配置可能非閉塞(rearrangeably non-blocking)であると明示する。すなわちBeneš網はClos網の特殊ケースではなく、Clos網を「限界まで再帰分割した」極限形であり、離散数学の教科書が輻輳1という理論的最適性を証明する対象は、工学系文献では具体的な構成的手続き(3段Closの再帰的展開)によって導出されている。両ソースを合わせて初めて、抽象的な輻輳最小性の証明と具体的な構成手順の両方が揃う。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 10 Communication Networks]] §10.9, [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Appendix F Interconnection Networks]] §F.4) - **静的な組合せ論的「輻輳」と、H&P Appendix Fが採用する二分帯域幅+動的輻輳管理という2つの評価軸は、同じ「ホットリンクを避ける」問題を異なる形式で切り取っている**: 本ページの数学的定義における輻輳(単一スイッチを通過する経路本数の最大値、ルーティング問題ごとに固定されたmaximin指標)に対し、[[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Appendix F Interconnection Networks]] §F.4は静的トポロジ評価に二分帯域幅(ネットワークを二等分した際の切断リンク帯域和)というカット基準の指標を用い、さらに§F.7でトラフィックが動的に変動する現実の運用下で生じる輻輳(リンクが最大容量で稼働している状態そのもの)と、それがhead-of-line blockingと結びついて初めて性能劣化を招くという因果関係を区別する。同章はパケット破棄・リンクレベルのフロー制御(バックプレッシャ)・チョークパケットという3方式で動的輻輳に対処する枠組みを示しており、これは本ページの未解決の問いが指摘していた「静的な組合せ論的指標と動的な輻輳制御対象は異なる概念である」という区別を、工学側の文献で明確に裏付ける。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 10 Communication Networks]] §10.2〜§10.9, [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Appendix F Interconnection Networks]] §F.4, §F.7) ## 未解決の問い - 本章の輻輳(単一スイッチを通過する経路数の最大値という静的指標)と、データセンターネットワークの実運用で使われる動的輻輳制御([[データセンター輻輳制御]]、DCQCN/DCTCP等)の「輻輳」との対応は、H&P Appendix Fの二分帯域幅・パケット破棄/フロー制御/チョークパケットという枠組みによって評価軸の違いは明確になったが、「高輻輳(静的)トポロジは動的輻輳制御の負荷をどう増やすか」という定量的な対応関係は依然未検証。 - バタフライネット・Beneš ネットのような多段トポロジは、現代のFat-Tree/Clos系データセンターネットワークの設計判断(例: マルチプレーンClos)にどこまで直接応用されているか、教科書側の記述からは確認できない。 - H&P Appendix Fの仮想チャネルによるデッドロック回避(資源への部分順序+エスケープ資源集合)は、本ページの静的な組合せ論的モデル(輻輳・直径・スイッチ数)には対応する概念を持たない——デッドロックはルーティングの動的な資源割り当て(バッファ・リンクの排他的グラント)から生じる現象であり、静的なルーティング問題としての置換πの実現可能性とは別次元の問題である。両者を統一的なフレームワークで扱えるかは未検証。 ## 関連 - 概念: [[木(グラフ理論)]] / [[データセンターネットワークトポロジ]] / [[単純グラフ]] / [[RDMA]] / [[データセンター輻輳制御]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 10 Communication Networks]] / [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Appendix F Interconnection Networks]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 10. - John L. Hennessy, David A. Patterson(改訂: Timothy M. Pinkston, José Duato), *Computer Architecture: A Quantitative Approach*, Sixth Edition, Morgan Kaufmann, 2019, Appendix F: Interconnection Networks, §F.4, §F.7.