高级计算机网络技术之路由选择技术概要ppt课件.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,路由选择技术,,一、互连网,概念,一个大型网络通常由多个子网互连而成，这种网络称为互连网，连接子网的网络设备称为路由器,,在网络体系结构中，网络互连功能由网络层定义的，网络层的功能定义是建立在互连网模型上,,,在互连网模型中，有两类节点：端节点,(,主机,),和中间节点,(,路由器,),，端到端的数据传输要经过中间节点的转发,,中间节点不关心数据内容,,,而是提供存储转发、路由选择、拥塞控制等功能,,,通过选择适当路径将数据传送到目的端,,中间节点比端节点复杂得多，很多功能是针对中间节点定义的，如路由选择、拥塞控制等,,二、,路由选择算法,,路由选择和拥塞控制是中间节点,(,路由器或交换机,),必备的两大重要功能,,在选择路由时,,,每个路由器都采用适当的路由选择算法支持路由选择,,,并维持一个路由表来记录有关路由信息,,,如端节点地址与线路,(,端口,),对应关系、路由开销等,,在转发分组时,,,路由器将根据分组的目的地址查找路由表获取有关路由信息,,,并采用某种路由选择算法计算最佳路由,,,然后按该路由转发分组,,路由选择的质量关键在于路由选择算法。

路由选择算法有很多种,,,大致可分成静态算法和动态算法两大类,1.,静态路由选择算法,静态路由选择算法是指采用某种路由选择算法预先计算出每个路由器的路由表，在路由器加电启动时加载到路由器中,,在路由器工作过程中，路由表内容保持不变如果网络拓扑结构或其它网络参数发生变化，则必须重新计算各个路由器的路由表，并重新加载到路由器中,,这种路由选择算法也称固定路由选择算法,,,常用的算法有最短路径,(Shortest Path, SP),选择和基于流量的路由选择,(Flow-based Routing, FR),等,(1) SP,算法,在,SP,算法中，根据网络拓扑结构将一个通信网络表示成一个加权无向图，图中每个节点代表网络中的路由器，连线代表通信线路，连线上标注的数字代表线路的权值,,权值可用线路长度、信道带宽、平均通信量、通信费用、队列长度、线路延时及占用可用资源数量等加权函数来计算,,SP,算法是根据线路的加权值寻找出最短路径,,,它是一个逐步搜索过程,,,其搜索过程如下：,,假如在第,m,步已经搜索到一个最短路径，该路径上有,n,个距离源节点最近的节点，它们构成了一个节点集合,N,,在第,m+1,步，继续搜索不属于,N,的距离源节点最近的节点，并搜索到的节点加入到,N,中,,继续搜索，直至到达目的节点，,N,中的节点集合便是从源节点到目的节点的最短路径,,在搜索过程中,,,每个节点用源节点沿已知的最短路径到本节点的距离来标注，例如，在,B(2,A),标注中，,B,表示本节点名，,2,表示在最短路径上源节点到本节点的距离,(,权值累加,),，,A,表示最短路径上的上游节点名,,在初始时，由于最短路径是未知的，故所有节点都标注为无穷大,(∞),,随着算法的进展和不断搜索到最短路径，节点的标注值也随之改变，反映出一个较好的路径,,将该算法应用于上图,，,假设搜索从,A,到,G,的最短路径，其搜索过程如下表,,每个路由器按,SP,算法计算出节点间最短路径,,,形成路由表,,,在路由器启动时加载到路由器中,,在路由器工作过程中,,,根据数据分组中的目的地址查找路由表,,,找出最短路径来转发数据分组,,SP,算法只是根据网络拓扑结构计算最短路径，没有考虑通信流量或负载,,在一些网络中,,,节点之间通信量是相对稳定和可预测的。

