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算法查询这条去往目的×网络的路由信息。