メモのページ - チラシの裏メモ 3枚目

通信技術や気になった事を黙々とメモし続ける

EIGRPのDiffusing Computation

Cisco Systems 通信技術

EIGRPの経路選択に関する検証。今回はEIGRPのネイバをダウンさせた後の様子のメモ。
EIGRPではOSPFのようにHelloパケットのDead Intervalを待つ事は無く、トポロジ変更を検知してすぐにネイバーダウン認識とEIGRPトポロジテーブルの更新が行われる。
EIGRPネイバー確立と同様にトポロジテーブルの更新が行われるのでコンバージェンスが早い。


フィージブルサクセサが無い場合のDUAL処理
Link Downを検知すると、経路情報の再計算の為にDUAL(Diffusing Update ALgorithm)と呼ばれる処理が実行される。
DUAL処理の方法としてDiffusing ComputationとLocal Computationの2通りがある。
宛先経路へのLinkがDownした際、宛先経路へのフィージブルサクセサが無い場合はDownしたLinkにActiveのステータスを付与し、ネイバに対しQUERYで代替経路を要求する。Link Down検知からネイバへのQUERY送信とReply受信、そしてトポロジ更新までの一連の処理をDiffusing Computationという。
今回は、Diffusing Computationの様子をdebugコマンドで出力させてみた。


Diffusing Computationとは
Link Down等により宛先へ到達可能なルートが利用出来なくなった場合、DUAL(Diffusing Update Algorithm)は拡散計算(Diffusing Computation)を呼び出し、問題のあるルートのすべてのトレースがネットワークから削除されるようにする。その時点で、通常のベルマンフォードアルゴリズムを使用して新しいルートを利用可能にする。
直訳すると「拡張計算」である。Ciscoの日本語サイトを始めCiscoの認定試験の解説サイト等では目にする事が無い用語だが、海外のエンジニア達とやりとりする時たまに出てくる。
初見はEIGRPの唯一の参考書「EIGRP NETWORK DESIGN SOLUTIONS (2000年,Ivan Pepelnjak著, Cisco Press刊)」であるが、Diffusing ComputationそのものはEIGRPの専門用語ではなく、1979年には既に論文にて挙げられている。※下記のリンク集(Termination detection for diffusing computations)を参照


当方の環境
構成（クリックすると拡大表示）

MI-CAT4503-S5-SW-01：Catalyst4503
MI-CAT4503-S5-SW-02：Catalyst4503
MI-CAT3750-ME-SW-01：Catalyst3750Metro
MI-CAT3750-ME-SW-01〜MI-CAT4503-S5-SW-02：EIGRP AS1
今回はMI-CAT3750-ME-SW-01〜MI-CAT4503-S5-SW-01区間のケーブルを抜線しLink Downを発生させてみた。


Diffusing Computationの流れ
1.debug eigrp fsmコマンドでDUAL処理の経緯を出力。
併せてdebug eigrp packetsコマンドでHelloやUpdateが送受信される様子を出力。

以下は、EIGRPネイバとーの間で送受信されるHelloパケットの様子。
デフォルトの5秒間隔で、2つのネイバー(Gi3/24ではMI-CAT3750-ME-SW-01、Gi3/23ではMI-CAT4503-S5-SW-02)との間でHelloが行き来している事が分かる。

MI-CAT4503-S5-SW-01#undebug all

