理论教育 计算机网络技术中的最佳路由算法

计算机网络技术中的最佳路由算法

时间:2023-11-22 理论教育 版权反馈
【摘要】:最好的路由算法是能够选择一条代价最小的路径,常称最短路径。复杂的路由算法可能采用多种代价度量来选择路由,通过一定的加权运算,将它们合并为单个的复合度量,再填入路由表中,作为寻径的标准。路由算法可分为静态算法和动态算法两种。静态路由算法都很简单,动态路由算法一般都采用自适应算法。距离矢量算法虽然仅把信息发送给相邻结点,但发送的是整个路由表,信息量较大,发送的信息是预估的,使用Bellman-Ford算法计算最短路径。

计算机网络技术中的最佳路由算法

路由算法通信双方选择一条路径,需要考虑最佳路径、简洁性、灵活性等因素,例如,算法应该快速收敛,防止引起震荡,即A路拥塞,大家都涌向B路,造成A路畅通,大家又返回A路。

最好的路由算法是能够选择一条代价最小的路径,常称最短路径。代价可以是跳数、带宽、时延、负载(吞吐量)、可靠性、开销、费用等。跳数是指一个分组从源结点到达目的结点经过的路由器的个数;带宽是指链路的数据传输速率;时延是指一个分组从源结点到达目的的结点所花费的时间;负载是指单位时间内通过路由器或线路的通信量;可靠性是指传输过程中的误码率;开销是指传输过程中的耗费;费用是指通信成本。复杂的路由算法可能采用多种代价度量来选择路由,通过一定的加权运算,将它们合并为单个的复合度量,再填入路由表中,作为寻径的标准。

用于计算一个结点到其他结点的最小代价路径的算法有Dijkstra算法和Bellman-Ford算法。

Dijkstra算法的思想是以源结点为集合,每次从集合的邻居结点中选取一个结点,往集合里添加该结点,添加后再重新计算源结点到集合里每个结点的最短路径,直到把网络中的所有结点都加进来。对于Dijkstra算法,每个结点必须知道网络的完整的拓扑信息,必须知道网络中所有链路的链路代价,一个结点必须与所有其他结点交换信息。

Bellman-Ford算法第1步找出到源结点跳数为0的最短路径,第2步找出跳数为1的最短路径,以此类推,直至最大跳数。Bellman-Ford算法根据来自相邻结点的信息和链路代价的信息来更新本结点的代价和网络拓扑,这些信息需要包含网络其他结点的相关路径信息。

路由算法可分为静态算法和动态算法两种。静态算法包括洪泛法、随机法和固定法等;动态算法包括距离矢量法和链路状态法等。静态路由算法都很简单,动态路由算法一般都采用自适应算法。

洪泛法把分组广播到除来线外的所有输出端口。洪泛法不需要任何网络信息,甚至不需要路由表。为防止分组形成环路或在网上无限巡游,需要每个分组具有唯一的标识和跳数限制,结点不再转发具有同一标识的重复分组。实际上,以太网交换机在开机后,就是先采用洪泛法,之后才通过逆向学习法建立起路由表。(www.daowen.com)

随机法就是随机选择一条线路把分组转发出去,也可以按轮流顺序选择输出线路,还可以按某种概率选择输出线路,如线路的利用率或数据速率。随机法也不需要路由表。

固定法就是预先在结点中装载路由表,路由表可以由网络管理员设置,或从中心结点中下载。固定法在源、目的结点之间有一条固定不变的路径,一般只有在网络拓扑发生变化时才修改路由表。

在距离矢量路由选择中,相邻结点之间周期性地相互交换各自的路由表,路由表中列出了该结点到其他各结点的最佳路径。路由表可看做是一个矢量(距离,方向),距离就是代价度量,方向就是下一个结点。实际上,这种方法并不完全知道网络的拓扑结构,这个矢量信息也是预估的,通过相邻结点不断交换矢量信息,最终可以找到最佳路径。

在链路状态路由选择中,每个结点都会向其他所有结点提供自己与邻居的链路状态信息(如连通还是断开、代价等),目的是映射网络的拓扑结构,使所有结点都知道整个网络的拓扑结构,从而计算出最短路径。

距离矢量算法虽然仅把信息发送给相邻结点,但发送的是整个路由表,信息量较大,发送的信息是预估的,使用Bellman-Ford算法计算最短路径。链路状态算法把信息发给网络上的所有结点,但只发送与自己相关的确切信息,信息量较小,常使用Dijkstra算法计算最短路径。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