BGPのベストパス選択アルゴリズム

BGP(Border Gateway Protocol)は同じ宛先の経路が複数存在する時、1つのベストパスを選択してルーティングテーブルに反映します。

本項では、BGPのベストパス選択アルゴリズムについて説明します。

BGPのUPDATEメッセージ処理

BGPでは、UPDATEメッセージを受信すると、以下の順に処理を行います。

各BGPピアごとに経路をAdj-RIB-Inで受信し、決定プロセスの実行でLoc-RIBとなり、各ピアごとにAdj-RIB-Outから送信される。

それぞれの意味は、以下のとおりです。

Adj-RIB-In
UPDATEメッセージを受信して未処理の状態の経路情報
Loc-RIB
決定プロセスによって選択された経路情報
Adj-RIB-Out
BGPピアへUPDATEメッセージを送信する経路情報

Loc-RIBがルーティングテーブルに反映される経路です。また、Adj-RIB-OutからBGPピアに経路が広報されます。

決定プロセス

BGPスピーカーが経路を扱う時は、以下3つの決定プロセスが行われます。

フェーズ1:優先度の計算
ポリシーなどによって、BGPピアから受信した各経路の優先度を計算します。
フェーズ2:経路の選択
フェーズ1の完了時に呼び出されます。宛先ごとにベストパスを選択して、Loc-RIBとします。
フェーズ3:経路の配布
Loc-RIBが変更された後に呼び出されます。ポリシーを適用して、Loc-RIB内の経路を各BGPピアに広報します。経路集約などは、このフェーズ内で行えます。

フェーズ1と2を経てLoc-RIBとなり、フェーズ3を経てAdj-RIB-Outになります。

ベストパスの決定

フェーズ2の時に、ベストパスの決定が行われます。その時、まずは以下の経路が除外されます。

NEXT_HOP属性
NEXT_HOP属性のIPアドレスに、到達不可の経路は除外します。理由は、通信不可の経路のためです。
ASループ
AS_PATH属性に、自身のAS番号が含まれている経路は除外します。理由は、経路がループしているためです。

上記を除外した後の優先順位は、以下のとおりです。

【ベストパス選択時の優先度】
優先順位 項目 説明
1 LOCAL_PREF属性 LOCAL_PREFの値が大きい経路を優先
2 AS_PATH属性 AS_PATH属性に含まれるAS番号が少ない経路を優先(AS_SETでは、AS数に関係なく1)
3 ORIGIN属性 ORIGIN属性の値が小さい経路を優先(IGPが最優先)
4 MULTI_EXIT_DISC属性 MULTI_EXIT_DISC(MED)属性の値が小さい経路を優先(同じASからの場合のみ)
5 EBGPとIBGP IBGPよりもEBGPで受信した経路を優先
6 内部コスト NEXT_HOP属性のIPアドレスへのIGP(OSPFなど)でのコストが小さい経路を優先
7 BGP識別子 BGP識別子が小さいBGPピアからの経路を優先(ORIGINATOR_IDがある場合は、それをBGP識別子として扱う)
8 CLUSTER_LIST属性 CLUSTER_LIST属性に含まれるクラスターIDが少ない経路を優先
9 BGPピアのアドレス BGPピアと設定しているIPアドレスが一番小さいピアからの経路を優先

LOCAL_PREF属性は、AS内部で明示的に付与する独自の優先度です。このため、最優先されます。

LOCAL_PREF属性がないなどの場合は、経由したASの数で判断されます。

ORIGIN属性は、IGP以外はまずないため、ここでベストパスが決定されることはないと思います。

MED属性は、外部のASで明示的に付与する優先度です。このような順番でベストパスが決定されます。

内部コストについて補足すると、以下でLOCAL_PREFもAS_PATHもMEDも同じ(または属性がない)だった場合、OSPFのコストなどでNEXT_HOPにもっとも近い経路が選択されます。

NEXT_HOPが203.0.113.1と192.0.2.1の2つがあった場合、その2つのアドレスへ到達するOSPFのコストが小さい経路が優先される。