在预算出节点之间平均通信量的条件下,,,采用适当算法对通信量建模分析,,,可以优化路由选择,,FR,算法是基于这种思想提出的,,,主要考虑了网络拓扑结构和通信量两方面因素来选择路由FR,算法的前提条件是：,,必须知道网络拓扑结构、节点间平均通信量和各条线路容量,,采用适当的路由选择算法,(2) FR,算法,,FR,算法的基本原理是：,,对于一个给定的线路，如果知道该线路容量和平均流量，则可以用队列理论计算出该线路的平均分组延迟,,由所有线路的平均延迟可直接计算出流量加权平均值，从而得到整个网络的平均分组延迟,,路由选择问题可归结为如何找出产生网络延迟最小的路由选择算法，该算法便是最好的路由选择算法,,,所计算出的路径就是最佳路由,,以上图为例，假设预先得到该网络有关参数：网络拓扑结构、各条线路的平均流量,F(,分组,/s),和线路容量,C(,分组,/s),，计算出各条线路的平均延迟时间和权值,,编写不同的路由选择算法程序，确定哪种算法求得的网络平均延迟时间最小，该算法便是最好的路由选择算法，所计算出的路径就是最佳路由,,例如，,A,到,G,有,8,个可选的路径，每个路径的网络平均延迟时间分别为：,,,(1) ABCDFG=57ms (2) ABDFG=38ms,,(3) ABCDEF=66ms (4) ABDEF=46ms,,(5) ACDEG=48ms (6) ACDFG=40ms,,(7)ACBDEG=52ms (8) ACBDFG=43ms,,,其中，路径,(2),的平均延迟时间最小,(38ms),，,该路径即是最佳路由,,由于这些计算是预先脱机进行的，可以不考虑计算开销和费时问题,,2.,动态路由选择算法,网络拓扑和通信量是动态变化的,,,如路由器的加入或退出,,,网络发生拥挤或阻塞等,,如果路由器能及时获得这些网络动态变化情况,,,并以此作为路由选择依据，则会有助于路由器优化路由选择,,动态路由选择算法就是采用这一机理来路由选择的，也称自适应路由选择算法,,现代计算机网络系统通常采用动态路由选择算法,,,常用的动态路由选择算法有距离矢量路由选择,(Distance Vector Routing, DVR),和链路状态路由选择,(Line State Routing, LSR),等算法,(1) DVR,算法,,DVR,算法最初应用于,ARPANET,中，后被其它网络系统所采用，著名的,RIP (Routing Information Protocol),协议就是基于该算法,,DVR,算法的基本原理是每个路由器都维护一个路由表，表中记录有通向目的节点的最佳距离和线路,,每个路由器都要与相邻的路由器交换路由信息来更新路由表，使路由表中的信息总是反映网络最新的动态变化情况,,在路由表中,,,每个表项包含两部分内容：,,通往目的节点的输出线路,,到达目的节点的距离或所需时间估算值，估算值度量可以是节点数、时间延迟估算值、该路由的队列长度等,,路由器要选择一种度量标准来估算本节点与目的节点之间的距离：,,如果选择,节点数,，则一个距离长度为一个节点,,如果选择,队列长度,，则路由器检查每个队列,,如果选择时间延迟，则路由器可以通过向相邻路由器发送一个特殊的回应,(Echo),分组请求对方回送带有时间标记的分组来获得时间延迟值,,在一个网络系统中,,,每个路由器都按约定采用某种度量标准来估算它到达目的节点的距离,,,并通知相邻路由器；同时,,,它也会从相邻路由器中得到类似估算值,,,并以此更新路由表,,这样，路由器就可以从路由表上这些估算值中找出最佳值，该估算值对应的输出线路便是最佳路由，并选择该路由转发数据分组,,DVR,算法存在两个主要缺陷：一是在选择路由时没有考虑线路带宽，而线路带宽可能在不断地提高；二是在获取路由信息时要耗费很多时间,(2) LSR,算法,LSR,算法被广泛应用于现代网络系统中，著名的,OSPF(Open Shortest Path First),路由协议采用的就是,LSR,算法,,,而,OSPF,协议广泛应用于,Internet,中,,每个路由器上的,LSR,算法都要执行如下过程：,,① 发现相邻路由器，获取其网络地址：,,当一个路由器加入到网络后,,,首先向每个相邻路由器发送一个特殊的,Hello,分组,,,目的是声明它的存在,,各个相邻路由器接收到,Hello,分组后,,,都必须回应一个包含本路由器地址的响应分组,,每个路由器地址是全局惟一的地址,,②测量到各个相邻路由器的时间延迟或线路开销：,,一个路由器可通过发送,Echo,分组来测量到各个相邻路由器的延迟,,从发送,Echo,分组开始到接收到响应分组所经历时间除以,2,，便是该线路的延迟时间估算值,,它反映了线路带宽状况，线路带宽越大，延迟时间越小；反之，线路带宽越小，延迟时间越大,,③ 将测量值通告给其它的路由器：,,路由器在获得有关路由器和链路状态信息后,,,构造一个链路状态,(LS),分组来发布链路状态信息,,LS,分组包含有发送者地址、序号、生存期以及各个相邻路由器地址和对应的延迟时间估算值等信息,,LS,分组可以周期性地发送,,,也可以在网络发生重大事件时发送,,,采用如下的传递机制：,,路由器周期地向所有的线路广播,LS,分组，每发送一个新的,LS,分组，分组序号加,1,,相邻路由器接收到,LS,分组后，通过核对发送者地址和序号来判断,LS,分组是否是重复的或过时的,,如果是新的,LS,分组，则在路由表中记录新的链路状态信息，并向除输入线路之外的所有线路扩散，传播给其它的路由器；如果是重复的或过时的,LS,分组，则丢弃该分组,,为了避免序号冲突问题，序号采用较长位数，如,32,位，序号以,2,32,为模，循环周期为,2,32,,链路状态信息以软状态方式保存在路由器中,,,路由器定期地,(,如每隔,1,秒钟,),检查它所记录的,LS,分组的生存期,,,并减,1,。