All possible debugging has been turned off
MI-CAT4503-S5-SW-01#
MI-CAT4503-S5-SW-01#
MI-CAT4503-S5-SW-01#debug eigrp fsm
EIGRP Finite State Machine debugging is on
MI-CAT4503-S5-SW-01#
MI-CAT4503-S5-SW-01#
MI-CAT4503-S5-SW-01#debug eigrp packets
　　(UPDATE, REQUEST, QUERY, REPLY, HELLO, IPXSAP, PROBE, ACK, STUB, SIAQUERY, SIAREPLY)
EIGRP Packet debugging is on
MI-CAT4503-S5-SW-01#
Apr 29 02:52:16.883: EIGRP: Sending HELLO on GigabitEthernet3/24
Apr 29 02:52:16.883:　 AS 1, Flags 0x0:(NULL), Seq 0/0 interfaceQ 0/0 iidbQ un/rely 0/0
Apr 29 02:52:17.371: EIGRP: Received HELLO on GigabitEthernet3/24 nbr 169.10.11.2
Apr 29 02:52:17.371:　 AS 1, Flags 0x0:(NULL), Seq 0/0 interfaceQ 0/0 iidbQ un/rely 0/0 peerQ un/rely 0/0
Apr 29 02:52:18.443: EIGRP: Sending HELLO on GigabitEthernet3/23
Apr 29 02:52:18.443:　 AS 1, Flags 0x0:(NULL), Seq 0/0 interfaceQ 0/0 iidbQ un/rely 0/0
Apr 29 02:52:21.023: EIGRP: Received HELLO on GigabitEthernet3/23 nbr 169.10.10.2
Apr 29 02:52:21.023:　 AS 1, Flags 0x0:(NULL), Seq 0/0 interfaceQ 0/0 iidbQ un/rely 0/0 peerQ un/rely 0/0


この辺で、MI-CAT4503-S5-SW-01とMI-CAT3750-ME-SW-01との間のケーブルを抜線。
EIGRPネイバーへのLinkダウンさせてみる。
Link Down検知をトリガーとした、Diffusing ComputationによるDUAL処理の流れは、以下のとおり。

・リンクダウンを検知すると即座に、経路情報169.10.11.0/30のDistance値を最大値である4294967295にセット。(下記[1])
・宛先169.10.11.0/30に対するフィージブルサクセサが無いか確認。(下記[2])
　NextHopは0.0.0.0になっている。Default-Routeみたいな感じ。
・トポロジデータベースにてダウンしたネイバーへの経路に「Active」のステータスを付与。(下記[3])
　Activeと言うと経路が有効になっているような印象を持つが、show ip eigrp topologyコマンドを実行すると解るとおり、有効な経路にはPassiveが付与される。
・Reply-Statusテーブルを作成し、ネイバーからのReplyを待つ。(下記[4])
・ここでEIGRPネイバーダウンの出力。(下記[5])
・EIGRPがLinkDownを検知。実際はもっと早い段階で検知している。(下記[6])
・経路情報169.100.10.3/32に対しても、上記[1]〜[6]同様の処理が実行される。(下記[7])
・トポロジIDリストの更新。この段階では、まだ169.10.11.0/30と169.100.10.3/32は一応有る事になっている。(下記[8])
・ここでメトリック再計算の処理は終了。リンクダウン検知からここまで同時に実行されている。以下よりActiveステータスの解除と経路情報の削除処理に入る。(下記[9])
・ネイバーに送信するQUERYをキューイング。(下記[10])
・ネイバーにQUERYを送信。QUERYでネイバに対し経路情報を問い合わせする。(下記[11])
　ネイバーからACKが返って来るまでの間は、Active状態である為にその宛先ヘのトラヒックは廃棄される。
・上記[11]のQUERYに対する応答を受信。(下記[12])
・ネイバーからReplyを受信。(下記[13])
　全てのネイバーからReplyを受信しACKで返答した段階で、上記[3]で付与したActiveステータスを解除する。
　またはActive Timerが切れるとActiveステータスが解除される。(デフォルト状態ではActive Timerは3分)
・上記[13]のRaplyに対するACKをキューイング。(下記[14])
・上記[13]のActiveステータスのまま。(下記[15])
・上記[13]で受信したReplyの内容。到達不可能な経路である為にDistance値は最大値のまま。(下記[16])
・上記[4]のReply-Statusテーブルを空にする。(下記[17])
・トポロジテーブルより経路情報を削除。(下記[18])
・経路情報169.100.10.3/32に対しても、上記[15]〜[18]同様の処理が実行される。(下記[19]から下)
・上記[13]のReplyに対するACKを送信。(下記[20])

