文档介绍：路由算法及比较
丁杰 08211057 通信0801
路由算法是网络层的核心问题,其主要功能:第一是为不同的原节点和目的节点对(SD)选择一条传输路径;第二是在路由选择好以后,将用户消息正确地送到目的节点。
路由算法的设计目标
路由算法通常具有下列设计目标的一个或多个:
(1) 正确性:算法必须是正确的。即沿着各节点(交换机或路由器)中路由表所指引的路由,分组一定能够最终达到目的节点(交换机或路由器)。并且,分组到达目的节点后不会再向其他节点转发该分组。
(2) 简洁性:算法设计简洁,路由协议必须高效地提供其功能,尽量减少软件和应用的开销。实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。
(3) 自适应性:又可称为“稳定性”或“鲁棒性”(robustness)。即算法能够适应网络业务量的拓扑的变化。当网络的总业务量发生变化时,算法能自适应地改变路由。当节点链路出现故障或修复后重新开始工作时,算法应能及时找到一条替换路径。
(4) 快速收敛:收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时,路由器就发出更新信息。路由更新信息遍及整个网络,引发重新计算最佳路径,最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。
(5) 公平性:算法对所有用户必须是等同的。例如,仅考虑使某一对用户的端到端时延为最小,它们就可能占用相对较多的网络资源,这样就明显不符合公平性的要求。
(6) 最优性:路由选择算法应该能提供最佳路由,从而使平均分组时延最小、吞吐量最大或可靠性最高。这里“最佳”可以是有多个因素决定的,如链路长度、数据率、链路容量、传输时延、节点缓冲区被占用的程度、链路的差错率、分组的丢失率等。
一个路由算法应当在高的业务负荷的情况下,在保证相同的实验条件下,可以增加网络的通过量;在轻负荷和中等负荷情况下,可以减少每一个分组的平均时延。在实际中,其实是没有完全符合以上所有目标的路由算法的,也正是因为如此,在设计路由算法的时候,选择其中的最重要的几个目标来设计路由算法,以尽可能达到最好的效果。
路由算法的分类
路由算法的分类方法有很多,根据基本分类要素的不同,可以从不同的角度来对路由算法进行分类:
静态与动态
静态路由算法很难算得上是算法,只不过是开始路由前由网管建立的表映射。这些映射自身并不改变,除非网管去改动。使用静态路由的算法较容易设计,在网络通信可预测及简单的网络中工作得很好。由于静态路由系统不能对网络改变做出反映,通常被认为不适用于现在的大型、易变的网络。
单路径与多路径
一些复杂的路由协议支持到同一目的的多条路径。与单路径算法不同,这些多路径算法允许数据在多条线路上复用。多路径算法的优点很明显:它们可以提供更好的吞吐量和可靠性。
平坦与分层
一些路由协议在平坦的空间里运作,其它的则有路由的层次。在平坦的路由系统中,每个路由器与其它所有路由器是对等的;在分层次的路由系统中,一些路由器构成了路由主干,数据从非主干路由器流向主干路由器,然后在主干上传输直到它们到达目标所在区域,在这里,它们从最后的主干路由器通过一个或多个非主干路由器到达终点。路由系统通常设计有逻辑节点组,称为域、自治系统或区间。
在分层的系统中,一些路由器可