计算机网络 第五章网络层

《计算机网络 第五章网络层》由会员分享，可在线阅读，更多相关《计算机网络 第五章网络层（85页珍藏版）》请在金锄头文库上搜索。

1、第五章第五章 网络层网络层网络层设计的有关问题网络层设计的有关问题路由选择算法路由选择算法拥塞控制算法拥塞控制算法网络互联网络互联因特网上的网络层因特网上的网络层网络层网络层端到端数据传输的最低层端到端数据传输的最低层网络层负责把源计算机发出的信息分组经过适网络层负责把源计算机发出的信息分组经过适当的路径送到目的计算机。当的路径送到目的计算机。网络层需要了解通信子网的拓扑结构，选择合网络层需要了解通信子网的拓扑结构，选择合适的传输路径。适的传输路径。网络层要预防和控制通信子网中超量的信息分网络层要预防和控制通信子网中超量的信息分组造成的拥塞。组造成的拥塞。网络层还要处理不同网络中源端和目的端之

2、间网络层还要处理不同网络中源端和目的端之间的差异。的差异。5.1 网络层设计的有关问题网络层设计的有关问题对网络层所提供的服务存在着两种观点：对网络层所提供的服务存在着两种观点：面向连接的服务，复杂的功能放在通信子网中。面向连接的服务，复杂的功能放在通信子网中。无连接服务，复杂的功能放在两端主机中。无连接服务，复杂的功能放在两端主机中。网络层的内部结构网络层的内部结构网络层提供的服务是否可靠与有无连接并没有关系。理论网络层提供的服务是否可靠与有无连接并没有关系。理论上存在四种组合，但最重要的只是其中的两种组合：上存在四种组合，但最重要的只是其中的两种组合：可靠的面向连接服务。可靠的面向连接服务

3、。不可靠的无连接服务。不可靠的无连接服务。针对两种服务，网络层有两种不同的工作方式：针对两种服务，网络层有两种不同的工作方式：虚电路（虚电路（virtual circuit）方式方式。当建立连接时，从信源。当建立连接时，从信源到信宿的路由就作为连接建立的一部分加以保存，此路到信宿的路由就作为连接建立的一部分加以保存，此路由用于传输连接上的所有数据，当释放连接时，虚电路由用于传输连接上的所有数据，当释放连接时，虚电路也随之撤消。也随之撤消。数据报（数据报（datagrams）方式方式。不预先选择路由，发出的。不预先选择路由，发出的每个分组所选择的路由独立于其前面发出的分组，后续每个分组所选择的路

4、由独立于其前面发出的分组，后续的分组可以走不同的路由，比虚电路方式更健壮，更容的分组可以走不同的路由，比虚电路方式更健壮，更容易处理传送失败和拥塞。易处理传送失败和拥塞。虚电路与数据报的比较虚电路与数据报的比较容易，如果能为每个VC预分配足够的缓冲空间困难拥塞控制所有经过失效路由器的VC都将终止除了崩溃时丢失的分组外毫无影响路由器失效的影响VC建立时选定路由，所有分组跟随这个路由每个分组独立路由路由选择每个VC占用子网表空间子网不保存状态信息状态信息每个分组包含一个短的VC号每个分组包含完整的源和目的地址地址必须的不需要电路设置VC子网子网数据报子网数据报子网观点观点5.2 路由选择算法路由选

5、择算法路由选择是网络层的主要功能，负责为分组选择合适的转发路径。路由选择是网络层的主要功能，负责为分组选择合适的转发路径。路由选择算法应具有以下几种特征：正确性（路由选择算法应具有以下几种特征：正确性（correctness）、）、简单性简单性（simplicity）、）、健壮性（健壮性（robustness）、）、稳定性（稳定性（stability）、）、公平性公平性（fairness）和最优性（和最优性（optimality）。）。一个好的路由选择算法是兼顾某几种重要的性能指标。一个好的路由选择算法是兼顾某几种重要的性能指标。公平性与最优公平性与最优性之间的矛盾性之间的矛盾路由选择算法的分

6、类路由选择算法的分类分为两大类：分为两大类：非自适应算法非自适应算法（non-adaptive algorithm）：）：也叫也叫静态路由选静态路由选择择（static routing），），预先离线计算好路由表，在网络启动时预先离线计算好路由表，在网络启动时装入到路由器中，在网络运行过程中不会根据网络流量和拓装入到路由器中，在网络运行过程中不会根据网络流量和拓扑结构的变化而改变。简单。扑结构的变化而改变。简单。自适应算法自适应算法（adaptive algorithm）：）：也叫也叫动态路由选择动态路由选择（dynamic routing），），根据当前网络流量和拓扑结构的变化，根据当前网络

7、流量和拓扑结构的变化，动态在线地计算网络的路由。复杂、健壮，网络负担重。动态在线地计算网络的路由。复杂、健壮，网络负担重。最佳原理和接收树最佳原理和接收树当计算两点之间的最佳路由时，存在一个当计算两点之间的最佳路由时，存在一个最佳原理最佳原理（optimality principle）：）：如果如果J位于位于I到到K的最佳路由上，则的最佳路由上，则J到到K的最佳路由也必定落的最佳路由也必定落在该路由上。可通过反证求得。在该路由上。可通过反证求得。根据最佳原理可以推出，所有源节点到一个给定目的节点的最佳路由的根据最佳原理可以推出，所有源节点到一个给定目的节点的最佳路由的集合组成一棵以该目的节点为

8、根的树，称为该目的节点的集合组成一棵以该目的节点为根的树，称为该目的节点的接收树接收树（sink tree）。）。接收树并不是唯一的。所有的路由算法都是要试图找出各个目的接收树并不是唯一的。所有的路由算法都是要试图找出各个目的节点的接收树，并利用这些接收树来转发数据。节点的接收树，并利用这些接收树来转发数据。最短通路路由选择算法最短通路路由选择算法最短通路（最短通路（shortest path）路由选择算法属于自适应路由算法。路由选择算法属于自适应路由算法。它将一个通信子网抽象成一张它将一个通信子网抽象成一张图图，图中的，图中的顶点顶点代表网络节点（路代表网络节点（路由器），由器），弧线弧线代

9、表通信线路，弧线上的代表通信线路，弧线上的权权代表相邻顶点间的代表相邻顶点间的“距距离离”（可为物理上的距离，或指分组在其间的传输时间，也可指（可为物理上的距离，或指分组在其间的传输时间，也可指线路上的通信费用等）。任意一对顶点之间的最小权值即为它们线路上的通信费用等）。任意一对顶点之间的最小权值即为它们的最短通路。的最短通路。求任意一对顶点之间的最短通路可有很多方法，其中求任意一对顶点之间的最短通路可有很多方法，其中迪杰斯特拉迪杰斯特拉（Dijkstra）提出了按通路长度递增的次序产生最短通路的算法，提出了按通路长度递增的次序产生最短通路的算法，基本思想为：基本思想为：首先从起始点出发，找出

