距离矢量

距离矢量算法

距离矢量路由协议

距离矢量的特点（通用属性）

距离矢量

距离矢量算法是以R.E.Bellman,L.R.Ford和D.R.Fulkerson所做的工作为基础的，鉴于此，我们把距离矢量路由协议称为Bellman-Ford或者Ford-Fulkerson算法。

距离矢量名称的由来是因为路由是以矢量（距离，方向）的方式被通告出去的，这里的距离是根据度量来决定的。通俗点就是：往某个方向上的距离。

每种路由协议都有自己的算法，路由协议在共享和传递路由更新信息，乃至收敛都因为算法的不同而不同。

路由协议根据算法可以分为两大类（也有说三类的—混合）：距离矢量（Distance Ventor）和链路状态（Link State）。

例如：“朝下一个路由器X的方向可以到达网络A，距此5跳之远”

每台路由器在信息上都依赖于自己的相邻路由器，而它的相邻路由器又是通过自它们自己的相邻路由器那里学习路由，依此类推，所以就好象街边巷尾的小道新闻——一传十，十传百，很快就能弄到家喻户晓了。呵呵。正因为如此，我们一般把距离矢量路由协议称之为“依照传闻的路由协议”

距离矢量算法

距离矢量路由算法是动态路由算法。它是这样工作的：每个路由器维护一张矢量表，表中列出了当前已知的到 每个目标的最佳距离，以及所使用的线路。通过在邻居之间相互交换信息，路由器不断地更新它们内部的表。

距离矢量路由算法最常见的是Ford－Fulkerson算法。该算法的核心思想是使用标号的方法不断寻找一个图上的 可增广路径并且进行调整，直到找不到可增广路径为止。距离矢量路由算法号召每个路由器在每次更新时发送它 的整个路由表，但仅仅给它的邻居。距离矢量路由算法倾向于路由循环，但比链路状态路由算法计算更简单。

算法描述如下：

给定带杈有向图G和源点s，求从s到G中任意顶点v的最短路径，该算法通过在一个路由中重申跳数的个数九来寻 找一个最短路径生成树。

在距离矢量路由选择算法中，每个路由器维持有一张子网中每一个以其他路由器为索引的路由选择表，表中的 每一个项目都对应于子网中的每个路由器。此表项包括两个部分，即希望使用的到目的地的输出线路和估计到达 目的地所需时间或距离。用度量标准可为站点，估计的时间延迟（ms），该路出排队的分组估计总数或类似的值。

假定路由器知道它到每个相邻路由器的“距离”。如果度量标准为站点，其距离就为一个站点；如果度量标准是队列长度，则路由器会简单地检查每个队列；如果度量标准是延迟，路由器可以直接发送一个特别“响应”（ECHO）分组来测出延迟，接收者只对它加上时间标记后就尽快送回。

距离矢量路由协议

1、IP路由信息协议–RIP

2、Xerox网络系统的XNS RIP

3、Novell的IPX RIP

4、Cisco的Internet网关路由选择协议–IGRP

5、DEC的DNA阶段4

6、Apple Talk的路由选择表维护协议–RTMP

7、外部Internet网关路由选择协议–EIGRP

距离矢量的特点（通用属性）

1、定期更新（Periodic Updates）

既然说到了是定期，那么它们都会在到达某一个时间点上“同时”发送更新信息，更新信息指的是各路由器各自的直连网络信息。一般这个时间周期为10S到90S。这个周期依照路由协议的不同而不同，常用的RIP为30S，而IGRP为90S。这里引发争议的是如果更新信息在网络中过于频繁就会浪费带宽，造成拥塞，如果更新信息发送太慢频率不高，收敛时间又会变长。

2、邻居（Neighbours）

邻居通常意味着共享相同的数据链路的路由器。距离矢量路由协议向邻居路由器发送更新信息，并依赖邻居向它的邻居传递更新信息，因此，距离矢量路由协议可以被看成是以“逐跳更新方式”来进行路由更新的协议。

3、包含整个路由表的更新

就好象两个知心好友一样，推心置腹……把自己知道的什么玩意儿都掏出来告诉对方。基本上所有的距离矢量路由协议都会采用这种简便的办法来向邻居路由器通告自己所知道的所有信息——告诉其他路由器自己的整张路由选择表，邻居在收到该信息后，去其糟粕，取其精华……完善自己的路由表。

4、依照传闻进行路由选择

5、路由计时器（在后面讲解RIP的时候会将到）。讲述距离矢量的几种计时器

6、水平分割（Split Horizon）详见CCNP-BSCI 002距离矢量路由协议–水平分割

7、计数到无穷大（在后面讲解RIP的时候会将到）

8、触发更新（Triggered Update）

触发更新又名快速更新：当路由收敛后，如果某台路由器得知自己直连的一条链路的度量变化了，（无论好或者坏）那么该路由器将立即发送更新信息，不必等到更新计时器的到期。

9、抑制计时器（Holddown Timer）

触发更新为正在进行收敛的网络增加了应变能力，为了降低接受错误路由信息的可能性，抑制计时器引入了某种程度的怀疑量

如果到一个目标的度量发生改变（无论是增大还是减小），那么路由器将会将该路由条目置为抑制状态——即加上一个抑制计时器。直到计时器超时，路由器才会接受有关此路由的信息。

它虽然降低了错误路由的可能性，但是收敛时间却会因此而变长，因为在对其进行配置的时候，一定要根据全网的情况来配置一个合适的值。

10、异步更新（Asynchronous Update）

假设有一组连接在以太网段上的路由器群，大家都记得，以太网的工作方式。如果每台路由器都共享一个广播网络的时候，很可能会出现更新同步的情况——几台路由器的更新时间同时到期，同时更新。那么就会造成报文的碰撞，然后根据CSMA/CD，它们会回退，但是，很可能这样一来影响到整个系统的时延，最终会造成整个网络的同步。所以，我们通常使用两种办法来防止同步保持异步更新：

·每台路由器的更新计时器都独立于路由进程，因为不会受到路由器处理负载的影响

·在每个更新周期中加入一个小的随机偏移量。