示例演示“距离矢量路由算法”工作原理

简介:

以下内容摘自刚刚上市,已被纳入全国高校教材系统,并在全国热销、好评如潮《深入理解计算机网络书。

7.5.3  距离矢量路由算法

    现代计算机网络通常使用动态路由算法,因为这类算法能够适应网络的拓扑和流量变化,其中最流行的两种动态路由算法是“距离矢量路由算法”和“链路状态路由算法”。

    距离矢量路由算法Distance Vector RoutingDVARPANET网络上最早使用的路由算法,也称Bellman-Ford路由算法和Ford-Fulkerson算法,主要在RIPRoute Information Protocol)协议中使用。CiscoIGRPEIGRP路由协议也是采用DV这种路由算法的。

    “距离矢量路由算法”的基本思想如下:每个路由器维护一个距离矢量(通常是以延时是作变量的)表,然后通过相邻路由器之间的距离矢量通告进行距离矢量表的更新。每个距离矢量表项包括两部分:到达目的结点的最佳输出线路,和到达目的结点所需时间或距离,通信子网中的其它每个路由器在表中占据一个表项,并作为该表项的索引。每隔一段时间,路由器会向所有邻居结点发送它到每个目的结点的距离表,同时它也接收每个邻居结点发来的距离表。这样以此类推,经过一段时间后便可将网络中各路由器所获得的距离矢量信息在各路由器上统一起来,这样各路由器只需要查看这个距离矢量表就可以为不同来源分组找到一条最佳的路由。

    现假定用延时作为距离的度量,举一个简单的例子,如图7-37所示。假设某个时候路由器Y收到其邻居路由器X的距离矢量,其中mY估计到达路由器X的延时。若Y路由器知道它到邻居Z的延时为n,那么它可以得知Z通过Y到达X需要花费时间m+n。如果Z路由器还有其他相邻路由器,则对于从其他每个邻居那儿收到的距离矢量,该路由器执行同样的计算,最后从中选择费时最小的路由作为Z去往X的最佳路由,然后更新其路由表,并通告给其邻居路由器。

7-37  距离矢量路由算法简单实例

    现以一个如图7-38所示的示例介绍距离矢量算法中的路由的确定流程,各段链路的延时均已在图中标注。ABCDE代表五个路由器,假设路由表的传递方向为:A → B → C → D → E(这与路由器启动的先后次序有关)。下面具体的流程。 

   (1)初始状态下,各路由器都只收集直接相连的链路的延时信息,各路由器结点得出各自的初始矢量表如图7-39所示。因为各结点间还没有交换路由信息,所以它们的初始状态的路由表也如它们的矢量表。 

图7-38 距离矢量算法路由确定示例

图7-39 初始状态下各结点的矢量表

   (2) 现在路由器A把它的路由表发给路由器B。此时它会综合从A路由器发来的路由表和它自己的初始路由表,更新为一个新的矢量表,如图7-40左图所示(最终的矢量表如图中深颜色部分)。从图中可以看出,从B结点到达E结点此时存在两条路径,一条是直达的,一条是通过A结点到达的。而且这两条线的开销不同,经过A结点到达E结点的开销(7)比直达线路的开销(8)更低,所以最终在形成的路由表中,把到达E结点的线路改为经由A结点这条线路,如图7-40右图所示。