10、距起始点最近的结点，然后以此结首先从起始点出发，找出距起始点最近的结点，然后以此结点为基础找出距起始点次近的结点，如此每次都找出比前一点为基础找出距起始点次近的结点，如此每次都找出比前一次短的通路，直至某个通路到达给定的目的，这时所得到的次短的通路，直至某个通路到达给定的目的，这时所得到的通路就是源到目的的最短通路。通路就是源到目的的最短通路。具体可采用标记方法。具体可采用标记方法。利用利用Dijkstra算法求算法求A到到D的最短通路的最短通路扩散法（扩散法（flooding）扩散法为静态算法，也称洪泛式。扩散法为静态算法，也称洪泛式。基本思想基本思想：路由器将收到的每个分组，：路由器将收到

11、的每个分组，从除了分组到来的线路外的所有输出线路上发出。从除了分组到来的线路外的所有输出线路上发出。可靠性高，但容易造成网络拥塞，改进办法有：可靠性高，但容易造成网络拥塞，改进办法有：在每个分组头中增加一个站点计数器（在每个分组头中增加一个站点计数器（hop counter）：）：每经过一个每经过一个站点，计数器减站点，计数器减1，当计数器减为，当计数器减为0时，就扔掉分组。计数器的值可时，就扔掉分组。计数器的值可设置为源到目的的长度或子网的直径。设置为源到目的的长度或子网的直径。记下分组扩散的路径，确保分组只转发一次。可以让源路由器对来记下分组扩散的路径，确保分组只转发一次。可以让源路由器对

12、来自主机的每个分组设置一个序号，每个路由器对应于每个源路由器自主机的每个分组设置一个序号，每个路由器对应于每个源路由器都有一张表，用来记录已转发过的分组（源路由器和序号）。都有一张表，用来记录已转发过的分组（源路由器和序号）。选择扩散法（选择扩散法（flood selectively）：）：只转发到与正确方向接近的那些线只转发到与正确方向接近的那些线路上。路上。适用于负荷轻的小规模网络以及特别强调健壮性的网络。适用于负荷轻的小规模网络以及特别强调健壮性的网络。基于流量（基于流量（flow-based）的路由选择的路由选择一种既考虑拓扑结构又兼顾载荷的静态路由选择算法。一种既考虑拓扑结构又兼顾载

13、荷的静态路由选择算法。基本思想基本思想：利用已知的载荷平均流量，计算出该线路上的平均分组：利用已知的载荷平均流量，计算出该线路上的平均分组延迟；由所有线路的平均延迟，计算出整个网络的平均分组延迟，延迟；由所有线路的平均延迟，计算出整个网络的平均分组延迟，从而找出具有网络最小延迟的最优路由选择算法。从而找出具有网络最小延迟的最优路由选择算法。采用这种技术必须预知的几种信息：采用这种技术必须预知的几种信息：网络的拓扑结构网络的拓扑结构给出通信量矩阵给出通信量矩阵Fij各线路容量的矩阵各线路容量的矩阵Cij选定一种路由选择算法选定一种路由选择算法从源端从源端 i 到目的端到目的端 j 的项表示从的项

14、表示从 I 到到 j的通信路由和从的通信路由和从 i 送到送到 j 每秒钟的分每秒钟的分组数量。组数量。基于流量路由选择的示例基于流量路由选择的示例线上的数值表示各方线上的数值表示各方向的容量向的容量C Ci i，单位为单位为单位为单位为bpsbps。通信量的通信量的数学分析数学分析1.计算每条线路总通信量计算每条线路总通信量 i ，例：例： 1= AB=9+4+1=14。2.设分组平均长度为设分组平均长度为1/ （在这里假定为（在这里假定为800位），则每条线路上分位），则每条线路上分组的容量为组的容量为 Ci，单位为分组单位为分组/s。例：例：C1=20kbps，则，则 C1=20k/80

15、0=25分组分组/s。3.由队列原理导出每条线路的平均延迟（包括排队时间和服务时间）由队列原理导出每条线路的平均延迟（包括排队时间和服务时间）： Ti=( Ci- i)-1如：如：T1=(25-14 )-1=91ms4.设每条线路的权值设每条线路的权值 i= i/i ，即在总即在总通信量中使用该线路的比通信量中使用该线路的比例。例。如：如： 1= 14/(14+12+6+11+13+8+10+8)=14/82=0.1715.则整个网络的平均延迟时间为则整个网络的平均延迟时间为iTi，即所有线路的加权延迟和。即所有线路的加权延迟和。本例中为本例中为86ms。距离矢量路由选择距离矢量路由选择距离矢

16、量路由选择（距离矢量路由选择（distance vector routing）算法是现代计算机网络两算法是现代计算机网络两个最常使用的动态路由选择算法之一。个最常使用的动态路由选择算法之一。最初用于最初用于ARPAnet；DECnet、Novell的的IPX以及以及Internet的一种内部网关的一种内部网关协议（协议（IGP，Interior Gateway Protocol）都使用了称作都使用了称作RIP（Route Information Protocol）的距离矢量路由选择算法；的距离矢量路由选择算法；Cisco则开发了一种改则开发了一种改进的协议，叫作进的协议，叫作IGRP（Inte

17、rior Gateway Routing Protocol）。）。基本思想基本思想：每个路由器维护一张（矢量）表，表中给出到每个目的节点：每个路由器维护一张（矢量）表，表中给出到每个目的节点已知的最佳距离和路径；每个路由器还不断测试到达相邻路由器的距离；已知的最佳距离和路径；每个路由器还不断测试到达相邻路由器的距离；相邻的路由器之间也不断地相互交换矢量信息；这样每个路由器将测试相邻的路由器之间也不断地相互交换矢量信息；这样每个路由器将测试出的到达相邻路由器的距离加上相邻路由器给出的矢量信息，就可得知出的到达相邻路由器的距离加上相邻路由器给出的矢量信息，就可得知通过相邻路由器到达每个目的节点的距

18、离，选择最佳路径更新表的信息。通过相邻路由器到达每个目的节点的距离，选择最佳路径更新表的信息。距离矢量路由选择示例距离矢量路由选择示例从从J的四个邻居收到的向量的四个邻居收到的向量J的新的新路由表路由表 新的估计的新的估计的 从从J的延时的延时路由器无穷计算无穷计算(count-to-infinity)的问题的问题DVR算法收敛慢，其时间复杂度为算法收敛慢，其时间复杂度为O(n3)。特别是它对好消息的反应迅速，特别是它对好消息的反应迅速，但对坏消息却反应迟钝。但对坏消息却反应迟钝。其对坏消息的反应迟钝，会造成相互交换的矢量信息错误，最终导致无其对坏消息的反应迟钝，会造成相互交换的矢量信息错误，

