BGPコミュニティがASパスプリペンドよりも優れている理由

インターネットを最も純粋な形で表せば、独立したネットワーク（自律システム（略してAS）とも呼ばれます）が緩く接続された図式になります。これらのネットワークは、BGP（Border Gateway Protocol）と呼ばれる信号プロトコルを使用して、ネットワーク内およびネットワーク経由でIPプレフィックス（IPアドレスのグループ）の到達可能性をネイバー（ピアとも呼ばれます）に通知しています。この交換の一部には、ネットワークルーティングの決定に関する情報を提供するために使用される、IPプレフィックスに関する有用なメタデータが含まれています。メタデータの一例が完全なASパスで、IPパケットが目的地に到達するために通過する必要のある個別の自律システムで構成されています。

パケットができるだけ早く目的地に届いてほしいので、所定のプレフィックスに対して最短のASパスを選択するのが理想的です。そこで登場するのがプリペンドというものです。

インターネットにおけるルーティング（入門編）

詳細な説明に入る前に、インターネットの最も基本的な仕組みについて簡単に説明します。

インターネットの中心には、何千ものネットワークが相互接続された大規模なネットワークが存在します。各ネットワークは、2つの重要なものを所有しています。

1. ASN（Autonomous System Number）：ネットワークを一意に識別するための32ビット整数。例えば、CloudflareのASN（複数あります）の1つは13335です。

2. IPプレフィックス。IPプレフィックスはIPアドレスの範囲を示すもので、2つずつの組み合わせとなるものです。IPv4空間では、2つのアドレスで/31プレフィックス、4つのアドレスで/30プレフィックスとなり、/0までが「すべてのIPv4プレフィックス」と称されます。IPv6でも同様ですが、最大32ビットではなく、最大128ビットを集約することが可能です。下図は、このIPプレフィックス間の関係を逆から見たもので、/24は2つの/25を含み、/25は2つの/26を含むというようになります。

インターネット上で通信を行うには目的地に到達する必要があります。そこで登場するのがルーティングプロトコルです。これにより、インターネット上の各ノードは、メッセージをどこに送ればよいのか（そして受信者はメッセージをどこに送り返せばよいのか）を知ることができます。

前述したように、これらの目的地はIPアドレスで識別され、IPアドレスの連続した範囲はIPプレフィックスとして表わされます。IPプレフィックスは、ルーティング効率を最適化するために使用されます。IPv4で40億 (2³²) ものIPアドレスを追跡するのは非常に複雑なことであり、多くのリソースを必要とします。プレフィックスを使用することで、その数を約100万個に減らすことができます。

ここで、自律システムは独立して運用・制御されるものであることを思い出してください。インターネットのネットワークにおいて、他のネットワークにいるソースAに、自分のネットワークにある（または経由して）目的地Bに行くための利用可能なパスがあることを伝えるにはどうすればよいでしょうか。そこでBGPの登場です。BGPとはBorder Gateway Protocolのことで、到達可能性の情報を伝えるために使用されます。ソースASNが生成する信号メッセージは、プレフィックス内のIPアドレスがオンラインで到達可能であることをインターネットに宣言するため、「アナウンスメント」と呼ばれます。

上の図を見てください。ソースAは、2つの異なるネットワークを介して目的地Bに到達する方法がわかっています。

実際のBGPメッセージはこのような感じです。

BGP Message
    Type: UPDATE Message
    Path Attributes:
        Path Attribute - Origin: IGP
        Path Attribute - AS_PATH: 64500 64496
        Path Attribute - NEXT_HOP: 198.51.100.1
        Path Attribute - COMMUNITIES: 64500:13335
        Path Attribute - Multi Exit Discriminator (MED): 100
    Network Layer Reachability Information (NLRI):
        192.0.2.0/24

ご覧のように、BGPメッセージにはIPプレフィックス（NLRIビット）とパスだけでなく、パスに関する追加情報を提供する他のメタデータもたくさん含まれています。その他に、コミュニティ（詳細は後述）、MED（オリジンコード）などがあります。MEDは、複数の選択肢がある場合に、どのパスを選択すべきかを直接接続された他のネットワークに提案するもので、値の小さい方が優先されます。オリジンコードは、IGP、EGP、Incompleteの3つの値のいずれかとなります。IGPはBGP経由でプレフィックスを生成した場合に設定され、EGPは古いルーティングプロトコルであるため使用されません。Incompleteは、他のルーティングプロトコル（IS-ISやOSPFなど）からBGPにプレフィックスを配布した場合に設定されます。

さて、ソースAが2つの異なるネットワーク経由で目的地Bに到達する方法がわかったところで、トラフィックエンジニアリングについて説明しましょう。

トラフィックエンジニアリング

