深入理解EIGRP

转载http://blog.sina.com.cn/s/blog_995092640101aw5w.html

深入理解EIGRP

摘要(Abstract):

    EIGRP是Cisco发明的一个私有路由协议,由IGRP发展而来,但是算法做了很大的改动.EIGRP和IGRP,RIP一样是一个采用D-V算法的动态路由协议,在收敛速度,占用网络带宽和系统资源等方面有了很大的改进,且有收敛快,无环路由计算,可以应用于大规模网络的优点.本文深入描述了EIGRP协议机制细节.

缩略语清单(List of abbreviations):

1 EIGRP协议简介

  EIGRP(Enhanced Inteior Gateway Routing Protocol),即增强型内部网关路由协议.它是Cisco发明的一种动态路由协议,由IGRP协议发展而来,号称是增强型的IGRP,但实际上除了Metric计算方式和IGRP类似之外,其他方面已经几乎看不到IGRP的影子.

  EIGRP的算法做了很大的改动,虽然和IGRP,RIP一样是一个采用D-V算法的动态路由协议,但是在收敛速度,占用网络带宽和系统资源等方面有了很大的改进,具有收敛快,无环路由计算,可以应用于较大规模网络的优点.

1.1EIGRP协议特性简介

  1.多进程机制.一台路由器上可以运行多个EIGRP协议的进程.各个进程之间用as号来区分.不同进程之间互不干扰,路由信息可以互相引入.和OSPF的多进程不一样,EIGRP的报文中携带有进程号,所以甚至可以在同一链路上运行EIGRP的多个进程.

  2.使用Hello报文建立并维护邻居关系.EIGRP的邻居机制和大部分路由协议类似,邻居建立后将互相交换路由信息.当网络上某台路由器失效时,其他路由器可以快速察觉并响应变化.

  3.触发更新和部分更新.仅在路由信息发生变化时,邻居路由器之间才进行路由信息的交换,并且只交换发生了变化的路由信息,这样可以占用较小的网络带宽.

  4.适应较大范围的网络.EIGRP的路由度量距离(Metric)是根据网络延时,带宽,可靠性,负载等参数计算出来,是一个32bit的数.这样EIGRP可以较为准确地反映网络链路的情况,Metric的取值范围大也可以使EIGRP适应大范围的网络.EIGRP比RIP有了广阔得多的适应范围,但是一般来说也不应该越过几十台的规模,否则将引起效率问题.

  5.快速收敛,无环路的DUAL计算.对收到的路由信息使用一种称为DUAL的算法进行处理,生成到达各个目标网络的最短路由信息.EIGRP的路由计算仅会波及到必要的路由和必要的路由器,而不会扩散到全网.DUAL算法的机制可以保证生成的路由是没有环路的,它的收敛时间也比较好,优于传统的D-V协议.

  6.路由聚合.使用路由聚合以后,对于聚合范围内的多条路由信息只向外发送一条路由信息,这样可以减少占用的网络带宽,也减少了对处理器和内存资源的使用.EIGRP既支持自动聚合,又支持任意长度掩码的手工聚合.

  7.路由引入.可以引入静态路由和其他路由协议(如RIP,OSPF)发现的路由.还可以引入其他EIGRP进程报告的路由.在引入IGRP和EIGRP的路由时,直接使用IGRP和EIGRP路由的度量距离metric.

  8.路由策略.在接收,引入,发布路由时,EIGRP支持使用路由策略对路由进行过滤.

  9.多种网络协议支持.支持IPv4,IPX,AppleTalk这三种网络层协议.

  10.支持不等价负载分担.EIGRP是目前唯一支持不等价负载分担的协议,即支持不同metric路由之间的负载平衡.