19、最终导致无穷计算的后果。穷计算的后果。在实际使用中，可通过设置距离的最大值（如设置为网络最长路由加在实际使用中，可通过设置距离的最大值（如设置为网络最长路由加1）来扼制这种无限的增长。来扼制这种无限的增长。X链路状态路由选择链路状态路由选择链路状态路由选择（链路状态路由选择（link state routing）算法算法1979年出现在年出现在ARPAnet上，作为一种用来取代上，作为一种用来取代DVR的动态路由选择算法，之后的动态路由选择算法，之后得到了广泛的应用。得到了广泛的应用。基本思想基本思想：通过各个节点之间的路由信息交换，每个节点都可获：通过各个节点之间的路由信息交换，每个节点都可

20、获得关于全网的拓扑信息，即所有的节点、各节点间的链路连接和得关于全网的拓扑信息，即所有的节点、各节点间的链路连接和链路的代价（时延或费用等），可将这些拓扑信息抽象成一张带链路的代价（时延或费用等），可将这些拓扑信息抽象成一张带权无向图，然后利用最短通路路由选择算法计算出到各个目的节权无向图，然后利用最短通路路由选择算法计算出到各个目的节点的最短通路。点的最短通路。链路状态路由选择算法的步骤链路状态路由选择算法的步骤1.找出所有可达的相邻节点及它们的网络地址；找出所有可达的相邻节点及它们的网络地址；2.测定到这些相邻节点的代价；测定到这些相邻节点的代价；3.将以上信息构成将以上信息构成链路状态分

21、组链路状态分组（link state packet）；）；4.向网上所有节点发送链路状态分组；向网上所有节点发送链路状态分组；5.利用收到的链路状态分组计算到各目的节点利用收到的链路状态分组计算到各目的节点的最短通路。的最短通路。1. 了解相邻节点了解相邻节点每个路由器启动后，首先在所有与之相连的点每个路由器启动后，首先在所有与之相连的点-点线路上发送一点线路上发送一个特殊的询问分组（个特殊的询问分组（HELLO分组），线路另一端的路由器收到分组），线路另一端的路由器收到后必须发回一个响应来告知它是谁（其网络地址）。后必须发回一个响应来告知它是谁（其网络地址）。2. 测量线路代价测量线路代价（

22、cost）路由器在链路上发送一个要求对方立即响应的特殊回声路由器在链路上发送一个要求对方立即响应的特殊回声（ECHO）分组，将回声分组的来回时间除以分组，将回声分组的来回时间除以2即得到该链路的即得到该链路的延迟时间（代价）。一般重复若干次，取平均值。延迟时间（代价）。一般重复若干次，取平均值。3. 构造链路状态分组构造链路状态分组每个链路状态分组包括每个链路状态分组包括源节点的网络地址源节点的网络地址、分组的、分组的序号序号和和寿命寿命，然后是一系列然后是一系列相邻节点的网络地址相邻节点的网络地址和去往该节点的链路和去往该节点的链路代价代价。决定何时创建链路状态分组一般有两种方法：决定何时创

23、建链路状态分组一般有两种方法：定期创建链路状态分组。定期创建链路状态分组。探测到网络连接发生变化时再创建链路状态分组。探测到网络连接发生变化时再创建链路状态分组。4. 发送链路状态分组发送链路状态分组通过改进的扩散法（记录分组扩散路径：每个路由器维护一张带有源节点和通过改进的扩散法（记录分组扩散路径：每个路由器维护一张带有源节点和最大分组序号的表，对来自于同一个源节点的重复分组（分组序号最大分组序号的表，对来自于同一个源节点的重复分组（分组序号表中序表中序号）不转发）向网上所有其它节点发送链路状态分组。号）不转发）向网上所有其它节点发送链路状态分组。所有的链路状态分组都要应答。当线路空闲时，从

24、缓冲区中选择发送一个分所有的链路状态分组都要应答。当线路空闲时，从缓冲区中选择发送一个分组或应答。组或应答。为了保证高效可靠地发送链路状态分组，需采取如下一些措施：为了保证高效可靠地发送链路状态分组，需采取如下一些措施：将分组序号长度设为将分组序号长度设为32位可防止序号重叠太快，若每隔位可防止序号重叠太快，若每隔1秒发送一个分组，秒发送一个分组，可发可发137年不重复。年不重复。为每个分组规定一个寿命，分组在路由器中时，其寿命每隔为每个分组规定一个寿命，分组在路由器中时，其寿命每隔1秒就减秒就减1，直，直到减为到减为0被抛弃。可解决路由器崩溃及分组序号传输出错等造成新旧分组被抛弃。可解决路由

25、器崩溃及分组序号传输出错等造成新旧分组不分的问题。不分的问题。前图中路由前图中路由器器B的分组的分组缓冲区，包缓冲区，包含新近到达含新近到达还未处理完还未处理完毕的分组。毕的分组。5. 计算新的路由计算新的路由当一个路由器收集齐了所有的链路状态分组后，便可构造当一个路由器收集齐了所有的链路状态分组后，便可构造出整个网络的拓扑带权图；出整个网络的拓扑带权图；通过最短通路路由选择算法就可确定到达所有其它节点的通过最短通路路由选择算法就可确定到达所有其它节点的最短路径；最短路径；将此结果存入路由选择表中达到更新目的。将此结果存入路由选择表中达到更新目的。链路状态路由选择算法的总结链路状态路由选择算法

26、的总结优点：优点：可靠性极高：因为构造网络拓扑的信息来自于各个节点亲自的探测。可靠性极高：因为构造网络拓扑的信息来自于各个节点亲自的探测。最佳的路由：根据当前整网的拓扑信息计算出的。最佳的路由：根据当前整网的拓扑信息计算出的。缺点：缺点：每个节点需要大的存储空间来存放其它所有节点发来的链路状态分组。每个节点需要大的存储空间来存放其它所有节点发来的链路状态分组。路由计算时间较长。路由计算时间较长。以上两点特别在网络规模很大时更加突出。以上两点特别在网络规模很大时更加突出。链路状态路由选择算法在实际网络中运行得很好，使用非常广泛链路状态路由选择算法在实际网络中运行得很好，使用非常广泛Interne

