EIGRP

EIGRP（Enhanced Interior Gateway Routing Protocol）は、シスコシステムズの独自ルーティングプロトコルで、IGRPに緩やかに基づいている。

自律システム (AS) 内のルーティングを行うInterior Gateway Protocol (IGP) の通信プロトコルである。

EIGRPは距離ベクトル型ルーティングプロトコルの拡張版であり、ネットワークトポロジーやルーターの帯域幅や処理能力を変更した後のルーティングの不安定さを最小にするよう最適化している。EIGRPをサポートするルーターは、32ビットのEIGRPメトリック（統計）情報を24ビットのIGRPメトリック情報に変換することで、隣接するIGRPルーター用の情報を自動的に再構築する。ルーティング最適化の多くはSRIの開発した Diffusing Update Algorithm (DUAL) に基づいており、ループフリー運用と高速コンバージェンス（収束）機構を提供している。

基本動作

EIGRPが収集するデータは以下の3つのテーブルに格納される。

隣接テーブル: 隣接するルータに関するデータを格納する。隣接するルーターとは、インタフェースが直接連結されていて、直接アクセス可能なルーターである。
トポロジテーブル: 名前から誤解されがちだが、ネットワークトポロジーの概要を格納するテーブルではない。むしろ、隣接するルーターから集めたルーティングテーブルに関する情報だけを格納している。EIGRPネットワークにおける送信先ネットワークの一覧と、それぞれのメトリック情報のテーブルである。そして、それぞれの送信先について、サクセサとフィージブルサクセサが（もしあれば）記述してある。ルーティングが安定している送信先は「パッシブ」、ルーティングに変更があり更新中の送信先は「アクティブ」とされている。
ルーティングテーブル: 全ての送信先についての実際のルート（経路）を格納している。トポロジテーブルからサクセサ（およびもしあればフィージブルサクセサ）を持つ送信先ネットワークのエントリを取りだして格納している（不等コスト負荷分散を行うには variance コマンドを使う）。サクセサおよびフィージブルサクセサは、その送信先の次のホップのルーターとして機能する。

他の距離ベクトル型プロトコルとは異なり、EIGRPではトポロジテーブルを保守するための定期的なルート更新を行わない。ルーティング情報は新たな隣接ルーターが接続されたときに交換し、その後は変更部分だけを送信する。

複数のメトリック情報

EIGRPでは、各経路ごとに異なる5種類のメトリック情報を持っている。

遅延合計（Total Delay、10μ秒単位）
最小帯域幅（Minimum Bandwidth、kbit/s単位）
信頼性（Reliability、1から255の数値で、255が最も信頼できる）
負荷（Load、1から255の値で、255が最も負荷が高い）
最小MTU（実際には計算で使っていない）

デフォルトでは遅延合計と最小帯域幅だけが使われるが、管理者がそれぞれのメトリック情報の収集を必要に応じて設定できる。

経路を比較するとき、以下のような式にこれらメトリック情報を入れて計算し、複合メトリック値を求める。

{\bigg [}{\bigg (}K_{1}\cdot {\text{Bandwidth}}+{\frac {K_{2}\cdot {\text{Bandwidth}}}{256-{\text{Load}}}}+K_{3}\cdot {\text{Delay}}{\bigg )}\cdot {\frac {K_{5}}{K_{4}+{\text{Reliability}}}}{\bigg ]}\cdot 256

式に出現する定数（ $K_{1}$ から $K_{5}$ ）はユーザー設定可能で、これによって動作が変化する。なお、 $K_{5}$ が0の場合（デフォルト設定）には ${\tfrac {K_{5}}{K_{4}+{\text{Reliability}}}}$ という項を1とみなして計算上考慮しないことになっている。

$K_{1}$ と $K_{3}$ はデフォルトでは1で、他の定数はデフォルトで0である。したがってデフォルト設定では上記の式が (Bandwidth + Delay) * 256 となっている。

EIGRPによるルーティングを行うネットワークでは、明らかに全てのルーターでこれらの定数を同じ設定にする必要がある。さもないと恒久的なルーティングループが生じる可能性が出てくる。シスコのEIGRPルーターは、これらの定数値が一致しない場合はエラーを報告し、他のルーターと隣接関係を形成しない。

EIGRPは帯域幅と遅延のメトリック情報を以下の計算でスケーリングする。

EIGRPの帯域幅 = 10⁷ / インタフェースの帯域幅

EIGRPの遅延 = インタフェースの遅延 / 10