如果一个,LS,分组的生存期减至,0,,则删除来自该,LS,分组的链路状态信息,,这样就避免了无效或出错的链路状态信息长期占据路由器的存储空间,,一个路由器所测量的链路状态信息通过上述传递机制发布给网络中所有的路由器每个路由器用接收到的,LS,分组来建立和更新其路由表,,④ 计算网络最短路径：,,各个路由器在建立路由表后，可采用适当的路由选择算法计算到达目的节点的最短路径，并按该路径转发数据分组,,,三、,路由协议,路由器的主要功能是为转发数据而选择适当的路由在动态路由选择算法中,,,路由器通过与相邻节点周期地交换路由信息来更新和维护路由表,,,交换路由信息所使用的协议就是路由协议,,路由协议有,ISO,路由协议和,Internet,路由协议等，,ISO,路由协议主要定义了一种路由框架结构和参考模型,,,而实际中主要应用,Internet,路由协议,,Internet,是一个全球性互连网络，由大量自治网络系统,(AS),互连而成在,AS,内部和,AS,之间都有各自的路由选择算法，并且采用统一的标准协议来交换路由信息,,AS,内部的路由选择算法称为内部网关协议,(IGP),，,AS,之间的路由选择算法称为外部网关协议,(EGP),,1.,内部网关协议,最初的,IGP,采用的是基于,SP,算法的,RIP,协议，随着,AS,的增大，,RIP,协议存在着路由计算收敛很慢等缺陷，后来被基于,LSR,算法的最短路径优先,(OSPF),协议所取代,,OSPF,协议是由,IETF,制定的开放的内部网关协议标准。

现在，很多的路由器都支持,OSPF,协议,,OSPF,支持三种网络连接：两个路由器之间的点到点线路；,LAN,链路,；,基于分组交换的,WAN,,OSPF,将一个,AS,分成若干区域,,,区域是子网的一般化表示从区域外部看，区域内部的拓扑结构和实现细节是不可见的,,各个区域之间不会重叠,,,每个,AS,都有一个主干区域；命名为区域,0,，所有的区域都要与主干区域相连；区域之间都要通过主干区域交换信息,,在同一区域内部,,,每个路由器都要有相同的链路状态数据库,,,并运行相同最短路径算法,,,计算本区域的最短路径,,连接两个区域的路由器要有两个区域的链路状态数据库,,,并在各自的区域上分别使用最短路径算法计算最短路径,,OSPF,要区分,4,种路由器：区域内部路由器、区域边界路由器、主干路由器和,AS,边界路由器其中有些部分是重叠的,,,如所有边界路由器都是主干区域一部分,,OSPF,定义了,5,种消息用于路由器交换路由信息：,,Hello,消息当一个路由器启动后,,,要向它所有连接的线路发送,Hello,消息相邻路由器对,Hello,消息进行应答,,,这样新加入路由器就可知道它的邻居,,Link state update,消息。

每个路由器都要定期地向相邻路由器发布,Link state update,消息，该消息中包含路由器链路状态、所使用的权值和序号,,,相邻路由器根据消息的序号可以判别一个消息的新旧当网络拓扑结构或权值发生变化时，路由器也都发布,Link state update,消息,,Link state,ack,消息当路由器接收到,Link state update,消息后，要使用,Link state,ack,消息进行确认,,Link state request,消息每个相邻路由器对之间可相互发送,Link state request,消息,,,以获取相应的链路状态,,当路由器接收到,Link state request,消息后，使用,Database description,消息进行应答这样，新的链路状态信息便可以在一个区域扩散开,,Database description,消息它是对,Link state request,消息的应答，给出发送者所拥有的所有链路状态序号,,在一个区域内，每个路由器利用上述路由消息传递机制来获取最新的链路状态信息，并从中计算出最短路径,,主干路由器可以从区域边界路由器处获取链路状态信息，计算出主干区域到每个区域的最短路径,,经过区域边界路由器的传递，这个消息便在一个区域内传播开,,这样，路由器可以利用该消息中的链路状态信息进行区域间寻径，从主干区域选择一个最佳的出口路由器,,OSPF,协议较好解决了,AS,内部的路由选择问题，被推荐在,Internet,中使用,,EGP,用于,AS,之间的路由选择。