1.2EIGRP协议的运行机制简介

   EIGRP周期性的使用组播在各个接口上发送一种低开销的hello报文.收到Hello报文的路由器会把这个路由器加入到自己的”邻居表”中,于是这两个路由器会开始进行路由信息交换.以后每次收到Hello报文,路由器则认为路由器是”活着的”,而且可以与之交换信息.当连续一段时间没有收到对端路由器的Hello报文,那么就会认为对端路由器已经失效,将之从邻居表中删除,其通告所有路由都随之变成不可达.

  在两台已经建立了邻居关系的路由器第一次交换路由时,它们将交换所有的路由信息:但是在这之后,只有当网络结构或者路由发生了变化时才会向外更新变化了的那一部分路由.EIGRP并不象RIP一样,EIGRP没有定期更新路由的机制.EIGRP将所有的收到的路由信息存放在”拓扑表”中,包括路由的目的地址,掩码,下一跳,度量距离(metric)等信息.EIGRP按照DUAL算法从拓扑表中挑选出最佳的,没有环路的路由,加入到路由表中.

  DUAL算法(Diffusing Update Algorithm),散播更新算法,是EIGRP核心内容,也正是DUAL算法保证了EIGRP的路由计算是没有环路的.DUAL算法使用一个有限状态自动机(FSM)来描述EIGRP的路由计算过程,这个有限状态机被称为”DUAL状态机”,有限状态机的机制保证了DUAL算法可以收敛.在后面的描述中提到DUAL这个缩写时,根据上下文,可能表示DUAL状态机,也可能表示DUAL算法.

  DUAL算法是一种D-V算法.D-V算法,即距离-矢量算法,它的基本思想是:要找一台路由器到目标网络的距离,那么把它到邻居的距离和邻居到目标网络的距离相加,得到经由某个邻居到目标网络的距离,然后对所有的邻居进行计算并从中取最小值,就得到了路由器到目标网络的最短距离.所有采用D-V算法的路由协议都必须考虑如何避免环路的生成.

  所谓”距离”,各个动态路由协议的定义是不一致的,例如RIP的定义是到目标网络所经过的路由器的数目–“跳数”.EIGRP针对每条网络路径,根据传输延时,链路带宽,有效带宽等参数计算出一个的综合度量距离(metric),用它来衡量各条路由的优劣.在后文中,提到”距离”这个词,往往指的是综合度量距离metric.

  就路由器A而言,对一个目标网络,”可靠后继”(Feasible Successor,简称FS)是指这样的邻居路由器B:通过B到达目标网络有一条路径,并且B到目标网络的距离小于A到目标网络的距离.

而”后继”指的是某条路由当前正在使用的下一跳

  例如在如下的网络拓扑结构中:

  假定:

       B-N的距离是10,C-N的距离是100.

       A到N的最短路径是A-B-N,最短距离是30.

  那么对于目标N:
       路由器A的可靠后继有B,但C却不是它的可靠后继,

       路由器B的可靠后继有N,但A却不是它的可靠后继.

  如果B是A的可靠后继,那么我们可以确信:路由器A通过路由器B到达目标网络不会有环路.也就是说,可靠后继是没有环路的充分条件.

  当网络发生变化时,DUAL会首先检测对目标网络是否还存在可靠后继:
  1.如果存在可靠后继,那么使用可靠后继中最优的一个作为到达目标网络的下一跳,没有必要重新计算路由.

  2.没有可靠后继,拓扑中也没有关于此目的地址的路由项,这说明目标网络已经不可达.

  3.没有可靠后继,但是拓扑表中还存在到达此目的地址的路由项,即还有相邻路由器宣称它可以通往此目的地.这种情况下,相邻路由器所报告的这条路由不能满足可靠后继条件,我们无法对这条路由作出没有环路的保证.此时不可以采用这个相邻路由器作为通往目的地址的下一跳,(因为不能确保没有环路),而必须启动DUAL进行路由重算,这也是一个重新确定可靠后继的过程.当计算结束时,或者可以找到新的可靠后继,找到新的可以确保无环路的路由;或者可以确信目标网络已经不可达.

  DUAL算法被称为一种散播算法,是因为它采用一种”分布的”,”扩散的”计算方式.具体说来,当一台路由器对某条路由找不到可靠后继,开始进行路由重算时,它会向所有邻居路由器提出”查询”(Query),这时我们称这条路由进入了active状态;等到所有的邻居路由器都对查询做出”应答”(Reply)后,这台路由器才会根据这些应答计算出新的可靠后继和新的最佳路由,这时我们称这条路由回到了passive状态,这个过程称之为“收敛“.

  当邻居路由器收到查询时,它也会检查自己的可靠后继条件:若条件满足,可靠后继存在,那么它将马上对查询做出应答;若条件不满足,找不到可靠后继,那么它只好先将查询搁置起来.然后它也会启动路由重算的过程,会向它所有的邻居发出查询,直到它的所有邻居应答后,它才会收敛并计算出新的可靠后继,这时它才会对先前搁置的查询做出应答.

  可以看出,DUAL是一个不断向外扩散的计算过程,看起来似乎会越来越多的路由器卷入到计算过程中.但是实际上,DUAL的机制可以保证计算不会被扩散到太远,计算一般只会波及到必须的路由器;DUAL也可以保证这些发出查询的路由器不会相互无休止地等待应答,它们都会在比较快的时间内收敛.计算的传播过程也伴随着路由信息的传播,这使EIGRP可以很快的感受到网络的变化并做出响应.

  伴随着DUAL计算,有许多报文在相邻路由器之间传送,这些报文携带着EIGRP的路由信息.EIGRP使用Raw IP在相邻路由器之间传送报文,因为Raw IP是一种不可靠的传输,所以EIGRP必须建立自身的可靠传输体系.EIGRP使用的序号确认,超时重传等机制确保报文的可靠送达.

  注:TCP/UDP类型的套接字只能够访问传输层以上的数据,因为当IP层把数据传递给传输层时,下层的数据包头已经被丢掉了.而原始套接字却可以访问传输层以下的数据,所以Raw套接字可以实现上至应用层的数据操作,也可以实现下至链路层的数据操作.

  只需要简单了解的读者看看这些就够了,如果想深入了解EIGRP,请继续向下看.

