5---路由算法解释.ppt

第5章 路由算法 第5章 内容概述 5.1 路由算法概述 5.2 常用的路由算法 5.4 数学基础—图论 5.5 最短路径算法 5.4 最短路径算法 讨论三种标准的集中式最短路径算法： Bellman-Ford算法（B-F算法） Dijkstra算法 Floyd-Warshall算法 Bellman-Ford算法和Dijkstra算法是点对多点的最短路径算法 Floyd-Warshall算法则是多点对多点的最短路径 算法。 5.4 最短路径算法 —B-F算法 典型的Bellman-Ford算法（简记为B-F算法）是一种集中式的点到多点的路由算法，即寻找网络中一个节点到其它所有节点的路由。 假定节点1是“目的节点”，我们要寻找网络中其它所有的节点到目的节点1的最短路径。 用dij表示节点 i 到节点 j 的长度；如果(i,j)不是图中的链路，则dij=∞。 最短行走长度用 表示。 第5章 路由算法 * 2014/11/24 Fundamental of Communication Networks 通信网络理论基础 第5章 内容概述 5.1 路由算法概述 5.2 常用的路由算法 5.4 数学基础—图论 5.5 最短路径算法 第5章 内容概述 5.1 路由算法概述 5.1.1 路由选择算法的分类 5.1.2 对路由选择算法的要求 5.1.3 路由算法的实现—路由表 5.2 常用的路由算法 5.4 数学基础—图论 5.5 最短路径算法 5.1 路由算法概述 (1) 网络层的功能包括寻址和选择路由，建立、保持和终止网络连接等。 路由算法是网络层的核心，其主要功能是指引分组通过通信子网到达正确的目的节点。具体表现为两个方面的内容： 寻径：为不同的源节点和目的节点对（SD）选择一条传输路径； 转发：在路由选择好以后，将用户的消息正确地送到目的节点。 5.1 路由算法概述 (2) 路由选择的目的和要求： 能正确、迅速、合理地传送分组（报文）信息。 能适应网络内节点或链路故障而引起的拓扑变化，使分组（报文）在有故障的条件下一般还能到达终点。在发生故障时，允许某些线路的通信量过载而增加时延。 能适应网络流量的变化，使各通路的流量均匀，整个网络的通信设备负荷平衡，充分发挥效率。 算法尽量简单，以减少网络开销。 5.1 路由算法概述 (3) 通过一个例子来看看路由选择对网络性能的影响： 两个源节点和一个目的节点 。所有链路的容量为10单位 ，两个源节点1和2的输入业 务量分别为λ1和λ2, 讨论: λ1=λ2=5单位 λ1=5单位, λ2=15单位 路由选择对网络性能的影响。 5.1 路由算法概述 (4) 当λ1=λ2=5时 如果节点1选择1→3→6, 节点2选择2→5→6, 则由于每条链路的业务量都只有信道容量的一半, 因而时延很小。 如果节点1选择1→4→6, 节点2选择2→4→6, 则链路4→6运载的业务量为10单位, 达到了链路的最大容量，因而时延会很大。 5.1 路由算法概述 (5) 当λ1=5, λ2=15时 节点2的输入业务量为15个单位。由于每条链路的容量仅为10个单位，在仅使用一条路径的情况下，节点2至少要丢弃5个单位的业务流量。 如果节点2将输入业务流量在2→4→6和2→5→6之间分摊，节点1选择1→3→6，则每条链路上的业务流量都不超过链路容量的75%，因而分组的时延较小。 5.1 路由算法概述 (5) 从图中可以看出：当节点1和2输入的流量很大时，根据不同的路由选择方法，网络可接纳的最大通过量为10～30单位。 由此可以看出：一个路由算法应当在高业务负荷的情况下，在保证相同的时延条件下，可以增加网络的通过量；在轻负荷和中等负荷的情况下，可以减少每一个分组的平均时延。 第5章 内容概述 5.1 路由算法概述 5.1.1 路由选择算法的分类 5.1.2 对路由选择算法的要求 5.1.3 路由算法的实现—路由表 5.2 常用的路由算法 5.4 数学基础—图论 5.5 最短路径算法 5.1.1 路由选择算法的分类 (1)