27、t上广泛使用的上广泛使用的OSPF（Open Shortest Path First）协议协议为为DECnet设计的，后被设计的，后被ISO采纳的采纳的IS-IS（Intermediate System to Intermediate System）协议协议分级路由选择（分级路由选择（hierarchical routing）将网络分成一些区域，每个区域内的路由器只负责本区域内的分将网络分成一些区域，每个区域内的路由器只负责本区域内的分组转发，而不管其它区域的情况，目的地址不在本区域内的分组组转发，而不管其它区域的情况，目的地址不在本区域内的分组都发给指定的区域路由器去处理。都发给指定的区域路

28、由器去处理。当网络规模很大时，往往需要分成多级。当网络规模很大时，往往需要分成多级。路由信息的交换只在本区域内进行，路由器内部需存储的路由信路由信息的交换只在本区域内进行，路由器内部需存储的路由信息大大减少。节省了路由器的存储空间和网络带宽。息大大减少。节省了路由器的存储空间和网络带宽。缺点是选择的路由可能不是最佳的。缺点是选择的路由可能不是最佳的。分级路由示例分级路由示例移动主机（移动主机（mobile host）的路由选择的路由选择移动用户（移动用户（mobile user）都有一个不变的永久性主方位（都有一个不变的永久性主方位（home location），），用一个永久性的主地址（如手

29、机号码）来确定。用一个永久性的主地址（如手机号码）来确定。用主地址作为动态用户在系统中的路由选择目标，在找到用户后，用主地址作为动态用户在系统中的路由选择目标，在找到用户后，再将分组发送到用户所在的任何地方。再将分组发送到用户所在的任何地方。移动主机的定位移动主机的定位世界按地理位置被分成许多小单元（通常是一个世界按地理位置被分成许多小单元（通常是一个LAN或无线单元），称作或无线单元），称作区区域域，包含有：，包含有：一个或多个一个或多个外地代理外地代理（foreign agent），），用来管理所有来到当地的动态用来管理所有来到当地的动态用户。用户。一个一个本地代理本地代理（home ag

30、ent），），用来管理原本属本区域，但当时正在外用来管理原本属本区域，但当时正在外地的用户。地的用户。当一个移动用户进入某区域时：当一个移动用户进入某区域时：移动主机和外地代理通过广播分组取得联系，移动主机向外地代理登记移动主机和外地代理通过广播分组取得联系，移动主机向外地代理登记注册，给出其原来所在地的地址、当前数据链路层地址以及一些安全性注册，给出其原来所在地的地址、当前数据链路层地址以及一些安全性信息。信息。外地代理与移动主机的本地代理取得联系，发出诸如外地代理的网络地外地代理与移动主机的本地代理取得联系，发出诸如外地代理的网络地址、安全信息等信息。址、安全信息等信息。本地代理检查安全信

31、息，验证通过后应答外地代理。本地代理检查安全信息，验证通过后应答外地代理。外地代理得到本地代理确认后，在其表中开设一个表项，通知移动主机外地代理得到本地代理确认后，在其表中开设一个表项，通知移动主机已经登录注册。已经登录注册。当一个移动用户离开某区域时，应退出登录当一个移动用户离开某区域时，应退出登录移动主机的分组路由传递移动主机的分组路由传递广播（广播（broadcast）路由选择路由选择将分组同时发往所有节点称作将分组同时发往所有节点称作广播广播（broadcasting）。）。有多种有多种方法实现广播发送：方法实现广播发送：发送站给每个目的站点都单独发送一个分组，浪费带宽。发送站给每个目

32、的站点都单独发送一个分组，浪费带宽。采用扩散法，产生太多的分组，消耗太大的带宽。采用扩散法，产生太多的分组，消耗太大的带宽。多目的路由选择算法，每个分组携带一个欲去往的目的地多目的路由选择算法，每个分组携带一个欲去往的目的地址列表，每个路由器根据目的地址列表确定一组输出线路，址列表，每个路由器根据目的地址列表确定一组输出线路，修改目的地址列表转发分组副本。在一条输出线路上只有修改目的地址列表转发分组副本。在一条输出线路上只有一个分组，节省带宽。一个分组，节省带宽。使用以发送站为根的生成树来转发分组。分组副本最少，使用以发送站为根的生成树来转发分组。分组副本最少，占用带宽最小。但需每个路由器了解

33、全网的拓扑结构并构占用带宽最小。但需每个路由器了解全网的拓扑结构并构造出生成树。造出生成树。逆向路径转发的广播路由逆向路径转发的广播路由逆向路径转发（逆向路径转发（reverse path forwarding）的思想：当一个广的思想：当一个广播分组到达时，路由器检查其源地址和输入线路，若输入线播分组到达时，路由器检查其源地址和输入线路，若输入线路是从该路由器去往源地址的最佳路径，则将该分组在除输路是从该路由器去往源地址的最佳路径，则将该分组在除输入线路以外的所有输出线路上转发出去；否则将其丢弃。入线路以外的所有输出线路上转发出去；否则将其丢弃。相比前四种方法，既合理有效，又易于实现。相比前四

34、种方法，既合理有效，又易于实现。H多点播送（多点播送（multicast）路由选择路由选择向处于网络中不同位置的一组（部分）用户广播，称向处于网络中不同位置的一组（部分）用户广播，称为多点播送或组播。为多点播送或组播。需要路由器知道哪些用户加入哪些组以及用户何时加需要路由器知道哪些用户加入哪些组以及用户何时加入或离开这个组。入或离开这个组。路由器通过计算得到覆盖整个子网的生成树，再根据路由器通过计算得到覆盖整个子网的生成树，再根据组的成员修剪出各组的生成树，多点播送分组仅沿相组的成员修剪出各组的生成树，多点播送分组仅沿相应生成树转发。应生成树转发。(a) 一个子网一个子网(b) 最左边路由器的

35、生成树最左边路由器的生成树(c) 小组小组1的多点播送树的多点播送树(d) 小组小组2的多点播送树的多点播送树5.3 拥塞控制拥塞控制拥塞拥塞当大量分组进入通信子网，超出了网络的处理能力时，就会引起网络当大量分组进入通信子网，超出了网络的处理能力时，就会引起网络局部或整体性能下降，这种现象称为局部或整体性能下降，这种现象称为拥塞拥塞。拥塞不加控制地发展下去，最终导致网络通信停顿（有效吞吐量为零）拥塞不加控制地发展下去，最终导致网络通信停顿（有效吞吐量为零），即，即阻塞阻塞。拥塞产生的原因拥塞产生的原因短时间内进入网络的分组数量过多；短时间内进入网络的分组数量过多；局部问题导致性能下降（多个输入