2 EIGRP的多进程

  EIGRP是支持多进程的,在同一台路由器上,可以运行多个EIGRP的进程,各个进程之间使用进程号(as-number)相区分.

  EIGRP每个进程之间是完全独立的,就像有几个协议一样:它们具有独立的使能网段,独立的协议配置,独立的接口配置,独立的邻居表,独立的拓扑表,独立的报文传送.进程的运行不会互相干扰,一个进程的运行状态和其他进程无关.EIGRP甚至可以在同一接口,同一链路上运行多个进程.EIGRP的各个进程之间可以相互引入路由.

  EIGRP报文头中包含有as number,EIGRP进程将会丢弃接收到的其他进程(as number)的报文.EIGRP只在具有同一as number的路由器之间建立邻居关系.

3 报文格式

3.1报文格式描述

  EIGRP使用Raw IP来封装报文,IP头中协议字段为88.

  EIGRP的报文共分为Hello,Query,Reply,Update,Request五种,但是其中Request报文目前并没有使用.EIGRP没有单独的确认(ACK)报文,确认消息包含在其他报文中.每种报文又是由一个报文头加上一个或多个TLV组成.

  TLV指Type-Length-Value,指的是由类型,长度,值三部分组成的信息单位.EIGRP目前有8种TLV:Parameter TLV,Authentication TLV,Sequence TLV,Software Version TLV,Next Multicast seq TLV,IP Request TLV,IP Metric TLV,IP Exterior TLV.其中IP Request TLV只用于Request报文,目前并没有使用.(其实还有一些IPX和AppleTalk网络使用的TLV,这两种网络不常用,所以也不再叙述.)

3.2EIGRP报文头

  所有EIGRP的报文都有如下一个头部:

  字段说明:

  Version:协议版本(目前为2)

  Opcod:报文类型

  其中Update(1)报文用来更新路由,Request(2)报文目前不再使用,Query(3)报文和Reqly(4)报文用于查询和应答,Hell0(5)报文用来维护邻居关系.

  报文的具体内容在后续的TLV的描述中会讲到.Update(1),Query(3),Reply(4)三种报文的具体用法会在”DUAL算法和DUAL状态机”详细描述.

  Checksum:校验和

  Flags:标志(0x01表示INIT,0x02表示CR).INIT标志表示发送给新邻居的第一个初始化Update报文,这个报文将携带所有的路由信息,而以后的普通的Update报文将只携带变化了的路由信息,关于CR(Conditional Receive)标志,将在”Sequence TLV”部分中讲述.

　Sequence Number：报文的序列号，用于确认机制，不需要确认的报文，如Hello报文，这个域为0.

　Ack　Number：报文携带的确认信息.表示已经收到了此序列号的报文.

　Autonomous-System Number：自治系统号，一般来说就是进程号.

3.3 EIGRP的TLV基本结构

  根据报文的不同类型,在报文头后面有一个或者多个TLV(Type-Length_value组).每个TLV的基本结构如下图所示.

  字段说明:

  TLV Type:表示TLV的类型.其中的高字节为0表示与网络层协议无关的TLV类型;为1表示IP网络的TLV类型;2表示AppleTalk网络;3表示IPX网络.

  TLV length:这个TLV的长度,由此来界定各个TLV.这个长度是指整个TLV的长度,包括TLV Length和TLV Length部分.

  TLV Value:TLV的内容,具体依据不同的TLV不同.

3.4 Parameter TLV 
  Parameter TLV被携带在Hello报文中,用来指定建立邻居所需要的一些参数.它的TLV Type为0x0001,长度为12字节.格式如下:

  字段说明:

  K1-K5:计算度量距离的系数K值.

  Hold-Time:这个Hello报文的有效时间,若超出这段时间还没有收到新的Hello报文,则认为此路由器已经失效,邻居关系终止.

3.5 Authentication TLV
  Authentication TLV用来携带认证信息,它的TLV Type为0x0002,它可能出现在任何报文中.按照Cisco的想法,对一份报文采用多种认证方式,但是目前只采用了MD5认证.

  字段说明:
  Auth Type:认证类型,目前只有MD5一种类型—0x02.

  Auth Length:认证的长度,对MD5来说,认证长度为0x10.

  Auth Data:认证信息.对于MD5来说,又包括Auth KeyID(4字节),Auth Pad(12字节),Auth Digest(16字节)三部分.Auth KeyID默认为0x00000001,可以在接口上配置;而Auth Pad没有意义,永远为0;Auth Digest包含MD5认证的信息.

