文档介绍：第5章路由算法 1 2014/11/ 24第5章路由算法 Fundamental of works 通信网络理论基础第5章路由算法 2 2014/11/ 24 第5章内容概述? 路由算法概述? 常用的路由算法? 数学基础—图论? 最短路径算法第5章路由算法 3 2014/11/ 24 第5章内容概述? 路由算法概述- 路由选择算法的分类- 对路由选择算法的要求- 路由算法的实现—路由表? 常用的路由算法? 数学基础—图论? 最短路径算法第5章路由算法 4 2014/11/ 24 路由算法概述(1) ?网络层的功能包括寻址和选择路由,建立、保持和终止网络连接等。?路由算法是网络层的核心,其主要功能是指引分组通过通信子网到达正确的目的节点。具体表现为两个方面的内容: ?寻径:为不同的源节点和目的节点对( SD )选择一条传输路径; ?转发:在路由选择好以后,将用户的消息正确地送到目的节点。第5章路由算法 5 2014/11/ 24 路由算法概述(2) ?路由选择的目的和要求: ?能正确、迅速、合理地传送分组(报文)信息。?能适应网络内节点或链路故障而引起的拓扑变化,使分组(报文)在有故障的条件下一般还能到达终点。在发生故障时,允许某些线路的通信量过载而增加时延。?能适应网络流量的变化,使各通路的流量均匀, 整个网络的通信设备负荷平衡,充分发挥效率。?算法尽量简单,以减少网络开销。第5章路由算法 6 2014/11/ 24 路由算法概述(3) ?通过一个例子来看看路由选择对网络性能的影响: 两个源节点和一个目的节点。所有链路的容量为 10单位,两个源节点 1和2的输入业务量分别为λ1和λ2, 讨论: ?λ1= λ 2=5 单位?λ 1=5 单位, λ 2=15 单位路由选择对网络性能的影响。第5章路由算法 7 2014/11/ 24 路由算法概述(4) 当λ 1=λ 2 =5 时?如果节点 1选择 1→3→6, 节点2选择 2→5→6, 则由于每条链路的业务量都只有信道容量的一半, 因而时延很小。?如果节点 1选择 1→4→6, 节点2选择 2→4→6, 则链路 4→6 运载的业务量为 10单位, 达到了链路的最大容量,因而时延会很大。第5章路由算法 8 2014/11/ 24 路由算法概述(5) 当λ 1 =5, λ 2 =15 时?节点 2的输入业务量为 15个单位。由于每条链路的容量仅为 10个单位,在仅使用一条路径的情况下,节点 2至少要丢弃 5个单位的业务流量。?如果节点 2将输入业务流量在2→4→6和2→5→6之间分摊,节点 1选择 1→3→6,则每条链路上的业务流量都不超过链路容量的 75% ,因而分组的时延较小。第5章路由算法 9 2014/11/ 24 路由算法概述(5) ?从图中可以看出:当节点 1 和2输入的流量很大时,根据不同的路由选择方法,网络可接纳的最大通过量为 10~ 30单位。?由此可以看出:一个路由算法应当在高业务负荷的情况下,在保证相同的时延条件下,可以增加网络的通过量;在轻负荷和中等负荷的情况下,可以减少每一个分组的平均时延。第5章路由算法 10 2014/11/ 24 第5章内容概述? 路由算法概述- 路由选择算法的分类- 对路由选择算法的要求- 路由算法的实现—路由表? 常用的路由算法? 数学基础—图论? 最短路径算法