シスコのルーターでは、インタフェースの帯域幅は設定可能な静的パラメータであり、kbit/s単位である。10⁷ kbit/s（つまり10Gbit/s）という値をインタフェースの帯域幅で割った値を上述の複合メトリック値の計算式で使用する。同様にインタフェースの遅延も設定可能な静的パラメータであり、μ秒単位である。これを10で割った値は10μ秒単位の値となり、それを上述の計算式で使用する。

IGRPでも基本的に同じ計算式で複合メトリック値を計算するが、IGRPの計算式では256という係数が使われていない。この係数はEIGRPとIGRPの後方互換性を保つ目的で導入された。複合メトリック値はIGRPでは24ビットの値だが、EIGRPでは32ビットの値になっている。したがって、24ビットの値を256倍することで8ビット左へシフトしたのと同じことになり、値が32ビットに拡張される。このため、EIGRPとIGRPの間で情報を交換する際には自動的に256倍したり256で割って変換している。

EIGRPはそれぞれの経路のホップ数も保持しているが、メトリック計算にはホップ数は使われない。ホップ数は事前設定された最大値（デフォルトでは100で、1から255の範囲で設定可能）と比較する用途でのみ使用する。ホップ数が最大値を超えている経路はルーターによって到達不能と判断される。

サクセサ

ある送信先のサクセサ (successor) とは、以下の2つの条件を満たす次のホップのルーターである。

その送信先への最小距離を提供する。
何らかのルーティングループの一部でないことが保証されている。

最初の条件は、同じ送信先をアドバタイズしている全隣接ルーターのメトリック情報について、それぞれのリンクコストを加えた上で比較し、トータルの距離が最小の隣接ルーターを選べばよい。次の条件は、その送信先をアドバタイズしている全隣接ルーターについて、後述するフィージビリティコンディションを調べればよい。トポロジーによっては、1つの送信先にサクセサが複数存在することもある。

各送信先のサクセサはトポロジテーブルに記録され、さらにルーティングテーブルでその送信先の次のホップを示すのに使われる。

フィージブルサクセサ

ある送信先のフィージブルサクセサ (feasible successor) とは、以下の条件を満たす次のホップのルーターである。

何らかのルーティングループの一部でないことが保証されている。

サクセサと同じく、フィージビリティコンディション（後述）を調べればよい。

したがって、サクセサであれば必ずフィージブルサクセサでもある。しかし、EIGRPを解説した文書では「フィージブルサクセサ」はループフリーの経路を持っているがサクセサではない（距離が最小でない）ルーターだけを指すとされていることが多い。そういう意味では、到達可能な1つの送信先には常に1つのサクセサがあるが、フィージブルサクセサは存在しない場合があることになる。

フィージブルサクセサはサクセサと同じ送信先への経路を提供できるが、距離が長い。ルーターはいつでも警告なしにパケットをサクセサまたはフィージブルサクセサ経由で「パッシブ」な送信先に送信でき、そのパケットが適切に転送されることを期待できる。フィージブルサクセサもトポロジテーブルに記録される。

フィージブルサクセサは、サクセサまたはサクセサとのリンクに障害が発生した場合のバックアップ経路を提供する。不等コスト負荷分散（経路コストと反比例するようにネットワークトラフィックを分散させること）を行う場合、フィージブルサクセサは負荷分散された送信先のルーティングテーブルで次のホップとして使われる。

デフォルトでは、1つの送信先のサクセサおよびフィージブルサクセサをルーティングテーブルに格納できる個数は4個に制限されている。この制限は1から6までの範囲で設定変更できる。最新のCisco IOS（12.4以降）では1から16まで設定可能になっている。

アクティブ状態とパッシブ状態

トポロジテーブルでは、送信先それぞれにパッシブまたはアクティブという印がついている。パッシブ状態では、その送信先についてのサクセサが特定されている。サクセサがフィージビリティコンディションを満たさなくなり、かつフィージブルサクセサがない場合（すなわちバックアップ経路がない場合）、その送信先はアクティブ状態とされる。隣接ルーターへのあらゆるクエリに応答が返ってきた場合、アクティブ状態からパッシブ状態に戻る。なお、ある送信先のサクセサがフィージビリティコンディションを満たさなくなっても、フィージブルサクセサがある場合はフィージブルサクセサのうちトータルの距離が最小のものを新たなサクセサに選ぶので、パッシブ状態のままとなる。

報告距離と到達可能距離

アドバタイズ距離 (AD) とは、送信先ネットワークへの経路に沿った複合メトリックであり、上流隣接ルーターによってアドバタイズされる^[1]。報告距離とも呼ばれ、サクセサである隣接ルーターを経由したときの送信先との最小距離と等しい。

