【文档说明】高级计算机网络技术之路由选择技术概要课件.ppt，共(66)页，1.757 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76921.html

以下为本文档部分文字说明：

路由选择技术一、互连网概念一个大型网络通常由多个子网互连而成，这种网络称为互连网，连接子网的网络设备称为路由器在网络体系结构中，网络互连功能由网络层定义的，网络层的功能定义是建立在互连网模型上在互连网模型中，有两类节点：端节点(主机)和中

间节点(路由器)，端到端的数据传输要经过中间节点的转发中间节点不关心数据内容,而是提供存储转发、路由选择、拥塞控制等功能,通过选择适当路径将数据传送到目的端中间节点比端节点复杂得多，很多功能是针对中间节点定义的，如路由选择、拥塞控制等二、路由选择算法路由选择和拥塞控制

是中间节点(路由器或交换机)必备的两大重要功能在选择路由时,每个路由器都采用适当的路由选择算法支持路由选择,并维持一个路由表来记录有关路由信息,如端节点地址与线路(端口)对应关系、路由开销等在转发分组时,路由器将根据分组的目的地址查找路由表获取

有关路由信息,并采用某种路由选择算法计算最佳路由,然后按该路由转发分组路由选择的质量关键在于路由选择算法。路由选择算法有很多种,大致可分成静态算法和动态算法两大类1.静态路由选择算法静态路由选择算法是指采用某种路由选择算

法预先计算出每个路由器的路由表，在路由器加电启动时加载到路由器中在路由器工作过程中，路由表内容保持不变。如果网络拓扑结构或其它网络参数发生变化，则必须重新计算各个路由器的路由表，并重新加载到路由器中这种路由选择算法也称固定路由选择算法,常用

的算法有最短路径(ShortestPath,SP)选择和基于流量的路由选择(Flow-basedRouting,FR)等(1)SP算法在SP算法中，根据网络拓扑结构将一个通信网络表示成一个加权无向图，图中

每个节点代表网络中的路由器，连线代表通信线路，连线上标注的数字代表线路的权值权值可用线路长度、信道带宽、平均通信量、通信费用、队列长度、线路延时及占用可用资源数量等加权函数来计算SP算法是根据线路的加权值寻找出最短路径,它是一个逐步搜索过程,其搜索过程如下：假如在第m步已经搜索到一

个最短路径，该路径上有n个距离源节点最近的节点，它们构成了一个节点集合N在第m+1步，继续搜索不属于N的距离源节点最近的节点，并搜索到的节点加入到N中继续搜索，直至到达目的节点，N中的节点集合便是从源节点到目的节点的最短路径在搜索过程中,每个节点用源节点沿已知的最

短路径到本节点的距离来标注，例如，在B(2,A)标注中，B表示本节点名，2表示在最短路径上源节点到本节点的距离(权值累加)，A表示最短路径上的上游节点名在初始时，由于最短路径是未知的，故所有节点都标注为无穷大(∞

)随着算法的进展和不断搜索到最短路径，节点的标注值也随之改变，反映出一个较好的路径将该算法应用于上图，假设搜索从A到G的最短路径，其搜索过程如下表每个路由器按SP算法计算出节点间最短路径,形成路由表,在路由器启动时加载到路由器中在路由器工作过程中,

根据数据分组中的目的地址查找路由表,找出最短路径来转发数据分组SP算法只是根据网络拓扑结构计算最短路径，没有考虑通信流量或负载在一些网络中,节点之间通信量是相对稳定和可预测的。在预算出节点之间平均通信量的条件下,采用适当算法对通信量建模分析,可以优化路由选择F

R算法是基于这种思想提出的,主要考虑了网络拓扑结构和通信量两方面因素来选择路由。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.动态路由选择算法网络拓扑和通信量是动态变化的,如路由器的加入或退出,网络发生拥挤或阻塞等如果路由器能及时

获得这些网络动态变化情况,并以此作为路由选择依据，则会有助于路由器优化路由选择动态路由选择算法就是采用这一机理来路由选择的，也称自适应路由选择算法现代计算机网络系统通常采用动态路由选择算法,常用的动态路由选择算法有

距离矢量路由选择(DistanceVectorRouting,DVR)和链路状态路由选择(LineStateRouting,LSR)等算法(1)DVR算法DVR算法最初应用于ARPANET中，后被其它网络系统所采用，著名的RIP(RoutingInformationProtocol)协议就是基于

该算法DVR算法的基本原理是每个路由器都维护一个路由表，表中记录有通向目的节点的最佳距离和线路每个路由器都要与相邻的路由器交换路由信息来更新路由表，使路由表中的信息总是反映网络最新的动态变化情况在路由表中,每个表项包含两部分内容：通往目的节点的输出线路到达目的节点的距离或所需时间估算

值，估算值度量可以是节点数、时间延迟估算值、该路由的队列长度等路由器要选择一种度量标准来估算本节点与目的节点之间的距离：如果选择节点数，则一个距离长度为一个节点如果选择队列长度，则路由器检查每个队列如果选择时间延迟，则路由器可以通过向相邻路由器发送一个特殊

