💭

ルーター(Cisco/Juniper)によるベストパス選択アルゴリズムの違い

2022/07/27に公開

network

routing

tech

ルーターは複数の経路を複数の方法で学習します。しかし、最終的にどれか1つの経路を選択しなくてはなりません。本記事では、このアルゴリズム（＝ベストパス選択アルゴリズム）についてまとめたいと思います。

実は、このアルゴリズムはルーターメーカーによって若干差分があります。そのため、この記事では、ルーターメーカーが混在した場合、具体的にはCisco製機器とJuniper製機器が混在したIPネットワークを構築する場合に、ベストパス選択アルゴリズムについて留意すべきことをまとめています。まとめにあたっては、「メーカー間で動作差分が生じるのはよくないことだ」という前提でまとめています。

ベストパス選択の原則

大原則として、ベストパス選定は以下の優先度で行われます。この原則はルーターメーカーによって変わることは絶対にありません（もしあったら、その機器はルーターとは呼んではならない何か別の機器でしょう）。

IPアドレスのビット数が最もマッチするものを選ぶ（ロンゲストマッチ）
1.が同じ場合、経路の学習方法（プロトコル）のうち、信頼度が最も高いものを選ぶ（AD値）
2.が同じ場合、プロトコル内で優先度が最も高いものを選ぶ（メトリクス）

以後の各章で、1. 2. 3. をそれぞれ説明します。ただし、結論、ルーターメーカー差分が発生するのは 2. がほとんどです。ですから、この記事は主に2. について述べています。ただし、1. 2. 3. 全てが全く同じだった場合の動作に若干の差分がありますので、その点も最後に触れています。

余談ですが、ネットワーク業界の俗語でベストパスを選出アルゴリズムのことを「勝負」と言ったり、より優先したい経路を「勝たせる」という表現をしたりすることがあります。この記事でもそういった言い回しを使うことがあります。

ロンゲストマッチ

ロンゲストマッチはIPネットワークの大原則であり、他のルールよりも必ず優先されます。ルーターメーカー差分も絶対にありません。

たとえば、192.168.0.0/16と192.168.0.0/24の2つの経路を持っている場合、192.168.0.1はどちらの経路にも該当します。しかし、192.168.0.0/16は前半16ビットのみが、192.168.0.0/24は前半24ビットがマッチするため、ビット数が最も多くマッチする192.168.0.0/24が採用されます（勝ちます）。これがロンゲストマッチです。

AD値

AD（Administrative Distance）値は、経路の学習方法ごとに定められている値です。信頼のおける学習方法には低い値が、比較的信頼のおけない学習方法には高い値が設定されており、ベストパス選択の際にはより低い値の方法で学習した経路を優先します。

Cisco製機器（IOSやIOS-XRを想定します）の場合、主な経路学習方法のAD値は以下の通りです。

学習方法	AD値
Connected	0
Static Route	1
eBGP	20
OSPF	110
IS-IS	115
RIP	120
iBGP	200

参考: https://www.cisco.com/c/ja_jp/support/docs/ip/border-gateway-protocol-bgp/15986-admin-distance.html

ただ、冒頭申し上げたとおり、この値は全ルーターメーカーで共通ではありません。更に、Juniper製機器（JuNOSを想定します）では、そもそもAD値という名前ですらありません。Route Preference、または単にPreferenceと呼びます。そのうえで、Juniper製機器のPreferenceは以下の設定になっています。

学習方法	Preference
Connected	0
Static Route	5
RSVP	7
LDP (動的)	9
OSPF (内部)	10
IS-IS Level 1 (内部)	15
IS-IS Level 2 (内部)	18
RIP	100
OSPF (AS外部)	150
IS-IS Level 1 (外部)	160
IS-IS Level 2 (外部)	165
BGP	170

参考: https://www.juniper.net/documentation/en_US/junos/topics/reference/general/routing-protocols-default-route-preference-values.html

細かく見ると結構違いますね。

ただ、実際のネットワークでは、異なるルーティングプロトコルで学習する経路はサブネット長が異なり、最初に述べた原則に従ってロンゲストマッチでベストパスが選択されるケースも多いです。これは、例えば別ASからの経路を自AS内に広告する際に経路集約をすることが多いからで、その場合には当然、ベストパス選択アルゴリズムのメーカー差分を気にする必要はありません。

もちろん、このメーカー差分を気にすべきケースもありえます。例として、以下のようなケースを取り上げます。

