BGPのベストパス選択アルゴリズム
BGP(Border Gateway Protocol)は同じ宛先の経路が複数存在する時、1つのベストパスを選択してルーティングテーブルに反映します。
本項では、BGPのベストパス選択アルゴリズムについて説明します。
BGPのUPDATEメッセージ処理
BGPでは、UPDATEメッセージを受信すると、以下の順に処理を行います。
それぞれの意味は、以下のとおりです。
- 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にもっとも近い経路が選択されます。