图7-40  B结点新的矢量表和路由表

   (3B再把最终形成的路由表发给路由器C。同样,路由器C也要把它原来的初始路由表与从B路由器发来的路由表进行综合,形成新的矢量表,如图7-41左图所示(最终的矢量表如图中深颜色部分)。在新的矢量表中,除了最初的直接连接的BD结点间的矢量外,还新收集了到达AE结点的矢量信息。因为C结点没有与AE结点的直接连接,在初始路由表中并没有到达这两个结点的路由信息,所以现在只有采用从B路由器发来的路由表中,经过B结点到达AE结点的路径。

    这里要注意一点,因为在B结点路由表中就已识别了直接通过B结点到达E结点的开销(8)还比依次通过BA结点到达E结点的开销(7)大,所以在C结点路由表中是采用依次通过BA结点到达E结点这条路径。最终形成的路由表如图7-41右图所示。

图7-41  C结点新的矢量表和路由表

  (4)路由器 C再把它的最终路由表发给路由器D。同样,路由器D也要把它原来的初始路由表与从C路由器发来的路由表进行综合,形成新的矢量表,如图7-42左图所示(最终的矢量表如图中深颜色部分)。在新的矢量表中,除了最初的直接连接的CE结点间的矢量信息外,还新收集了到达AB结点的矢量信息。因为D结点没有与AB结点的直接连接,所以在其最初的路由表中并没有到达这两个结点的矢量信息,此时仍采用经过C结点到达AB结点的路径。

   在这里同样要注意一点,从D结点到达E结点也有两条路径:一是直接到达,二是依次通过CBA结点到达,经过比较发现直接连接到达的开销(2)要比通过CBA结点到达E结点路径的开销(10)要小,所以在D结点中,到达E结点是采用直接连接这条线路。最终形成的路由表如图7-42右图所示。

   (5)路由器 D再把它的最终路由表发给路由器E。同样,路由器E也要把它原来的初始路由表与从D路由器发来的路由表进行综合,形成新的矢量表,如图7-43左图所示(最终的矢量表如图中深颜色部分)。在新的矢量表中,除了最初的直接连接的ABD结点间的矢量外,还新收集了到达C结点的矢量信息,因为E结点没有与C结点的直接连接。此时仍采用经过D结点到达C结点的路径。

图7-42  D结点新的矢量表和路由表

   在这里有两个要注意的地方:一是从E结点到达A结点的路径问题,因为此时E结点与A结点是直接连接的,而且其开销(1)要比原来从D路由口器发来的路由表中提供的通过DCB结点到达A结点路径开销(11)要小,所以在最终的E结点路由表中,到达A结点是采用直接连接这条线路。二是E结点虽然也是与B结点直接连接,但它的开销(8)还要比原来从D路由器发来的路由表中提供的依次经过DC这两个结点到达B结点的开销(5)大,所以在最终的E结点路由表中,到达B结点是采用依次经过DC两个结点这条路径。最终形成的路由表如图7-43右图所示。

图7-43  E结点新的矢量表和路由表

    通过以上步骤,网络中各路由器就完整了整个路由表的确定,当然在拓扑结构发生变化时,各路由器的路由表又会发生变化,重新进行更新。

本文转自王达博客51CTO博客,原文链接http://blog.51cto.com/winda/1152866如需转载请自行联系原作者


茶乡浪子

相关文章
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
73 3
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
软演员-评论家算法(Soft Actor-Critic, SAC)是深度强化学习领域的重要进展,基于最大熵框架优化策略,在探索与利用之间实现动态平衡。SAC通过双Q网络设计和自适应温度参数,提升了训练稳定性和样本效率。本文详细解析了SAC的数学原理、网络架构及PyTorch实现,涵盖演员网络的动作采样与对数概率计算、评论家网络的Q值估计及其损失函数,并介绍了完整的SAC智能体实现流程。SAC在连续动作空间中表现出色,具有高样本效率和稳定的训练过程,适合实际应用场景。
78 7
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
理解CAS算法原理
CAS(Compare and Swap,比较并交换)是一种无锁算法,用于实现多线程环境下的原子操作。它通过比较内存中的值与预期值是否相同来决定是否进行更新。JDK 5引入了基于CAS的乐观锁机制,替代了传统的synchronized独占锁,提升了并发性能。然而,CAS存在ABA问题、循环时间长开销大和只能保证单个共享变量原子性等缺点。为解决这些问题,可以使用版本号机制、合并多个变量或引入pause指令优化CPU执行效率。CAS广泛应用于JDK的原子类中,如AtomicInteger.incrementAndGet(),利用底层Unsafe库实现高效的无锁自增操作。
理解CAS算法原理
令牌桶算法原理及实现,图文详解
本文介绍令牌桶算法,一种常用的限流策略,通过恒定速率放入令牌,控制高并发场景下的流量,确保系统稳定运行。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
令牌桶算法原理及实现,图文详解
【AI系统】布局转换原理与算法
数据布局转换技术通过优化内存中数据的排布,提升程序执行效率,特别是对于缓存性能的影响显著。本文介绍了数据在内存中的排布方式,包括内存对齐、大小端存储等概念,并详细探讨了张量数据在内存中的排布,如行优先与列优先排布,以及在深度学习中常见的NCHW与NHWC两种数据布局方式。这些布局方式的选择直接影响到程序的性能,尤其是在GPU和CPU上的表现。此外,还讨论了连续与非连续张量的概念及其对性能的影响。
70 3
5大负载均衡算法及原理,图解易懂!
本文详细介绍负载均衡的5大核心算法:轮询、加权轮询、随机、最少连接和源地址散列,帮助你深入理解分布式架构中的关键技术。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
5大负载均衡算法及原理,图解易懂!
OSPF的路由计算算法:原理与应用
OSPF的路由计算算法:原理与应用
82 4
OSPF的SPF算法介绍:原理、实现与应用
OSPF的SPF算法介绍:原理、实现与应用
102 3
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等