A. eBGPとOSPFをベースとしたネットワークを構築しているとき、Cisco製機器はeBGPが、JuniperはOSPFが優先される
B. MPLSネットワークを構築しているとき、Cisco製機器では常にラベルテーブルが優先される（＝AD値による勝負ではない）が、Juniper製機器ではPreferenceに応じたベストパスが選択される

A. eBGPとOSPF

この条件に合致するネットワークを考えました。無理矢理考えたので、若干不自然かもしれませんがご容赦ください。

具体的には、以下のケースのR1を考え、Network Aのベストパスがどの経路になるかを考えると、

Cisco製機器の場合：ベストパス（図中BP(C)）
Juniper製機器の場合：ベストパス（図中BP(J)）

となるかと思います。

R1とR3はAS1、R2とR4はAS2に属する
AS内はいずれもOSPFv2で経路交換されている
R3やR4はNetwork Aと直接接続されており、その経路をOSPFへ再配送
R1とR2は直接接続されており、eBGPピアを貼っている。eBGPにはOSPFで学習した経路を再配送

対処方法を3つ考えてみましたので説明します。

対処1. 経路集約してロンゲストマッチさせる

おそらく、eBGPでR1-R2間で広告しあいたい経路は、Network Aだけではないのではないかと想像します。アドレス設計次第ですが、例えば上図のようにNetwork B, Network Cが接続されており、かつ一つの集約アドレスに集約可能だとしたら、経路集約を使う設計に変えたいですね。

AS内ではOSPFの経路集約機能を使わずに、R3やR4からNetwork A, B, Cの経路をそのまま流します。そして、R1・R2では、他ASに広告する際に経路集約を行い、詳細経路は再配布しません。こうすると、R1からみると、AS2方面からやってくる経路は集約経路なのでプレフィックス長が長く、AS内部からやってくる経路は詳細経路なのでプレフィックス長が短いです。そのため、ロンゲストマッチによりAS内経路が優先され、メーカー差分は発生しません。

対処2. 外部経路をBGP化してメトリクスで勝負させる

自分で例を作っておきながらなんですが、そもそも外部経路を何も考えずにOSPFでAS内に流通させるか？ OSPFをそのままeBGP再配送することなんてあるのか？とか、いろいろ思ってしまいますね。

Network Aがホスト直結ではない（＝ルーターを有するネットワークである）という前提になりますが、iBGP/eBGPを使って真面目に構築したら、この問題は解決しそうです。具体的には、Network AがBGPをしゃべれるという前提で、OSPFはあくまでAS内のルーターのループバックアドレス（および必要ならインターフェースアドレス）だけを流通させ、外部AS経路であるNetwork Aの経路ははフルメッシュiBGPで流通させます。

このとき、BGPのメトリクスはAS_PATHが短い経路が優先される（詳細は次の章を参照ください）ため、ベストパスはiBGP側となります。BGPのメトリクスにメーカー差分はありませんので、この方法でもメーカー差分は発生しません。

余談ですが、仮にAS_PATHが同一だと、eBGPとiBGPの勝負となりeBGPが勝ってしまいますね。

対処3. AD値を変更する

Cisco製機器もJuniper製機器も、AD値(Preference)は設定で手動変更できます。一見、根本的な解決方法のように見えてしまいがちですが、私はAD値(Preference)の変更は最終手段と考えた方がいいと思っています。

いろんな考え方はあろうかと思いますが、そもそも、よいネットワーク（＝シンプルなネットワーク、十分設計されたネットワーク、などとでも言いましょうか･･･）であれば、同じプレフィックス長の経路がeBGPとOSPFの両方から回ってくることはあまりないです。ですから、まずは対処1や対処2のようにメーカー差分が発生しないところでベストパス勝負ができるような設計を検討するのが先にやるべきことだと思います。

もちろん、やむを得ないケースもあります。その場合は以下の設定で変更できます。

Cisco製機器(IOS-XR)でOSPFのAD値を調整する例

(config)# router ospf <プロセス番号>
(config-ospf)# distance weight <AD値>

参考: https://www.cisco.com/c/en/us/td/docs/routers/xr12000/software/xr12k_r4-0/routing/command/reference/rr40xr12kbook_chapter4.html#wp51475950

Juniper製機器(JuNOS)でBGPのPreferenceを調整する例

set protocols bgp preference <Preference>

※他のヒエラルキーでも設定可能なようです。詳細は参考ドキュメントをご覧ください。

参考: https://www.juniper.net/documentation/jp/ja/software/junos/bgp/topics/ref/statement/preference-edit-protocols-bgp.html

B. MPLS

この記事はIPルーティングに関する記事ですので、MPLS（Multi-Protocol Label Switching）の話をするのは本来の話題から少しずれるのですが、どうしても触れたかったので簡単に述べさせてください。