トラフィックエンジニアリングは、あらゆるネットワークの日常的な管理において重要な役割を担っています。実際の世界と同じように、事業者はネットワークへのトラフィック流入（インバウンド）とネットワークからのトラフィック流出（アウトバウンド）を最適化するために迂回路を設置することができます。アウトバウンドトラフィックエンジニアリングは、ネイバーのネットワークを選択でき、一部のトラフィックを他のトラフィックより優先させることもできるため、インバウンドトラフィックエンジニアリングよりはるかに簡単です。これに対して、インバウンドトラフィックエンジニアリングでは、まったく別の誰かが運営しているネットワークに影響を及ぼす必要があります。ネットワークの自律性と自己管理は最も重要であるため、オペレータは利用可能なツールを使用して、他のネットワークからの受信パケットフローに情報を提供したり、そのフローを形成したりします。これらのツールは理解することが難しく、使い方が複雑であるため、問題になることもあります。

トラフィックエンジニアリングのツールは、インバウンドおよびアウトバウンドの両方で、所定のパスの属性（メタデータ）を操作することに依存しています。ここでは、独立したネットワーク間のトラフィックエンジニアリングを取り上げているので、EBGPで学習したパスの属性を操作することになります。BGPは2つのカテゴリーに分けられます。

EBGP：異なる2つのASN間のBGP通信
IBGP：同一ASN内のBGP通信

プロトコルは同じですが、EBGPセッションで交換されない特定の属性がIBGPセッションで交換されることがあります。その1つがローカルプリファレンスです。詳しくは後述します。

BGPベストパス選択

ネットワークが他の複数のネットワークやサービスプロバイダーに接続されている場合、それらのネットワークの多くから同じIPプレフィックスへのパス情報を受け取ることができますが、それぞれ属性が微妙に異なることになります。それから、BGPベストパス選択アルゴリズムを使用して「ベスト」のプレフィックス（およびルート）を選択し、これを使用してIPトラフィックを転送するかは、その情報を受け取ったネットワーク次第です。「ベスト」というのは主観的な条件なので、かっこで囲みました。「ベスト」が最短になることはよくありますが、自分のネットワークにとってベストでも、他のネットワークにとってベストな結果となるとは限りません。

BGPは受信したオプションをフィルタリングする際に、複数のプレフィックス属性を考慮します。しかし、BGPベストパス選択では、これらの属性を1つの選択基準にまとめるのではなく、属性を階層的に使用します。どの階層においても、利用可能な属性がベストパスを選択するのに十分であれば、アルゴリズムはその選択で終了します。

BGPベストパス選択アルゴリズムは、与えられたプレフィックスに対して利用可能なベストパスを選択する15の離散的なステップを含む広範囲なものです。多くのステップを考えると、できるだけ早い段階で最適なパスを決定することがネットワークの利益となるのです。最初の4つのステップは最も利用されていて影響力が大きく、下図に漏斗として描かれています。

通常は、可能な限り最短のパスを選択することが理想的であるため、「ASパス長」はアルゴリズムの初期に実行されるステップとなっています。しかし、上の図を見ると、「ASパス長」は最短のパスを見つけるための属性であるにもかかわらず、2番目に表示されています。では、最初のステップであるローカルプリファレンスについて説明しましょう。

ローカルプリファレンス
ローカルプリファレンスは、好みのルートとパスの組み合わせを選ぶことができるため、オペレータに好まれています。これは、任意のルート、ネイバー、ASパスの組み合わせに対して一意であるため、アルゴリズムの最初の属性となります。

ネットワークは、（ネイバーネットワークからルートを学習した）パスのインポート時にローカルプリファレンスを設定します。非遷移的であることは、EBGPメッセージで他のネットワークに送信されることのない属性であることを意味します。これは本質的に、例えばAS 64496のオペレータが、隣接するAS 64511内の自分自身の（または通過する）IPプレフィックスへのルートのローカルプリファレンスを設定できないことを意味します。このことが、EBGPによるインバウンドトラフィックエンジニアリングが難しくなる理由の1つです。

人為的にASパス長を増加させるプリペンド
どのネットワークも他のネットワーク内のプレフィックスに対するローカルプリファレンスを直接設定できないため、他のネットワークの選択に影響を及ぼす最初の機会はASパスを修正することです。ネクストホップが有効で、所定のルートに対するすべての異なるパスのローカルプリファレンスが同じであれば、ASパスを変更することは、自分のネットワークに向かうトラフィックのパスを変更するための明白なオプションとなります。BGPメッセージでは、プリペンドは次のように表示されます。

使用前：

