EIGRP中DUAL算法路由查詢優化的研究

楊蕾 王健 高玉宏 張作君 侯振陽

摘? ?要：EIGRP是一個高級距離矢量路由協議，支持中到大型網絡，屬于基于傳聞協議在一組網絡運行EIGRP中路由器之間路由更新機制，是依靠擴散更新DUAL算法進行觸發路由更新。但是，這種算法在某些網絡結構中，會出現發送大量查詢路由報文、浪費網絡設備CUP和內存資源、消耗大量網絡鏈路帶寬等問題。文章提出了兩種方法來減少擴散更新DUAL算法中查詢路由，對今后網絡運行EIGPR動態選擇路由協議，提供了一些參考價值。

關鍵詞：EIGRP;DUAL算法;路由查詢;優化

中圖分類號：TP393.1? ? ? ? ? 文獻標識碼：A

Abstract： EIGRP is an advanced distance vector routing protocol， a gossip-based protocol. It supports medium-scale and large-scale networks. The routing update mechanism between routers of EIGRP in one group of network operation depends on DUAL to trigger the routing update. However， in some network architectures， such algorithm will send lots of query routing messages， waste the CUP and memory of network devices， consume a large amount of network link bandwidths. Therefore， two methods are proposed to reduce the DUAL query routing， to provide reference for the dynamic selection of routing protocols of EIGPR in network operation in the future.

Key words： EIGRP; DUAL; routing query; optimization

1 引言

EIGRP（Enhanced Interior Gateway Routing Protocol，增強內部網關路由選擇協議）是思科的一個私有協議，是一個無類、增強的距離矢量協議，使用了自治系統的概念來描述相鄰路由器的集合，自治系統中的路由器使用相同的路由協議并共享相同的路由信息。2013年這個協議開始公開稱為公有協議[1]。

EIGRP具有距離矢量和鏈路狀態特性，相反，它的發送傳統的距離矢量更新，其中包含網絡信息以及從發送通告的路由器到達這些網絡的開銷[2]。運行EIGRP中會同步相鄰路由器上的路由表，并在每次拓撲更改時發送特定的更新數據，這些數據具有鏈路狀態協議特征。

EIGRP不是使用跳數作為度量值，跳數只是用來限定EIGRP路由更新數據包在被拋棄之前可以經過的路由器個數，這個跳數的數值用于限定AS的大小，最大跳數為255（其默認值為100），與度量值計算無關[3]。

2 EIGRP協議原理

一組網絡運行EIGRP路由選擇協議，首次路由器彼此用Hello包來建立鄰居關系，路由器初次更新會把所有路由都全部發送一遍給其他路由器。為了維持這種鄰居關系，EIGRP路由器依賴于Hello數據包來維護鄰居狀態，并且不發送路由信息[4]。當網絡發生變化（網絡不可達或者更換路徑）時，會影響路由器的路由表中路由條目，只會把發送變化的路由信息進行更新，這也叫做觸發更新（或增量觸發更新）。

EIGRP有四種子協議分別為鄰居發現協議、可靠傳輸協議、擴散更新算法（DUAL算法）、PDM協議依賴模塊。鄰居發現協議為Hello協議，兩個路由器先交互Hello包，再建立鄰居關系，依靠周期性發送Hello包來維護維持鄰居關系。用專用RTP（Reliable Transport Protocol）管理路由器間的信息傳輸，從而實現了數據更新的快速投遞以及對接收數據的跟蹤，為可靠傳輸協議。DUAL算法為EIGRP提供選擇為維護到達每個目的網絡的最佳路徑，可以實現路由備份、動態的路由恢復和查詢路由等功能。PDM協議依賴模塊來實現對不同網絡層協議的支持，每個EIGRP的PDM將會為指定的協議維護多個相互獨立的表，這些表保存著特定協議的路由選擇信息。

3 擴散更新DUAL算法

DUAL算法是EIGRP的核心，包含兩種計算方式：本地計算和擴散計算。可以使EIGRP選擇到達每個目的網絡的最佳路徑，并且保證這些路徑都是無環的。在初始化收斂和網絡發生變化時收斂是這些動態路由選擇協議中最快的。

在一組網絡中，當本地路由器丟失路由時，在拓撲表中找到備份路由，備份路由將替換最優路由，直接進行路由切換，并將備份路由添加到本地路由器路由表中，并且要向所有路由器發送更改更新，通告所有路由器以替換路由，這就是本地計算。

在一組網絡中，本地路由器丟失一條路由時，在拓撲表中沒有備份路由，會通過擴散更新計算來發送查詢，路由器將發送query包給所有鄰居，詢問鄰居是否存在這條丟失路由的路徑信息[5]。鄰居收到查詢后，根據自身路由表的路由條目進行響應，根據鄰居答復，判斷哪條路徑最優從而加入本地路由表，使用新的路徑來訪問目的地，這就是擴散計算。

4 DUAL算法查詢路由的工作原理

擴散更新DUAL算法在某些網絡結構中，存在一些浪費查詢情況。如圖1所示，網絡結構中運行EIGRP協議，R1路由器中一條去往目的×網絡的路由丟失，R1將會聯動所有鄰居路由器進行DUAL算法查詢這條去往目的×網絡的路由信息。