的回应(Echo)分组请求对方回送带有时间标记的分组来获得时间延迟值在一个网络系统中,每个路由器都按约定采用某种度量标准来估算它到达目的节点的距离,并通知相邻路由器；同时,它也会从相邻路由器中得到类似估算值,并以此更新路由表这样，路由器就可以从路由表上这些估算

值中找出最佳值，该估算值对应的输出线路便是最佳路由，并选择该路由转发数据分组DVR算法存在两个主要缺陷：一是在选择路由时没有考虑线路带宽，而线路带宽可能在不断地提高；二是在获取路由信息时要耗费很多时间(2)LSR算法L

SR算法被广泛应用于现代网络系统中，著名的OSPF(OpenShortestPathFirst)路由协议采用的就是LSR算法,而OSPF协议广泛应用于Internet中每个路由器上的LSR算法都要执行如下过程：①发现相邻路由器，获取其网络地址：当一个路由器加入到网络后,首先向每

个相邻路由器发送一个特殊的Hello分组,目的是声明它的存在各个相邻路由器接收到Hello分组后,都必须回应一个包含本路由器地址的响应分组每个路由器地址是全局惟一的地址②测量到各个相邻路由器的时间延迟或线路开销：一个路由

器可通过发送Echo分组来测量到各个相邻路由器的延迟从发送Echo分组开始到接收到响应分组所经历时间除以2，便是该线路的延迟时间估算值它反映了线路带宽状况，线路带宽越大，延迟时间越小；反之，线路带宽

越小，延迟时间越大③将测量值通告给其它的路由器：路由器在获得有关路由器和链路状态信息后,构造一个链路状态(LS)分组来发布链路状态信息LS分组包含有发送者地址、序号、生存期以及各个相邻路由器地址和对应的延迟时间估算值等信息LS分组可以周期性地发送,也可以在网络发生重大事件时发送

,采用如下的传递机制：路由器周期地向所有的线路广播LS分组，每发送一个新的LS分组，分组序号加1相邻路由器接收到LS分组后，通过核对发送者地址和序号来判断LS分组是否是重复的或过时的如果是新的LS分组，则在路由表中记录新的链路状态信

息，并向除输入线路之外的所有线路扩散，传播给其它的路由器；如果是重复的或过时的LS分组，则丢弃该分组为了避免序号冲突问题，序号采用较长位数，如32位，序号以232为模，循环周期为232链路状态信息以软状态方式保存在路由器中,路由器定期地(如每隔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链路；基于分组交换的WANOS

PF将一个AS分成若干区域,区域是子网的一般化表示。从区域外部看，区域内部的拓扑结构和实现细节是不可见的各个区域之间不会重叠,每个AS都有一个主干区域；命名为区域0，所有的区域都要与主干区域相连；区域之间都要通过主干区域交换信息在同一区域内部,每个路

由器都要有相同的链路状态数据库,并运行相同最短路径算法,计算本区域的最短路径连接两个区域的路由器要有两个区域的链路状态数据库,并在各自的区域上分别使用最短路径算法计算最短路径OSPF要区分4种路由器：区域内部路由器、区域边界路由器、主干路由器和AS边界路

由器。其中有些部分是重叠的,如所有边界路由器都是主干区域一部分OSPF定义了5种消息用于路由器交换路由信息：Hello消息。当一个路由器启动后,要向它所有连接的线路发送Hello消息。相邻路由器对Hello消息进行应答,这样新

加入路由器就可知道它的邻居Linkstateupdate消息。每个路由器都要定期地向相邻路由器发布Linkstateupdate消息，该消息中包含路由器链路状态、所使用的权值和序号相邻路由器根据消息的序号可以判别一个消

息的新旧。当网络拓扑结构或权值发生变化时，路由器也都发布Linkstateupdate消息Linkstateack消息。当路由器接收到Linkstateupdate消息后，要使用Linkstateack

消息进行确认Linkstaterequest消息。每个相邻路由器对之间可相互发送Linkstaterequest消息,以获取相应的链路状态当路由器接收到Linkstaterequest消息后，使用Databasedescription消息进行应答。这样，新的链路状态信息便可以在一个区域扩

散开Databasedescription消息。它是对Linkstaterequest消息的应答，给出发送者所拥有的所有链路状态序号在一个区域内，每个路由器利用上述路由消息传递机制来获取最新的链路状态信息，并从中计算出最短路径主干路由器可以从

区域边界路由器处获取链路状态信息，计算出主干区域到每个区域的最短路径经过区域边界路由器的传递，这个消息便在一个区域内传播开这样，路由器可以利用该消息中的链路状态信息进行区域间寻径，从主干区域选择一个最佳的出口路由器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协议采用该方法来解决网络拥塞问题当网络发生严重拥塞时，路由器往往采用载荷脱落(LoadShedding)，即丢弃报文的方法来疏导交通路由器通常采取某种策略来丢弃报文

,如按FIFO规则丢弃后到的报文；按报文优先级规则丢弃优先级低的报文等。被丢弃的报文要重新传输按报文优先级丢弃报文的方法被很多网络系统或协议所采用，如ATM网络、帧中继网络以及IP协议等面向数据报的拥塞控制算法模型思考题：拥塞控制与流量控制有哪些不

同？为什么说交通整形算法主要用于面向连接通信中？在无连接通信中，主要采用哪些拥塞控制方法？能使用交通整形算法吗？