BGP Message
    Type: UPDATE Message
    Path Attributes:
        Path Attribute - Origin: IGP
        Path Attribute - AS_PATH: 64500 64496
        Path Attribute - NEXT_HOP: 198.51.100.1
        Path Attribute - COMMUNITIES: 64500:13335
        Path Attribute - Multi Exit Discriminator (MED): 100
    Network Layer Reachability Information (NLRI):
        192.0.2.0/24

導入後：

BGP Message
    Type: UPDATE Message
    Path Attributes:
        Path Attribute - Origin: IGP
        Path Attribute - AS_PATH: 64500 64496 64496
        Path Attribute - NEXT_HOP: 198.51.100.1
        Path Attribute - COMMUNITIES: 64500:13335
        Path Attribute - Multi Exit Discriminator (MED): 100
    Network Layer Reachability Information (NLRI):
        192.0.2.0/24

具体的には、オペレータはASパスのプリペンドを行うことができます。ASパスのプリペンドを行う場合、オペレータはパスに自律システムを追加します（通常オペレータは自分のASを使用しますが、プロトコル上強制されることはありません）。ここでは、ASパスの長さは1から255まで選択できます。長さが飛躍的に伸びているため、そのルートの具体的なパスは選択されないことになります。オペレータは、異なるピアにアドバタイズするASパスを変更することで、ネットワークに流入するトラフィックフローを制御することができます。

残念ながら、プリペンドには落とし穴があります。決定要素とするためには、他の属性がすべて同じである必要があるのです。特に大規模なネットワークでは、目的地までの多くのルートの中から選択することができるため、このようなことが起こることはほとんどありません。

ビジネスポリシーエンジン

BGPはビジネスポリシーエンジンとも呼ばれます。パフォーマンスの観点から最適なパスを選択するのではなく、大抵はビジネスの観点から最適なパスを選択します。ビジネス上の基準には、投資（ポート）効率から収益の増加まで、あらゆるものが考えられます。奇妙に聞こえるかもしれませんが、これこそがBGPが行うように設計されていることなのです。BGPのパワー（と複雑さ）は、ネットワークオペレータがオペレータのニーズ、契約、ポリシーに従って選択できるようにします。その多くは従来のエンジニアリングパフォーマンスの概念では反映されないものです。

ローカルプリファレンスの違い

多くのネットワーク（Cloudflareを含む）は、ルートを送信するために使用される接続の種類に応じて、ローカルプリファレンスを割り当てます。値が高いほど優先度が高くなります。例えば、トランジットネットワーク接続から学習したルートは、使用コストが最も高いためにローカルプリファレンスが100と低くなり、バックボーンから学習したルートは150、インターネットエクスチェンジ（IX）ルートは200、最後にプライベートインターコネクト（PNI）ルートは250になります。つまり、Cloudflareのネットワークではエグレス（アウトバウンド）トラフィックに対して、IXやトランジットネイバーを通じてより短いASパスが利用できる場合でも、デフォルトではPNIで学習したルートが優先されます。

IXではなくPNIが好まれる理由の1つが信頼性です。なぜなら、当社がコントロールできないサードパーティのスイッチングプラットフォームが存在しないからです。これが重要なのは、すべてのハードウェアが最終的には壊れるという前提に立って運用を行っているためです。もう1つは、ポート効率上の理由です。ここでいう効率とは、各ポートで転送されるメガビットあたりのコストで定義されます。大雑把に言うと、コストは以下のように計算されます。

(スイッチングのコスト / ポート数) + トランシーバのコスト)

これは、クロスコネクトコスト（月額使用料（MRC）または1回限りの料金）と組み合わされます。PNIは、ポートの利用率が高いほど単価が下がるため、転送するメガビットあたりの総コストを削減して価値の最適化に役立つため、望ましいと言えます。

これは他の多くのネットワークにも当てはまり、トランジットネットワークでは非常に一般的なものです。BGPは、少なくともパフォーマンスと同程度にコストとビジネスポリシーに関わるものです。

トランジットローカルプリファレンス

わかりやすくするために、トランジットと言う場合は従来のTier 1トランジットネットワークを指します。これらのネットワークは、その性質上2つの異なるネットワークピアのセットを持ちます。

1. カスタマー（Cloudflareなど）
2.決済のないピア（他のTier 1ネットワークなど）

通常の場合、トランジットカスタマーには、決済のないピアに使用されるものよりも高いローカルプリファレンスが割り当てられます。これは、プレフィックスをいくらプリペンドしても、トラフィックがそのトランジットネットワークに入ると、常にそのトランジットネットワークとの相互接続に着地し、他のピアにオフロードされることはないということを意味します。