36、对应一个输出，慢速处理器，低带局部问题导致性能下降（多个输入对应一个输出，慢速处理器，低带宽线路）。宽线路）。解决办法解决办法针对某个因素的解决方案，只能对提高网络性能起到一点点好处，甚针对某个因素的解决方案，只能对提高网络性能起到一点点好处，甚至可能仅仅是转移了影响性能的瓶颈；至可能仅仅是转移了影响性能的瓶颈；需要全面考虑各个因素。需要全面考虑各个因素。拥塞控制拥塞控制拥塞控制与流量控制的差别拥塞控制与流量控制的差别拥塞控制拥塞控制（congestion control）需要确保通信子网需要确保通信子网能够承载用户提交的通信量，是一个全局性问题，能够承载用户提交的通信量，是一个全局性问题，涉

37、及主机、路由器等很多因素；涉及主机、路由器等很多因素；流量控制流量控制（flow control）与点到点的通信量有关，与点到点的通信量有关，主要解决快速发送方与慢速接收方的问题，是局部主要解决快速发送方与慢速接收方的问题，是局部问题，一般都是基于反馈进行控制的。问题，一般都是基于反馈进行控制的。拥塞拥塞引起网络性能下降引起网络性能下降拥塞控制的基本原理拥塞控制的基本原理根据控制论，拥塞控制方法分为两类根据控制论，拥塞控制方法分为两类开环控制（开环控制（拥塞预防拥塞预防）通过好的设计来解决问题，避免拥塞发生；通过好的设计来解决问题，避免拥塞发生；拥塞控制时，不考虑网络当前状态；拥塞控制时，不考

38、虑网络当前状态；闭环控制（闭环控制（拥塞解决拥塞解决）基于反馈机制；基于反馈机制；工作过程工作过程监控系统，发现何时何地发生拥塞；监控系统，发现何时何地发生拥塞；把发生拥塞的消息传给能采取动作的站点；把发生拥塞的消息传给能采取动作的站点；调整系统操作，解决问题。调整系统操作，解决问题。拥塞控制的基本原理拥塞控制的基本原理衡量网络是否拥塞的参数衡量网络是否拥塞的参数缺乏缓冲区造成的丢包率；缺乏缓冲区造成的丢包率；平均队列长度；平均队列长度；超时重传的包的数目；超时重传的包的数目；平均包延迟；平均包延迟；包延迟变化（包延迟变化（Jitter）。）。反馈方法反馈方法向负载发生源发送一个告警包；向负载

39、发生源发送一个告警包；包结构中保留一个位或域用来表示发生拥塞，一旦发生拥塞，包结构中保留一个位或域用来表示发生拥塞，一旦发生拥塞，路由器将所有的输出包置位，向邻居告警；路由器将所有的输出包置位，向邻居告警；主机或路由器主动地、周期性地发送探报（主机或路由器主动地、周期性地发送探报（probe），），查询是否查询是否发生拥塞。发生拥塞。拥塞控制算法拥塞控制算法拥塞预防策略拥塞预防策略开环控制开环控制影响拥塞的网络设计策略影响拥塞的网络设计策略通信量整形和通信量管制通信量整形和通信量管制通信量整形通信量整形（traffic shaping）：）：迫使分组按预定的速迫使分组按预定的速率进入网中，避免

40、突发性的大通信量造成网络瞬间过率进入网中，避免突发性的大通信量造成网络瞬间过载。广泛用于面向连接的工作方式（如载。广泛用于面向连接的工作方式（如ATM）。）。通信量管制通信量管制（traffic policing）：）：网络对用户的通信量网络对用户的通信量进行监视，对遵守约定的用户，保证其要求的服务；进行监视，对遵守约定的用户，保证其要求的服务；对违反协议的数据采取惩罚措施，如丢弃、降低优先对违反协议的数据采取惩罚措施，如丢弃、降低优先级、不保证服务质量等。级、不保证服务质量等。以上方法一般用于以虚电路方式工作的网络层，在建以上方法一般用于以虚电路方式工作的网络层，在建立虚电路的时候由双方协商

41、而定。在数据报子网上实立虚电路的时候由双方协商而定。在数据报子网上实现比较困难，但可应用于传输层的连接中。现比较困难，但可应用于传输层的连接中。漏桶（漏桶（leaky bucket）算法算法在主机和网络之间接入一个在主机和网络之间接入一个“漏桶漏桶”（固定长度的分（固定长度的分组队列），无论主机以多大的速率发送分组，组队列），无论主机以多大的速率发送分组，“漏桶漏桶”中的分组总是以恒定的速率注入网中。若主机发送中的分组总是以恒定的速率注入网中。若主机发送过快，当过快，当“漏桶漏桶”满了以后，多余的分组即被丢弃。满了以后，多余的分组即被丢弃。令牌桶（令牌桶（token bucket）算法算法令牌

42、桶算法能较快地响应突发数据的到来，且不会令牌桶算法能较快地响应突发数据的到来，且不会丢失数据。丢失数据。令牌桶中每隔定长的时间产生出一个令牌（计数器）令牌桶中每隔定长的时间产生出一个令牌（计数器），当桶装满后，随后产生的令牌就被丢弃。分组在，当桶装满后，随后产生的令牌就被丢弃。分组在桶外的缓冲区中等待发送，桶中有多少令牌就允许桶外的缓冲区中等待发送，桶中有多少令牌就允许发送多少个分组，每个令牌用后即销毁，当桶中没发送多少个分组，每个令牌用后即销毁，当桶中没有令牌时必须停止发送。有令牌时必须停止发送。为了平滑大量突发数据的出现，可在令牌桶后面增为了平滑大量突发数据的出现，可在令牌桶后面增加一个漏

43、桶，使得漏桶的速率大于令牌桶但小于网加一个漏桶，使得漏桶的速率大于令牌桶但小于网络的峰值速率络的峰值速率(a) 漏桶的输入漏桶的输入(b) 漏桶的输出漏桶的输出(c) (e) 一个具有一个具有250KB、500KB和和750KB容量的令牌容量的令牌桶的输出桶的输出(f) 一个一个500KB令牌桶令牌桶接一个接一个10MB/s漏漏桶后的输出桶后的输出流说明流说明流说明用于描述通信量的注入模式和服务质量的衡量标准。流说明用于描述通信量的注入模式和服务质量的衡量标准。流说明既可适用于虚电路上传送的分组，也适用于从源端到流说明既可适用于虚电路上传送的分组，也适用于从源端到目的端传送的数据报序列。目的端

44、传送的数据报序列。流说明的例子：流说明的例子：最大传输速率（字节/s）令牌桶大小（字节）令牌桶速率（字节/s）最大分组大小（字节）输入的特性输入的特性质量保证最大延迟变化（ s ）最小注意延迟（ s ）突发丢失敏感性（分组）丢失间隔（s）丢失敏感性（字节）需要的服务需要的服务拥塞的解决拥塞的解决1.虚电路子网中采用虚电路子网中采用许可控制许可控制（admission control）的三种策略：的三种策略：一旦出现拥塞的信号，就不再创建任何虚电路，直至拥塞解一旦出现拥塞的信号，就不再创建任何虚电路，直至拥塞解除。除。允许建立新的虚电路，但要仔细选择路由，以便所有新的虚允许建立新的虚电路，但要仔