到達可能距離 (FD) とは、あるルーターから特定の送信先への既知の最小の距離である。これはアドバタイズ距離 (AD) にそのADを送信した隣接ルーターまでのコストを加えた値である^[1]。なお、このメトリック情報は「その経路が最近アクティブからパッシブ状態になった時点」以降の最小距離である。すなわち経路がパッシブ状態であればFDは距離が減少する場合のみ更新され、さもなくば更新されない。一方、経路をアクティブ状態にする必要が生じた場合、経路がアクティブ状態からパッシブ状態になったときにFDが更新される。このときFDは増加することもある。アクティブ状態からパッシブ状態への変化を契機として、その経路の新たな履歴が開始される。

例えば、新たに発見された送信先 X への経路がアクティブからパッシブになり、距離が10だったとする。ルーターはADとFDを10とする。その後距離が10から8に減少したとする。パッシブ状態のままなので（距離の減少はフィージビリティコンディションには影響しないため）、ルーターはADとFDを8とする。さらにその後、距離が12に増加したが、サクセサとフィージブルサクセサはそのままだとする。その場合、ADは12に更新されるが、FDは8のままとなる。つまり、ADとFDが一致しなくなる。その後サクセサが障害状態になり、他のフィージブルサクセサが存在しないとする。するとその経路はアクティブ状態となり、ルーターは隣接ルーターに送信先 X の新たな経路を問い合わせる。新たに見つかった経路の距離が100だったとすると、ルーターは経路をパッシブ状態にした上でADとFDを100とする。

フィージビリティコンディション

フィージビリティコンディションとは、EIGRPネットワークにおけるループフリー（ループがない状態）の十分条件である。サクセサとフィージブルサクセサは送信先までのループフリーな経路を持つことを保証されており、そのためにフィージビリティコンディションを使う。その大まかな条件は非常に単純である。すなわち、「ある送信先について、隣接ルーターが距離をアドバタイズしていて、その距離が到達可能距離以下であれば、その隣接ルーターはその送信先のループフリーな経路上にある」というものである。言い換えれば、「ある送信先について、ある隣接ルーターがその送信先に既知のルーターよりも近いと知らせてきた場合、その隣接ルーターはその送信先のループフリーな経路上にある」ということになる。

正確に言えば、ある送信先について AD < FD となる隣接ルーターはその送信先へのループフリーな経路上にある。

この条件は Source Node Condition とも呼ばれ、SRIの J. J. Garcia-Luna-Aceves が提案している条件の1つである。Source Node Condition は Diffusing Update Algorithm (DUAL) に関する論文にある^[2]。

この条件が十分条件であって必要条件ではないという点は重要である。すなわち、この条件を満たす隣接ルーターはループフリーな経路上にあるが、この条件を満たさなくてもループフリーな経路上にある隣接ルーターは存在しうる。しかしそのようなルーターは最短経路上にはないので、それを使わなくともネットワークの機能には大きな影響はない。そのような隣接ルーターがその送信先についてアクティブ状態となった場合、パッシブ状態に戻ったときに再評価されることになる。

距離ベクトル型としての分類

従来、EIGRPはシスコのマーケティング資料では平衡型ハイブリッドルーティングプロトコルだと説明されていた。ハイブリッドとは、リンクステート型と距離ベクトル型のプロトコルの長所を組み合わせたものと説明されていた。しかし、このような説明は本質的には正しくない。定義によれば、

距離ベクトル型ルーティングプロトコルは、分散型のベルマン-フォード法に基づいて最短経路を求める。ノード間で既知の全送信先についての距離ベクトルを交換しあう。それ以上のトポロジー情報は交換しない。これによって、各ノードはネットワーク内の全送信先を知り、各隣接ノード経由でのそれぞれの送信先への距離を知ることができる。しかし、ノードは実際のネットワークトポロジーを知らないし、それを必要としない。
リンクステート型ルーティングプロトコルは、グラフ理論の最短経路を求めるアルゴリズム（ダイクストラ法がよく使われる）に基づいている。ノード間でノードの接続関係の情報を交換する（基本的には、ノードの隣接関係情報をネットワーク全体に通知する）。したがって、各ノードは正確なネットワークトポロジーを知っており、ネットワークをグラフとして表現できる。このグラフを使い、各送信先への最短経路を求める。

EIGRPルーターは帯域幅、遅延、負荷、信頼性、経路のMTUといった情報を相互にやり取りしている。それぞれのルーターは送信先への距離を計算するためにそれらのパラメータを使用する。メッセージにはそれ以上のトポロジー的情報は存在しない。このような動作原理はまさしく距離ベクトル型プロトコルである。したがって、EIGRPは基本的には距離ベクトル型プロトコルに分類できる。

EIGRPが素朴な距離ベクトル型プロトコルにはない技法をいくつか使っていることは事実である。例えば、以下のようなものがある。

