理想的路由算法是什么?

2016-07-12 1686 0 编辑:Monster 来源:互联网

路由选择协议的核心就是路由算法,即需要何种算法来获得路由表中的各项目,一个理想的路由算法应具有如下的一些特点[BELL86]:

(1)算法必须是正确的和完整的。这里,“正确”的含义是:沿着各路由表所指引的路由,分组一定能够最终到达目的网络和目的主机。

(2)算法在计算上应简单。路由选择的计算不应使网络通信量增加太多的额外开销。

(3)算法应能适应通信量和网络拓扑的变化,这就是说,要有自适应性。当网络中的通信量发生变化时,算法能自适应地改变路由以均衡各链路的负载。当某个或某些结点、链路发生故障不能工作,或者修理好了再投入运行时,算法也能及时地改变路由。有时称这种自适应性为“稳健性”。

(4)算法应具有稳定性。在网络通信量和网络拓扑相对稳定的情况下,路由算法应收敛于一个可以接受的解,而不应使得出的路由不停地变化。

(5)算法应是公平的。路由选择算法应对所有用户(除对少数优先级高的用户)都是平等的。例如,若仅仅使某一对用户的端到端时延为最小,但却不考虑其他的广大用户,这就明显地不符合公平性的要求。

(6)算法应是最佳的。路由选择算法应当能够找出最好的路由,使得分组平均时延最小而网络的吞吐量最大。虽然我们希望得到“最佳”的算法,但这并不总是最重要的。对于某些网络,网络的可靠性有时要比最小的分组平均时延或最大吞吐量更加重要。因此,所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。

一个实际的路由选择算法,应尽可能接近于理想的算法。在不同的应用条件下,对以上提出的六个方面也可有不同的侧重。

应当指出,路由选择是个非常复杂的问题,因为它是网络中的所有结点共同协调工作的结果。其次,路由选择的环境往往是不断变化的,而这种变化有时无法事先知道,例如,网络中出了某些故障。此外,当网络发生拥塞时,就特别需要有能缓解这种拥塞的路由选择策略,但恰好在这种条件下,很难从网络中的各结点获得所需的路由选择信息。

倘若从路由算法能否随网络的通信量或拓扑自适应地进行调整变化来划分,则只有两大类,即静态路由选择策略与动态路由选择策略。静态路由选择也叫做非自适应路由选择,其特点是简单和开销较小,但不能及时适应网络状态的变化。对于很简单的小网络,完全可以采用静态路由选择,用人工配置每一条路由。动态路由选择也叫做自适应路由选择,其特点是能较好地适应网络状态的变化,但实现起来较为复杂,开销也比较大。因此,动态路由选择适用于较复杂的大网络。


本站文章均为深正网站建设摘自权威资料,书籍,或网络原创文章,如有版权纠纷或者违规问题,请即刻联系我们删除,我们欢迎您分享,引用和转载,但谢绝直接搬砖和抄袭!感谢...
关注深正互联
我们猜你喜欢