45、细选择路由，以便所有新的虚电路绕过拥塞的区域。电路绕过拥塞的区域。在虚电路建立时，子网与主机对所需服务质量进行协商。若在虚电路建立时，子网与主机对所需服务质量进行协商。若不能满足主机最低要求，则拒绝建立连接；否则就保留连接不能满足主机最低要求，则拒绝建立连接；否则就保留连接所需的多种资源，避免拥塞发生。所需的多种资源，避免拥塞发生。2.抑制分组抑制分组（choke packet）：）：每个路由器监视本节点的资源利用情况，若某个方向的资源每个路由器监视本节点的资源利用情况，若某个方向的资源利用率超过一定的门限，则该路由器向有关源节点发送抑制利用率超过一定的门限，则该路由器向有关源节点发送抑制分组

46、，源节点相应减少发往该方向的数据量，直至该方向的分组，源节点相应减少发往该方向的数据量，直至该方向的拥塞解除。拥塞解除。为了公平合理地控制引起拥塞的源节点的行为，可采用为了公平合理地控制引起拥塞的源节点的行为，可采用加权加权公平队列公平队列（weighted fair queuing）。）。在（高速的）在（高速的）WAN中为了中为了及时解脱拥塞，可以上游及时解脱拥塞，可以上游使用更多的缓存为代价，使用更多的缓存为代价，这种方法称为这种方法称为站到站抑制站到站抑制分组分组。(a)一个仅影响源端的抑制一个仅影响源端的抑制分组。分组。(b)一个影响沿途所有站点一个影响沿途所有站点的抑制分组。的抑制分

47、组。3.负载丢弃负载丢弃（load shedding）：）：在没有办法消除拥塞时，只能采取极端措施，即丢弃部分在没有办法消除拥塞时，只能采取极端措施，即丢弃部分的分组来解决拥塞。的分组来解决拥塞。为了使网络能合理地丢弃分组，应用程序应对各分组标注为了使网络能合理地丢弃分组，应用程序应对各分组标注优先级别，以便有选择依据。优先级别，以便有选择依据。4.延时差控制延时差控制：为满足音频或视频数据流传输时对延时变化的敏感性，需为满足音频或视频数据流传输时对延时变化的敏感性，需要对传输延迟进行控制，以保证可接受的最大延时差。要对传输延迟进行控制，以保证可接受的最大延时差。通过在沿途经过的路由器中计算分

48、组传输的延迟，与预期通过在沿途经过的路由器中计算分组传输的延迟，与预期的传输平均延迟之差决定其在输出队列中的优先次序，能的传输平均延迟之差决定其在输出队列中的优先次序，能够有效的减小传输延迟差。够有效的减小传输延迟差。5.多点播送的拥塞控制：多点播送的拥塞控制：多点播送要实现多个源端到多个目的端的分组传输流，其多点播送要实现多个源端到多个目的端的分组传输流，其拥塞控制必须适应目的端的不断变换，加入不同的多点播拥塞控制必须适应目的端的不断变换，加入不同的多点播送组造成的带宽需求变化。送组造成的带宽需求变化。RSVP资源重复利用协议资源重复利用协议：根据接收者向上传送至发送者的：根据接收者向上传送

49、至发送者的带宽保留消息，沿途设置从源到目的的多点播送树的带宽带宽保留消息，沿途设置从源到目的的多点播送树的带宽预留，接收者可同时声明一个或多个想接收的源并在其中预留，接收者可同时声明一个或多个想接收的源并在其中自由切换。各个路由器利用这些信息来优化整体带宽使用自由切换。各个路由器利用这些信息来优化整体带宽使用计划。计划。(a) 一个网络；一个网络；(b) 主机主机1的多点播送的多点播送生成树；生成树；(c) 主机主机2的多点播送的多点播送生成树。生成树。(a) 主机主机3申请一条到申请一条到主机主机1的通道；的通道；(b) 主机主机3申请又一条申请又一条通道，到主机通道，到主机2；(c) 主机

50、主机5申请一条到申请一条到主机主机1的通道。的通道。5.4 网络互联网络互联各种不同标准、不同拓扑、不同体系结构、不同协议的异型网络各种不同标准、不同拓扑、不同体系结构、不同协议的异型网络的互联。的互联。连接不同网络的设备统称连接不同网络的设备统称“网关网关”（gateway），），用来在不同网用来在不同网络之间对数据进行转换。络之间对数据进行转换。网络互联设备网络互联设备根据其工作层次的不同，分别称为：根据其工作层次的不同，分别称为：中继器中继器（repeater）：）：在物理层上再生放大物理信号。在物理层上再生放大物理信号。网桥网桥（bridge）：）：在数据链路层上，采用存储在数据链路层

51、上，采用存储-转发方式转发方式对数据帧进行传递。对数据帧进行传递。多协议路由器多协议路由器（multiprotocol router）：）：类似网桥，但类似网桥，但工作在网络层，转发分组时要进行路由选择，对连接的工作在网络层，转发分组时要进行路由选择，对连接的不同网络还要进行不同协议的转换。不同网络还要进行不同协议的转换。传输网关传输网关（transport gateway）：）：用来建立两个网络间用来建立两个网络间的传输连接。的传输连接。应用网关应用网关（application gateway）：）：在应用层上进行协在应用层上进行协议转换。议转换。半网关半网关网关可从中间分成两部分，每个部分

52、称为一个半网关，每个网络网关可从中间分成两部分，每个部分称为一个半网关，每个网络都拥有和管理一个半网关，半网关之间用无源的导线相连，两个都拥有和管理一个半网关，半网关之间用无源的导线相连，两个半网关的接口处使用相同的中间协议进行网络互连。半网关的接口处使用相同的中间协议进行网络互连。网络的差异造成互联的问题网络的差异造成互联的问题不同类型的网络，其差异可能表现在许多方面，完全消除这些差异是不不同类型的网络，其差异可能表现在许多方面，完全消除这些差异是不可能的，网络互联只能尽力而为。可能的，网络互联只能尽力而为。按连接时间、分组数、字节数或不计费按连接时间、分组数、字节数或不计费计费方式计费方式

