# 階層的ルーティングとアドレス集約 ## 定義 階層的ルーティングとアドレス集約は、インターネットの規模拡大(ノード数・ネットワーク数の増大)にルーティングシステムを対応させるための中核的な設計手法である。単一ドメイン内ではエリア分割(area、バックボーンエリアと非バックボーンエリアの2層構造)によって経路情報の伝搬範囲を限定し、ドメイン間では自律システム(AS)という管理単位を導入して、ドメイン内ルーティング(intradomain)とドメイン間ルーティング(interdomain)を分離する。ドメイン間ルーティングを担う BGP は、ディスタンスベクタでもリンクステートでもなく、AS を列挙した完全な経路(complete path)を広告する path-vector プロトコルであり、各 AS が持つ経済的関係に基づく複雑なポリシー(Provider-Customer / Customer-Provider / Peer)の遵守と、経路中の自 AS 番号検出によるループ防止を両立させる。アドレス空間の側でも、CIDR に始まりプロバイダに階層的にプレフィックスを割り当てる方式(IPv6 でも踏襲)によって、ルータが保持すべき経路エントリ数を抑える。(Source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 4 Advanced Internetworking]] §4.1, §4.2.2) ## レイヤリングによるルーティング問題の分解(ch.4 §4.3) 『The Real Internet Architecture』第4章は、本ページが記録するアドレス集約とは**別の**スケーラビリティ手法として、レイヤリングによるルーティング問題の分解を提示する。 - **分解の一般形(§4.3.1)**: ネットワークが外側メンバー(外部と接続する側)と内側メンバー(内部の転送を担う側)を持つとき、外側メンバーの集合を完全結合のオーバーレイとしてレイヤリングすると、ルーティングと転送がオーバーレイ・アンダーレイの2つの別問題に分解される。IPエッジネットワークのEthernetへのレイヤリングや、クラウドのテナントEthernetのデータセンターネットワークへのレイヤリングがこの一般形の実例である。(Source: ch.4 §4.3.1) - **BGPスケーラビリティへの直接的な効果(§4.3.2)**: IPトランジットネットワークをMPLS網にレイヤリングすると、グローバルBGPルーティングに参加するのは外側メンバー(ゲートウェイ)だけになり、内側メンバーはOSPF計算済み転送テーブルで足りる。これはグローバルBGPに参加するフォワーダ数を劇的に削減すると同時に、ネットワーク内部の名前ブロックを細分化する必要がなくなる分だけ集約度を上げる——集約度の向上は転送規則数の減少に対応する。すなわちレイヤリングは、本ページが記録するCIDR的なプレフィックス集約(アドレス空間側の集約)とは異なる経路で、**参加ノード数そのものを減らす**という形でBGPのスケーラビリティに寄与する。(Source: ch.4 §4.3.2) - **定量的視点(§4.3.3、LAOD)**: 「レイヤリングとしての最適化分解」(Layering As Optimization Decomposition)は、Network Utility Maximization問題を(1) セッションプロトコルによるXの調整とルーティングによるRの調整という時間スケールの異なる分解、(2) 集中アルゴリズムから分散アルゴリズムへの分解、の2通りに整理する。オーバーレイがアンダーレイにレイヤリングされるとき、オーバーレイNUM問題の容量CはアンダーレイNUM問題の伝送速度Xに等しく、両ネットワークが同時にルーティングを変更するか(RONの例)、異なる時間スケールで別々に最適化するか(IPトランジット・MPLSの例)によって、依存関係の強さが変わる。(Source: ch.4 §4.3.3.1, §4.3.3.2) ## 横断的知見 - **アドレス集約(CIDR)とレイヤリングによる分解(RIA第4章)は、どちらも「BGPが処理すべき経路情報を減らす」という同じ目標に対する、独立した2つの手段である**: 本ページの定義が記録するCIDR的アドレス集約は、プロバイダに階層的にプレフィックスを割り当てることでルータが保持すべき経路エントリ数を抑える、アドレス空間側の手法である。これに対しRIA第4章§4.3.2が示すレイヤリング(IPトランジットネットワークのMPLS網への層化)は、グローバルBGPに参加するフォワーダの数そのものを削減する、参加者側の手法である。両者はSystems Approach第4章の「情報隠蔽が大規模ネットワークのスケーリングに不可欠」というKey Takeawayを共有しながら、隠蔽の対象(アドレス空間の詳細か、内部フォワーダの存在そのものか)が異なる。BGPのスケーラビリティは単一の手法ではなく、アドレス集約とレイヤリングという直交する2軸の組み合わせで達成されていることが、RIAのingestで初めて明確になった。(Source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 4 Advanced Internetworking]] §4.1, §4.2.2, [[@2024__PrincetonUP__The Real Internet Architecture - Chapter 4 The Real Internet Architecture]] §4.3.2) - **教科書はBGPを協調のためのプロトコル機構として描き、システム管理者向けの解説書は同じBGPを「正しさを保証しない、信頼に基づくディレクトリサービス」として描く**: 『Computer Networks: A Systems Approach』第4章は BGP を「AS が経路広告・ポリシー遵守・ループ防止という機能を実現する仕組み」として、プロトコルメカニクス(path-vector、AS relationship の3類型、iBGP/eBGP)に焦点を当てて説明する。一方 Burgess の『Principles of Network and System Administration』第10章は同じ BGP を「経路の正しさを保証しない『ディレクトリサービス』であり、AS 間の協調は強制ではなく信頼に基づく」と評し、Principle 53 として一般化する。前者が「BGP は何を達成できるよう設計されているか」を語るのに対し、後者は「BGP が達成を保証しないものは何か」——単純な設定ミスが広範なルーティング障害を招きうるという運用上のリスク——を語っており、同じプロトコルに対する設計者の視点と運用者の視点の違いが際立つ。(Source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 4 Advanced Internetworking]] §4.1.2, [[@2004__Wiley__Principles of Network and System Administration - Chapter 10 Network-level services]] §10.6, §10.6.3) - **両ソースとも、AS を「詳細を隠蔽するブラックボックス」として捉える点で一致する**: 教科書は「情報隠蔽が大規模ネットワークのスケーリングに不可欠であり、経路の最適性よりも優先される設計目標である」という Key Takeaway を提示する。Burgess は AS を「詳細を隠蔽する政治的単位」と表現し、AS 内部は距離ベクトル(RIP)またはリンクステート(OSPF)、AS 間は BGP という2層構造を強調する。教科書が「なぜ隠蔽するか(スケーラビリティのため)」という設計原理を語るのに対し、管理者向け解説書は「隠蔽が組織の自律性・政治的独立性の反映である」という運用上の含意を強調しており、同じ AS という抽象化の技術的動機と社会的動機が異なる文献で相補的に語られている。(Source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 4 Advanced Internetworking]] §4.1.1 Key Takeaway, [[@2004__Wiley__Principles of Network and System Administration - Chapter 10 Network-level services]] §10.6) - **RIA第3章は、BGPの経路選択・エクスポートポリシー(顧客優先・対等次点・プロバイダ最後)を「階層的な原則に従う限り不安定性・非決定性を防ぐ」という安定性の主張の裏付けとして提示するが、この結びつきの形式的な証明は示さない**: 本ページはSystems Approach第4章のBGPメカニクスとBurgessの「信頼に基づくディレクトリサービス」という運用者視点を対比してきたが、いずれも「ビジネス階層とBGPの安定性がなぜ結びつくのか」という因果関係そのものには深く踏み込まなかった。[[ブリッジング]]概念が記録するRIA第3章§3.2.2.2-3は、顧客/プロバイダ関係が階層に沿い対等関係が水平方向をつなぐという構造が「階層的な原則に従う限りBGPの発散・非決定的収束という最悪ケースの不安定性を防ぐ」と明言するが、これも参考文献[35]への参照にとどまり、本章自体は証明を与えない。3つの文献を並べても、「なぜ階層的ポリシーがBGPを安定させるのか」という形式的な根拠は本wikiにまだ蓄積されていない。(Source: [[@2024__PrincetonUP__The Real Internet Architecture - Chapter 3 Composing Networks and Services]] §3.2.2.2, §3.2.2.3, [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 4 Advanced Internetworking]] §4.1) - **SD-Fabricは、ドメイン内部を集中計算に置き換えつつ境界だけにBGPを残す、SDN時代の階層的ルーティングの実例を提供する**: 本ページが記録するBGP/AS階層は、AS内部が距離ベクタ/リンクステート、AS間がpath-vector(BGP)という2層構造を前提とする。これに対し *Software-Defined Networks: A Systems Approach* 第7章が報告するSD-Fabricは、ファブリック内部(リーフ-スパイン間)ではOSPFのような分散経路学習プロトコルを一切使わず、SDNコントローラ(ONOS)が大域計算した経路をmatch/actionルールとして直接投入する。ファブリックを外部ネットワークへ接続する境界でのみ、FPM(Forwarding Plane Manager)がローカルのQuaggaプロセスを介してBGPピアと経路を交換し、学習した経路をRoute serviceへ追加する。これは「ドメイン内部は完全に集中化し、外部境界だけに標準の分散プロトコル(BGP)を残す」という設計であり、本ページが記録するAS内/AS間の2層構造(いずれも何らかの分散プロトコルが動く)とは異なる、SDNコントローラによる集中計算とBGPという境界プロトコルを組み合わせた第三の階層パターンを示す。(Source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 4 Advanced Internetworking]] §4.1, [[@2021__SystemsApproach__Software-Defined Networks - A Systems Approach - Chapter 7 Leaf-Spine Fabric]] ch.7 §7.3) ## 未解決の問い - SD-Fabricのファブリック全体はBGPピアから見て一つのAS(自律システム)として振る舞うのか、それともSD-FabricのFPMが個別のBGPスピーカーとして直接ネイバーと経路を交換するだけで、AS番号や階層構造上の位置づけを持たないのか。*Software-Defined Networks: A Systems Approach* 第7章はこの点に触れておらず、本ページが記録するAS抽象化とSD-Fabricの関係は未解明。 - Burgess が Principle 53 として述べる「BGP は信頼に基づく」という性質は、RPKI(Resource Public Key Infrastructure)のような経路正当性検証機構によってどこまで緩和されたか。2004 年の記述と 2020 年の教科書はいずれもこの点に触れておらず、本 wiki にはまだ RPKI を扱う source がない。 - エリア分割(OSPF area)と AS 分割(BGP)という2つの階層は、どちらも「情報隠蔽によるスケーラビリティ確保」という同じ設計原理に従うが、両者を橋渡しする明示的な理論(1つの階層原理の2つの表れであることを示す統一的な議論)は本章には現れない。他のソースでこの統一的視点は示されているか。 - RIA第3章が引用する参考文献[35]([38])は、階層的BGPポリシーが安定性・決定的収束を保証する形式的な証明を含むと推測されるが、本wikiにはまだ ingest されていない。この文献を追加すれば、本ページの「なぜ階層原理がBGPを安定させるか」という未解決の問いに直接答えられる可能性がある。 - RIA第4章§4.3.2が示す「レイヤリングによるBGP参加ノード数の削減」は定性的な説明にとどまり、実際にどの程度のノード数削減・集約度向上が生じるかの定量値は示されない。§4.3.3のLAOD(NUM問題としての定式化)がこの定量化に応用できるかは、本ページではまだ検証していない。 ## 関連 - 概念: [[MPLS]] / [[エニキャストルーティング]] / [[ブリッジング]] / [[レイヤリング]](本ページとは異なる経路でBGPスケーラビリティに寄与する姉妹メカニズム) / [[データセンターL2ファブリック]] - 出典章: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 4 Advanced Internetworking]] / [[@2004__Wiley__Principles of Network and System Administration - Chapter 10 Network-level services]] / [[@2024__PrincetonUP__The Real Internet Architecture - Chapter 3 Composing Networks and Services]] / [[@2024__PrincetonUP__The Real Internet Architecture - Chapter 4 The Real Internet Architecture]] / [[@2021__SystemsApproach__Software-Defined Networks - A Systems Approach - Chapter 7 Leaf-Spine Fabric]] - 実体: [[SD-Fabric]] ## 出典 - Larry Peterson and Bruce Davie, *Computer Networks: A Systems Approach*, 6th edition, Chapter 4: Advanced Internetworking, §4.1, §4.2.2. https://book.systemsapproach.org/scaling.html - Mark Burgess, *Principles of Network and System Administration*, 2nd edition, Wiley, 2004, Chapter 10, §10.6, §10.6.3. - Pamela Zave, Jennifer Rexford, *The Real Internet Architecture*, Princeton University Press, 2024, Chapter 3, §3.2.2; Chapter 4, §4.3.1-§4.3.3. - Peterson, Cascone, O'Connor, Vachuska, and Davie, *Software-Defined Networks: A Systems Approach*, 2021, Chapter 7: Leaf-Spine Fabric, §7.3. https://sdn.systemsapproach.org/trellis.html