路由算法及比较(简单了解)

《路由算法及比较(简单了解)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、路由算法及比较丁杰08211057通信0801路由算法是网络层的核心问题，其主要功能：第一是为不同的原节点和目的节点对(SD)选择一条传输路径；第二是在路由选择好以后，将用户消息正确地送到目的节点。一、路由算法的设计目标路由算法通常具有下列设计目标的一个或多个：(1)正确性：算法必须是正确的。即沿着各节点（交换机或路由器）中路由表所指引的路由，分组一定能够最终达到目的节点（交换机或路由器）。并且，分组到达目的节点后不会再向其他节点转发该分组。　(2)简洁性：算法设计简洁，路由协议必须高效地提供其功能，尽量减少软件和

2、应用的开销。实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。　(3)自适应性：又可称为“稳定性”或“鲁棒性”（robustness）。即算法能够适应网络业务量的拓扑的变化。当网络的总业务量发生变化时，算法能自适应地改变路由。当节点链路出现故障或修复后重新开始工作时，算法应能及时找到一条替换路径。　(4)快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最

3、佳路径。收敛慢的路由算法会造成路径循环或网络中断。(5)公平性：算法对所有用户必须是等同的。例如，仅考虑使某一对用户的端到端时延为最小，它们就可能占用相对较多的网络资源，这样就明显不符合公平性的要求。(6)最优性：路由选择算法应该能提供最佳路由，从而使平均分组时延最小、吞吐量最大或可靠性最高。这里“最佳”可以是有多个因素决定的，如链路长度、数据率、链路容量、传输时延、节点缓冲区被占用的程度、链路的差错率、分组的丢失率等。一个路由算法应当在高的业务负荷的情况下，在保证相同的实验条件下，可以增加网络的通过量；在轻负荷和

4、中等负荷情况下，可以减少每一个分组的平均时延。在实际中，其实是没有完全符合以上所有目标的路由算法的，也正是因为如此，在设计路由算法的时候，选择其中的最重要的几个目标来设计路由算法，以尽可能达到最好的效果。二、路由算法的分类路由算法的分类方法有很多，根据基本分类要素的不同，可以从不同的角度来对路由算法进行分类：1、静态与动态静态路由算法很难算得上是算法，只不过是开始路由前由网管建立的表映射。这些映射自身并不改变，除非网管去改动。使用静态路由的算法较容易设计，在网络通信可预测及简单的网络中工作得很好。由于静态路由系统不

5、能对网络改变做出反映，通常被认为不适用于现在的大型、易变的网络。2、单路径与多路径一些复杂的路由协议支持到同一目的的多条路径。与单路径算法不同，这些多路径算法允许数据在多条线路上复用。多路径算法的优点很明显：它们可以提供更好的吞吐量和可靠性。3、平坦与分层一些路由协议在平坦的空间里运作，其它的则有路由的层次。在平坦的路由系统中，每个路由器与其它所有路由器是对等的；在分层次的路由系统中，一些路由器构成了路由主干，数据从非主干路由器流向主干路由器，然后在主干上传输直到它们到达目标所在区域，在这里，它们从最后的主干路由器

6、通过一个或多个非主干路由器到达终点。路由系统通常设计有逻辑节点组，称为域、自治系统或区间。在分层的系统中，一些路由器可以与其它域中的路由器通信，其它的则只能与域内的路由器通信。在很大的网络中，可能还存在其它级别，最高级的路由器构成了路由主干。分层路由的主要优点是它模拟了多数公司的结构，从而能很好地支持其通信。多数的网络通信发生在小组中（域）。因为域内路由器只需要知道本域内的其它路由器，它们的路由算法可以简化，根据所使用的路由算法，路由更新的通信量可以相应地减少。4、主机智能与路由器智能一些路由算法假定源结点来决定整

7、个路径，这通常称为源路由。在源路由系统中，路由器只作为存贮转发设备，无意识地把分组发向下一跳。其它路由算法假定主机对路径一无所知，在这些算法中，路由器基于自己的计算决定通过网络的路径。前一种系统中，主机具有决定路由的智能，后者则为路由器具有此能力。主机智能和路由器智能的折衷实际是最佳路由与额外开销的平衡。主机智能系统通常能选择更佳的路径，因为它们在发送数据前探索了所有可能的路径，然后基于特定系统对“优化”的定义来选择最佳路径。然而确定所有路径的行为通常需要很多的探索通信量和很长的时间。5、域内与域间一些路由算法只在

8、域内工作，其它的则既在域内也在域间工作。这两种算法的本质是不同的。其遵循的理由是优化的域内路由算法没有必要也成为优化的域间路由算法。4、链接状态与距离向量链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。距离向量算法（也叫做Bellman-Ford算法）中每个路由器发送路由表的全部或部分