高中数学 第三章 空间向量与立体几何 3.1 空间向量及其运算 距离向量路由计算素材 新人教A版选修2-1（通用）

距离向量路由算法距离向量路由算法(Bellman-Ford Routing Algorithm)，也叫做最大 流量演算法(Ford-Fulkerson Algorithm)，其被 距离向量协议作为一个算法，如RIP, BGP, ISO IDRP, NOVELL IPX。使用这个算法的 路由器必须掌握这个距离表(它是一个一维排列-“一个向量”)，它告诉在 网络中每个 节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。表中数据的量和在网络中的所有的接点(除了它自己本身)是等同的。这个表中的列代表直接和它相连的邻居，行代表在网络中的所有目的地。每个 数据包括传送数据包到每个在网上的目的地的路径和距离/或时间在那个路径上来传输(我们叫这个为“成本”)。这个在那个算法中的度量公式是跳跃的次数， 等待时间，流出数据包的数量，等等。在距离向量路由算法中，相邻路由器之间 周期性地相互交换各自的 路由表备份。当 网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。距离向量路由算法 - 路由表的建立和更新如上图，有三个 路由器，A，B和C。路由器A的两个 网络接口E0和S0分别连接在 10.1.0.0和10.2.0.0网段上；路由器B的两个网络接口S0和S1分别连接在 10.2.0.0和10.3.0.0网段上；路由器C的两个网络接口S0和E0分别连接在 10.3.0.0和10.4.0.0网段上； 如上图中各 路由表的前两行所示，通过路由表的网络接口到与之直接相连的网络的网络连接，其向量距离设置为0。这即是最初的路由表。当路由器B和A以及B和C之间相互交换路由信息后，它们会更新各自的路由表。例如，路由器B通过 网络端口S1收到路由器C的路由信息（10.3.0.0,S0,0）和(10.4.0.0,E0,0)后，在自己的路由表中增加一条(10.4.0.0,S1,1)路由信息。该信息表示：通过路由器B的网络接口S1可以访问到10.4.0.0网段，其向量距离为1,该向量距离是在路由器C的基础上加1获得的。同样道理，路由器B还会产生一条(10.1.0.0,S0,1)路由，这条路由是通过网络端口S0从路由器A获得的。如此反复，直到最终收敛，形成图中所示的路由表。概括地说，距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其它路由器。路由表中的每一条记录都包括目标 逻辑地址、相应的网络接口和该条路由的向量距离。当一个路由器从它的相邻处收到更新信息时，它会将更新信息与本身的路由表相比较。如果该路由器比较出一条新路由或是找到一条比当前路由更好的路由时，它会对路由表进行更新：将从该路由器到邻居之间的向量距离与更新信息中的向量距离相加作为新路由的向量距离。参与运算信息目的地址：在算法的IP实现中，这指的是主机或的IP 地址。 下一跳地址：到信宿的路由中的第一个 路由器。 接口：用于到下一跳物理。 metric值：一个数，指明本路由器到信宿的开销。 定时器：路由项最后一次被修改的时间。 路由标记：区分路由为内部 路由协议的路由还是外部路由协议的路由的标记。运算路由器间交换的最重要的信息是修改报文，参加路由维护计划的路由器发送当前存在于实体的描述路由库的路由修改报文。仅通过相邻路由器间交换路由信息是可以维护整个系统的最佳路由的，这在接下来的讨论中会逐步得到证明。 距离向量算法总是基于一个这样的事实：路由库中的路由已是目前通过报文交换而得到的最佳路由。同时，报文交换仅限于相邻的实体间，也就是说，实体共享同一个。当然，要定义路由是最佳的，就必须有衡量的办法，这就用到前面所说的“metric”。RIP简单的中，通常用可行路由所经的路由器数简单地计算metric值。在复杂的中，metric一般代表该路由传输报的延迟或其它发送开销。 令D代表从实体i到实体j的最佳路由的metric值，d（i，j）代表从i直接到j的开销，因为开销是可加的，算法中最佳路由如此获取表示： D（i，i）=0， 对所有的i D（i，j）=MINd（i，j）+D（k，j）， 当i不