EGP,与,IGP,的侧重点有所不同,, IGP,侧重的是如何高效地选择路由来转发分组，,EGP,主要侧重路由策略问题,,所谓路由策略是指从政治、安全和经济等方面因素来考虑路由选择问题例如，敏感的数据不能经过某些,AS,传送；如果没有可选的路由，则只能经过缺省的,AS,等都可认为路由策略,2.,外部网关协议,,常用的,EGP,是边界网关协议,(BGP),按,BGP,的观点,,,全球网络是由,BGP,路由器互连而成的，,BGP,路由器之间采用面向连接的传输层协议,(,如,TCP,协议,),进行通信,,,既保证了通信的可靠性,,,又隐藏了所经网络的拓扑结构和细节,,BGP,采用距离矢量路由选择法,,,但有别于,RIP,协议所采用的算法每个,BGP,路由器要记录所使用的确切路由,,,并定期向相邻,BGP,路由器广播确切路由,,,拥塞控制算法,,网络拥塞现象是由于网络流量或交通量超过网络信道额定容量引起的，致使网络的吞吐能力急剧下降,,网络信道容量通常是按照能满足传输需求的平均水平设计的如果网络浪涌交通量大大超过这个平均水平，则可能引起网络拥塞现象,一、拥塞控制基本概念,,拥塞控制与流量控制不同，拥塞控制主要用于保证网络通畅地传送报文，涉及网络中所有与之相关的主机和路由器的发送和转发行为，是全局控制措施,,流量控制只涉及发送端和接收端之间点到点的流量控制行为，主要用于保证发送端的发送速率与接收端的缓冲区容量相匹配，以防止在接收端缓冲区不足时发生报文丢失现象,,引起拥塞的原因可能是多方面的，如接收节点的缓冲区溢出、线路拥挤以及带宽不足等,,当发生网络拥塞现象时，必须通过适当的拥塞控制措施来疏导网络交通。

拥塞控制算法大致可分成两大类：,,,(1),开环控制,,,(2),闭环控制,,开环控制算法是通过良好的网络系统设计来避免拥塞问题的发生,,,在网络运行过程中,,,何时接受新报文,,,何时丢弃报文以及丢弃哪些报文都是事先规划好的,,,并不考虑当前的网络流量状况,,闭环控制算法通过反馈机制来调整当前网络流量,,,使网络流量与网络可用资源相协调,,,能有效解决网络拥塞问题,,由于闭环控制算法能根据当前网络状况对流量进行动态控制,,,具有较高效率,,闭环控制算法的关键技术是：,,能随时发现拥塞问题的检查机制,,能将发生拥塞的信息传送到适当控制点的反馈机制,,能通过调整系统操作来排除拥塞问题的调整机制,,检查机制将根据当前网络状况来监视网络是否发生了拥塞，判断的依据或基准参数主要有：因缺少缓冲区空间而丢弃的报文数量、平均报文队列长度、超时重发报文的数量、平均报文延迟时间等如果基准参数超过临界值，则意味着发生了网络拥塞,,反馈机制将发生拥塞的信息从检查点传送到控制点,,反馈方式有显式反馈和隐式反馈两种：,,显式反馈由检查点向控制点反馈一个警告消息来通告网络已发生了拥塞,,隐式反馈由控制点,(,源端,),通过观察应答报文返回所用时间进行推断来判断网络是否发生了拥塞,,调整机制是通过检查点和控制点相互协作来共同解决拥塞问题,,控制点通过降低载荷,(,即降低报文发送速率,),来缓解拥塞,,检查点通过载荷脱落,(,即丢弃某些报文,),来疏导交通，或者通过增加系统资源,(,如增加附加线路或提高线路带宽,),来提高流量通过能力,,在拥塞控制算法中，根据数据交换方式,(,虚电路或数据报,),的不同，采用不同的控制策略,,二、面向虚电路的拥塞控制算法,虚电路交换采用开环控制策略,,,首先由发送者通过中间的路由器节点与接收者建立一条虚连接,,在建立连接时，其建立连接请求报文中包含了用于说明发送者传输模式的流说明信息，如最大分组长度、最大传输速率以及其它说明等,,报文经过各个路由器时,,,路由器要记录流说明信息,,,接收者则要根据流说明信息来确定它所能接受的流量传输模式,,,然后通过应答报文传送给发送者,,应答报文经过各个路由器时,,,对路由器记录的发送者流说明信息进行确认,,因此，在建立连接的同时，发送者、路由器和接收者可以协商该连接的流量传输模式,,,并最终达成一致的传输模式,,面向虚电路的拥塞控制算法模型,,在数据传输过程中，路由器将为协商好的传输模式保留系统资源,(,如缓冲区等,),，并对该连接上的交通进行整形,,交通整形是指通过调整数据传输的平均速率，使数据按照传输模式规定的速率进行传输，尽量避免突发性增大通信量，导致产生拥塞问题,,交通整形主要采用两种算法：漏桶算法和令牌桶算法,,漏桶,算法,漏桶算法是将交通整形操作比作一个底部带有一个小孔的水桶，不管流入桶中的水速多大，从小孔流出的水速是恒定的。

