弥散更新算法(DUAL)

DUAL认为,即使短暂的路由环路对路由选择也是有害的.DUAL最早是由E. W. Dijkstra 和 C. S. Scholten提出.

DUAL的预备知识:

为了是DUAL能正常工作,需要满足以下条件:  

1.节点可以在有限时间内检测到邻居的变动    
2.一个正在运行的链路上,所有信息都是在有限时间内正确按序接收到    
3.所有的信息(链路cost的变化,链路失效和发现新邻居的通告)都应该一次一个的处理,并且被有顺序的检测到.    
Cisco以RTP及邻居维护机制来解决上述前提

DUAL的几个概念

  • 邻接:两个可以正常交换路由信息的路由器在逻辑上的关联关系.这里的路由更新消息包括路由器知道的所有路由条目及cost.

  • Feasible Distance:到达每一个目的网络的最小度量值.

  • Feasible Condition:对于某条路由条目.邻居通告的AD是否小于本地FD.

  • Feasible successor:邻居满足了FC,则会成为本地的FS.

  • successor:实际路由表中的下一跳

FS和FC是DUAL保证无环的重点.因为邻居通告的AD比本地FD小,所以路由器不会再次选择一个经过自己的路径.

举个例子    

这里我们修改了mteric的K值,使用了 metric 0 0 0 1 0 0 即只使用delay作为度量计算.之前也提到过,由于ospf也使用带宽作为度量值,所以,bandwidth这个参数最好不要随便调整.

拓扑表中包括,路由条目和可行后继.(768/256)这样的字段表示FD/AD

FS如果通告了一条cost更小的路由条目,那么这台FS就会成为successor.下面三种情况会引起这一变化:

  • 发现一条新的路由

  • 后继路由器的度量值增加超过了FS

  • FS度量值减少到小于当前后继

当一条路由失效时,会首先查找是否存在FS,如果存在FS则切换到FS而不是再次进行路由计算.所以EIGRP拓扑设计的关键在于,确保所有目的网段都有FS.

DUAL有限状态机

DUAL不执行扩散计算时,路由条目处于passive状态

触发路由器重新评估路由条目的input:

  • 直连链路cost的变化

  • 直连链路的翻动

  • 收到一个update数据包

  • 收到一个query数据包

  • 收到一个reply数据包

重新评估的第一步就是对路由条目进行一个本地的计算,也就是对所有的可行后继重新计算可行距离.可能出现的情况:

  • FS的cost比当前后继低,则FS转为后继

  • 新的cost比当前cost低,则更新successor的cost

  • cost出现变化的话,发update更新.

在进行local computing的时候,路由状态依旧是passive.

如果发现有FS,则发送更新出去,没有状态产生变化.如果没有发现FS,那么悲剧了,要启动Diffusing computation.此时拓扑表中的相关的条目状态变为active.在弥散计算完成之前,路由器不能:

  • 改变路由的后继路由器

  • 改变正在通告的cost

  • 改变路由的FD

  • 开始进行该路由的另一个扩散计算

路由器开始发送query消息给所有邻居,query消息包含了自己本地计算的到目的网段的cost. 收到query的邻居,开始在自己身上执行local computation.执行完了有两个结果:

  • 如果邻居有可行后继, 那么回送reply消息给query始发路由器,消息中包含自己到目的网段的最小cost

  • 如果邻居没有可行后继,则把自己active,并且开始执行diffusing computation.    

每一个被发送query消息的邻居,都会被标记.直到所有被标记的邻居都回复了reply消息后该路由器的diffusing computation才算结束.在低速链路或者链路质量较差的大型网络中,可能会出现某个节点无法收到reply的情况,导致全网拓扑无法再次收敛.这种情况叫做SIA(stuck-in-active).实际设计中有个active timer,按照原剧本,计时器超时后还没有收到reply的话,就断开邻居关系.

active timer缺省配置3min,可以通过timer active-timer进行调整

DUAL有限状态机    

关于debug消息      

debug eigrp packets      
*Mar 1 10:58:02.491: EIGRP: Sending UPDATE on Serial1/0 nbr 12.1.1.2      
*Mar 1 10:58:02.491: AS 90, Flags 0x0, Seq 2/1 idbQ 0/0 iidbQ un/rely 0/0 peerQ un/rely 0/1 serno 4-4      
flags:指出包头中的相关标记      
seq:序列号/确认序列号      
idbq:输入队列数据包数/输出队列数据包数      
iidbq:接口上等待传送的不可靠组播数据包数/等待传送的可靠组播数据包数      
peerQ:接口上等待传送的不可靠单播数据包数/等待传送的可靠单播数据包数      
serno:只想某条路由的双重连接的指针(搞不懂)

DUAL算法的核心内容:

  • Any time an input event occurs, perform a local calculation.

  • If one or more feasible successors are found in the topology table, take the ones with the lowest metric cost as the successors.

  • If no feasible successor can be found, make the route active and query the neighbors for a feasible successor.

  • Keep the route active until all queries are answered by reply or by the expiration of the active timer.

  • If the diffusing calculation does not result in the discovery of a feasible successor, declare the destination unreachable.