1、计计 算算 机机 网网 络络 COMPUTER NETWORKS第第7章章 网络层网络层学习本章方法学习本章方法n本章是本书最重要的一章本章是本书最重要的一章,其中其中7.5节是重中之重节是重中之重.1)算法着重理解算法着重理解,也可自己发明新的算法或改也可自己发明新的算法或改进已有的算法进已有的算法,并能根据现有的算法编写程序并能根据现有的算法编写程序 2)IP地址地址,子网的划分子网的划分,超网的构造超网的构造,路由选择路由选择n网络层是向传输层提供以下服务网络层是向传输层提供以下服务:n 路由选择路由选择n 拥塞控制拥塞控制n 网络互联网络互联第第7 章网络层章网络层nISO 定义定义n
2、 网络层为一个网络连接的两个传送实体间交换网络网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法，它使传送实体独服务数据单元提供功能和规程的方法，它使传送实体独立于路由选择和交换的方式。立于路由选择和交换的方式。n网络层与数据链路层的区别：网络层与数据链路层的区别：n 网络层是将网络层是将源端发出的分组经各种途径送到目的端源端发出的分组经各种途径送到目的端。n 而数据链路层仅将数据帧从传输介质的一端送到另而数据链路层仅将数据帧从传输介质的一端送到另一端。因此，网络层是处理一端。因此，网络层是处理端到端端到端数据传输的最低层。数据传输的最低层。n网络层要解决的关键问题网
3、络层要解决的关键问题n 了解通信子网的拓扑结构，选择路由。了解通信子网的拓扑结构，选择路由。7.2 路由算法路由算法n路由算法n 就是产生路由表的算法；n 是网络层软件的一部分。n 子网采用数据报方式，每个包都要做路由选择；n 子网采用虚电路方式，只需在建立连接时做一次n 路由选择。n理想的路由算法n 正确性（correctness）：算法必须正确；n 简单性（simplicity）：算法开销小，效率高；n 健壮性（robustness）：算法能适应网络负荷和拓朴的变化；n 稳定性（stability）：算法必须收敛，不能振荡发散；n振荡：算法得出的路由是在一些路由之间回荡。n 公平性（fai
4、rness）：算法对所有用户必须是平等的；n 最优性（optimality）：算法应提供最佳路径选择；n 最佳：链路长度、传输时延、数据速率、链路容量、链路n 差错率、链路丢失率等。n路由算法分类n 非自适应算法（静态路由算法）；n 简单、开销小，但不能适应网络状态变化；n 采用离线方式求出路由表。n 自适应算法（动态路由算法）；n 复杂、开销大，但能适应网络状态变化；7.2.17.2.1最优化原则（最优化原则（optimality principle）n 从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树（sink tree）；n 路由算法的目的是找出
5、并使用汇集树。最短路径路由算法最短路径路由算法n属于静态路由算法n基本思想 构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。n测量路径长度的方法n结点数量n地理距离n传输延迟n距离、信道带宽等参数的加权函数Dijkstra算法算法n 采用标注的方式求出某一结点的汇集树和路由表。采用标注的方式求出某一结点的汇集树和路由表。n每个结点用从源结点沿已知最佳路径到本结点的距离来标每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注；注，标注分为临时性标注和永久性标注；n初始时，所有结点都为临时性
6、标注，标注为无穷大；初始时，所有结点都为临时性标注，标注为无穷大；n将源结点标注为将源结点标注为0，且为永久性标注，并令其为工作结点；，且为永久性标注，并令其为工作结点；n检查与工作结点相邻的临时性结点，若该结点到工作结点检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点；算得到的和重新标注该结点；n在整个图中查找具有最小值的临时性标注结点，将其变为在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点；永久性结点，并成为下一轮检查的
7、工作结点；n 重复第重复第、步，直到所有结点成为工作结点；步，直到所有结点成为工作结点；请指出请指出AD最短路径最短路径Dijkstra算法算法程序程序7.2.37.2.3洪泛算法（也叫扩散算法）洪泛算法（也叫扩散算法）n属于静态路由算法属于静态路由算法n基本思想基本思想 把收到的每一个包，向除了该包到来的线路外的所有把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。输出线路发送。n主要问题主要问题 产生大量重复包，导致出现拥塞现象。产生大量重复包，导致出现拥塞现象。n解决措施解决措施 方法方法1：每个包头包含站点计数器（端到端的最大段：每个包头包含站点计数器（端到端的最大段数），每
8、经过一站计数器减数），每经过一站计数器减1，为，为0时则丢弃该包。时则丢弃该包。方法方法2：在每个节点建立一个登记表，凡经过此节点的：在每个节点建立一个登记表，凡经过此节点的进行登记，若再次经过该节点，丢弃该包。进行登记，若再次经过该节点，丢弃该包。n选择性扩散算法（选择性扩散算法（selective flooding）n扩散法的一种改进。扩散法的一种改进。n将进来的每个包仅发送到与正确方向接近的将进来的每个包仅发送到与正确方向接近的线路上。线路上。n应用情况应用情况n路由器和线路的资源过于浪费，实际很少直路由器和线路的资源过于浪费，实际很少直接采用；接采用；n具有很强的具有很强的健壮性健壮性
9、，常用于军用网；，常用于军用网；n作为衡量标准评价其它路由算法。作为衡量标准评价其它路由算法。7.2.47.2.4基于流量的路由算法基于流量的路由算法n属于静态路由算法n基本思想n既考虑拓扑结构，又兼顾网络负荷；n前提：每对结点间平均数据流相对稳定和可预测；n根据网络带宽和平均流量，可得出平均包延迟，因此路由选择问题归结为找产生网络最小延迟的路由选择算法;n提前离线计算。n需要预知的信息n网络拓扑结构；n通信量矩阵Fij，即线路ij之间的平均通信量。n线路带宽矩阵Cij，即线路ij 之间允许的最大通信量。n路由算法（可能是临时的）。7.2.57.2.5距离矢量路由算法距离矢量路由算法n属于动态
10、路由算法属于动态路由算法n 最初应用于最初应用于ARPANET，后来应用于因特网的，后来应用于因特网的RIP协议（路由信息协议）。协议（路由信息协议）。n基本思想基本思想n每个结点通过每个结点通过测取测取与相邻结点的距离，再依据与其与相邻结点的距离，再依据与其相邻结点交换的距离信息，间接地求出路由表；相邻结点交换的距离信息，间接地求出路由表；n各结点周期性地测取相邻结点的距离；各结点周期性地测取相邻结点的距离；n 向相邻结点发送它到每个目的结点的距离表，同向相邻结点发送它到每个目的结点的距离表，同时，它也接收每个邻居结点发来的距离表；时，它也接收每个邻居结点发来的距离表；n结点中的老路由表在计
11、算中不被使用。结点中的老路由表在计算中不被使用。n操作过程：每个路由器维护一张表，表中列出了到每个目的地操作过程：每个路由器维护一张表，表中列出了到每个目的地址的最佳距离和线路，并通过与邻居结点交换信息来更新表。址的最佳距离和线路，并通过与邻居结点交换信息来更新表。n表表(路由表路由表)的构成：以子网中其它路由器为表的索引，到达目的构成：以子网中其它路由器为表的索引，到达目的结点的最佳输出线路，和到达目的结点所需时间或距离。的结点的最佳输出线路，和到达目的结点所需时间或距离。n路由器需要知晓自己到邻居结点的路由器需要知晓自己到邻居结点的“距离距离”。所用的度量标准。所用的度量标准可以为站点、估
12、计的时间延迟等。可以为站点、估计的时间延迟等。n如果为站点，本路由器到每个邻居结点的距离都为如果为站点，本路由器到每个邻居结点的距离都为1。n如果是延迟，本路由器就发送一个要对方立即响应的如果是延迟，本路由器就发送一个要对方立即响应的ECHO分组，用来回时间除以分组，用来回时间除以2即得到延迟时间，即得到延迟时间，n每隔一段时间，路由器向所有邻居结点发送它到每个目的结点每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表。的距离表，同时它也接收每个邻居结点发来的距离表。n邻居结点邻居结点X发来的表中，发来的表中，X到路由器到路由器i的距离为的距离
13、为Xi。本路由器到。本路由器到X的距离为的距离为m，则本路由器经过，则本路由器经过X到到i的距离为的距离为Xi+m。根据。根据不同邻居发来的信息，计算不同邻居发来的信息，计算Xi+m，取最小值，更新本路由，取最小值，更新本路由器的表。器的表。n注意：在计算中不使用本路由器中的老路由表。注意：在计算中不使用本路由器中的老路由表。路由器路由器J计算到达计算到达路由器路由器C的最新的最新路由路由JAC=8+25=33msJIC=10+18=28msJHC=12+19=31msJKC=6+36=42ms其中其中JIC是最好的。是最好的。因此在路由器因此在路由器J的的新路由表中填上新路由表中填上到到C的
14、延迟为的延迟为28ms，经过路，经过路由器由器I。距离向量路由算法的缺陷距离向量路由算法的缺陷n缺陷缺陷无穷计算问题无穷计算问题n对好消息反应迅速：在最长路径为对好消息反应迅速：在最长路径为N各结点的子网中，各结点的子网中，在在N次交换之内，所有的路由器都会指导新增的线路和次交换之内，所有的路由器都会指导新增的线路和路由器。路由器。n对坏消息反应迟钝：对于已经消失的结点，相互欺骗。对坏消息反应迟钝：对于已经消失的结点，相互欺骗。n图例如下图例如下。n水平分裂算法基本思想水平分裂算法基本思想n工作过程与距离向量算法相同，区别在于到工作过程与距离向量算法相同，区别在于到X的距离不的距离不向真正通向
15、向真正通向X的邻居结点报告。从而使得坏消息以每次的邻居结点报告。从而使得坏消息以每次一个结点的速度传播。一个结点的速度传播。n举例：如右图。举例：如右图。n在路由信息的交换中，在路由信息的交换中，B知道可以直达知道可以直达A，并告诉，并告诉C，通过通过B到到C路径为路径为1。C得到得到B发来的路由信息后，告诉发来的路由信息后，告诉D通过通过C到达到达A距离为距离为2，告诉，告诉B通过通过C到达到达A为无穷。为无穷。D得到得到C发来的路由信息后，告诉发来的路由信息后，告诉E通过通过D到达到达A距离为距离为3，告诉，告诉C通过通过D到达到达A为无穷。为无穷。n当当A下网后，下网后，第一次交换：第一
16、次交换：B发现到达发现到达A的直达路线没有了，而且的直达路线没有了，而且C也向也向B说说到达到达A为无穷，故为无穷，故B将其到达将其到达A的距离设置为无穷。的距离设置为无穷。第二次交换：第二次交换：C得到得到B的通知，的通知，B到达到达A为无穷；同时为无穷；同时D也告诉也告诉C，通过，通过D到达到达A为无穷，故为无穷，故C将其到达将其到达A的距离设置为无穷。的距离设置为无穷。以次类推，在第四次交换的时候，以次类推，在第四次交换的时候，E也知道也知道A不可达了。不可达了。解决方案之一水平分裂解决方案之一水平分裂A B C D E水平分裂不能解决所有的问题水平分裂不能解决所有的问题n水平分裂虽然广
17、泛使用，但有时候会失败。水平分裂虽然广泛使用，但有时候会失败。n如右图如右图。n开始时，开始时，A和和B到到D的举例都为的举例都为2，C到到D的举例为的举例为1。n假设假设CD线路断了，使用水平分裂，线路断了，使用水平分裂，A和和B都告诉都告诉C，它们不能到达，它们不能到达D，同时，同时C自己也发现直达自己也发现直达D的线路断了，于是的线路断了，于是C很快认定很快认定D不可达了。不可达了。n但是，但是，A认为认为B有一条通向有一条通向D长度为长度为2的的路径，通过路径，通过B经过经过3个结点可到达个结点可到达D。类似，类似，B也这样认为。于是两个结点每也这样认为。于是两个结点每交换一次信息，到
18、达交换一次信息，到达D的距离就增加的距离就增加1，直至加大无穷。直至加大无穷。7.2.6链路状态路由算法链路状态路由算法n距离向量路由算法的主要问题距离向量路由算法的主要问题n由于延迟度量仅仅是队列长度，在选择路由时没有考由于延迟度量仅仅是队列长度，在选择路由时没有考虑线路带宽。虑线路带宽。n即使使用了水平分裂，路由收敛速度依然慢。即使使用了水平分裂，路由收敛速度依然慢。n在在1979年前，年前，ARPANET上都采用距离向量路由算法，上都采用距离向量路由算法，但是之后，即为链路状态路由算法所替代。但是之后，即为链路状态路由算法所替代。n链路状态路由算法的简单步骤链路状态路由算法的简单步骤n发
19、现邻居结点，并学习它们的网络地址。发现邻居结点，并学习它们的网络地址。n测量到每个邻居结点的延迟或开销。测量到每个邻居结点的延迟或开销。n将所有学习到的内容封装成一个分组。将所有学习到的内容封装成一个分组。n将这个分组发送给所有其它路由器。将这个分组发送给所有其它路由器。n计算到每个其它路由器的最短路径。计算到每个其它路由器的最短路径。步骤步骤1：发现邻居结点：发现邻居结点n发现邻居结点，并学习它们的网络地址。发现邻居结点，并学习它们的网络地址。n路由器启动后，通过发送路由器启动后，通过发送HELLO分组，并得到邻居路由器的响分组，并得到邻居路由器的响应来发现邻居结点。应来发现邻居结点。n路由
20、器的名称必须是唯一的。路由器的名称必须是唯一的。n当两个或多个路由器连在一个当两个或多个路由器连在一个LAN时，引入人工结点。时，引入人工结点。n图例图例。步骤步骤2/3：测量线路开销和封装分组：测量线路开销和封装分组n测量到每个邻居结点的延迟或开销，一种直接的方法是：发测量到每个邻居结点的延迟或开销，一种直接的方法是：发送一个要对方立即响应的送一个要对方立即响应的ECHO分组，来回时间除以分组，来回时间除以2即为即为延迟时间。延迟时间。n如果在测量延迟时间的时候，考虑负载，会是什么情况？如果在测量延迟时间的时候，考虑负载，会是什么情况？n将所有学习到的内容封装成一个分组，即在信息收集完毕后，
21、将所有学习到的内容封装成一个分组，即在信息收集完毕后，构造一个包含所有数据的分组。构造一个包含所有数据的分组。n该分组的结构为：发送方的标识符、序号、年龄、邻居结点该分组的结构为：发送方的标识符、序号、年龄、邻居结点列表（邻居结点标识符，线路开销值）。列表（邻居结点标识符，线路开销值）。n创建链路状态分组的时机：一是定期创建，一是在发生重大创建链路状态分组的时机：一是定期创建，一是在发生重大事件后创建。事件后创建。步骤步骤4：发布链路状态分组：发布链路状态分组n链路状态分组的发布算法链路状态分组的发布算法n基本思想：洪泛链路状态分组。基本思想：洪泛链路状态分组。n为控制洪泛，每个分组中增加一个
22、序号域，每次发送为控制洪泛，每个分组中增加一个序号域，每次发送新分组时加新分组时加1。n路由器记录信息对路由器记录信息对(源路由器，序号源路由器，序号)，当一个链路状，当一个链路状态分组到达时，若是新的，则分发；若是重复的，则态分组到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃。过时而丢弃。n基本算法所产生的问题基本算法所产生的问题n序号循环使用会混淆。序号循环使用会混淆。n路由器崩溃后，所有的序号丢失，从路由器崩溃后，所有的序号丢失，从0开始记，以后开始记，以后所有的新到分组都可能被当作重复分组而
23、被拒绝。所有的新到分组都可能被当作重复分组而被拒绝。n序号在发送出去后出现错误。序号在发送出去后出现错误。步骤步骤4：发布链路状态分组：发布链路状态分组n基本算法的改进方案基本算法的改进方案n为了避免序号重复，使用为了避免序号重复，使用32位的序号。位的序号。n解决序号丢失和出错的方法是增加年龄解决序号丢失和出错的方法是增加年龄(age)域，每域，每秒钟年龄减秒钟年龄减1，至零则丢弃。，至零则丢弃。n链路状态分组到达后，延迟一段时间链路状态分组到达后，延迟一段时间(被放置在一个保被放置在一个保持区中持区中)，并与其它已到达的来自同一路由器的链路状，并与其它已到达的来自同一路由器的链路状态分组比
24、较序号，丢弃重复分组和超龄分组。态分组比较序号，丢弃重复分组和超龄分组。n为了防止链路出错，所有的链路状态分组都需要应答。为了防止链路出错，所有的链路状态分组都需要应答。步骤步骤5：计算新路由：计算新路由n在路由器积累了一整套网络的链路状态分在路由器积累了一整套网络的链路状态分组后，就可以通过计算得到整个网络的结组后，就可以通过计算得到整个网络的结构。可以利用构。可以利用Dijkstra算法计算得到每个算法计算得到每个其它路由器的最短路径。其它路由器的最短路径。n基于链路状态的路由协议基于链路状态的路由协议nOpen Shortest Path First(OSPF)nIntermediate
25、 System-Intermediate System(IS-IS)7.2.7分层路由分层路由n网络规模增长带来的问题网络规模增长带来的问题n路由器中的路由表增大。路由器中的路由表增大。n路由器为选择路由而占用的内存、路由器为选择路由而占用的内存、CPU时间和网络带时间和网络带宽增大。宽增大。n解决办法解决办法 分层路由分层路由n对于大型网络分而治之，每个路由器只知道自己所在对于大型网络分而治之，每个路由器只知道自己所在子网的路由信息，而不去了解其他子网的内部结构。子网的路由信息，而不去了解其他子网的内部结构。n根据需要，可以分成区域根据需要，可以分成区域(regions)、聚类、聚类(clu
26、sters)、区、区(zones)和组和组(groups)n图例。图例。n分级路由带来的问题分级路由带来的问题n路由表中的路由不一定是最优路由。路由表中的路由不一定是最优路由。分级路由图例分级路由图例小结小结 路由算法路由算法n最优化原则最优化原则n路由算法的目的是找出并使路由算法的目的是找出并使用汇集树。用汇集树。n最短路径路由算法最短路径路由算法n目的是构建两个路由器间的目的是构建两个路由器间的路由，算法是在子网拓扑图路由，算法是在子网拓扑图中找出最短路径。中找出最短路径。Dijkstra算法。算法。n洪泛算法洪泛算法n把收到的每一个分组，向除把收到的每一个分组，向除了该分组到来的线路外的
27、所了该分组到来的线路外的所有输出线路发送。有输出线路发送。n基于流量的路由算法基于流量的路由算法n根据网络带宽和平均流量，根据网络带宽和平均流量，可得出平均延迟，因此路由可得出平均延迟，因此路由问题归结为找产生网络最小问题归结为找产生网络最小延迟的路由算法。延迟的路由算法。n距离向量路由算法距离向量路由算法n根据两个结点间的队列长度根据两个结点间的队列长度来完成路由选择，但是最大来完成路由选择，但是最大的问题是无穷计算，而且水的问题是无穷计算，而且水平分裂也不能完全解决所有平分裂也不能完全解决所有的问题。的问题。n链路状态路由算法链路状态路由算法n发现邻居结点发现邻居结点n测量线路开销测量线路
28、开销n将所有学习到的内容封装成将所有学习到的内容封装成一个分组一个分组n发布链路状态信息发布链路状态信息n计算新路由计算新路由n分级路由分级路由n对于大型网络分而治之，每对于大型网络分而治之，每个路由器只知道自己所在子个路由器只知道自己所在子网的路由信息，而不去了解网的路由信息，而不去了解其他子网的内部结构。其他子网的内部结构。7.3 拥塞控制算法拥塞控制算法n拥塞（congestion）n 网络资源上有太多的分组时，导致性能会下降。n对资源的需求 可用资源n资源：链路容量、交换结点中的缓存和处理机等。n拥塞产生的原因n 结点缓存容量太小；多个输入对应一个输出；n 结点处理机速度不高；n 低带
29、宽线路；针对某个因素改善拥塞针对某个因素改善拥塞n若结点缓存容量太小，到达结点的分组无空间暂存;n若增大结点缓存容量，而链路容量和处理机速度未提高，分组排队会很长，导致时延增大，可能因超时发送端进行重发，拥塞更加恶化；n提高结点处理机速度，增大链路容量，固然可以改善拥塞，但可能瓶颈转移到其它地方。n 因此，针对某个因素的解决方案，只能对提高网络性能起到一定的好处，甚至仅仅是转移了影响性能的瓶颈。拥塞控制与流量控制的差别拥塞控制与流量控制的差别n拥塞控制（congestion control）n需要确保通信子网能够承载用户提交的通信量，是一个全局性过程，涉及主机、路由器等很多因素；n流量控制（f
30、low control）n与点到点的通信量有关，主要解决快速发送方与慢速接收方的问题，是局部过程，一般都是基于反馈进行控制的。拥塞控制的分类拥塞控制的分类n根据控制论，拥塞控制可分为两类。根据控制论，拥塞控制可分为两类。n开环控制开环控制(防患于未然防患于未然)n通过良好的设计解决问题，以避免拥塞发生。一旦运行，就通过良好的设计解决问题，以避免拥塞发生。一旦运行，就不再做中间阶段的更正。不再做中间阶段的更正。n进行开环控制的工具需要决定何时接收新的分组、何时丢弃进行开环控制的工具需要决定何时接收新的分组、何时丢弃分组、丢弃哪些分组，制定网络中不同地点的计划表等。利分组、丢弃哪些分组，制定网络中
31、不同地点的计划表等。利用开环进行拥塞控制时，所有这些操作都不会考虑网络的当用开环进行拥塞控制时，所有这些操作都不会考虑网络的当前状态。前状态。n闭环控制闭环控制(因地制宜因地制宜)n基于反馈机制。其工作过程为：基于反馈机制。其工作过程为：监控系统，发现何时何地发生拥塞。监控系统，发现何时何地发生拥塞。把发生拥塞的消息传给能采取动作的站点。把发生拥塞的消息传给能采取动作的站点。调整系统操作，解决拥塞问题。调整系统操作，解决拥塞问题。n闭环控制操作需要完成以下三个问题：何为拥塞、如何反馈闭环控制操作需要完成以下三个问题：何为拥塞、如何反馈和如何解决。和如何解决。闭环控制闭环控制n何为拥塞何为拥塞
32、衡量网络拥塞的参数衡量网络拥塞的参数n缺乏缓冲区造成的丢包率缺乏缓冲区造成的丢包率n平均队列长度平均队列长度n超时重传的分组数目超时重传的分组数目n平均分组延迟平均分组延迟n分组延迟变化分组延迟变化(Jitter)n如何反馈如何反馈 反馈方法反馈方法n向负载的发生源发送一个报警分组，这同时加强了拥塞。向负载的发生源发送一个报警分组，这同时加强了拥塞。n在分组结构中保留一个位或一个域来表示发生拥塞，一旦发生拥在分组结构中保留一个位或一个域来表示发生拥塞，一旦发生拥塞，路由器将所有输出分组的拥塞位填充，报警。塞，路由器将所有输出分组的拥塞位填充，报警。n主机或路由器主动地、周期性地发送探报主机或路
33、由器主动地、周期性地发送探报(probe)，查询是否，查询是否发生拥塞。发生拥塞。n如何解决如何解决 利用拥塞控制算法利用拥塞控制算法开环控制开环控制 拥塞预防策略拥塞预防策略n影响拥塞的网络设计影响拥塞的网络设计策略策略n数据链路层数据链路层 重传、乱序缓存、重传、乱序缓存、确认、流控确认、流控n网络层网络层 子网中的虚电路和子网中的虚电路和数据报、分组排队数据报、分组排队和服务策略、分组和服务策略、分组丢弃策略、路由算丢弃策略、路由算法、分组的生存时法、分组的生存时间管理间管理n传输层传输层 重传、乱序缓存、重传、乱序缓存、确认、流控、超时确认、流控、超时中止中止开环控制开环控制 通信量整
34、形通信量整形n通信量整形通信量整形(Traffic Shaping)的基本思想的基本思想n网络上，突发的通信量是造成拥塞的主要原因。网络上，突发的通信量是造成拥塞的主要原因。n强迫分组以某种可以预见的速率传送，减少拥塞，这种方法就被强迫分组以某种可以预见的速率传送，减少拥塞，这种方法就被称为通信量整形。称为通信量整形。n此方法广泛应用于此方法广泛应用于ATM网络中。网络中。n漏桶算法和令牌桶算法都可以实现通信量整形。漏桶算法和令牌桶算法都可以实现通信量整形。n漏桶算法漏桶算法(The Leaky Bucket Algorithm)n基本原理：基本原理：n在计算机中的使用在计算机中的使用 漏桶漏
35、桶有限内部队列；水有限内部队列；水 通信量，需要发送的分组。通信量，需要发送的分组。分组到达队列时，队列满，分组被丢弃；队列空，分组放置在队尾。分组到达队列时，队列满，分组被丢弃；队列空，分组放置在队尾。n效果效果 将用户发出的不平滑的分组流转变成网络中平滑的分组流。将用户发出的不平滑的分组流转变成网络中平滑的分组流。漏桶算法既可以用于分组长度固定的协议，如漏桶算法既可以用于分组长度固定的协议，如ATM，使用分组计数；，使用分组计数；也可用于可变长分组的协议，如也可用于可变长分组的协议，如IP，使用字节计数。，使用字节计数。无论水流进桶的速度为多少，只要桶中有水，水从桶中外漏的速度是恒定的。桶
36、空了，速度为零。桶满了，水外泄。令牌桶算法令牌桶算法n由于漏桶算法不够灵活，由于漏桶算法不够灵活，因此加入令牌机制。因此加入令牌机制。n令牌桶算法令牌桶算法(The Token Bucket Algorithm)n基本思想：漏桶存基本思想：漏桶存放令牌，每放令牌，每 T秒产秒产生一个生一个令牌，分组令牌，分组发送传输之前必须发送传输之前必须获得一个令牌，传获得一个令牌，传输之后删除该令牌。输之后删除该令牌。n令牌代表的不是发令牌代表的不是发送一个分组的权利，送一个分组的权利，而是可以发送的字而是可以发送的字节数。节数。小结小结 拥塞控制算法拥塞控制算法n拥塞控制的基本原理拥塞控制的基本原理n网
37、络中存在过多分组的时候，网络性能降低，产生拥塞。网络中存在过多分组的时候，网络性能降低，产生拥塞。n开环控制开环控制(通过良好的设计解决问题通过良好的设计解决问题)拥塞预防策略：数据链路层、网络层、传输层都策略可以进行预防拥塞预防策略：数据链路层、网络层、传输层都策略可以进行预防 通信量整形通信量整形 强迫分组以某种可以预见的速率传送。强迫分组以某种可以预见的速率传送。漏桶和令牌桶均可实现通信量整形。漏桶和令牌桶均可实现通信量整形。流说明流说明n闭环控制闭环控制 虚电路网络中的拥塞控制虚电路网络中的拥塞控制 许可控制、绕开拥塞、资源预留许可控制、绕开拥塞、资源预留 抑制分组：向源主机发送抑制分
38、组。抑制分组：向源主机发送抑制分组。为了公平，可以采用加权公平算法为了公平，可以采用加权公平算法(字节轮巡字节轮巡)。为了得到快速的抑制效果，可采用为了得到快速的抑制效果，可采用Hop-by-Hop抑制分组，抑抑制分组，抑制分组对其所经过的路由器都起作用。制分组对其所经过的路由器都起作用。负载丢弃：对不同服务采用不同的丢弃策略。负载丢弃：对不同服务采用不同的丢弃策略。7.4 网络互联网络互联n互联网（internet）：两个或多个网络构成互联网。n因特网（Internet）：是互联网的著名例子。网络互联示例网络互联示例n多种不同网络（协议）存在的原因n历史原因：不同公司的网络产品大量使用；n价
39、格原因：网络产品价格低，更多的人有权决定使用何种网络；n技术原因：不同网络采用不同技术、不同硬件、不同协议。n网络互联要解决的问题n不同的寻址方式、不同的最大分组长度；n不同的超时控制、不同的路由选择技术；n不同的差错控制、不同的网络接入机制；n不同的管理方式、不同的网络计费方式；n不同的服务（面向连接服务和无连接服务）；网络互联设备网络互联设备(P130)(P130)图 7-14 OSI各层使用的中继系统问：交换机是ISO哪层设备？路由器与交换机的主要区别体现在以下几个方面：路由器与交换机的主要区别体现在以下几个方面：（1）工作层次不同）工作层次不同 最初的的交换机是工作在数据链路层，也就是
40、第最初的的交换机是工作在数据链路层，也就是第二层，而路由器一开始就设计工作在网络层。由于交二层，而路由器一开始就设计工作在网络层。由于交换机工作在换机工作在OSI的第二层（数据链路层），所以它的的第二层（数据链路层），所以它的工作原理比较简单，而路由器工作在工作原理比较简单，而路由器工作在OSI的第三层的第三层（网络层），可以得到更多的协议信息，路由器可以（网络层），可以得到更多的协议信息，路由器可以做出更加智能的转发决策。做出更加智能的转发决策。（2）数据转发所依据的对象不同）数据转发所依据的对象不同 交换机是利用交换机是利用物理地址物理地址或者说或者说MAC地址来确定转地址来确定转发数据的
41、目的地址。而路由器则是利用不同网络的发数据的目的地址。而路由器则是利用不同网络的ID号（即号（即IP地址）来确定数据转发的地址。地址）来确定数据转发的地址。IP地址是在地址是在软件中实现的，描述的是设备所在的网络，有时这些软件中实现的，描述的是设备所在的网络，有时这些第三层的地址也称为协议地址或者第三层的地址也称为协议地址或者网络地址网络地址。MAC地地址通常是硬件自带的，由网卡生产商来分配的，而且址通常是硬件自带的，由网卡生产商来分配的，而且已经固化到了网卡中去，一般来说是不可更改的。而已经固化到了网卡中去，一般来说是不可更改的。而IP地址则通常由地址则通常由网络管理网络管理员或系统自动分配
42、。员或系统自动分配。（3）传统的交换机只能分割）传统的交换机只能分割冲突域冲突域，不能分割广播域；，不能分割广播域；而路由器可以分割广播域而路由器可以分割广播域 由交换机连接的网段仍属于同一个广播域，广播由交换机连接的网段仍属于同一个广播域，广播数据包会在交换机连接的所有网段上传播，在某些情数据包会在交换机连接的所有网段上传播，在某些情况下会导致通信拥挤和安全漏洞。连接到路由器上的况下会导致通信拥挤和安全漏洞。连接到路由器上的网段会被分配成不同的广播域，广播数据不会穿过路网段会被分配成不同的广播域，广播数据不会穿过路由器。虽然第三层以上交换机具有由器。虽然第三层以上交换机具有VLAN功能，也可
43、功能，也可以分割广播域，但是各子广播域之间是不能通信交流以分割广播域，但是各子广播域之间是不能通信交流的，它们之间的交流仍然需要路由器。的，它们之间的交流仍然需要路由器。（4）路由器提供了防火墙的服务）路由器提供了防火墙的服务 路由器仅仅转发特定地址的数据包，不传送不支路由器仅仅转发特定地址的数据包，不传送不支持持路由协议路由协议的数据包传送和未知目标网络数据包的传的数据包传送和未知目标网络数据包的传送，从而可以防止广播风暴。送，从而可以防止广播风暴。如果是考试用的：路由器是三层，交换机是二层，核如果是考试用的：路由器是三层，交换机是二层，核心交换机三层心交换机三层 7.4.1网络互联方法网络
44、互联方法 级联虚电路级联虚电路n级联虚电路级联虚电路(Concatenated Virtual Circuits)的工的工作过程作过程n建立连接建立连接 当目的主机不在本子网内时，则在子网内找一个离目的网络最当目的主机不在本子网内时，则在子网内找一个离目的网络最近的路由器，与之建立一条虚电路；该路由器与外部网关建立近的路由器，与之建立一条虚电路；该路由器与外部网关建立虚电路；该网关与下一个子网中的一个路由器建立虚电路。虚电路；该网关与下一个子网中的一个路由器建立虚电路。重复上述操作，直到到达目的主机。重复上述操作，直到到达目的主机。n传输数据传输数据 相同连接的分组相同连接的分组沿同一虚电路按
45、沿同一虚电路按照顺序传输；照顺序传输；网关根据需要转网关根据需要转换分组格式和虚换分组格式和虚电路号。电路号。n拆除连接拆除连接7.4.2网络互联方法网络互联方法 无连接网络互联无连接网络互联(数据报模型数据报模型)n无连接网络互联无连接网络互联(Connectionless Internetworking)的工的工作过程作过程n无连接网络互联的工作过程与数据报子网的工作过程相似。无连接网络互联的工作过程与数据报子网的工作过程相似。n每个分组独立路由，不保证分组按顺序到达，提高网络利用每个分组独立路由，不保证分组按顺序到达，提高网络利用率率。其中，连接不同子网的多协议路由器做协议转换，包括。其
46、中，连接不同子网的多协议路由器做协议转换，包括分组格式转换和地址转换等。分组格式转换和地址转换等。级连虚电路与无连接网络互联的比较级连虚电路与无连接网络互联的比较n级连虚电路级连虚电路n优点优点 路由器预留缓冲区等资源，保证服务质量。路由器预留缓冲区等资源，保证服务质量。分组按序号传输。分组的报文头部较短。分组按序号传输。分组的报文头部较短。n缺点缺点 路由器需要大量内存存储虚电路信息。路由器需要大量内存存储虚电路信息。一旦发生拥塞，没有其它路由，健壮性差。一旦发生拥塞，没有其它路由，健壮性差。如果网络中有一个不可靠的数据报子网，级连虚电路很难实现。如果网络中有一个不可靠的数据报子网，级连虚电
47、路很难实现。n无连接网络互联无连接网络互联n优点优点 能够容忍拥塞，并能适应拥塞。能够容忍拥塞，并能适应拥塞。健壮性好。健壮性好。可用于多种网络互联。可用于多种网络互联。n无连接网络互联的缺点无连接网络互联的缺点 分组的报文头部较长。分组的报文头部较长。不能保证分组按序号到达。不能保证分组按序号到达。不能保证服务质量。不能保证服务质量。7.4.3网络互联方法网络互联方法 隧道技术隧道技术(为了将两个不同的网络相互连接起来为了将两个不同的网络相互连接起来)n路由器路由器1剥掉局域网帧头、帧剥掉局域网帧头、帧尾，将得到的尾，将得到的IP分组封装到广分组封装到广域网帧中域网帧中(如如PPP)，IP地
48、址地址不变，帧地址不变，帧地址=路由器路由器2-帧帧地址；地址；n广域网传输；广域网传输；n路由器路由器2剥掉广域网帧头、帧剥掉广域网帧头、帧尾，将得到的尾，将得到的IP分组封装到局分组封装到局域网帧中，域网帧中，IP地址不变，帧地地址不变，帧地址址=主机主机2-MAC地址；地址；n局域网传输；局域网传输；n主机主机2接收。接收。n如果源和目的主机所在网络类型如果源和目的主机所在网络类型相同相同，但连接它们的是一个不同类型，但连接它们的是一个不同类型的网络，可采用隧道技术的网络，可采用隧道技术(Tunneling)。n隧道技术的工作过程隧道技术的工作过程n主机主机1构造一个分组，构造一个分组，
49、IP地址地址=主机主机2-IP，将分组封装到局域，将分组封装到局域网帧中，帧地址网帧中，帧地址=路由器路由器1-MAC；n局域网传输；局域网传输；7.4.4网络互联方法网络互联方法 互联网路由互联网路由n互联网路由互联网路由(Internetwork Routing)的工作过程的工作过程n互联网络的路由与单独子网的路由过程相似，只是更复杂。互联网络的路由与单独子网的路由过程相似，只是更复杂。n一般使用两级路由算法：一般使用两级路由算法：内部网关协议内部网关协议(interior gateway protocol)：RIP，OSPF 外部网关协议外部网关协议(exterior gateway p
50、rotocol)：BGP 自治系统自治系统AS(Autonomous System)：使用统一算法的一个网：使用统一算法的一个网络。络。7.4.5网络互联方法网络互联方法 分段分段(如何把大的分组传向小的分组目标网络如何把大的分组传向小的分组目标网络)n每种网络都对分组的最大长度有限制，因为：每种网络都对分组的最大长度有限制，因为：n硬件要求。硬件要求。n操作系统，例如所有缓冲区都是操作系统，例如所有缓冲区都是512字节。字节。n协议，例如分组长度域的比特数。协议，例如分组长度域的比特数。n与标准的兼容性；与标准的兼容性；n希望减少传输出错的概率。希望减少传输出错的概率。n希望避免一个分组占用
