レジリエントネットワークグラフ（RNG）の起源と進化

背景：最適な経路と展開子（Expander Graphs）の研究の歴史

• ルーツ：最適な経路を見つけるためのネットワーク研究は、1970 年代後半まで遡ります。数学者たちは「展開子（expander）」と呼ばれる特殊なネットワークを定義しました。
  • 強い連結性を有するグラフであり、頂点の任意のサブセットが他の部分から孤立することはないことを保証しています。
• 理論的進展：
  • 1976 年：レスリー・ヴァリアントは、これら展開子についての早期な議論を展開しました。アロン・ボーパナによる研究に基づき、最適構成法について言及されました。
  • 提案者の課題：ルボチスキー、フィリップス、サナークらが構成法を提案しましたが、これらは複雑で高度な数論を必要とし、特定のサイズと次数（degree）にのみ適用可能でした。
• ランダムグラフの発見：
  • 1991 年：フリードマンは、確率が高い場合、ランダムに配線されたネットワークが明示的な構成による最良の展開子とほぼ同等の性能を持つことを示しました。
  • 2023 年：数学的発見により、ランダムグラフがこの限界値に達することが確認されました。
  • 結論：最適なルーティング用ネットワークを望む場合、単にランダムに配線すればよいという事実に至りました。

ネットワーク業界の道筋：ファットツリーと VL2

• 従来のアプローチ：
  • 1980 年代中期以降、クロス結合網（Clos interconnects）に触発され、スイッチのレイヤーを持つファットツリートポロジーが構築されてきました。
  • クラウドコンピューティングの成長に伴い、規模拡大は益々高度化していきました。
• VL2 の革新（2009 年）：
  • アルバート・グリーンバーグらを筆頭とする研究チームにより、「VL2：スケーラブルで柔軟なデータセンターネットワーク」が発表されました。
  • 主な手法：
    • 平坦なアドレス指定手法の導入。
    • **「ランダム化されたヴァリアント負荷平衡（Valiant Load Balancing）」**を採用し、トラフィックを一様に分散させることでパフォーマンスを向上させました。
  • 評価：2019 年に SIGCOMM の「タイムのテスト」賞を受賞。構造化されたトポロジーにおいても、経路のランダム化がパフォーマンス向上に寄与することが実証されました。
• 残された課題：基盤となるネットワーク自体は依然として階層的で剛性的であり、ケーブル配線も複雑でした。

橋渡し：Jellyfish とその限界

• 提案の経緯：2012 年、イリノイ大学の研究チームが「Jellyfish（ジャリーフィッシュ）」というランダムグラフとデータセンターネットワークを結びつける案を提唱しました。
• 理論モデルの課題：単純な理論とシミュレーションに基づくため、以下のような難しい問題は未解決でした。
  • ルーティング：ランダムグラフ内でのルーティングは困難で、データの進む経路が多様化します。
  • 配線：端末ノードがランダムに選択されるため、配線と運用が予測不能です。
  • 実現性：大規模なランダムネットワークの構築、およびルーティング・配線・運用という 3 つの課題の解決が未達成でした。

RNG（レジリエントネットワークグラフ）の誕生と進化

歴史的背景

• 調査の開始：2023 年、ジェコモ・ベルナルディとラトール・マハラジャンは、データセンタールーターを「ペノーズタイル」に従って平坦に配置できるか調査を開始しました。
• 壁への直面：2024 年中頃、シミュレーションされたネットワークが信頼性が低く効率性に乏しいことが判明しました。結論として、構造をランダム性に取り替えると著しく優れた成果が得られることが分かりました（「ただ、ランダムにすればいい！」という Inside Joke に）。
• 新モデルの必要性：アマゾン規模での平坦ネットワーク構築手法への言及が無かったため、新たなモデル開発が必要になりました。セシャドリー・コマンドゥーを含むチームが理論的なバックアップを提供し、以下の 3 つの障壁に挑みました。

技術的障壁の克服

チームは以下の 3 つの課題に対して具体的な解決策を開発しました。