3.6 Sequense TLV

  Sequense TLV可能出现在Hello报文中,它的TLV Type为0x0003,它的作用让某些邻居路由器进入到CR(Conditional Receive)状态.

  字段说明:
  Address Length:地址的长度,对于IPv4地址族,取4

  Protocol Independent Address:网络层地址,对于IPv4地址,它长4字节.

  每一组Address Length和Protocols Independent Address,表示了一个邻居路由器的IP地址,Sequense TLV可以携带多个IP地址的列表.凡是接收到这个TLV的邻居路由器将检查自己是否在这个列表中,如果不在这个列表中,则把自己置为CR状态.只有处于CR状态的路由器,才能接收带有CR标志的报文.(EIGRP报文头部分中关于Flags字段的说明).

  让我们通过一个例子来了解CR状态的作用,某路由器R在一个接口上有A,B,C三个邻居.它向这个接口发送了一个Update报文,然后收到了A,C的确认,但是因为某种原因没有收到B的确认,这样无法知道B是否收到了这份Update报文.此时,路由器R既不想继续等B的确认;也不希望B在没有收到第一份Update报文的情况下接收第二份Update报文,因为这种失序有可能引起混乱.于是,路由器R发了一个带有Sequense TLV的Hello报文,里面列出了B的IP地址,这样A,C就会将自己置于CR状态,B则会保持正常态.R发出的后续Update报文将在报文头中打上CR标志,这样只有A,C才会接收到这些报文,而B因为不是CR状态,将会忽略带有CR标志的报文,这样就保证了B不会接收到失序的报文.路由器R将在稍后向B依次发送B所错过的报文.

3.7 Software Version TLV

  出现在Hello报文中,它的TLV Type为0x0004,用来指定EIGRP协议软件的版本.

  字段说明

  Sys Major和Sys Minor:系统的主版本号和从版本号.目前分别取1和0.

  EIGRP Major和EIGRP Minor:EIGRP的主版本号和从版本号.目前分别取1和0.

3.8 Next Multicast seq TLV

  Next Multicast Seq TLV可以出现在Hello报文中,它的TLV Type为0x0005.它需要和与Sequense TLV配合使用,单独的Next Multicast Seq TLV没有意义.

  在有Sequense TLV,但没有Next Multicast Seq TLV时,表示处于CR状态的邻居路由器可以接收以后所有带CR标志的报文.
  在有Sequense TLV和Next Multicast Seq TLV都有时,则Next Multicast Seq TLV指定了一个序列号,处于CR状态的邻居路由器只可以接收带CR标志,并且序列号为这个指定序列号的报文.

  字段说明:

  Seq Number:下一个可以接收的多播报文的序列号.

3.9 IP Request　TLV

  Request TLV是专用于Request报文,它的TLV Type为0x0101,表示向对端路由器请求关于某几个IP网络地址路由信息.但是现在的EIGRP协议版本没有使用Request报文.

  字段说明:
  使用Mask Bit Count和IP Address表示一个网络地址,这是一种”紧缩”的表示方式.如果表示10.0.0.0/255.0.0.0,那么Mask Bit Count取8,IP Address长一个字节,置10;如果表示192.2.0.0/255.255.0.0,那么Mask Bit Count取16,IP Address 长两个字节,分别置192和2.

3.10 Metric TLV

  IP Metric TLV可以出现在Query,Reply,Update报文中,它的TLV Type为0x0102,用来表示到某个目的地址的EIGRP内部路由及其度量距离.(EIGRP内部路由是指由EIGRP发现,非引入的路由)

  字段说明:
  Next Hop Forwarding Address:路由的下一跳的IP地址.

  灰色标记的部分表示计算一个综合度量距离Metric的各个要素.

  Delay,Bandwidth,MTU,Hop Count,Reliability,Load:依次是总延时,最小带宽,MTU值,跳数,可信度,负载.

  Mask Bit Count和IP Address:目标网络的IP地址.用”紧缩”的方式(见IP Request TLV中的说明).一个IP Metric TLV中可以有多个目标网络,表示多条路由信息,它们的下一跳和Metric相同.

3.11  IP Exterior TLV

　　IP Exterior TLV可以出现在Query,Reply,Update报文中，它的TLV Type为0x0103，用来表示到某个目的地址的EIGRP外部路由及其度量距离.（EIGRP外部路由是指由EIGRP引入的路由）

  字段说明:

  Next Hop Forwarding Address:路由的下一跳的IP地址.

  上方浅灰色的部分表示EIGRP外部路由信息.

    Router ID:引入这条路由的路由器的IP地址

    AS Number:引入这条路由的路由器所在的自治系统.

    Administrator Tag:可以用来携带一组路由映射的标记.

    External Protocol Metric:所引入路由在原协议中的Metric值

    External Protocol:所引入路由的原协议号.(IGRP为1;EIGRP为2;静态路由为3;RIP为4,OSPF为6;BGP为9;直连网段为11)

    Flags Field:标志位(0x01表示EXTERNAL;0x02为CD).EXTERNAL标志表示外部路由;CD标志表示Candidate Default路由.

  下方深灰色标记的部分表示计算一个综合度量距离Metric的各个要素.

    Delay,Bandwidth,MTU,Hop Count,Reliability,Load;依次是总延时,最小带宽,MTU值,跳数,可信度,负载.

  Mask Bit Count和IP Address:紧缩格式的目标网络IP地址,可以有多个,表示多条路由信息.

