1、第5章 路由算法 1 2014/11/24第第5章章 路由算法路由算法Fundamental of Communication Networks 通信网络理论基础通信网络理论基础第5章 路由算法 2 2014/11/24第第5章章 内容概述内容概述 5.1 路由算法概述路由算法概述 5.2 常用的路由算法常用的路由算法 5.4 数学基础数学基础图论图论 5.5 最短路径算法最短路径算法 第5章 路由算法 3 2014/11/24第第5章章 内容概述内容概述 5.1 路由算法概述路由算法概述 -5.1.1 路由选择算法的分类-5.1.2 对路由选择算法的要求-5.1.3 路由算法的实现路由表 5
2、.2 常用的路由算法常用的路由算法 5.4 数学基础数学基础图论图论 5.5 最短路径算法最短路径算法 第5章 路由算法 4 2014/11/245.1 路由算法概述路由算法概述 (1)网络层网络层的功能包括寻址寻址和选择路由选择路由，建立、保持和终止网络连接等。路由算法路由算法是网络层的核心核心，其主要功能是指引分组通过通信子网到达正确的目的节点。具体表现为两个方面的内容：p 寻径寻径：为不同的源节点和目的节点对（SD）选择一条传输路径；p 转发转发：在路由选择好以后，将用户的消息正确地送到目的节点。第5章 路由算法 5 2014/11/245.1 路由算法概述路由算法概述 (2)路由选择的
3、目的和要求：p 能正确、迅速、合理地传送传送分组（报文）信息。p 能适应适应网络内节点或链路故障而引起的拓扑变化，使分组（报文）在有故障的条件下一般还能到达终点。在发生故障时，允许某些线路的通信量过载而增加时延。p 能适应网络流量的变化适应网络流量的变化，使各通路的流量均匀，整个网络的通信设备负荷平衡，充分发挥效率。p 算法算法尽量简单简单，以减少网络开销减少网络开销。第5章 路由算法 6 2014/11/245.1 路由算法概述路由算法概述 (3)通过一个例子来看看路由选择对网络性能的影响：两个源节点和一个目的节点。所有链路的容量为10单位，两个源节点1和2的输入业务量分别为1和2,讨论:p
4、 1=2=5单位p 1=5单位,2=15单位路由选择对网络性能的影响。第5章 路由算法 7 2014/11/245.1 路由算法概述路由算法概述 (4)当当1=2=5时时p 如果节点1选择136,节点2选择256,则由于每条链路的业务量都只有信道容量的一半,因而时延很小。p 如果节点1选择146,节点2选择246,则链路46运载的业务量为10单位,达到了链路的最大容量，因而时延会很大。第5章 路由算法 8 2014/11/245.1 路由算法概述路由算法概述 (5)当当1=5,2=15时时p 节点2的输入业务量为15个单位。由于每条链路的容量仅为10个单位，在仅使用一条路径的情况下，节点2至少
5、要丢弃5个单位的业务流量。p 如果节点2将输入业务流量在246和256之间分摊，节点1选择136，则每条链路上的业务流量都不超过链路容量的75%，因而分组的时延较小。第5章 路由算法 9 2014/11/245.1 路由算法概述路由算法概述 (5)p 从图中可以看出：当节点1和2输入的流量很大时，根据不同的路由选择方法，网络可接纳的最大通过量为1030单位。p 由此可以看出：一个路由算法应当在高业务负荷高业务负荷的情况下，在保证相同的时延条件下，可以增加网络的通过量；在轻负荷和中等负荷的情况下，可以减少减少每一个分分组的平均时延组的平均时延。第5章 路由算法 10 2014/11/24第第5章
6、章 内容概述内容概述 5.1 路由算法概述路由算法概述 -5.1.1 路由选择算法的分类路由选择算法的分类-5.1.2 对路由选择算法的要求-5.1.3 路由算法的实现路由表 5.2 常用的路由算法常用的路由算法 5.4 数学基础数学基础图论图论 5.5 最短路径算法最短路径算法 第5章 路由算法 11 2014/11/245.1.1 路由选择算法的分类路由选择算法的分类 (1)路由算法的分类 算法能否跟随网络拓扑变化p 非自适应的非自适应的（不根据实测或估计的网络当前业务量和拓扑结构来做路由选择。路由事先就计算好，在网络启动时就下载到网络路由器中。这种策略的最大优点是简单简单和开销小开销小）
7、p 自适应自适应第5章 路由算法 12 2014/11/245.1.1 路由选择算法的分类路由选择算法的分类 (2)路由算法的分类按路由决策方法p 集中式集中式（指网络的路由是由路由控制中心路由控制中心计算的，该中心周期性收集各链路的状态，经过路由计算后周期性地向各网络节点提供路由表。）p 分布式分布式（指网络中所有节点通过相互交换路由信息，独立地计算到达各节点的路由。）第5章 路由算法 13 2014/11/245.1.1 路由选择算法的分类路由选择算法的分类 (3)路由算法的分类 按应用场合p 广域网路由（解决一个子网内的路由）p 互联网路由（解决不同子网之间的路由）第5章 路由算法 14
8、 2014/11/24第第5章章 内容概述内容概述 5.1 路由算法概述路由算法概述 -5.1.1 路由选择算法的分类-5.1.2 对路由选择算法的要求-5.1.3 路由算法的实现路由算法的实现路由表路由表 5.2 常用的路由算法常用的路由算法 5.4 数学基础数学基础图论图论 5.5 最短路径算法最短路径算法 第5章 路由算法 15 2014/11/245.1.3 路由算法的实现路由算法的实现路由表路由表 路由算法的实现通过路由表路由表。节点上的路由表路由表指明该节点如何选择分组的传送路径选择分组的传送路径。节点节点1 1上的路由表上的路由表节点节点4 4上的路由表上的路由表目的节点2345
9、6目的节点12356下一个节点22442下一个节点12355p 路径选择原则原则是使到达目的节点的链路数最少。p 当存在2条以上具有相同链路数的最少链路数路径时，可以选择其中任意一条。p 路由表对每个目的节点指出分组应发向的下一个节点。第5章 路由算法 16 2014/11/245.1.3 路由算法的实现路由算法的实现路由表路由表 当路由表建立起来之后，在进行路由选择时只是简单地查找查找路由表中的信息，无须再作计算。然而对自适应路由自适应路由选择来说，会要求相当数量相当数量的计算计算来维持维持这张路由表路由表。通常路由表中还会包含一些附加信息，例如基于最少链路数准则的算法可能包括到达目的节点到
10、达目的节点的估计链路数估计链路数，这样上表所示的路由表要修改为下表所示的形式。目的节点23456下一个节点22442链路数12123包含最少链路数的节点1上的路由表第5章 路由算法 17 2014/11/24第第5章章 内容概述内容概述 5.1 路由算法概述路由算法概述 5.2 常用的路由算法常用的路由算法 5.4 数学基础数学基础图论图论 5.5 最短路径算法最短路径算法 第5章 路由算法 18 2014/11/245.2 常用的路由算法常用的路由算法 (1)不同的应用场合对路由算法有不同的要求。广域网广域网内的路由主要解决子网内分组的传输路径问题子网内分组的传输路径问题，它主要包括三种路由
11、算法：p 广播广播p 最短路由最短路由p 最佳路由最佳路由 互连网互连网解决不同子网之间的路由，采用的设备有网关和路由器等。Ad Hoc网络Ad Hoc网络，它是一种分布式的PRNET网络，该网络中使用了多种形式的路由算法。第5章 路由算法 19 2014/11/245.2 常用的路由算法常用的路由算法 (2)广播中的路由算法广播中的路由算法(1)广播是通信网中最常用的方式，用来传播公共信息、拓扑变化信息（包括节点和链路工作变化和故障等信息）。广播分组的接收节点通常是全网所有成员。如果接收节点为一个组或部分网络节点，则称为多播多播（Multicast）。第5章 路由算法 20 2014/11/
12、245.2 常用的路由算法常用的路由算法 (3)广播中的路由算法广播中的路由算法(2)可以逐一地把要广播的分组按照点对点的路由算法点对点的路由算法（Unicast）发送给每一个目的节点，但这种方法可能会浪费大量的网络资源，并且广播节点需要知道全网所有节点的路由信息。广播时采用的路由算法可以有多种方法：如泛洪泛洪（Flooding）路由、采用生成树生成树（Spanning Tree）的广播方式等。第5章 路由算法 21 2014/11/245.2 常用的路由算法常用的路由算法 (4)广域网广域网内的路由主要解决子网内分组的传输路径问题子网内分组的传输路径问题，它主要包括三种路由算法：p 广播广播
13、p 最短路由最短路由p 最佳路由最佳路由 互连网互连网解决不同子网之间的路由，采用的设备有网关和路由器等。Ad Hoc网络Ad Hoc网络，它是一种分布式的PRNET网络，该网络中使用了多种形式的路由算法。第5章 路由算法 22 2014/11/245.2 常用的路由算法常用的路由算法 (5)最短路由（最短路由（Shortest Path Routing）(1)许多实际的路由算法如RIP（Routing Information Protocol），OSPF（Open Shortest Path First）等都是基于最短路径这一概念。分组交换网络的各种路由算法实质实质上都是建立在某种某种形式的
14、最小费用准则形式的最小费用准则的基础上。p 譬如，我们把准则定为“最短路径”，那就有“最短路径路由算法”；p 注意：这里所说的“最短路径”并不单纯意味着一条物理长度最短的通路，它可以是从发送节点发送节点到达接接收节点收节点的中转次数最少中转次数最少。第5章 路由算法 23 2014/11/245.2 常用的路由算法常用的路由算法 (6)最短路由（最短路由（Shortest Path Routing）(2)最短路由关心一个节点对一个节点对之间的一条路径的选择和求解，因而有两个方面的缺陷：p 为每对节点之间仅提供一条路由，因而限制了网络的通过量；p 适应业务变化的能力受到防止路由振荡的限制。第5章
15、 路由算法 24 2014/11/245.2 常用的路由算法常用的路由算法 (7)广域网广域网内的路由主要解决子网内分组的传输路径问题子网内分组的传输路径问题，它主要包括三种路由算法：p 广播广播p 最短路由最短路由p 最佳路由最佳路由 互连网互连网解决不同子网之间的路由，采用的设备有网关和路由器等。Ad Hoc网络Ad Hoc网络，它是一种分布式的PRNET网络，该网络中使用了多种形式的路由算法。第5章 路由算法 25 2014/11/245.2 常用的路由算法常用的路由算法 (8)最佳路由（最佳路由（Optimal Routing）(1)最佳路由是从全网全网的范围寻找所有可能所有可能的传输
16、路径路径，从而使得发送节点到达接收节点的信息流的时延最小时延最小、流量最大流量最大，而不是局限于一条所谓的最短路径。采用最佳路由（基于平均时延最佳化）可以克服最短路径的上述缺陷，它可以将节点对之间的流量分配在多条路径上，从而可使网络的通过量最大，时延最小。第5章 路由算法 26 2014/11/24第第5章章 内容概述内容概述 5.1 路由算法概述路由算法概述 5.2 常用的路由算法常用的路由算法 5.4 数学基础数学基础图论图论 5.5 最短路径算法最短路径算法 第5章 路由算法 27 2014/11/245.3 数学基础数学基础图论图论(1)每一个网络网络都可以抽象成一个图图。一个图G由一
17、个非空的节点集合节点集合 N 和节点间的链路链路 A 组成，即 G=(V,E)。有方向/无方向p 如果节点i和j之间仅有i j 的链路，则称该链路是有有方向的方向的（或单向链路单向链路）。p 如果节点i和j之间同时有i j 及j i的链路，则称该链路是无方向的无方向的（或双向链路双向链路）。第5章 路由算法 28 2014/11/245.3 数学基础数学基础图论图论(2)方向图：当图G中的每一条边都有规定方向，则称该图为有向图有向图（方向图方向图）；对应的无方向图无方向图G=(N，A)。关联（Incident）：它表示链路与节点的关系。在方向图中，链路链路用关联的节点关联的节点来表示，若A1=
18、(1,2)，则表示链路A1关联的两个节点是1（起点）和2（终点）。注意：这里讨论的图不允许任何链路关联的两个节点相同，即不允许不允许有一条自环的链路自环的链路。第5章 路由算法 29 2014/11/245.3 数学基础数学基础图论图论(3)路径路径：由一些节点的序列组成，例如u=（n1,n2,n3nk）称为一条路径，也称为方向性行走方向性行走（walk）。p 给定每条链路（i,j）指定一个实数dij作为其长度，则一条方向性路径p=（i,j,k,l,m）的长度就是各链路长度之和，即d=ijjklm。p 最短路径问题最短路径问题就是寻找从i到m的最小长度方向性路径。p 根据长度的不同定义，寻找最
19、短路径的算法有不同的含义。第5章 路由算法 30 2014/11/245.3 数学基础数学基础图论图论(4)连通连通：对于无方向图，若节点u、v之间存在一条路径（链路），则称u和v是连通的。p 若图G中的任意两个节点都是连通的，则称图是图是连通连通的，否则就是非连通的图非连通的图。非联通的图可分解为若干连通的子图。第5章 路由算法 31 2014/11/245.3 数学基础数学基础图论图论(5)连通的方向图：连通的方向图：对于方向图，去掉方向之后该图是连通的。强连通方向图：强连通方向图：对于方向图的任意两个顶点u和v之间存在u到v的路径和v到u的路径时，称该图为强连通的。连通的方向图强连通的方
20、向图第5章 路由算法 32 2014/11/24第第5章章 内容概述内容概述 5.1 路由算法概述路由算法概述 5.2 常用的路由算法常用的路由算法 5.4 数学基础数学基础图论图论 5.5 最短路径算法最短路径算法 第5章 路由算法 33 2014/11/245.4 最短路径算法最短路径算法 讨论三种标准的集中式最短路径算法集中式最短路径算法：*Bellman-Ford算法（B-F算法）*Dijkstra算法*Floyd-Warshall算法 Bellman-Ford算法和Dijkstra算法是点对多点点对多点的最短路径算法 Floyd-Warshall算法则是多点对多点的最短路径 算法。第
21、5章 路由算法 34 2014/11/245.4 最短路径算法最短路径算法 B-F算法算法 典型的Bellman-Ford算法（简记为B-F算法）是一种集集中式中式的点到多点点到多点的路由算法，即寻找网络中一个节点一个节点到其它所有节点其它所有节点的路由。假定节点1是“目的节点”，我们要寻找网络中其它所有的节点到目的节点1的最短路径最短路径。用dij表示节点 i 到节点 j 的长度；如果(i,j)不是图中的链路，则dij=。最短行走长度用 表示。hiD第5章 路由算法 35 2014/11/245.4 最短路径算法最短路径算法 B-F算法算法 从从h步步Walk中寻找最短路由的算法：中寻找最短
22、路由的算法：p 第一步：初始化。即对所有i(i1)，令 =。p 第二步：对所有的节点 j（ji），先找出一条链路的最短（h1）的Walk长度；p 第三步：对所有的节点 j（j i），再找出两条链路的最短（h2）的Walk长度；p 依次类推：如果对所有i有：（即继续迭代下去以后不会再有变化），则算法在h次迭代后结束。1hhiiDD0iD例 5.2第5章 路由算法 36 2014/11/245.4 最短路径算法最短路径算法Dijkstra算法算法 Dijkstra算法算法也是一种典型的点到多点点到多点的路由算法，即寻找网络中一个节点一个节点到其它所有节点其它所有节点的路由。算法的基本思想是按照路径
23、长度增加的顺序来寻找最短路径。（也即是通过逐步标定到达目的节点路径长度的方法来求解最短的路径）。设每个节点i标定的到达目的节点1的最短路径长度估计为Di。如果在迭代的过程中，Di已变成一个确定的值，称节点i为永久标定的节点，这些永久标定的节点标定的节点的集合用P表示。第5章 路由算法 37 2014/11/245.4 最短路径算法最短路径算法Dijkstra算法算法 Dijkstra算法描述如下：p 初始化，即P=1,D1=0，Dj=dj1,j1。p 寻找下一个与目的节点最近的节点最近的节点，即求使下式成立的i，i P 置P=P U i。如P包括了所有的节点，则算法结束。p 更改标定值，即对所有的 j P，置 返回上步。例 5.3第5章 路由算法 38 2014/11/245.4 最短路径算法最短路径算法Dijkstra算法算法 Dijkstra算法的关键之处：p 在算法的每一步中，选择P以外的节点，选择与目的节点最近的节点加入到集合P中。p 各条链路根据实际情况可以反复考虑。