Apr 29 02:52:26.579: EIGRP-IPv4(1): rcvupdate: 169.10.11.0/30 via Connected metric 4294967295/
4294967295 on tid 0 [1]
Apr 29 02:52:26.579: EIGRP-IPv4(1): Find FS for dest 169.10.11.0/30. FD is 28160, RD is 28160
 on tid 0　[2]
Apr 29 02:52:26.579: EIGRP-IPv4(1):     0.0.0.0 metric 4294967295/4294967295 not found Dmin
 is 4294967295　[2]
Apr 29 02:52:26.579: DUAL: AS(1) Peer total 2 stub 0 template 2 for tid 0
Apr 29 02:52:26.579: DUAL: AS(1) Dest 169.10.11.0/30 entering active state for tid 0.　[3]
Apr 29 02:52:26.579: EIGRP-IPv4(1): Set reply-status table. Count is 2.　[4]
Apr 29 02:52:26.579: EIGRP-IPv4(1): Not doing split horizon
Apr 29 02:52:26.579: %DUAL-5-NBRCHANGE: EIGRP-IPv4 1: Neighbor 169.10.11.2 (GigabitEthernet
3/24) is down: interface down　[5]
Apr 29 02:52:26.579: IGRP2: linkdown: start - 169.10.11.2 via GigabitEthernet3/24　[6]
Apr 29 02:52:26.579: DUAL: Destination 169.100.10.3/32 for tid 0　[7]
Apr 29 02:52:26.579: EIGRP-IPv4(1): Find FS for dest 169.100.10.3/32. FD is 156160, RD is 156160
 on tid 0
Apr 29 02:52:26.579: EIGRP-IPv4(1):     169.10.11.2 metric 4294967295/4294967295 not found
 Dmin is 4294967295
Apr 29 02:52:26.579: DUAL: AS(1) Peer total 1 stub 0 template 1 for tid 0
Apr 29 02:52:26.579: DUAL: AS(1) Dest 169.100.10.3/32 entering active state for tid 0.
Apr 29 02:52:26.579: EIGRP-IPv4(1): Set reply-status table. Count is 1.
Apr 29 02:52:26.579: EIGRP-IPv4(1): Not doing split horizon
Apr 29 02:52:26.579: DUAL: Destination 169.10.10.0/30 for tid 0　[8]
Apr 29 02:52:26.579: DUAL: Destination 169.10.11.0/30 for tid 0
Apr 29 02:52:26.579: DUAL: AS(1) Clearing handle 1, count now 1
Apr 29 02:52:26.579: DUAL: Destination 169.100.10.2/32 for tid 0
Apr 29 02:52:26.579: DUAL: Destination 169.100.10.1/32 for tid 0
Apr 29 02:52:26.579: DUAL: linkdown: finish　[9]
Apr 29 02:52:26.591: EIGRP: Enqueueing QUERY on GigabitEthernet3/23 tid 0 iidbQ un/rely 0/1
 serno 12-13　[10]
Apr 29 02:52:26.599: EIGRP: Sending QUERY on GigabitEthernet3/23 tid 0　[11]
Apr 29 02:52:26.599: 　AS 1, Flags 0x0:(NULL), Seq 17/0 interfaceQ 0/0 iidbQ un/rely 0/0 serno 12-13
Apr 29 02:52:26.603: EIGRP: Received ACK on GigabitEthernet3/23 nbr 169.10.10.2　[12]
Apr 29 02:52:26.603: 　AS 1, Flags 0x0:(NULL), Seq 0/17 interfaceQ 0/0 iidbQ un/rely 0/0 peerQ
 un/rely 0/1