4 邻居的发现和维护

  首选需要指出的是,EIGRP只会在使能的接口上工作.即启动EIGRP之后,需要使用Network命令打开相应的接口,这个接口所连网段的路由才会被EIGRP发布,同时EIGRP也会向这个接口发送报文并接收来自这个接口的报文.当一个接口被指定为passive-interface.那么,这个接口上将既不发送也不接收EIGRP报文(包括Hello报文),但是这个接口所连网段的路由仍然会被其他接口发布.

  邻居是通过定期发送的Hello报文实现的,相邻路由器之间通过Hello报文建立邻居关系,在一段时间内没有收到报文将清除邻居关系,路由信息报文的连续发送失败和一些配置命令也会导致邻居关系的清除.

4.1 发送Hello报文

  EIGRP定期将向开启的各个接口发送Hello报文,默认每隔5秒钟发送一次,发送间隔可以根据需要在接口模式下配置.发送采用一个定时器控制.发送使用组播地址224.0.0.10,所有运行EIGRP的路由器将加入这个多播组.

  Hello报文不携带路由信息,只有as number,系数K值,保持有效时间(Hold-Time)等一些参数,这样报文比较短小,占用很少的带宽资源.Hello报文是不需要确认的,也就是说Hello报文采用不可靠传输.

4.2 邻居的发现

  当一台路由器接收到来自其他路由器的Hello报文时,而且这台路由器还不在它的邻居表中,那么EIGRP将检查Hello报文中携带的as number,系数K值是否与自己的一致,如果一致,将和这台路由器建立邻居关系,将其添加到自己的邻居表中.接收到Hello报文也将刷新一个Hold Time定时器,这个定时器控制邻居是否超时.

  具体来说,邻居建立的条件有如下:
　1.自治系统号相同

  2.系数常量相同(K1,K2,K3,K4,K5)

  3.在同一个网段上(地址借用除外)

4.3 邻居建立的握手过程
  在收到对端路由器发送过来的Hello报文后,并满足邻居建立条件,EIGRP就会与其建立邻居关系.但是,必须经过三次握手后,才可以正常的发送和接收路由信息.

  如下图所示:

  三次握手示意图(1)的说明:

  1.A发送一个带INIT标记的UPDATE报文给B.

  2.B收到邻居A发送过来的带INIT标志的UPDATE报文后会接着发一个带INIT标记的UPDATE报文给A,同时这个UPDATE报文中带有ACK号,应答邻居A的INIT标记报文.

  3.A收到B的带有INIT标志的UPDATE报文(有ACK号)以后,会发送一个ACK报文给B.

  这时,邻居关系才算真正建立起来,可以正常交换剩下的路由信息.

  同时,还可以通过如下方式来完成三次握手(如下图):

  三次握手示意图(2)的说明:

  1.A与B同时(或者在没有收到对方带INIT标志的报文前)向对方发送带INIT标志的UPDATE报文.

  2.A和B在收到对方发送过来的带INIT标志的UPDATE报文后,分别向对方发送一个ACK报文,对收到的报文进行确认.

  在三次握手过程中,可能会出现一端没有准备好的情况(例如还没有从这个路由器收到Hello报文),如下图所示:

  在一方没有准备好的情况下的三次握手的具体说明:

  1.A收到B的Hello报文,与B建立邻居关系,立即发送一个INIT标志设置为1的UPDATE报文,想与B交换拓扑表.

  2.但是,B没有收到A的Hello报文,故无法与A建立邻居关系,所以收到的带有INIT标志的UPDATE报文是来自于未知邻居,丢弃这个UPDATE报文,不作处理.

  3.A重发这个UPDATE报文(注意是超时重发),但是,B在没有收到A的Hello报文与A建立邻居关系之前,就不会处理这个UPDATE报文.

  4.B收到A的Hello报文,与A建立邻居关系,立即发送一个INIT标志设置为1的UPDATE报文,想与A交换拓扑表.

  5.B是A的有效邻居,所以A收到B的带INIT标志的UPDATE报文后,应答和处理这个报文,并且重发自己的初始化UPDATE报文.(超时重发)

  6.B再收到A的带INIT的UPDATE报文后,由于与A正常建立了邻居关系,能够正常应答和处理该UPDATE报文.

  7.A与B正常交换剩余的路由信息.

  实际上,Cisco的设备在在邻居建立的三次握手过程中,并不是严格按照以上步骤来进行的,如下图所示:

  此过程的说明如下:
  1.A发送一个带INIT标记的UPDATE报文给B.

  2.B收到邻居A发送来的带INIT标志的UPDATE报文后,直接发送一个ACK报文给A,对收到的报文进行确认.

  3.A三次握手成功,可以正常接收B发送过来的路由信息.

  (实际中一般不会出现这种情况,但是可以通过测试程序模拟)

