--路由算法详解课件

Klicken Sie,um das Titelformat zu,Klicken Sie,um die Formate des Vorlagentextes zu bearbeiten,Zweite Ebene,Dritte Ebene,Vierte Ebene,Fnfte Ebene,第,5,章 路由算法,*,2014/11/,24,第,5,章 路由算法,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,选择,136,节点,2,选择,256,则由于每条链路的业务量都只有信道容量的一半,因而时延很小。,如果节点,1,选择,146,节点,2,选择,246,则链路,46,运载的业务量为,10,单位,达到了链路的最大容量，因而时延会很大。,5.1,路由算法概述,(5),当,1,=5,2,=15,时,节点,2,的输入业务量为,15,个单位。由于每条链路的容量仅为,10,个单位，在仅使用一条路径的情况下，节点,2,至少要丢弃,5,个单位的业务流量。,如果节点,2,将输入业务流量在,246,和,256,之间分摊，节点,1,选择,136,，则每条链路上的业务流量都不超过链路容量的,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),路由算法的分类,算法能否跟随网络拓扑变化,非自适应的,（不根据实测或估计的网络当前业务量和拓扑结构来做路由选择。路由事先就计算好，在网络启动时就下载到网络路由器中。这种策略的最大优点是,简单,和,开销小,）,自适应,5.1.1,路由选择算法的分类,(2),路由算法的分类,按路由决策方法,集中式,（指网络的路由是由,路由控制中心,计算的，该中心周期性收集各链路的状态，经过路由计算后周期性地向各网络节点提供路由表。）,分布式,（指网络中所有节点通过相互交换路由信息，独立地计算到达各节点的路由。）,5.1.1,路由选择算法的分类,(3),路由算法的分类,按应用场合,广域网路由（解决一个子网内的路由）,互联网路由（解决不同子网之间的路由）,第,5,章 内容概述,5.1,路由算法概述,5.1.1,路由选择算法的分类,5.1.2,对路由选择算法的要求,5.1.3,路由算法的实现,路由表,5.2,常用的路由算法,5.4,数学基础,图论,5.5,最短路径算法,5.1.3,路由算法的实现,路由表,路由算法的实现通过,路由表,。,节点上的,路由表,指明该节点如何,选择分组的传送路径,。,节点,1,上的路由表,节点,4,上的路由表,目的节点,2,3,4,5,6,目的节点,1,2,3,5,6,下一个节点,2,2,4,4,2,下一个节点,1,2,3,5,5,路径选择,原则,是使到达目的节点的链路数最少。,当存在,2,条以上具有相同链路数的最少链路数路径时，可以选择其中任意一条。,路由表对每个目的节点指出分组应发向的下一个节点。,5.1.3,路由算法的实现,路由表,当路由表建立起来之后，在进行路由选择时只是简单地,查找,路由表中的信息，无须再作计算。然而对,自适应路由,选择来说，会要求,相当数量,的,计算,来,维持,这张,路由表,。,通常路由表中还会包含一些附加信息，例如基于最少链路数准则的算法可能包括,到达目的节点,的,估计链路数,，这样上表所示的路由表要修改为下表所示的形式。,目的节点,2,3,4,5,6,下一个节点,2,2,4,4,2,链路数,1,2,1,2,3,包含最少链路数的节点,1,上的路由表,第,5,章 内容概述,5.1,路由算法概述,5.2,常用的路由算法,5.4,数学基础,图论,5.5,最短路径算法,5.2,常用的路由算法,(1),不同的应用场合对路由算法有不同的要求。,广域网,内的路由主要解决,子网内分组的传输路径问题,，它主要包括三种路由算法：,广播,最短路由,最佳路由,互连网,解决不同子网之间的路由，采用的设备有网关和路由器等。,Ad Hoc,网络,Ad Hoc,网络，它是一种分布式的,PRNET,网络，该网络中使用了多种形式的路由算法。,5.2,常用的路由算法,(2),广播中的路由算法,(1),广播是通信网中最常用的方式，用来传播公共信息、拓扑变化信息（包括节点和链路工作变化和故障等信息）。,广播分组的接收节点通常是全网所有成员。如果接收节点为一个组或部分网络节点，则称为,多播,（,Multicast,）。,5.2,常用的路由算法,(3),广播中的路由算法,(2),可以逐一地把要广播的分组按照,点对点的路由算法,（,Unicast,）发送给每一个目的节点，但这种方法可,能会浪费大量的网络资源，并且广播节点需要知道,全网所有节点的路由信息。,广播时采用的路由算法可以有多种方法：如,泛洪,（,Flooding,）路由、采用,生成树,（,Spanning Tree,）的广播方式等。,5.2,常用的路由算法,(4),广域网,内的路由主要解决,子网内分组的传输路径问题,，它主要包括三种路由算法：,广播,最短路由,最佳路由,互连网,解决不同子网之间的路由，采用的设备有网关和路由器等。,Ad Hoc,网络,Ad Hoc,网络，它是一种分布式的,PRNET,网络，该网络中使用了多种形式的路由算法。,5.2,常用的路由算法,(5),最短路由（,Shortest Path Routing,）,(1),许多实际的路由算法如,RIP,（,Routing Information Protocol,），,OSPF,（,Open Shortest Path First,）等都是基于最短路径这一概念。,分组交换网络的各种路由算法,实质,上都是建立在,某种形式的最小费用准则,的基础上。,譬如，我们把准则定为“最短路径”，那就有“最短路径路由算法”；,注意：这里所说的“最短路径”并不单纯意味着一条物理长度最短的通路，它可以是从,发送节点,到达,接收节点,的,中转次数最少,。,5.2,常用的路由算法,(6),最短路由（,Shortest Path Routing,）,(2),最短路由关心,一个节点对,之间的一条路径的选择和求解，因而有两个方面的缺陷：,为每对节点之间仅提供一条路由，因而限制了网络的通过量；,适应业务变化的能力受到防止路由振荡的限制。,5.2,常用的路由算法,(7),广域网,内的路由主要解决,子网内分组的传输路径问题,，它主要包括三种路由算法：,广播,最短路由,最佳路由,互连网,解决不同子网之间的路由，采用的设备有网关和路由器等。,Ad Hoc,网络,Ad Hoc,网络，它是一种分布式的,PRNET,网络，该网络中使用了多种形式的路由算法。,5.2,常用的路由算法,(8),最佳路由（,Optimal Routing,）,(1),最佳路由是从,全网,的范围寻找,所有可能,的传输,路径,，从而使得发送节点到达接收节点的信息流的,时延最小,、,流量最大,，而不是局限于一条所谓的最短路径。,采用最佳路由（基于平均时延最佳化）可以克服最短路径的上述缺陷，它可以将节点对之间的流量分配在多条路径上，从而可使网络的通过量最大，时延最小。,第,5,章 内容概述,5.1,路由算法概述,5.2,常用的路由算法,5.4,数学基础,图论,5.5,最短路径算法,5.3,数学基础,图论,(1),每一个,网络,都可以抽象成一个,图,。一个图,G,由一个非空的,节点集合,N,和节点间的,链路,A,组成，即,G=(V,E),。,有方向,/,无方向,如果节点,i,和,j,之间仅有,i j,的链路，则称该链路是,有方向的,（或,单向链路,）。,如果节点,i,和,j,之间同时有,i j,及,j i,的链路，则称该链路是,无方向的,（或,双向链路,）。,5.3,数学基础,图论,(2),方向图：当图,G,中的每一条边都有规定方向，则称该图为,有向图,（,方向图,）；对应的,无方向图,G=(N,，,A),。,关联（,Incident,）：它表示链路与节点的关系。在方向图中，,链路,用,关联的节点,来表示，若,A1=(1,2),，则表示链路,A1,关联的两个节点是,1,（起点）和,2,（终点）。,注意：这里讨论的图不允许任何链路关联的两个节点相同，即,不允许,有一条,自环的链路,。,5.3,数学基础,图论,(3),路径,：由一些节点的序列组成，例如,u=,（,n,1,n,2,n,3,n,k,）称为一条路径，也称为,方向性行走,（,walk,）。,给定每条,链路（,i,j,）指定一个实数,d,ij,作为其长度，则一条方向性路径,p=,（,i,j,k,l,m,）的长度就是各链路长度之和，即,d=,d,ij,+,d,jk,+,d,lm,。,最短路径问题,就是寻找从,i,到,m,的最小长度方向性路径。,根据长度的不同定义，寻找最短路径的算法有不同的含义。,5.3,数学基础,图论,(4),连通,：对于无方向图，若节点,u,、,v,之间存在一条路径（链路），则称,u,和,v,是连通的。,若,图,G,中的任意两个节点都是连通的，则称,图是连通,的，否则就是,非连通的图,。非联通的图可分解为若干连通的子图。,5.3,数学基础,图论,(5),连通的方向图：,对于方向图，去掉方向之后该图是连通的。,强连通方向图：,对于方向图的任意两个顶点,u,和,v,之间存在,u,到,v,的路径和,v,到,u,的路径时，称该图为强连通的。,连通的方向图,强连通的方向图,第,5,章 内容概述,5.1,路由算法概述,5.2,常用的路由算法,5.4,数学基础,图论,5.5,最短路径算法,5.4,最短路径算法,讨论三种标准的,集中式最短路径算法,：,Bellman-Ford,算法（,B-F,算法）,Dijkstra,算法,Floyd-,Wars