Apr 29 02:52:26.603: EIGRP: GigabitEthernet3/23 multicast flow blocking cleared
Apr 29 02:52:26.619: EIGRP: Received REPLY on GigabitEthernet3/23 nbr 169.10.10.2　[13]
Apr 29 02:52:26.619: 　AS 1, Flags 0x0:(NULL), Seq 11/17 interfaceQ 0/0 iidbQ un/rely 0/0 peerQ
 un/rely 0/0
Apr 29 02:52:26.619: EIGRP: Enqueueing ACK on GigabitEthernet3/23 nbr 169.10.10.2 tid 0　[14]
Apr 29 02:52:26.619: 　Ack seq 11 iidbQ un/rely 0/0 peerQ un/rely 1/0
Apr 29 02:52:26.619:  　Handling TLV: 242 43 for 0
Apr 29 02:52:26.619: EIGRP-IPv4(1): dest(169.10.11.0/30) active　[15]
Apr 29 02:52:26.619: EIGRP-IPv4(1): rcvreply: 169.10.11.0/30 via 169.10.10.2 metric 4294967295/
4294967295 for tid 0　[16]
Apr 29 02:52:26.619: EIGRP-IPv4(1): reply count is 1
Apr 29 02:52:26.619: DUAL: AS(1) Clearing handle 0, count now 0
Apr 29 02:52:26.619: DUAL: AS(1) Freeing reply status table　[17]
Apr 29 02:52:26.619: EIGRP-IPv4(1): Find FS for dest 169.10.11.0/30. FD is 4294967295, RD is 4294967295
 on tid 0 found
Apr 29 02:52:26.619: DUAL: AS(1) Removing dest 169.10.11.0/30, nexthop 0.0.0.0　[18]
Apr 29 02:52:26.619: DUAL: AS(1) Removing dest 169.10.11.0/30, nexthop 169.10.10.2　[18]
Apr 29 02:52:26.619: DUAL: AS(1) No routes.  Flushing dest 169.10.11.0/30 route:
 169.10.11.0/30　[18]
Apr 29 02:52:26.619: 　Handling TLV: 242 43 for 0
Apr 29 02:52:26.619: EIGRP-IPv4(1): dest(169.100.10.3/32) active　[19]
Apr 29 02:52:26.619: EIGRP-IPv4(1): rcvreply: 169.100.10.3/32 via 169.10.10.2 metric 
4294967295/4294967295 for tid 0
Apr 29 02:52:26.619: EIGRP-IPv4(1): reply count is 1
Apr 29 02:52:26.619: DUAL: AS(1) Clearing handle 0, count now 0
Apr 29 02:52:26.619: DUAL: AS(1) Freeing reply status table
Apr 29 02:52:26.619: EIGRP-IPv4(1): Find FS for dest 169.100.10.3/32. FD is 4294967295, RD is 4294967295
 on tid 0found
Apr 29 02:52:26.623: DUAL: AS(1) Removing dest 169.100.10.3/32, nexthop 169.10.11.2
Apr 29 02:52:26.623: DUAL: AS(1) Removing dest 169.100.10.3/32, nexthop 169.10.10.2
Apr 29 02:52:26.623: DUAL: AS(1) No routes.  Flushing dest 169.100.10.3/32 route: 169.100.10.3/32
Apr 29 02:52:26.623: EIGRP: Sending ACK on GigabitEthernet3/23 nbr 169.10.10.2 tid 0　[20]
Apr 29 02:52:26.623: 　AS 1, Flags 0x0:(NULL), Seq 0/11 interfaceQ 0/0 iidbQ un/rely 0/0 peerQ 
un/rely 1/0


2.DUAL処理の後は、上記1.と同様にHelloパケットの送受信が続く。
ここで抜線したリンクのInterfaceダウンがログで出力された。DUAL処理の後とは言え抜線後からわずか2秒後なので決して遅くは無い。
しかしLink DownはDUAL処理前に既に検知している。