4.4 邻居的删除
  有下面这几种情况会导致邻居的删除:

  1.Hold Time定时器超时,说明在这段时间一直没有接到这个邻居的报文;

  2.路由信息报文连续重发16次,一直没有接到对方的确认报文.

  3.邻居对我方发出的查询在SIA时限内没有应答;

  4.一些配置命令会导致邻居的清除和重新建立,具体说来如下.

    以下命令将清除相应接口上的所有邻居:

    passive-interface

    ip authentication key-id eigrp (Csico上无次命令.ip authentication key-chain eigrp)

    ip authentication key-string eigrp (Csico上无次命令)

    ip authentication mode eigrp

    offset-list(配置接口参数)  (Csico上无次命令)

    ip split-horizon eigrp

    ip summary eigrp

    以下命令将清除本进程下的所有邻居:

    metric weights

    network

    distribute-list

    offset-list(全局)

    auto-summary

  5.接口失效时将删除接口上所有的邻居.

  6.用户还可以通过命令clear ip eigrp neighbor来手工删除一个邻居.

5 EIGRP报文的MD5认证

  EIGRP可以配置MD5认证来保证报文的合法性和完整性.如果配置了MD5认证,EIGRP在发送报文时将使用MD5算法对报文生成摘要;在收到报文后,EIGRP将校验MD5摘要,EIGRP将丢弃认证失败的报文.

  MD5认证是保证报文完整性,合法性的一种重要手段.一般说来,MD5认证按照如下方式进行.

  1.双方协商好一个密码.

  2.报文发送端将密码填入到报文的某一个字段中,然后按照MD5算法对包含密码的整个报文进行运算,得到MD5摘要,将生成的摘要填回到同一字段,覆盖密码.

  3.报文接收端收到报文后,先将摘要字段保存起来,然后也将密码填入到报文的这个字段中,再按照MD5算法计算,得到摘要.比较这个摘要与先前保存的摘要,如果一样,就说明报文是合法的.

  EIGRP的MD5认证的密码和摘要是放在Authentication TLV的Auth Digest字段中.和一般报文的MD5认证相比,EIGRP有一点不同:EIGRP进行MD5计算时,只计算一部分的报文内容,报文的最后的20字节(相当于报文头的长度)不参加计算.如图

  进行MD5认证时,EIGRP将16字节密码填入到Auth Digest字段中,然后对灰色部分(不包含最后20字节)进行MD5计算,得出16字节的摘要,再将这16字节的摘要填回到Auth Digest字段中.得到经过认证的报文.(以上MD5验证过程适用于密码长度小于等于15的情况,密码长度大于等于16的验证过程还不详.)

  Cisco在接口上配置认证时给出的是Key-chain的名称,然后在Key-chain模式下配置Key-id和Key-string.一个Key-chain下面可以配置多组Key-id和Key-string,对于每组Key-id和Key-string,还可以设置各自的有效时段.Cisco在发送认证报文时,使用在有效时段内并且Key-id最小的Key-String作为密码字符串;Cisco在接收认证报文时,将使用报文中Auth KeyID字段中指定的值作为Key-id,查找相对应的Key-string作为密码字符串.

6 拓扑表的维护

  拓扑表是EIGRP存放路由信息的重要数据结构,DUAL算法,组织报文都是以拓扑表做为依据的.EIGRP从路由报文,路由聚合,路由引入等不同来源中提取路由信息,并根据这些路由信息进行对拓扑表进行维护.拓扑表的变化将触发DUAL有限状态机,以得到新的可靠后继.

6.1 拓扑表的结构

  拓扑表中包含了如下信息:

  1.目标网络地址

  2.下一跳(邻居路由器)的地址,所在接口

  3.到目标网络的最优度量距离(Feasible Distance)

  4.邻居路由器报告的它到目标网络的度量距离(Report Distance)

  5.EIGRP外部路由信息(包括外部路由的来源等)

  对于一个目标网络,拓扑表中可能会有多个下一跳的纪录,即多条路由纪录.

  度量距离的计算,Feasible Distance和Report Distance的含义将在”FD,RD以及可靠后继条件”中介绍.

6.2 EIGRP的Metric计算

  任何动态路由协议都有自己的尺度来衡量路由的优劣,这就是多次提到的度量距离Metric.在EIGRP中的度量距离Metric是按照如下公式计算得到的:

  注:Metric的计算结果只保留整数部分,小数部分舍去;

  其中:

  K1-K5:系数K值,分别表示带宽系数,有效带宽系数,延时系数,可信度系数.默认情况下,K1=K3=1,K2=K4=K5=0.

  bandwidth:带宽衡量值,由路径上的最小带宽(Min BandWidth)计算得到.

     bandwidth:(/最小带宽)*256……最小带宽单位为kbps

  delay:延时衡量值,由路径上的总延时(Sum of Delay)计算得到.

     delay=总延时*256…………………..总延时单位为10微秒

  load:链路负载,0-255.255表示最大负载.

  reliability:可信度,值越大路由越可信.

  可以看出在默认情况下:

Metric越小说明”距离”越小,路径越优.

下面是一个简单的例子,用来说明Metric的计算:

  假设:

    A-B网络的带宽为56(kbps),延时为2000(10微秒)

    B-N网络的带宽为10000(kpbs),延时为100(10微秒)

  那么:

    A-B的Metric为(/56+2000)*256=

    B-N的Metric为(/10000+100)*256=

    A-B-N的Metric为(/56+(2000+100))*256=

  注意,A-B-N的Metric并不等于A-B和B-N两段路径的Metric相加.即在这个算法中”整体”并不等于”部分”的算术相加,但是可以保证”整体”大于任一个”部分”.”整体”大于任一个”部分”是D-V算法的基本数学前提.

  对接口上的直连网络,它们的可信度和负载默认是255和1,它们的延时和带宽根据接口类型的不同分别有一个默认值.

  接口上的带宽和延时可以通过接口模式下的配置命令bandwidth和delay进行修改.

6.3 FD(Feasible Distance),RD(Report Distance)以及可靠后继条件(Feasible Condition)

  拓扑表中每条路由纪录的都有可靠距离(Feasible Distance)和上报距离(Report Distance)两项,简称FD和RD,分别表示到目标网络的是优距离和邻居路由器报告的距离.

  继续上小节中的例子:
  很显然,A到目标网络N,只有A-B-N这样一条路由.那么,A到目标网络的最短距离,即FD,为A-B-N的Metric—;而B向A报告的距离,即RD,为B-N的Metric—.

  让我们使用FD和RD再简单描述一下可靠后继条件(Feasible Cndition–FC):对给定目标网络,路由器A的可靠后继是这样的邻居路由器,它向A报告的RD小于A的FD.(对于可靠后继条件的详细描述可以参见”可靠后继条件”)

  满足FC条件的邻居路由器就是可靠后继(Feasible Succssor).比如说,如果这时有一个路由器C和A也建立了邻居关系,并且C向A通告:C到达目标网络N的距离为.从A的角度,C报告的RD为,小于自己的FD ,所以C是到目标网络的可靠后继.这也说明:通过C到达目标网络的路径也许不是最佳的,但是一定没有环路.如果A-B之间的网络发生故障,那么A可以马上采用C作为到达目标网络的下一跳.

  如果C向A报告到目标网络的距离为,大于A的FD ,那么C无法满足可靠后继条件,也就无法保证A经过C到达目标网络会没有环路.那么,如果A-B发生故障,尽管此时拓扑表中关于还有C到N的路由项,A也不能采纳,而是向各个邻居路由器发出查询,启动路由重算的过程.当这个过程结束后,也许会使用C作为下一跳通向目标网络(A将相应的更新FD);也许会发现目标网络已经不可达(这时A的FD为无穷大).

6.4 拓扑表的变化将触发状态机

  收到路由信息报文(Update,Query,Reply),接口上的直连网段发生变化,引入其他路由协议的路由,执行路由聚合,这些事件都会产生路由变化信息.路由变化信息将包括:目标网络地址,下一跳,新的Metric(FD和RD),新的外部路由信息.

  EIGRP会根据这些路由变化信息更新拓扑表,保持拓扑表和实际情况的同步.更新拓扑表完成后将触发DUAL算法,以根据拓扑表的变化计算出新的最佳路由.下面的章节将继续讲述DUAL算法是如何计算得到最佳路由的.

7 DUAL算法和DUA状态机

7.1 D-V算法和Metric计算

  总体上来说,EIGRP采用的DUAL算法仍然是一种D-V算法.也就是说,对于某个目标网络,路由器是根据邻居上报的结果,再”加上”本路由器到各个邻居的”距离”,从中比较出最小值,得到本路由器到目标网络的最短距离和最优路径.这里”加上”和”距离”被加上引号是因为在EIGRP中,它们有特殊的涵义.

  在EIGRP中,”距离”指的是综合度量距离Metric,”加上”也并不代表算术相加.因为从”EIGRP的Metric计算”中我们可以知道A-B-N的Metrice并不等于A-B的Metric简单加上B-N Metric,而是根据Metric的各个分量重新计算的结果.这也是为什么报文中使用IP Metric TLV和IP Exterior TLV传递路由信息时必须传递延时,最小带宽,负载等各个Metric分量,而不只是传递一个计算后的Metric值.

  事实上,DUAL算法对如何计算Metric,如何衡量路由优劣没有做出规定.DUAL算法也并不关心Metric是如何计算的,它只要求计算方式可以保证整体大于部分就可,即A-B-N的Metric一定会大于B-N的Metric.所以在后文对DUAL算法的描述中,为了简洁起见,我们常采用简单相加的方式来计算度量距离Metric,这对叙述DUAL算法完全没有影响.但是在具体描述EIGRP协议时,我们必须明确,Metric值不可以算术相加.