まず、Cisco製機器とJuniper製機器で、MPLSのラベルルートに対する考え方が異なります。

Cisco製機器: MPLSラベルテーブルとIPテーブル(RIB)は全く別のテーブル。MPLSラベルテーブルはIPテーブルよりも常に優先される
Juniper製機器: MPLSラベルテーブルとIPテーブル(RIB)は同じテーブル。優先度はPreferenceによって制御される

この差により問題が生じることはほとんどありません。ただし、showコマンドで経路を確認する方法が少し変わるので、覚えておくとちょっとだけ役に立ちます。

一方、私が唯一知っているこの差分により問題が起こる事例は、PHP（Penultimate Hop Popping）に関わるものです。この話をしているともう1つ記事が書けてしまいそうなので、概要だけ説明します。

PHPは、ルーターの負荷軽減を目的に、MPLSネットワークとIPネットワークの境界の1つ前のルータでMPLSラベルをはずしてしまう動作のことです。ただし、あるルーターが、同じ経路に対してPHPするネクストホップ・PHPしないネクストホップの両方を広告されている状態では、ルーターメーカーによって少しだけ動作が変わる場合があります。その差が問題になれば、PHPを無効にして、Explicit-Nullを設定することが解決策になるかもしれません。最近のルーターは高性能ですから、Explicit-Nullにしたところで大した問題はないんじゃないですかね。

メトリクス

メトリクスはルーティングプロトコル毎に異なります。しかし、原則としてルーターメーカーによって異なることはありません。

OSPFの場合

古典的には、リンク速度に応じて自動でメトリクスを決める方法がありますが、100Mbps以上のリンクでは同じメトリクスになってしまうため、2022年現在では意味をなしません。100Mpbsという閾値を変更する方法もありますが、ルーターへ手動でcostを設定し低い方の経路をベストパスとして選出方法がより良いと思います。costはインターフェースに対して設定をします。

私の知る限り、ルーターメーカーによる差分はありません。

Cisco製機器(IOS-XR)でOSPFのコストを設定する例

(config) router ospf <プロセス名>
(config-ospf) area <エリア番号>
(config-ospf-ar) interface <IF名>
(config-ospf-ar-if) cost 10

Juniper製機器(JuNOS)でOSPFのコストを設定する例

set protocols ospf area <エリア番号> interface <IF名> metric 10

BGPの場合

原則として、ベストパス選択アルゴリズムに定められたとおりに評価します。

優先度	内容
1	WEIGHTが最も大きい【Cisco製ルータのみ】
2	LOCAL_PREFが最も大きい
3	自生成経路である(そうでないものより優先される)
4	AS_PATHが最も短い
5	ORIGINが最も小さい(IGP起因が0、EGP起因が1、再配布が2)
6	MEDが最も小さい
7	eBGPである(iBGPより優先される)
8	ネクストホップまでのIGPメトリクスが最も小さい
9	eBGPの場合、最も古い
10	BGPネイバのルータIDが最小
11	BGPネイバのIPアドレスが最小

参考: https://www.cisco.com/c/ja_jp/support/docs/ip/border-gateway-protocol-bgp/13753-25.html

こちらも原則、ルーターメーカーの差はありません。ただし、Cisco製機器の場合のみ、Weightというとても強いアトリビュートがあります。Weightの利用を控えることで、ルーターメーカーの差分は無くなります。

現実的な代替策としては、Weightの代わりに似たような挙動をするLOCAL_PREF(Local preference)を使うことが考えられます。しかし、LOCAL_PREFはiBGPでしか使えません。eBGPで代わりになるものがないので、そこは難しいところです。両AS共に自社の管理するASであれば、MEDを使って相手から優先度を広告してもらう方法が採用できますが･･･。

Staticの場合

Static Routingを複数設定する場合、その優先度を設定できます。この動作にメーカー差分は発生しませんが、Static Routingの設定方法はメーカーによるクセが強いです。

Cisco製機器(IOS-XR)でStatic Routingの優先度を設定する場合

(config)# router static
(config-static)# address-family ipv4 unicast 
(config-static-afi)# x.x.x.x/x y.y.y.y <Distance>

Ciscoでは、優先度をDistanceといいます。Distanceは低い方が優先されます。このようなStatic Routingの経路をFloating Static Routeと呼びます。

参考: https://www.cisco.com/c/en/us/td/docs/routers/xr12000/software/xr12k_r3-9/routing/configuration/guide/xr12krc39_chapter8.html

Juniper製機器(JuNOS)でStatic Routingの優先度を設定する場合