Apr 29 02:52:27.439: %LINEPROTO-5-UPDOWN: Line protocol on Interface GigabitEthernet3/24, 
changed state to down
Apr 29 02:52:27.935: EIGRP: Sending HELLO on GigabitEthernet3/23
Apr 29 02:52:27.935: 　AS 1, Flags 0x0:(NULL), Seq 0/0 interfaceQ 0/0 iidbQ un/rely 0/0
Apr 29 02:52:28.439: %LINK-3-UPDOWN: Interface GigabitEthernet3/24, changed state to down
Apr 29 02:52:30.063: EIGRP: Received HELLO on GigabitEthernet3/23 nbr 169.10.10.2
Apr 29 02:52:30.063: 　AS 1, Flags 0x0:(NULL), Seq 0/0 interfaceQ 0/0 iidbQ un/rely 0/0 peerQ
 un/rely 0/0
Apr 29 02:52:32.243: EIGRP: Sending HELLO on GigabitEthernet3/23
Apr 29 02:52:32.243: 　AS 1, Flags 0x0:(NULL), Seq 0/0 interfaceQ 0/0 iidbQ un/rely 0/0
Apr 29 02:52:34.603: EIGRP: Received HELLO on GigabitEthernet3/23 nbr 169.10.10.2
Apr 29 02:52:34.603: 　AS 1, Flags 0x0:(NULL), Seq 0/0 interfaceQ 0/0 iidbQ un/rely 0/0 peerQ
 un/rely 0/0
MI-CAT4503-S5-SW-01#
MI-CAT4503-S5-SW-01#undebug all    

All possible debugging has been turned off
MI-CAT4503-S5-SW-01#

・EIGRPメトリック値の再計算におけるDUALの処理方法は、上記のDiffusing Computationの他にLocal Computationもある。
フィージブルサクセサが存在する場合は、その段階で一番小さいDistance値を持つ経路情報がサクセサになる。
フィージブルサクセサが存在しない場合は、直接接続しているLinkのCost値が下げられる場合のみ再計算を実施する。
Local Computationに関するメモは次回にて。


ところでOSPFと何が違う?
ダイナミックルーティングプロトコルとして一括りにされるが、EIGRPはOSPFと似て非なるもの。
EIGRPは、フィージブルサクセサが存在する場合はLocal Computationを実行し、即座に次の代替パスを特定する。フィージブルサクセサが存在しない場合はDiffusing Computationを実行し、ネイバに対しQUERYを投げて経路情報を問い合わせする。EIGRPの代替経路選択は「AS内全体の経路情報を知らなくてもネイバに聞けば何とかなる」というスタンス。
EIGRPは、ある宛先への代替経路は何本有っても良いが、宛先へのHop数が少ないようなネットワークには向いている。


リンク集
https://www.amazon.co.jp/dp/1578701651　EIGRP Network Design Solutions
https://debslink.hatenadiary.jp/entry/20150416/1429195527　EIGRPのLocal Computation
https://debslink.hatenadiary.jp/entry/20150419/1429422783　EIGRPのDiffusing Computation メトリック値変更編
https://debslink.hatenadiary.jp/entry/20150425/1429926903　EIGRPのDiffusing Computation SIA編
https://debslink.hatenadiary.jp/entry/20150503/1430659609　EIGRPのDiffusing Computation 経路追加編
https://debslink.hatenadiary.jp/entry/20150417/1429268810　EIGRPの優先ルートの選定 offset-list編
https://www.cs.utexas.edu/users/EWD/ewd06xx/EWD687a.PDF 1979, W.Dijkstra and C.S.Schalten, Termination detection for diffusing computations
http://www.ece.ucf.edu/~yuksem/teaching/ip/reading/garcia-luna-aceves.pdf 1993, J.J.Garcia-Lunes-Aceves, Loop-Free Routing Using Diffusing Computations