ルーター間の隣接関係を発見し保守する目的で hello パケットを明示的に使用する。
ルーティング更新情報の送信に信頼性のあるプロトコルを使用する。
ループフリーな経路を選択するためにフィージビリティコンディションを使う。
ネットワークの経路に障害や変更が発生したとき、新たな最短経路を計算するための拡散計算を使用する。

これらの技法はEIGRPの基本的動作原理に影響を与えるものではなく、しかも他の距離ベクトル型プロトコルでも似たような技法を使っているものがある（例えばAODVとDSDV）。EIGRPは拡張された距離ベクトル型ルーティングプロトコルだが、ハイブリッドプロトコルではない。

真のハイブリッドのルーティングプロトコルとしてはマルチエリアの Open Shortest Path First (OSPF) プロトコルがある。OSPFはエリア内ではリンクステート型であり、エリア内の正確なトポロジーを使っている。エリア間のルーティングには距離ベクトル型の手法を使っている。

EIGRPの各種コマンド

show ip protocols （ルーティングプロトコルの状態を表示。動作しているEIGRPのAS番号ごとに K値やルータIDの情報、および自動集約の有無を確認できる）
show ip eigrp topology　（EIGRPのトポロジテーブルを表示。サクセサ、フィージブルサクセサ、FD値、AD値が確認できる）
show ip eigrp interfaces　（EIGRPが動作するインターフェースの情報。各インターフェイスで確立しているネイバー数も表示される。detailオプションあり）
show ip eigrp neighbors　（EIGRPの隣接機器の情報を表示）

その他の詳細

EIGRPは Classless Inter-Domain Routing (CIDR) を扱え、可変長サブネットマスクを使える。この点がIGRPからの大きな改善点である。逆に問題点はシスコの機器以外ではサポートされていないため、EIGRPを採用した組織で一種のベンダロックインに繋がる点である。またEIGRPは、ルーターが正確なネットワークトポロジーを知っていないとできない用途に使うことができない（例えば、MPLSのトラフィック・エンジニアリング）。

EIGRPはPDM (Protocol-Dependent Module) を使って、IP、IPv6、IPX、AppleTalkに対応したルーティングプロセスを別個に実行できる。しかし、これを使ってプロトコル間の変換はできない。

Cisco IOS ルーター上でかつてのクラスのあるIPアドレス方式を使うEIGRPの設定の例を以下に示す。

Router> enable
Router# config terminal
Router(config)# router eigrp ?
  <1-65535>  Autonomous system number
Router(config)# router eigrp 1
Router(config-router)# network 192.168.0.0
Router(config-router)# end

下記は、クラスのないIPアドレスを使っている場合の設定例である。この例にあるワイルドカード 0.0.15.255 は、最大4094台のホストを持つサブネットを示している。これは、サブネットマスク 255.255.240.0 のビット単位の補数である。no auto-summary コマンドはクラスのあるネットワークとの境界での自動的な経路集約を防ぐもので、これを設定しないとループが発生する。

Router> enable
Router# config terminal
Router(config)# router eigrp 1
Router(config-router)# network 10.201.96.0 ?
  A.B.C.D  EIGRP wild card bits
  <cr>
Router(config-router)# network 10.201.96.0 0.0.15.255
Router(config-router)# no auto-summary
Router(config-router)# end

脚注

[脚注の使い方]

^ ^a ^b Feasible Distance, Reported Distance, and Feasible Successor Enhanced Interior Gateway Routing Protocol、CISCO
^ J. J. Garcia-Luna-Aceves, Loop-Free Routing Using Diffusing Computations、IEEE/ACM Transactions of Networking, 1993年2月

参考文献

外部リンク

[EIGRPdoc-1] Feasible Distance, Reported Distance, and Feasible Successor Enhanced Interior Gateway Routing Protocol、CISCO

[2] J. J. Garcia-Luna-Aceves, Loop-Free Routing Using Diffusing Computations、IEEE/ACM Transactions of Networking, 1993年2月

[1]

[2]

表話編歴ルーティングプロトコル
一般	Babel（英語版） B.A.T.M.A.N. BGP IS-IS Optimized_Link_State_Routing_Protocol OSPF RIP
ベンダー主導型	(Cisco) IGRP / EIGRP (Nortel) Split multi-link trunking（英語版） / R-SMLT（英語版） / Distributed Split Multi-Link Trunking（英語版）
特殊目的	Collection Tree Protocol（英語版） Constrained Shortest Path First（英語版） Distance_Vector_Multicast_Routing_Protocol（英語版）
過去	Border_Gateway_Multicast_Protocol（英語版） EGP