桶中无水，速率为,0,；桶中水满，水将从桶边溢出流掉,,漏桶算法实际上是一种具有恒定服务时间的单服务排队系统，相当于在路由器内部实现一个有限长度队列,,路由器将输入的报文排到队列尾部,,,并以恒定速率从队列中取出报文发送出去,,,一旦队列饱和，新来的报文将被丢弃,,主机系统也可采用该算法来整形分组的发送，将上层应用进程不均匀的数据流整形成均匀的报文流向网络发送，平滑了突发的数据流，大大减少了发生拥塞的机会,,漏桶算法模型,,单服务排队模型,,漏桶算法是以恒定速率输出，而令牌桶算法则允许一定量的突发数据流,,令牌桶算法以恒定速率产生令牌放入桶中,,,每发送一个报文都要获得和消耗一个令牌如果令牌消耗完,,,则新来的报文就要等待生成新令牌或被丢弃,,由于突发性输入流往往导致拥塞发生,,,如果将获得令牌的报文快速地输出,,,则会使突发的输入流得到迅速的疏导,令牌桶算法,,在令牌桶算法中,,,使用一个令牌计数器来计数令牌数量令牌计数器每隔,Δt,时间加,1,，表示新增加一个令牌；每发送一个报文，令牌计数器减,1,，表示已消耗一个令牌当计数器减至,0,时,,,表示令牌已消耗完,,,不能再发送报文了,,这两种交通整形算法既可用于平滑主机向网络发送分组的通信量,,,也可用于路由器之间的交通整形。

ATM,交换机和,RSVP,协议就是应用上述交通整形算法来解决网络拥塞问题的,,令牌桶算法模型,,数据报是无连接传输方式,,,主要采用闭环控制策略路由器一旦检测到系统可用资源,(,如线路利用率或队列长度,),超过临界值,,,就会向源主机发送一个抑制消息,,,警告网络可能发生拥塞,,源主机周期侦听抑制消息,,,如果收到了该消息,,,则逐步降低数据速率；如果没有收到抑制消息,,,则逐渐增加通信量,三、面向数据报的拥塞控制算法,,主机可以通过调整其发送操作的相关参数来减少通信量，如改变发送窗口尺寸或漏桶输出速率等,,路由器通常采用加权公平队列算法来处理报文排队，检测是否超过临界值，以及何时发送抑制消息,,在广域网环境下，完全采用由远程源主机减少通信量来缓解拥塞的方法并不很有效,,,因为距离远,,,反应慢一般采用逐段控制通信量的方法来解决,,逐段控制方法是抑制消息途经的各个路由器都要抑制通信量，使拥塞得到迅速控制同时要求路由器提供一定数量的缓冲区用于暂存过量的报文,,当抑制消息到达源主机后，由源主机采取措施最终才能使通信量降下来,,这种方法可以迅速控制拥塞，但路由器节点需要提供较大的缓冲区空间,,IP,协议采用该方法来解决网络拥塞问题,,当网络发生严重拥塞时，路由器往往采用载荷脱落,(Load Shedding),，,即丢弃报文的方法来疏导交通,,路由器通常采取某种策略来丢弃报文,,,如按,FIFO,规则丢弃后到的报文；按报文优先级规则丢弃优先级低的报文等。

被丢弃的报文要重新传输,,按报文优先级丢弃报文的方法被很多网络系统或协议所采用，如,ATM,网络、帧中继网络以及,IP,协议等,,面向数据报的拥塞控制算法模型,,思考题：,拥塞控制与流量控制有哪些不同？,,为什么说交通整形算法主要用于面向连接通信中？,,在无连接通信中，主要采用哪些拥塞控制方法？能使用交通整形算法吗？,,。