プリペンドは、1つのトランジットと複数の識別されたリンクがある場合に、1つのリンクからトラフィックを切り替え/オフロードしたい場合や、トラフィックのソースが複数のトランジットの背後でマルチホームされている場合（そして別のトランジットを優先する独自のローカルプリファレンスプレイブックを持っていない場合）にも使用できます。しかし、ASパスのプリペンドによって、あるトランジットポートから別のトランジットポートへトラフィックをエンジニアリングするインバウンドトラフィックは、大きなリターンの減少をもたらします。3つのプリペンドを過ぎると、その時点ではほとんど何も変わらないでしょう。

例

上記のシナリオでは、CloudflareがAS 64496に向けてASパスを調整しても、ASパスの観点からOrigin A → Transit B → Transit A → Cloudflareのパスが短くても、トラフィックはTransit B <> Cloudflare相互接続を通じて流れ続けることになります。

このシナリオでは、あまり大きな変化はありませんが、Origin Aは2つのトランジットプロバイダーの背後にマルチホームされるようになりました。この場合、Origin A側で見られるパスは、プリペンドされたパスとされていないパスの両方であるため、ASパスのプリペンドが有効であったことになります。Origin Aがエグレストラフィックエンジニアリングを行っておらず、両方のトランジットネットワークを同等に扱っている限り、Origin A → Transit A → Cloudflareというパスが選択されます。

コミュニティベースのトラフィックエンジニアリング

ここで、オペレータにとってのインターネットのエコシステム内の重要な問題が明らかになりました。つまり、上記のようなツールでは、トラフィックが自分のネットワークに流入するルートを正確に指示することは必ずしも可能ではなく（完全に不可能という人もいるかもしれません）、自律システムが自分のネットワークに対して持つ制御力が低下するということです。幸いなことに、この問題を解決する方法があります。それは、コミュニティベースのローカルプリファレンスです。

トランジットプロバイダーによっては、BGPコミュニティを使用して、カスタマーがトランジットネットワークのローカルプリファレンスに影響を与えることを許可しています。BGPコミュニティは、ルートアドバタイズのオプションの遷移的属性です。コミュニティは情報提供（「ローマでこのプレフィックスを覚えた」）になりますが、受信側のアクションを引き起こすためにも使われます。例えば、Cogentでは以下のようなアクションコミュニティを発行しています。

コミュニティ	ローカルプリファレンス
174:10	10
174:70	70
174:120	120
174:125	125
174:135	135
174:140	140

Cogentが、そのネットワークで以下のデフォルトのローカルプリファレンスを使用していることがわかったとします。

ピア → ローカルプリファレンス 100
カスタマー → ローカルプリファレンス 130

提供されたコミュニティを使って、使用するルートを変更する仕組みは容易に想像がつくと思います。しかし、ルートのローカルプリファレンスを100（または130）に設定することはできないため、ローカルプリファレンスが同じになることはなく、ASパスのプリペンドはほとんど無意味であることに注意してください。

例えば、次のような構成です。

term ADV-SITELOCAL {
    from {
        prefix-list SITE-LOCAL;
        route-type internal;
    }
    then {
        as-path-prepend "13335 13335";
        accept;
    }
}

Cloudflare ASNを2回プリペンドしたことでASパスが合計3つになっていますが、それでもCogentのリンクに多すぎるほどのトラフィックが流入していました。その時点で、エンジニアは別のプリペンドを追加できますが、Cloudflareのようによく接続されたネットワークでは、2つか3つのプリペンドであまり効果がない場合、4つか5つでも効果は変わりません。その代わりに、上記のCogentのコミュニティを活用して、Cogent内のルーティングを変更できます。

term ADV-SITELOCAL {
    from {
        prefix-list SITE-LOCAL;
        route-type internal;
    }
    then {
        community add COGENT_LPREF70;
        accept;
    }
}

上記の設定により、トラフィックのフローはこのように変化します。

これこそが当社が望んでいたものです。

まとめ

ASパスのプリペンドはまだ有用であり、オペレータがトラフィックエンジニアリングを行うためのツールチェーンの一部として使用されていますが、今後は使用を控えるのがよいでしょう。過剰なプリペンドはネットワークをより広範なルートハイジャックにさらすことになり、これは何としても避けたい事態です。そのため、コミュニティベースのイングレストラフィックエンジニアリングを使用することが大いに推奨されます。コミュニティが利用できない（またはカスタマートラフィックを制御できない）場合、プリペンドを適用することはできますが、オペレータはその効果を積極的に監視し、効果がない場合はロールバックすることをおすすめします。

余談ですが、P MarcosらはASパスのプリペンドに関する興味深い論文を発表しており、プリペンドに関連するいくつかの傾向について触れていますので、ぜひ一読をおすすめします。 https://www.caida.org/catalog/papers/2020_aspath_prepending/aspath_prepending.pdf

Cloudflare ブログ