53、超时、流说明等超时、流说明等参数参数秘密规则、加密等秘密规则、加密等安全性安全性漏桶、抑制分组等漏桶、抑制分组等拥塞控制拥塞控制滑动窗口、速度控制等滑动窗口、速度控制等流量控制流量控制可靠的、无序的或有序的发送可靠的、无序的或有序的发送出错处理出错处理没有与有没有与有服务质量服务质量网络所明确的最大值网络所明确的最大值分组大小分组大小具有的与没有的具有的与没有的多点播送多点播送平面的（平面的（802802）与分层的（）与分层的（IPIP）寻址方式寻址方式IPIP，IPXIPX，CLNPCLNP，Apple TalkApple Talk，DECnetDECnet等等协议协议面向连接的和无连接的面

54、向连接的和无连接的提供的服务提供的服务差差 异异项项 目目网络互联的两种形式网络互联的两种形式1.面向连接的级联虚电路面向连接的级联虚电路（Concatenated Virtual Circuits）2.无连接网络互联无连接网络互联（Connectionless Internetworking）级联虚电路级联虚电路从信源到信宿的虚电路穿越沿途各网络及网关。其建立方式同普从信源到信宿的虚电路穿越沿途各网络及网关。其建立方式同普通虚电路一样，只是对连接不同协议网络的多协议路由器要求进通虚电路一样，只是对连接不同协议网络的多协议路由器要求进行协议转换。行协议转换。无连接网络互联无连接网络互联网络层只

55、提供最简单、最基本的数据报传输服务：无连接、独立网络层只提供最简单、最基本的数据报传输服务：无连接、独立路由、不可靠、无序。路由、不可靠、无序。隧道（隧道（Tunneling）实际上要转换两种不同协议的网络是很困难的，甚至实际上要转换两种不同协议的网络是很困难的，甚至不可能。不可能。有一种特殊情况：当信源和信宿都处在同一类型的网有一种特殊情况：当信源和信宿都处在同一类型的网络中，而这两个网络又通过另一种类型的网络进行互络中，而这两个网络又通过另一种类型的网络进行互联。可采用挖隧道方式简单巧妙地解决协议的转换。联。可采用挖隧道方式简单巧妙地解决协议的转换。在挖隧道方式中，实际并没有进行任何的协议

56、转换，在挖隧道方式中，实际并没有进行任何的协议转换，只是将被传输的数据分组作为中间网络分组承载的数只是将被传输的数据分组作为中间网络分组承载的数据，穿越过去。据，穿越过去。互联网络的路由选择互联网络的路由选择互联网络的路由选择分成两个层次：互联网络的路由选择分成两个层次：单个网络内部的路由选择。其路由选择算法称为单个网络内部的路由选择。其路由选择算法称为内部网关协议内部网关协议IGP （Interior Gateway Protocol）。）。每个网络都是一个独立的每个网络都是一个独立的自治系统自治系统AS（Autonomous System），），可使用不同的路由算法。可使用不同的路由算法。

57、网络间的路由选择。其路由选择算法称为网络间的路由选择。其路由选择算法称为外部网关协议外部网关协议EGP（Exterior Gateway Protocol），），可能涉及到不同网络协议的转可能涉及到不同网络协议的转换，需要时使用隧道技术。另外在费用、业务类型、服务质量，甚换，需要时使用隧道技术。另外在费用、业务类型、服务质量，甚至政治因素等方面都较为复杂。至政治因素等方面都较为复杂。A12E4CB3DF5ABDFEC分段（分段（fragmentation）不同的网络的分组长度是不一样的，当一个大分组穿不同的网络的分组长度是不一样的，当一个大分组穿越分组定义较小的网络时，网关必须将一个大分组划越

58、分组定义较小的网络时，网关必须将一个大分组划分成若干个小的段（分成若干个小的段（fragment），），把各段作为单独的把各段作为单独的分组进行发送。分组进行发送。透明分段透明分段：在中间网络进出时分别进行分段和重组工：在中间网络进出时分别进行分段和重组工作。每个小分组须含有计数字段或分组结束标志以便作。每个小分组须含有计数字段或分组结束标志以便出口网关重组，所有分组必须经同一网关发出。出口网关重组，所有分组必须经同一网关发出。不透明分段不透明分段：中间网关不重组各分段，每个分段的分：中间网关不重组各分段，每个分段的分组都作为单独原始的分组独立传递，最后在目的地主组都作为单独原始的分组独立传递

59、，最后在目的地主机上进行重组。机上进行重组。分组的重组（分组的重组（reassembly）分段的编号分段的编号头中包含：分组编号；分组中首分段的编号；分组结束标志位。头中包含：分组编号；分组中首分段的编号；分组结束标志位。防火墙（防火墙（firewall）防火墙设有过滤分组的网关，只有检查合格的数据才能进出网络。防火墙设有过滤分组的网关，只有检查合格的数据才能进出网络。由两部分组成：两个用作进出分组过滤的路由器和一个用于对数据由两部分组成：两个用作进出分组过滤的路由器和一个用于对数据内容进行检查的应用网关。内容进行检查的应用网关。5.5 因特网上的网络层因特网上的网络层因特网：在网络层，可以看

60、作是一组由主干连接在一因特网：在网络层，可以看作是一组由主干连接在一起的多个起的多个自治系统自治系统（autonomous system）子网。子网。IP协议是连接因特网的网络层协议协议是连接因特网的网络层协议IP（Internet protocol）分组的头：分组的头：INTERNET网络层协议网络层协议-IP头包括头包括20个字节的固定部分和变长（最长个字节的固定部分和变长（最长40字节）的可选部分，字节）的可选部分，从左到右传输；从左到右传输；-版本域（版本域（version）；）；-IHL：IP包头长度，最小为包头长度，最小为5，最大为，最大为15，单位为，单位为32-bit word

61、；-服务类型域（服务类型域（Type of Service）3个优先级位；个优先级位；3个标志位：个标志位：D（Delay）、）、T（Throughput）、）、R（Reliability）；）；2个保留位；个保留位；目前，很多路由器都忽略服务类型域。目前，很多路由器都忽略服务类型域。-总长度域（总长度域（Total length）-标识域（标识域（Identification）-DF：Dont Fragment；所有机器必须能够接收小于等于所有机器必须能够接收小于等于576字节的字节的段。段。-MF：More Fragments；除最后一个段外的所有段都要置除最后一个段外的所有段都要置MF位

62、。位。INTERNET网络层协议网络层协议段偏移量（段偏移量（Fragment offset）l除最后一个段外的所有段的长度必须是除最后一个段外的所有段的长度必须是8字节（基本字节（基本段长）的倍数。段长）的倍数。ID=xoffset=0fragflag=0length=4000ID=xoffset=0fragflag=1length=1500ID=xoffset=1480fragflag=1length=1500ID=xoffset=2960fragflag=0length=1040One large datagram becomesseveral smaller datagramsINTE