set routing-options static route x.x.x.x/x next-hop y.y.y.y
set routing-options static route x.x.x.x/x preference <Preference>
set routing-options static route x.x.x.x/x qualified-next-hop y.y.y.y
set routing-options static route x.x.x.x/x qualified-next-hop y.y.y.y preference <Preference>

Juniperでは、優先度をPreferenceといいます。Preferenceは低い方が優先されます。このようなネクストホップをQualified Next Hopsといいます。

参考: https://www.juniper.net/documentation/us/en/software/junos/static-routing/topics/topic-map/static-route-prefer-qualified-next-hop.html

なお、Cisco製機器の場合、ネクストホップをIPアドレスではなくIF名を設定することもできます（もしかして、今はJuniper製機器でもできるのでしょうか？）。ルーターメーカーによってネクストホップの指定方法を混在させてしまうと、リンクダウン時の動作にメーカー差分が発生することとなります。今回のベストパス選択アルゴリズムとはあまり関係ないものの、揃えておきたいところですね。

ロードバランス

さて、ここまでで、1. ロンゲストマッチ、2. AD値、3. メトリクスの説明は終わりました。しかし、3. までで決着が付かない場合、すなわち各プロトコルのメトリクスも同じだった場合、ルーターはどうやって経路を決めるのでしょうか。

プロトコル毎の違い

OSPFの場合、経路までのコストが全く同じだと、両方の経路がベストパスとして選出され、実際の転送先はルーターハードウェアがどちらを使うかラウンドロビンで決定します。これを ECMP（Equal Cost Multi-Path） といいます。

BGPの場合、一見するとこんなことは起こらなさそうです。優先度11のBGPネイバのIPアドレスで勝負すれば、同じで勝負がつかないということはほぼ起こりえないからです。しかしながら、あえて複数のベストパスを選択したい場合に BGPマルチパスという設定をすることができます。この場合、先に説明したBGPのベストパス選択アルゴリズムは優先度8までしか評価が行われず、そこでも決着が付かなかった場合はどちらの経路もベストパスとして認識されるようになります。その際、実際の転送先は、ECMPと同様ラウンドロビンで決定されます。

Staticの場合は･･･ごめんなさい、分かりません。そんな設定にしようと思ったことがないからです。というか、コミット時に怒られてしまい、設定できないかもしれませんね。

per-flowとper-prefix

プロトコル毎の違いで説明した部分は、ルーターメーカーによって違いがない部分でした。しかし、実際のラウンドロビン動作は、ルーターメーカーによって差があります。ラウンドロビンでロードバランス先を決定する単位が違います。具体的には、以下2つのパターンがあります。

per-packet: 実際にパケットが到達した際に都度どちらを使うか選択
per-prefix: ルーティングテーブルで現れる経路(prefix)の単位でどちらかを使うか選択

少し砕けた表現で説明しますと、 per-packetの方がより "ばらけます"。 同じ経路(prefix)だったとしても、実際に到達するパケット毎にロードバランスされるからです。

各ルーターメーカーの採用している方法は以下のとおりです。

メーカー	per-packet	per-prefix
Cisco	○(初期設定)	×(設定不可)
Juniper	△(設定可)	○(初期設定)

表からわかるとおり、この2つのメーカーを同じ設定にしたければJuniper製ルーターの設定を変えるしかありません。ルータ全体での設定を変える場合、routing-optionsヒエラルキーに設定しちゃいましょう。

set policy-options policy-statement LB-POLICY
set policy-options policy-statement LB-POLICY then load-balance per-packet
set routing-options forwarding-table export LB-POLICY

参考: https://www.juniper.net/documentation/us/en/software/junos/sampling-forwarding-monitoring/topics/concept/policy-configuring-per-packet-load-balancing.html

注意点として、実はper-packetとかper-prefixという名前自体が、ルーターメーカーによって統一されていません。正直、私も記事で紹介したこの呼び方が正しいのか、よく分かりません。per-prefixのことをper-flowと呼んだり、per-packetのことをper-flowと呼んだりします。ほんとに分かりません。

まとめ

いかがでしたでしょうか。相変わらず長文になってしまいましたが、ベストパス選択アルゴリズムに関するルーターメーカーの差分について、まあまあよくまとまったのではないかと思います。

AD値はルーターメーカーによって違う（特にeBGPとOSPFに注意）
Cisco製ルーターはBGPのWeightが使える
ロードバランスメカニズムの初期値もルーターメーカーによって違う

なお、実機検証環境がなくなってしまったので、実機検証できていません。ツッコミどころがあればコメント頂けると嬉しいです。それでは。