更新时间：2022-10-26 00:00
距离矢量算法是以R.E.Bellman,L.R.Ford和D.R.Fulkerson所做的工作为基础的，鉴于此，我们把距离矢量路由协议称为Bellman-Ford或者Ford-Fulkerson算法。
每种路由协议都有自己的算法，路由协议在共享和传递路由更新信息，乃至收敛都因为算法的不同而不同。
路由协议根据算法可以分为两大类（也有说三类的—混合）：距离矢量（Distance Vector）和链路状态（Link State）。
例如：“朝下一个路由器X的方向可以到达网络A，距此5跳之远”
每台路由器在信息上都依赖于自己的相邻路由器，而它的相邻路由器又是通过自它们自己的相邻路由器那里学习路由，依此类推，所以就好像街边巷尾的小道新闻——一传十，十传百，很快就能弄到家喻户晓了。正因为如此，我们一般把距离矢量路由协议称之为“依照传闻的路由协议”
路由以矢量（距离、方向）的方式被通告出去的，其中距离是根据度量来定义的，方向是根据下一跳路由器定义的。被认为是“依照传闻进行路由选择”
距离矢量协议直接传送各自的路由表信息。网络中的路由器从自己的邻居路由器得到路由信息，并将这些路由信息连同自己的本地路由信息发送给其他邻居，这样一级级的传递下去以达到全网同步。每个路由器都不了解整个网络拓扑，它们只知道与自己直接相连的网络情况，并根据从邻居得到的路由信息更新自己的路由。
距离矢量协议无论是实现还是管理都比较简单，但是它的收敛速度慢，报文量大，占用较多网络开销，并且为避免路由环路得做各种特殊处理。目前基于距离矢量算法的协议包括 RIP、IGRP、BGP。其中 BGP是距离矢量协议变种，它是一种路径矢量协议。
距离矢量路由算法是动态路由算法。它是这样工作的：每个路由器维护一张矢量表，表中列出了当前已知的到 每个目标的最佳距离，以及所使用的线路。通过在邻居之间相互交换信息，路由器不断地更新它们内部的表。
距离矢量路由算法最常见的是Ford－Fulkerson算法。该算法的核心思想是使用标号的方法不断寻找一个图上的 可增广路径并且进行调整，直到找不到可增广路径为止。距离矢量路由算法号召每个路由器在每次更新时发送它 的整个路由表，但仅仅给它的邻居。距离矢量路由算法倾向于路由循环，但比链路状态路由算法计算更简单。
算法描述如下：
给定带杈有向图G和源点s，求从s到G中任意顶点v的最短路径，该算法通过在一个路由中重申跳数的个数九来寻 找一个最短路径生成树。
在距离矢量路由选择算法中，每个路由器维持有一张子网中每一个以其他路由器为索引的路由选择表，表中的 每一个项目都对应于子网中的每个路由器。此表项包括两个部分，即希望使用的到目的地的输出线路和估计到达 目的地所需时间或距离。用度量标准可为站点，估计的时间延迟（ms），该路出排队的分组估计总数或类似的值。
假定路由器知道它到每个相邻路由器的“距离”。如果度量标准为站点，其距离就为一个站点；如果度量标准是队列长度，则路由器会简单地检查每个队列；如果度量标准是延迟，路由器可以直接发送一个特别“响应”（ECHO）分组来测出延迟，接收者只对它加上时间标记后就尽快送回。
1、IP路由信息协议–RIP
2、Xerox网络系统的XNS RIP
3、Novell的IPX RIP
5、DEC的DNA阶段4
6、Apple Talk的路由选择表维护协议–RTMP
7、增强型内部网关路由选择协议–EIGRP（Enhanced Interior Gateway Routing Protocol）
RIP协议
RIP(Routing Information Protocols，路由信息协议)是使用最广泛的距离矢量协议，它是由施乐(Xerox)在70年代开发的。TCP/IP版本的RIP是施乐协议的改进版。RIP最大的特点是，无论实现原理还是配置方法，都非常简单。RIP基于跳数计算路由，并且定期向邻居路由器发送更新消息。
IGRP协议
IGRP是CISCO专有的协议，只在CISCO路由器中实现。它也属于距离矢量类协议，所以在很多地方与RIP有共同点，比如广播更新等等。它和RIP最大的区别表现在度量方法、负载均衡等几方面。IGRP支持多路径上的加权负载均衡，这样网络的带宽可以得到更加合理的利用。另外，与RIP仅使用跳数作为度量依据不同，IGRP使用了多种参数，构成复合的度量值，这其中可以包含的因素有：带宽、延迟、负载、可靠性和MTU(最大传输单元)等等。
EIGRP协议
EIGRP是IGRP的增强版，它也是CISCO专有的路由协议。EIGRP采用了扩散更新(DUAL)算法，在某种程度上，它和距离向量算法相似，但具有更短的收敛时间和更好的可操作性。作为对IGRP的扩展，EIGRP支持多种可路由的协议，如IP、IPX和AppleTalk等等。运行在IP环境时，EIGRP还可以与IGRP进行平滑的连接，因为它们的度量方法是一致的。
1、定期更新（Periodic Updates）
既然说到了是定期，那么它们都会在到达某一个时间点上“同时”发送更新信息，更新信息指的是各路由器各自的直连网络信息。一般这个时间周期为10S到90S。这个周期依照路由协议的不同而不同，常用的RIP为30S，而IGRP为90S。这里引发争议的是如果更新信息在网络中过于频繁就会浪费带宽，造成拥塞，如果更新信息发送太慢频率不高，收敛时间又会变长。
2、邻居（Neighbours）
邻居通常意味着共享相同的数据链路的路由器。距离矢量路由协议向邻居路由器发送更新信息，并依赖邻居向它的邻居传递更新信息，因此，距离矢量路由协议可以被看成是以“逐跳更新方式”来进行路由更新的协议。
3、包含整个路由表的更新
就好象两个知心好友一样，推心置腹……把自己知道的什么玩意儿都掏出来告诉对方。基本上所有的距离矢量路由协议都会采用这种简便的办法来向邻居路由器通告自己所知道的所有信息——告诉其他路由器自己的整张路由选择表，邻居在收到该信息后，去其糟粕，取其精华……完善自己的路由表。
4、依照传闻进行路由选择
5、路由计时器，描述距离矢量的几种计时器
6、水平分割（Split Horizon）详见CCNP-BSCI 002距离矢量路由协议–水平分割
7、计数到无穷大
最大15跳，避免产生Loop
8、触发更新（Triggered Update）
触发更新又名快速更新：当路由收敛后，如果某台路由器得知自己直连的一条链路的度量变化了，（无论好或者坏）那么该路由器将立即发送更新信息，不必等到更新计时器的到期。
9、抑制计时器（Holddown Timer）
触发更新为正在进行收敛的网络增加了应变能力，为了降低接受错误路由信息的可能性，抑制计时器引入了某种程度的怀疑量
如果到一个目标的度量发生改变（无论是增大还是减小），那么路由器将会将该路由条目置为抑制状态——即加上一个抑制计时器。直到计时器超时，路由器才会接受有关此路由的信息。
它虽然降低了错误路由的可能性，但是收敛时间却会因此而变长，因为在对其进行配置的时候，一定要根据全网的情况来配置一个合适的值。
10、异步更新（Asynchronous Update）
假设有一组连接在以太网段上的路由器群，大家都记得，以太网的工作方式。如果每台路由器都共享一个广播网络的时候，很可能会出现更新同步的情况——几台路由器的更新时间同时到期，同时更新。那么就会造成报文的碰撞，然后根据CSMA/CD，它们会回退，但是，很可能这样一来影响到整个系统的时延，最终会造成整个网络的同步。所以，我们通常使用两种办法来防止同步保持异步更新：
· 每台路由器的更新计时器都独立于路由进程，因为不会受到路由器处理负载的影响。
· 在每个更新周期中加入一个小的随机偏移量。