7.2 触发更新,部分更新机制.

  EIGRP的路由更新是通过Update报文实现的.Update报文有单播和多播两种方式.

  1.在两台路由器首次建立邻居关系时,它们会向对方发出带有”INIT”标志的Update报文进行初始化(参见”EIGRP报文头”).初始化的Update报文中包含所有的路由信息,即整个数据库.这个Update报文采用单播的方式传送.

  2.以后,每当路由器的路由发生变化时,路由器将以多播的方式向所有的邻居路由器发送Update报文,报文中只包含更新的路由信息,即变化了的数据库.

7.3 可靠后继条件(FC)
  前面已经描述了EIGRP使用的可靠后继条件:邻居报告的RD小于自己的FD.用反证法不难证明,这个条件是没有路由环路的充分条件.

  可靠后继条件是DUAL的重要内容之一,但是事实上,DUAL算法提出的可靠后继条件并不是唯一的.在参考资料”Loop-Free Routing Using Diffusing COmputaion”这篇论文中,作者J.JGarcia-Lunes_Aceves一共描述了三个可靠后继条件:

  1.DIC(Distance Increase Condition)

    这个条件称为距离增加条件.也就是说如果在任何时候,如果路由器A发现链路的COST减少,或者邻居上报到目标的距离减少,这时A可以随意在当前所有邻居中选择具有最优路由的邻居作为下一跳,这时可以保证没有环路发生.否则则不能保证.

    DIC还有一个不那么严格的版本.也就是说,如果A发现到链路或邻居的Metric增加,只要A还能找到一个邻居路由,经过个邻居路由器到达目标网络的距离最小,并且小于等于原来的最优距离(A到目标网络在这段时间的最小值),那么A仍然可以将这个邻居作为自己的下一跳路由器,这时可以保证没有环路的发生.如果找不到这样的邻居路由器,那么A就无法保证无环路条件.

    这个条件的充分性是很显然的,如果发生路由变化后,本路由器到目标网络的最优距离和原来相比没有增大,而一定不会有环路的发生.

    DIC条件可简单概括为:新的最优距离小行等于原来的最优距离.(FD<=old_FD)

  2.CSC(Current Successor Condition)

    这个条件称为当前后继条件.具体来说,假设路由器A原来的后继是路由器B,如果当路由发生变化时,假设这段时间内B到目标网络的最小值是S.如果路由器A可以找到这样一台路由器X,首先A经过X到目标网络是最近的,并且X到目标网络的距离小于等于S(原来的后继B到目标网络距离的最小值).那么A就可以将X作为自己的新的后继,这个时候是可以保证没有环路的.如果找不到这样的路由器X,那么就不能保证找到无环路的路由.

    这个条件显然也是充分的.新的后继X到目标网络比原来的后继B更近,说明X到目标网络是不可能绕回路由器A形成环路的,A到X是直连,所以综合起来也不会形成环路.

    CSC条件可以简单概括为:新的后继到目标网络的距离小于等于原来后继到目标网络的距离.(RD<=old_RD)

  3.SNC(Source Node Condition)

    SNC就是我们所叙述的条件,也是目前Cisco EIGRP所采用的.

    这个条件称为源节点条件.也就是说,如果路由器A到目标网络可以找到这样一台路由器X,首先A经过X到目标网络是最近的,并且X到目标网络的距离小于原来的最优距离(A到目标网络在这段时间的最小值).

    这个条件也是充分的,因为新的后继X到目标网络的距离小于A到目标网络的距离,那么X就不可能是绕回A到目标网络的,所以A经过X到目标网络不会形成环路.

    注意到这个条件是三个条件中唯一判断”小于”的条件,DIC和CSC都是判断”小于等于”.这是因为SNC在等于的情况下不能确保无环路的发生.

    这个条件比前2个条件相比更加宽松一些,因为它毕竟是RD和FD的比较,并不加上原来A到邻居的距离.也正是因为这样的原因,这个条件更加具有实用性,被Cisco用来作为EIGRP协议DUAL算法的基本判断条件.实际上,前2个条件在前人的论文中都进行过阐述,J.J.Garcia-Lunes_Aceves的这篇论文着重阐述并证明了SNC.

    SNC条件可以简单的概括为:新的后继到目标网络的距离小于原来的最优距离.(RD

  在Cisco的很多资料中,一般都只强调了RD

描述三个条件时都强调了邻居路由器必须先满足到目标网络最优这个条件
.论文中的条件是更加严谨的,因为路由优选是所有路由协议遵守的基本原则.

  简单说,在判断路由器是否可以收敛时,只有同时满足2个条件才能认为满足可靠后继条件:1)有邻居路由器RD