図解！BGPベストパス選択アルゴリズム

概要

BGPではあるネットワークアドレスに対するルート情報を複数受信することがとても多くなっています。同じネットワークアドレスに対する複数のBGPルートを受信すると、ベストパス(最適ルート)を決めて、ルーティングテーブルに登録します。また、ベストパスとなったルート情報のみを他のネイバーへアドバタイズします。

どのような順序でBGPルートのパスアトリビュートを評価して、ベストパスを決定するかについて、詳しく図解します。

BGPとIGPでのベストパス選択

あるネットワークへのルートが複数あっても、原則として、1つの最適ルート(ベストパス)のみをルーティングテーブルに登録します。これは、OSPFなどのIGPでもBGPでも同じです。

OSPFなどのIGPでは、ベストパスの選択はメトリックに基づいて行います。メトリックの算出方法はさまざまですが、結局は1つの数値です。メトリックが最小となっているルート情報をベストパスとします。

一方、BGPではベストパスの選択はパスアトリビュートに基づいて行います。BGPのルート情報に付加されているパスアトリビュートは1つだけではありません。さまざまなパスアトリビュートに基づいて、柔軟にベストパスを決められることがBGPの大きな特徴です。

等コストロードバランスまたは不等コストロードバランスによって、あるネットワーク宛ての複数のルートをルーティングテーブルに登録することもできます。

OSPFなどのIGPでのメトリックについて、以下の記事も合わせてご覧ください。

ネットワークのおべんきょしませんか？

宛先ネットワークまでの距離を計測～アドミニストレイティブディスタンスとメトリ...

https://www.n-study.com/iprouting/administrative-distance

ルーティングテーブルには宛先ネットワークへの最適ルートのみを登録します。そのために、アドミニストレイティブディスタンスとメトリックを組み合わせて、宛先ネットワークまでの距離を計測します。

BGPルートに付加されるパスアトリビュートについて、以下の記事も合わせてご覧ください。

ネットワークのおべんきょしませんか？

BGP Well Known Mandatory アトリビュート -ORIGIN/AS_PATH/NEXT_HOP-

https://www.n-study.com/bgp-detail/bgp-well-known-mandatory-attribute

BGPルートには、さまざまなパスアトリビュートが付加されています。必ず付加されるパスアトリビュートがWell Known MandatoryのORIGIN/AS_PATH_NEXT_HOPの3つのパスアトリビュートです。

BGPベストパス選択プロセス

前提

ベストパスを決める前に、前提として受信したBGPルート情報が有効でなければいけません。受信したBGPルートを利用するには、以下の条件を満足していなければいけません。

NEXT_HOPアトリビュートのIPアドレスに到達可能であること
同期が有効なとき、同期の条件を満足していること

現在のCisco IOSでは、BGPの同期はデフォルトで無効です。また、同期を有効にしなければいけないようなBGPの構成を取ることはまずないので、同期についての条件は特に意識しなくても大丈夫です。1点目のNEXT_HOPアトリビュートのIPアドレスに到達可能かどうかをしっかりと確認してください。

AS_PATHによってループとみなされていないことも前提です。ただ、AS_PATHでループとみなされていると、そもそもBGPルートを破棄するのでBGPテーブルには格納されません。

ベストパス選択プロセス

同じネットワークアドレスに対する複数のBGPルートを受信したときに、以下の順序でルートに付加されているパスアトリビュートを評価して、ベストパスを決定します。

以下のプロセスの中には、パスアトリビュートによらないベストパスの決定もあります。あるプロセスでベストパスが決まったら、それ以降のプロセスは見ません。

最大のWEIGHTを持つBGPルートを優先する
最大のLOCAL_PREFを持つBGPルートを優先する
ローカルで生成したBGPルートを優先する
最短のAS_PATHを持つBGPルートを優先する
最小のORIGINを持つBGPルートを優先する
最小のMEDを持つBGPルートを優先する
IBGPルートよりもEBGPルートを優先する
NEXT_HOPへ到達するための最小のIGPメトリックを持つBGPルートを優先する
EBGPルートのとき、先に受信したルートを優先する
最小のルータIDのBGPネイバーから受信したBGPルートを優先する
最小のCLUSTER_LISTを持つBGPルートを優先する
最小のIPアドレスのBGPネイバーから受信したBGPルートを優先する

以降で、それぞれのプロセスについてもう少し詳しく見ていきます。なお、説明の都合上、それぞれの項目のアトリビュートのみに注目します。しかし、BGPルートには1つではなく、いろんなアトリビュートが付加されていることを忘れないでください。また、図中のBGPテーブルにおいて、ベストパスをCiscoの表記に合わせて「>」で表します。

ベストパスを選択するときのアトリビュートを評価する順序を暗記する必要はありません。必要なときにこのページなどを参照してください。もし、CCNPやCCIEを受験するときには暗記してください。

最大のWEIGHTを持つBGPルートを優先する

WEIGHTアトリビュートはCisco独自です。BGPルートに付加されているわけではなく、ルータローカルでWEIGTHアトリビュートを付加できます。WEIGTHを付加するような設定を行っている場合、WEIGHTアトリビュートが最大のBGPルートをベストパスとします。

最大のLOCAL_PREFを持つBGPルートを優先する

WEIGHTの次にLOCAL_PREFアトリビュートを見ます。LOCAL_PREFアトリビュートは、他のASのネットワークへルーティングするときの出口となるルータを決めるときに利用します。LOCAL_PREFアトリビュートが最大のBGPルートをベストパスとして決定します。