63、RNET网络层协议网络层协议生存期（生存期（Time to live）l实际实现中，实际实现中，IP包每经过一个路由器包每经过一个路由器TTL减减1，为，为0则丢则丢弃，并给源主机发送一个告警包。弃，并给源主机发送一个告警包。协议域（协议域（Protocol）：）：上层为哪种传输协议，上层为哪种传输协议，TCP、UDP头校验和（头校验和（Header checksum）l只对只对IP包头做校验；包头做校验；l算法：每算法：每16位求反，循环相加（进位加在末尾），和再位求反，循环相加（进位加在末尾），和再求反。求反。源地址（源地址（Source address）和目的地址和目的地址（Destin

64、ation address）INTERNET网络层协议网络层协议选项（选项（Options）l变长，长度为变长，长度为4字节的倍数，不够则填充，最长为字节的倍数，不够则填充，最长为40字节；字节；IP地址地址2542,031,616C65,53416,384B16,777,214126AMax. host/networkMax. networksClass一些特殊的一些特殊的IP地址地址IP子网子网子网掩码（子网掩码（ subnet mask ）：将）：将IP地址分为子网地址地址分为子网地址和主机和主机ID两部分。例如：掩码两部分。例如：掩码 255.255.252.0使得一个使得一个B类地址

65、包含类地址包含64个子网，每个子网最多容纳个子网，每个子网最多容纳1022个主机。个主机。130.50.4.1130.50.7.254130.50.8.1130.50.11.254 130.50.64.1130.50.67.254因特网控制协议因特网控制协议因特网控制消息协议因特网控制消息协议ICMP（Internet Control Message Protocol）地址解析协议地址解析协议ARP（Address Resolution Protocol）反向地址解析协议反向地址解析协议RARP（Reverse Address Resolution Protocol）因特网控制消息协议因特网控

66、制消息协议ICMPICMP用来报告和检测因特网的运行情况，每个用来报告和检测因特网的运行情况，每个ICMP消息类型消息类型封装在封装在IP分组中。分组中。类似回声应答，但加上时间标志类似回声应答，但加上时间标志时间标记应答时间标记应答类似回声请求，但加上时间标志类似回声请求，但加上时间标志时间标记请求时间标记请求是的，我还活着是的，我还活着回声应答回声应答向一个机器发回应请求看其是否活着向一个机器发回应请求看其是否活着回声请求回声请求告诉路由器有关地理路线告诉路由器有关地理路线重定向重定向抑制分组抑制分组源端抑制源端抑制无效的头字段无效的头字段参数问题参数问题生命期字段为生命期字段为0超时超时

67、分组不能提交分组不能提交目的地不可达目的地不可达描描 述述消息类型消息类型地址解析协议地址解析协议ARP数据链路层只能识别数据链路层只能识别MAC地址，不能识别分组地址。地址，不能识别分组地址。ARP用来实现用来实现IP地址到地址到MAC地址的映射。数据链路层地址的映射。数据链路层根据映射关系使用根据映射关系使用MAC地址传送分组数据。地址传送分组数据。反向地址解析协议反向地址解析协议RARPRARP用来实现用来实现MAC 地址到地址到IP地址的映射。地址的映射。当一台无盘工作站启动时，仅知道自己的当一台无盘工作站启动时，仅知道自己的MAC地址时，可利用地址时，可利用RARP广播其广播其MAC

68、地址，地址，请求请求RARP服务器返回他的服务器返回他的IP地址。地址。但但RARP广播仅在数据链路层，路由器不会转广播仅在数据链路层，路由器不会转发，因此每个局域网上都要设置发，因此每个局域网上都要设置RARP服务器。服务器。后来发明的后来发明的BOOTP协议可在网络层上使用协议可在网络层上使用UDP分组广播，实现分组广播，实现MAC地址到地址到IP地址、默地址、默认网关地址和子网掩码的映射。认网关地址和子网掩码的映射。内部网关路由选择协议内部网关路由选择协议因特网由大量因特网由大量自治系统自治系统（ autonomous system ）所组所组成，各自治系统内部可使用不同的路由选择算法。

69、自成，各自治系统内部可使用不同的路由选择算法。自治系统内的路由选择算法统称为治系统内的路由选择算法统称为内部网关协议内部网关协议。最初的因特网内部网关协议采用基于最初的因特网内部网关协议采用基于Bellman-Ford的的距离矢量算法距离矢量算法，称为，称为路由信息协议路由信息协议RIP（Routing Information Protocol）。）。随着自治系统变得越来越大，随着自治系统变得越来越大，RIP协议难以应付庞大的路由信息和网络拓扑的变化，协议难以应付庞大的路由信息和网络拓扑的变化，由于无限计算问题造成收敛太慢，需要更好的由于无限计算问题造成收敛太慢，需要更好的内部网内部网关协议取

70、代它。关协议取代它。开放最短路径优先开放最短路径优先OSPF后来出现的后来出现的开放最短路径优先开放最短路径优先OSPF（Open Shortest Path First）内部网关协议采用了内部网关协议采用了链路状态路由选择算法链路状态路由选择算法，逐渐，逐渐成为主要的因特网内部网关协议。它具有：成为主要的因特网内部网关协议。它具有：开放的算法（公开发表）开放的算法（公开发表）支持各种距离度量（跳数、延迟、开销等）支持各种距离度量（跳数、延迟、开销等）动态，能快速适应拓扑结构的变化动态，能快速适应拓扑结构的变化支持多种服务类型支持多种服务类型支持负载平衡，将负荷分流到多条线路上支持负载平衡，将

71、负荷分流到多条线路上支持分级网络支持分级网络提供安全措施提供安全措施支持支持IP隧道隧道OSPF中自治系统、主干和区域间的关系中自治系统、主干和区域间的关系外部网关路由选择协议外部网关路由选择协议外部网关协议普遍设计成能提供多种用于自治系统间外部网关协议普遍设计成能提供多种用于自治系统间通信的通信的路由策略路由策略，例如，例如边界网关协议边界网关协议BGP（Border Gateway Protocol）。）。路由策略基于政治、安全和经济等方面的考虑。为确路由策略基于政治、安全和经济等方面的考虑。为确保路由是适合的，一般由手工配置到每个路由器中。保路由是适合的，一般由手工配置到每个路由器中。BGP基本上是一个基本上是一个距离矢量协议距离矢量协议，与，与RIP不同的是每个不同的是每个BGP路由器记录所使用的确切路由，而不是每个目的路由器记录所使用的确切路由，而不是每个目的地的开销，并向邻居说明正在使用的确切路由。地的开销，并向邻居说明正在使用的确切路由。注意：这里没有无穷计算问题，因为每个路由器记录所注意：这里没有无穷计算问题，因为每个路由器记录所使用的确切路由。使用的确切路由。第五章习题第五章习题7，9，14，27，28，29，39，40，49，50