距离向量算法




距离向量算法的思想很简单：所有参加RIP协议的路由器周期性地向外广播路由刷新报文，主要内容是由很多路由项（entry）组成的路由刷新报文。对路由来说，最主要的内容是目的地址和下一跳地址（next hop）。对动态路由协议来说，为了找到本协议概念中的最佳路由，还必须注意路由的开销（metric）。所以路由项主要包括了目的地址、下一跳地址和路由开销。其他的如路由标记（tag）等内容在讲报文格式时，将具体讲到。




在设计时，每个路由器的另外RIP管理了一个路由数据库，该路由数据库为系统中所有可能的信宿包含一个路由项，并为每个信宿保留如下信息：




·目的地址：在算法的IP实现中，这指的是主机或网络的IP 地址。
·下一跳地址：到信宿的路由中的第一个路由器。
·接口：用于到下一跳物理网络。
·metric值：一个数，指明本路由器到信宿的开销。
·定时器：路由项最后一次被修改的时间。
·路由标记：区分路由为内部路由协议的路由还是外部路由协议的路由的标记。




数据库由与系统直接相连的实体的描述初始化，通过从相邻路由器受到的报文修改维护。




路由器间交换的最重要的信息是修改报文，参加路由维护计划的路由器发送当前存在于实体的描述路由数据库的路由修改报文。仅通过相邻路由器间交换路由信息是可以维护整个系统的最佳路由的，这在接下来的讨论中会逐步得到证明。




距离向量算法总是基于一个这样的事实：路由数据库中的路由已是目前通过报文交换而得到的最佳路由。同时，报文交换仅限于相邻的实体间，也就是说，实体共享同一个网络。当然，要定义路由是最佳的，就必须有衡量的办法，这就用到前面所说的“metric”。RIP简单的网络中，通常用可行路由所经的路由器数简单地计算metric值。在复杂的网络中，metric一般代表该路由传输数据报的延迟或其它发送开销。




令D(i,j)代表从实体i到实体j的最佳路由的metric值，d（i，j）代表从i直接到j的开销，因为开销是可加的，算法中最佳路由如此获取表示：




D（i，i）=0， 对所有的i
D（i，j）=MIN[d（i，j）+D（k，j）， 当i不等于k时




实体i从相邻路由器k收到k到j的开销的估计D(i，j)，i将D（i，j）加上i到k的开销估计d（i，j），i比较从所有相邻路由器得到的数值，取得最小数，就得到了它到j的最佳路由。




具体地说，距离向量算法如下所述：




首先，路由器刚启动时，对距离向量路由表（V-D路由表）进行初始化，该初始化路由表包含所有去往与本路由器直接相连的网络的路径。由于去往直接相连的网络不经过中间路由器，所以初始化的V-D路由表中的各路由的距离均为0。




.1初始V-D路由表的一个示例。


.1的“信宿网”域含信宿网IP地址。
然后，各路由器周期性地向外广播其V-D路由表内容。与某路由器直接相连的（位于同一物理网络）的路由器收到该路由表报文后，根据此报文对本地路由表进行刷新。刷新时，路由器逐项检查来自相邻路由器的V-D报文，遇到下述表目之一，须修改本地路由表（假设路由器Gi收到路由器Gj的V-D报文）：





1） Gj列出的某表目Gi路由表中没有。则Gi路由表中须增加相应表目，其“信宿”是Gj表目中的信宿，其“路径”为“Gj”（即下一路由器为Gj）。

2） Gj去往某信宿的距离值比Gi去往该信宿的距离减1还小。
这种情况说明，Gi去往某信宿若经过Gj，距离会更短。则Gi修改本表目，其中“信宿”域不变，“距离”为Gj表目中距离加1，“路径”为“Gj”。

3） Gi去往某信宿的路由经过Gj，而Gj去往该信宿的路由发生变化。
这里分两种情况：





a. Gj的V-D表不再包含去往某信宿的路由，则GI中相应路由须删除。
b. Gj的V-D表中去往某信宿的路由距离发生变化，则Gi中相应表目“距离”须修改，以Gj中的“距离”加1取代原来的距离。




.2中对以上描述给出直观的说明，其中Gi、Gj为相邻路由器。

（a）路由器Gi原路由表


（b）路由器Gj广播的V-D报文


（c）路由器Gj刷新后的路由表

图 2.2 中，“ ”所指示为须刷新的表目，“ ”为引起刷新的表目，“ ”为刷新后的表目。




这里要特别强调的是， V-D 算法的路由刷新发生在相邻路由器之间，所以 V-D 报文不一定以广播方式发送出去，一种比较优化的思想是路由器直接向相邻路由器发送 V-D 报文，不必采用广播方式。