文档介绍：对路由算法的讨论电气学院自动化1313金莉萍5摘要:路由算法是提高路由协议功能,尽量减少路由时所带来开销的算法。路由算法在路由协议中起着至关重要的作用,采用何种算法往往决定了最终寻径结果。本文就对各路由算法在不同模型下,综合对比它们路径选择的差异以展开研究讨论。关键词:路由算法差异不同模式研究讨论随着科学技术的飞速发展,不仅传统业务流量大大增加,而且出现了许多新业务,如语音、数据和多媒体应用等对网络传输质量的要求差别很大,关于IP网络相关问题变得日益尖锐,特别是宽带业务,对网络性能加转发速度、流量控制以及网络的可扩展性等提出了较高的要求、随着主干网链路传输速度的不断提高,IP网络中节点上的包转发成了网络的瓶颈,在不断地需求下,人们提出了新的高效的路由算法,这种算法是通过提高网络的调节和控制功能使流量分布更加合理,以达到尽可能减少网络阻塞、最小的网络代价、分布的网络负载等目标。路由算法,又名选路算法,可以根据多个特性来加以区分。实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。路由算法必须健壮,即在出现不正常或不可预见事件的情况下必须仍能正常处理,例如硬件故障、高负载和不正确的实现。因为路由器位于网络的连接点,当它们失效时会产生重大的问题。最好的路由算法通常是那些经过了时间考验,证实在各种网络条件下都很稳定的算法。就我看来,一个理想的路由算法应该在计算上应简单。路由选择的计算不应使网络通信量增加太多的额外开销。算法应具有稳定性。在网络通信量和网络拓扑结构相对稳定的情况下,路由算法应收敛于一个可以接受的解,而不应使得出的路由不停的变化。算法必须是正确的和完整的。这里,“正确”的含义是指沿着各路由表所指引的路由,分组一定能够最终到达目的网络和目的主机。算法应能适应通信量和网络拓扑的变化,这就是说要有自适应性。当网络中的通信量发生变化时,算法能自适应的改变路由以均衡个链路的负载。等某个或某些节点、链路发生故障不能工作,或者修理好了再投入运行时,算法也能及时的改变路由。有时称这种自适应性为“稳健性”。算法应是最佳的。路由选择算法应当能够找出最好的路由,使得分组平均延时最小而网络的吞吐量最大。我们希望得到“最佳”的算法,但这并不是最重要的。对于某些网络,网络的可靠性有时要比最小的分组平均延时或最大吞吐量更加重要。因此,所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。一个实际的路由选择算法,应尽可能接近于理想算法。在不同的应用条件下对以上提出的六个方面也可有不同的侧重。所以,路由是个非常复杂的问题,因为它是网络中的所有结点共同协调工作的结果。路由算法应是公平的。路由选择算法应对所有用户(除了少数优先级高的用户)都是平等的。例如,若仅仅使某一对用户的端到端时延为最小,但却不考虑其他的广大用户,这就明显的不符合公平性的要求。路由算法的核心是路由选择算法,常见的路由选择算法有最短路径法、扩散法、基于流量的路由选择、距离向量路由选择、链路状态路由选择、分级路由选择、移动主机的路由选择、组播路由选择、广播路由选择。这种算法是个非常复杂的问题,因为它是网络中的所有节点共同协调工作的结果。其次,路由选择的环境往往是不断变化的,而这种变化有时无法事先知道,例如,网络中出现了某些故障。此外,当网络发生拥塞时,就特别需要有能缓解这种拥塞的路由选择策略