• ルーティングについて：
  • グラフの展開性を活用し、ルーターメモリを過負荷にしない「Spraypoint」フォワーディングスキームを開発。トラフィックを効率的に分散させます。
• 配線について：
  • 「ShufleBox」という受動的な光学デバイスを開発。内部配線とランダム化された ShufleBox 同士の配線を組み合わせることで、「準ランダム（quasi-random）」なグラフを実現しました。
• 運用について：
  • ファットツリーで既に使われているルーターと光デバイスを活用し、抽象的なグラフを物理的な設置指示書および診断情報に変換するソフトウェアツールを構築。
  • デプロイ前に数学的にファブリックのパフォーマンスを検証・予測できるようにしました。

実装への決断（2024–2026）

• 実装の命令：ネットワークエンジニアリング担当バイスプレジデントのマット・レヒダーは、「実際にデータセンターで提案された設計を構築してください」と挑戦を発令しました。
• 第一段階（2024 年）：少人数チームにより、アイルランドダブリン郊外に最初の RNG データセンターが建設されました。
• 第二段階（2025 年～）：実験から多くのことを学んだチームは、ネットワークを取り壊して設計を最適化し、新たに以下のデータを構築しました。
  • ドイツのデータセンター
  • スペインのデータセンター

顕著な成果（ファットツリーとの比較）

従来のファットツリーと比較して、RNG は以下のような大幅な改善を示しました。

• ルーター使用数：69% 削減
• スループット：33% 向上
• ネットワーク消費電力：40% 削減
• 運用コスト：27% 低減
• 現状：2026 年初頭、RNG が世界中の新たに構築されるアマゾンのデータセンターにおけるデフォルト設計となりました。

RNG とファットツリーとの相対的優位性

項目	RNG (レジリエントネットワークグラフ)	ファットツリー
レジリエンス（耐障害性）	ローターは同等重要。1% のローター損失に対し、容量も約1% で減少。劣化は比例して予測可能。	誤ったスパインスイッチの損失が、不均衡な割合の容量ダウンを招く可能性がある。
効率性	すべての経路が統計的に同等。容量は相互置換可能。特定のレイヤーにロックされた「未使用帯域幅」なし。	階層構造により、特定レイヤーで帯域幅が浪費されることがある。
スケーラビリティ	連続的拡張可能。ルーター追加だけでグラフが成長。トポロジー再設計不要。「容量の崖（cliff）」にぶつかることなく拡大。	スイッチレディックスやレイヤー数によって固定サイズが決まる。再設計が必要。

RNG の相対的限界（および緩和策）

• 運用上の複雑さ
  • 課題：ランダムグラフ内の経路はツリー構造より予測しにくく、従来のツールでのトラブルシューティングが困難です（階層的構造がないため）。
  • 緩和策：専用診断ソフトウェアの構築。トラフィック分布と障害局在化への可視性を確保することで対応しています。
• パフォーマンス保証
  • 課題：最悪-case のパフォーマンスは知られていますが、RNG は確率的な保証（高い確率で性能が良い）です。
  • 緩和策・認識：これは想像以上に弱い制約ではありません。大規模ネットワークでは故障も頻繁に発生するため、事実上ファットツリーでも確率的な保証となります。RNG はこの確率的性質を明示的にし、設計之初からこれに対応するように構築されています。

参考文献

• RNG 研究論文：https://arxiv.org/abs/2604.15261
• アマゾンストーリー：https://www.aboutamazon.com/stories/aws-random-graph-theory-data-center-network-design?&utm_term=36
• アマゾンサイエンスストーリー：https://www.amazon.science/blog/how-flat-is-replacing-fat-in-aws-data-center-networks
• YouTube ビデオ解説：https://www.youtube.com/watch?v=yDoRYRRPOA0
• 関連画像：https://amazongca.getbynder.com/share/B6E5A14E-AFFB-43AD-83599AFEABCBAB6A/?viewType=grid

参照論文

• "VL2: A Scalable and Flexible Data Center Network"
  • 著者：Albert Greenberg, James R. Hamilton, Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, Dave A. Maltz, Parveen Patel, Sudipta Sengupta
  • 発表場：SIGCOMM 2009