LOCAL_PREFによるベストパスの決定について、以下の記事も合わせてご覧ください。

ネットワークのおべんきょしませんか？

マルチホームAS ベストパス選択のポイント

https://www.n-study.com/bgp-detail/bgp-bestpath-selection-for-multihome-as

マルチホームASでインターネット接続を冗長化したときに、ベストパスの選択を制御してパケットの転送を制御します。マルチホームASでのベストパス選択のポイントについて解説します。

ローカルで生成したBGPルートを優先する

ローカルで生成したBGPルートとは、networkコマンドやaggregate-addressコマンドの設定によってBGPルートとして生成したものです。他のBGPネイバーから受信したBGPルートよりも、そのルータ自身で生成したBGPルートを優先します。

Cisco IOSにおいてローカルでBGPルートを生成するための具体的なコマンドを以下の記事で詳しく解説しています。

ネットワークのおべんきょしませんか？

BGPの基本設定と確認コマンド

https://www.n-study.com/bgp-detail/bgp-basic-configuration

BGPの基本的な設定の流れは、以下の3ステップです。1.BGPルーティングプロセスの有効化2.BGPネイバーの設定3.BGPルートの生成

最短のAS_PATHを持つBGPルートを優先する

AS_PATHには、BGPルートが経由してきたAS番号がリストされています。AS_PATHの長さとは、含まれているAS番号の数です。たとえば、以下の図では、R2から受信したBGPルート192.168.1.0/24のAS_PATHの長さは「2」です。R3から受信したBGPルート192.168.1.0/24のAS_PATHの長さは「3」です。つまり、経由してきたASの数が最も少ないBGPルートを優先してベストパスとして決定します。

最小のORIGINを持つBGPルートを優先する

ORIGINアトリビュートには、3つの値があります。

0 (IGP)
1 (EGP)
2 (Incomplete)

最小のORIGINアトリビュートのBGPルートがベストパスに決まります。

ただ、ORIGINアトリビュートでベストパスが決まることはほとんどありません。基本的にBGPルートに付加するORIGINアトリビュートは0、すなわちIGPになるからです。

普通はベストパスを決めるときにORIGINで決まるようなことはありませんが、CCIEのラボ試験では、ORIGINでベストパスにさせるような条件が出題されることもあります。

最小のMEDを持つBGPルートを優先する

MEDは、隣のASから自ASのネットワークへルーティングするときの入り口となるルータを決めるために利用するアトリビュートです。OSPFなどのIGPでのメトリックに相当するアトリビュートで、値が小さい方が優先されます。

なお、ここでは詳細について割愛していますが、MEDの評価にはさまざまな条件があります。

MEDによるベストパスの決定について、以下の記事も合わせてご覧ください。

ネットワークのおべんきょしませんか？

マルチホームAS ベストパス選択のポイント

https://www.n-study.com/bgp-detail/bgp-bestpath-selection-for-multihome-as

IBGPルートよりもEBGPルートを優先する

IBGPネイバーから受信したBGPルートよりもEBGPネイバーから受信したBGPルートを優先してベストパスとして決定します。

NEXT_HOPへ到達するための最小のIGPメトリックを持つBGPルートを優先する

BGPルートがルーティングテーブルに登録されるときに、ネクストホップはNEXT_HOPアトリビュートのIPアドレスです。NEXT_HOPアトリビュートのIPアドレスは、必ずしも直接接続されているネットワークのIPアドレスとは限りません。NEXT_HOPアトリビュートのIPアドレスへルーティングするために、ルーティングテーブルを再帰的に検索することもあります。IBGPネイバーから受信したBGPルートの場合、たいてい、ルーティングテーブルの再帰検索が必要です。

再帰的にNEXT_HOPアトリビュートのIPアドレスを検索するときのIGPメトリックの値が最小となるBGPルートを優先してベストパスとして決定します。つまり、NEXT_HOPアトリビュートのIPアドレスへ最短で到達できるBGPルートを優先します。

図 NEXT_HOPへ到達するための最小のIGPメトリックを持つBGPルートを優先する

EBGPルートのとき、先に受信したルートを優先する

EBGPネイバーから受信しているBGPルートの場合、先に受信しているルートを優先してベストパスとして決定します。

最小のルータIDのBGPネイバーから受信したBGPルートを優先する

BGPルータにも、OSPFと同じように各ルータを識別するためのルータIDがあります。ルータIDが最小のBGPネイバーから受信したBGPルートを優先してベストパスとして決定します。

最小のCLUSTER_LISTを持つBGPルートを優先する

CLUSTER_LISTは、ルートリフレクタを構成しているときに付加されるパスアトリビュートです。CLUSTER_LISTには、ルートリフレクタのルータIDが含まれています。CLUSTER_LISTのルータIDが最小のルートをベストパスとして決定します。

最小のIPアドレスのBGPネイバーから受信したBGPルートを優先する

同じルータとIPアドレスを変えて複数のBGPネイバーを確立することもできます。そして、ここまでのプロセスでベストパスが決定できなかったときには、最小のIPアドレスのBGPネイバーから受信したBGPルートを優先してベストパスとして決定します。

たいていはMEDまでで決まるように

以上のようにあるネットワークアドレスについてのBGPルートを複数受信したときに、さまざまなパスアトリビュートによってベストパスを決定します。ただ、ベストパスを決めるために、こうしたプロセスの後ろの方まで評価するようなことはしません。ベストパスを決定するために、よく使うパスアトリビュートとして以下があげられます。