第4章 网络层.ppt

《第4章 网络层.ppt》由会员分享，可在线阅读，更多相关《第4章 网络层.ppt（171页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章网络层网络层主讲人主讲人陈慧陈慧学习目的和要求学习目的和要求n本章介绍网络层的内容，网络层设计的是将本章介绍网络层的内容，网络层设计的是将源端发出的分组经过各种途径传送到目的端，源端发出的分组经过各种途径传送到目的端，在数据链路层提供的两个相邻节点之间的数在数据链路层提供的两个相邻节点之间的数据帧的传输功能上，进一步管理网络中的数据帧的传输功能上，进一步管理网络中的数据通信，将数据从源端经过若干中间节点传据通信，将数据从源端经过若干中间节点传送到目的端。网络层是送到目的端。网络层是OSI模型中面向数据模型中面向数据通信的底三层中最为复杂、关键的一层。通信的底三层中最为复杂、关键的一

2、层。网络层网络层n5.1通信子网的操作方式和网络层提供的服通信子网的操作方式和网络层提供的服务务n5.2路由选择路由选择n5.3拥塞控制拥塞控制n5.4服务质量服务质量n5.5网络互连网络互连n5.6因特网的互连层协议因特网的互连层协议通信子网的操作方式和网络层通信子网的操作方式和网络层提供的服务提供的服务n考核要求：考核要求：n领会：网络层的功能领会：网络层的功能n领会：通信子网的两种操作方式：虚电路和数据领会：通信子网的两种操作方式：虚电路和数据报，两种操作所提供的两种服务，两种子网的比报，两种操作所提供的两种服务，两种子网的比较。较。网络层的功能网络层的功能n网络层是网络层是OSI参考模

3、型中的第三层参考模型中的第三层n网络层关系到通信子网的运行控制，体现了网络层关系到通信子网的运行控制，体现了网络应用环境中资源子网访问通信子网的方网络应用环境中资源子网访问通信子网的方式，是式，是OSI模型中面向数据通信的低三层模型中面向数据通信的低三层(也也即通信子网即通信子网)中最为复杂、关键的一层。中最为复杂、关键的一层。n网络层的目的是实现两个端系统之间的数据网络层的目的是实现两个端系统之间的数据透明传送，具体功能包括路由选择、阻塞控透明传送，具体功能包括路由选择、阻塞控制和网际互连等制和网际互连等。5.1通信子网的操作方式和网络通信子网的操作方式和网络层提供的服务层提供的服务n端点之

4、间的通信是依靠通信子网中的节点间端点之间的通信是依靠通信子网中的节点间的通信来实现的的通信来实现的n在分组交换方式中，通信子网向端系统提供在分组交换方式中，通信子网向端系统提供虚电路和数据报两种网络服务，而通信子网虚电路和数据报两种网络服务，而通信子网内部的操作也有虚电路和数据报两种方式。内部的操作也有虚电路和数据报两种方式。n通信子网的操作方式：虚电路操作方式和数据报通信子网的操作方式：虚电路操作方式和数据报操作方式操作方式n网络层提供的服务：虚电路服务和数据报服务网络层提供的服务：虚电路服务和数据报服务5.1.1虚电路操作方式虚电路操作方式n网络的源节点和目的节点之间先要建立一条逻辑通网络

5、的源节点和目的节点之间先要建立一条逻辑通路，因为这条逻辑通路不是专用的，所以称之为路，因为这条逻辑通路不是专用的，所以称之为“虚虚”电路。电路。n节点间的物理信道在逻辑上均可看做由多条逻辑信节点间的物理信道在逻辑上均可看做由多条逻辑信道组成，这些逻辑信道实际上由节点内部的道组成，这些逻辑信道实际上由节点内部的分组缓分组缓冲器冲器来实现。来实现。n不同的逻辑信道在节点内部通过不同的逻辑信道在节点内部通过逻辑信道号逻辑信道号加以区加以区分，各条逻辑信道分，各条逻辑信道异步分时复用异步分时复用同一条物理信道同一条物理信道。n各节点内部必须建立一张各节点内部必须建立一张虚电路表虚电路表，用以记录该点，

6、用以记录该点的各条虚电路所占用的各个逻辑信号。的各条虚电路所占用的各个逻辑信号。相关名词相关名词H1H5H2H4H3ACDBH6E分组交换网端系统端系统节点节点虚电路虚电路逻辑信道逻辑信道物理信道物理信道虚虚电路的特点电路的特点n一条一条物理链路可以对应多条逻辑信道物理链路可以对应多条逻辑信道n一条虚电路由各物理链路上的逻辑信道级联一条虚电路由各物理链路上的逻辑信道级联而成，占用了节点上的一条逻辑信道实际上而成，占用了节点上的一条逻辑信道实际上就是占用了该节点上的分组缓冲器就是占用了该节点上的分组缓冲器n分组靠逻辑信道号选择路由，因逻辑信道号分组靠逻辑信道号选择路由，因逻辑信道号只有局部意义，

7、所以减少了分组头部的开销只有局部意义，所以减少了分组头部的开销和处理的复杂度和处理的复杂度一个虚电路表建立一个虚电路表建立n各节点的虚电路表是在虚电路建立过程中建立的。各节点的虚电路表是在虚电路建立过程中建立的。n第一步：源端系统可发出一个呼叫请求分组，该分组除了包含目的地第一步：源端系统可发出一个呼叫请求分组，该分组除了包含目的地址外，还包含源端系统所选取的不用的最小逻辑信道号址外，还包含源端系统所选取的不用的最小逻辑信道号N。n第二步：第二步：A节点收到请求分组后，在节点收到请求分组后，在A节点与下一节点节点与下一节点B间所有已使用间所有已使用的逻辑信道号之外，选取一个最小编号的逻辑信道号

8、之外，选取一个最小编号NA，并将请求分组中的逻辑信并将请求分组中的逻辑信道号道号N替换成该逻辑信道号替换成该逻辑信道号NA，再将分组发送给节点再将分组发送给节点B。n中间：此后的各节点依次逐个根据自身实际情况，选取新的逻辑信道中间：此后的各节点依次逐个根据自身实际情况，选取新的逻辑信道号号(如如NB、NC、ND等等)来替换收到的分组中的逻辑信道号。来替换收到的分组中的逻辑信道号。n最后：目的节点将请求分组传送给连接它的端系统。最后：目的节点将请求分组传送给连接它的端系统。n每个节点的虚电路表中要记录两个逻辑信道：前一个节点所每个节点的虚电路表中要记录两个逻辑信道：前一个节点所选取的逻辑信道号和

9、本节点所选取的逻辑信道号。选取的逻辑信道号和本节点所选取的逻辑信道号。虚电路建立示例虚电路建立示例5.1.2数据报操作方式数据报操作方式n在数据报操作方式中，每个分组被称为一个数据报，在数据报操作方式中，每个分组被称为一个数据报，若干个数据报构成一次要传送的报文或数据块。每若干个数据报构成一次要传送的报文或数据块。每个数据报自身携带有足够的信息，它的传送是被单个数据报自身携带有足够的信息，它的传送是被单独处理的。独处理的。n发送一个报文时，将报文拆成若干个带有序号和地发送一个报文时，将报文拆成若干个带有序号和地址信息的数据报，依次发给网络节点。址信息的数据报，依次发给网络节点。n各个数据报所走

10、的路径就可能不同，网络节点要为各个数据报所走的路径就可能不同，网络节点要为每个数据报做路由选择。每个数据报做路由选择。数据报的特点数据报的特点n每个分组的寻路是独立的，可以合理利用网络资源每个分组的寻路是独立的，可以合理利用网络资源n如果途中一个节点或一条链路发生故障，能给分组如果途中一个节点或一条链路发生故障，能给分组重选路由重选路由n分组头需要包含地址字段，也会增加开销分组头需要包含地址字段，也会增加开销n各分组途经的路径可能不同，因此有可能出现先发各分组途经的路径可能不同，因此有可能出现先发后到现象后到现象5.1.3虚电路服务虚电路服务n虚电路服务是网络层向传输层提供的一种使虚电路服务是

11、网络层向传输层提供的一种使所有分组按顺序到达目的端系统的可靠的数所有分组按顺序到达目的端系统的可靠的数据传送方式。据传送方式。nOSI中面向连接的网络服务就是虚电路服务。中面向连接的网络服务就是虚电路服务。n虚电路的服务是网络层向传输层提供的服务，虚电路的服务是网络层向传输层提供的服务，也是通信子网端向系统提供的网络服务。也是通信子网端向系统提供的网络服务。虚电路服务的实际操作虚电路服务的实际操作n提供这种虚电路服务的通信子网内部的实际操作既提供这种虚电路服务的通信子网内部的实际操作既可是虚电路方式的，也可以是数据报方式的。可是虚电路方式的，也可以是数据报方式的。n以虚电路操作方式的网络，一般

12、总是提供虚电路服以虚电路操作方式的网络，一般总是提供虚电路服务。务。nSNA就是采用这种虚电路操作支持虚电路服务方式的实就是采用这种虚电路操作支持虚电路服务方式的实例。例。n以数据报方式操作的网络以数据报方式操作的网络,也可以提供虚电路服务也可以提供虚电路服务,通信子网内部节点按数据报方式交换数据通信子网内部节点按数据报方式交换数据,而与端而与端系统相连的网络节点则向端系统提供虚电路服务系统相连的网络节点则向端系统提供虚电路服务。n在在ARPANET中，其内部使用数据报操作方式，但可以向中，其内部使用数据报操作方式，但可以向端系统提供数据报和虚电路两种服务。端系统提供数据报和虚电路两种服务。5

13、.1.4数据报服务数据报服务n数据报服务一般仅由数据报交换网来提供。数据报服务一般仅由数据报交换网来提供。n端系统的网络层同网络节点中的网络层之间，端系统的网络层同网络节点中的网络层之间，一致地按照数据报操作方式交换数据。一致地按照数据报操作方式交换数据。n当端系统要发送数据时，网络层给该数据附当端系统要发送数据时，网络层给该数据附加上地址、序号等信息，然后作为数据报以加上地址、序号等信息，然后作为数据报以发送给网络节点；目的端系统收到的数据报发送给网络节点；目的端系统收到的数据报可能是不按序到达的，也可能有数据报的丢可能是不按序到达的，也可能有数据报的丢失。失。操作和服务操作和服务虚电路操作

14、方式虚电路操作方式数据报操作方式数据报操作方式虚电路服务虚电路服务数据报服务数据报服务SNAARPANET5.1.5虚电路子网和数据报子网虚电路子网和数据报子网的比较的比较n路由器的内存空间和带宽之间的平衡路由器的内存空间和带宽之间的平衡n建立虚电路所需要的时间和地址解析的时间建立虚电路所需要的时间和地址解析的时间n路由器内存中所需要的表空间的数量路由器内存中所需要的表空间的数量n虚电路子网可以提前预留资源虚电路子网可以提前预留资源n需要建立和消除虚电路需要建立和消除虚电路n路由器失效的影响路由器失效的影响虚电路和数据报子网比较虚电路和数据报子网比较数据报子网数据报子网虚电路子网虚电路子网建立

15、电路建立电路不需要不需要需要需要地址信息地址信息每每个个分分组组包包括括完完整整的的源源地地址址和和目的地址目的地址每每个个分分组组含含有有一一个个短短的的虚虚电电路路号号状态信息状态信息路路由由器器不不保保留留任任何何有有关关连连接接的的状态信息状态信息每每个个虚虚电电路路都都要要求求路路由由器器为为每每个连接建立表项个连接建立表项路由选择路由选择每个分组单独选择路由每个分组单独选择路由建建立立虚虚电电路路时时选选择择路路由由，以以后后所有分组都使用该路由所有分组都使用该路由路路由由器器失失败败的的影响影响除除了了在在崩崩溃溃时时正正在在由由该该路路由由器器处处理理的的分分组组都都丢丢失失外

16、外，无无其其他他影响影响所所有有经经过过失失效效路路由由器器的的虚虚电电路路都要被终止都要被终止服服务务质质量量和和拥拥塞控制塞控制很难实现很难实现如如果果有有足足够够的的缓缓冲冲区区分分配配给给已已建立的虚电路，则容易控制建立的虚电路，则容易控制习题习题n4.4.考考虑虑下下面面虚虚电电路路服服务务实实现现涉涉及及的的设设计计问问题题。如如果果虚虚电电路路用用在在子子网网内内部部，每每个个数数据据报报文文必必须须有有一一个个3 3字字节节的的报报文文，每每个个路路由由器器必必须须留留有有8 8字字节节的的空空间间来来标标示示虚虚电电路路。如如果果内内部部使使用用数数据据报报，则则需需要要使使

17、用用一一个个1515字字节节的的分分组组头头。假假定定每每站站段段传传输输带带宽宽的的费费用用为为每每10106 6字字节节1 1元元人人民民币币；路路由由器器存存储储器器的的价价格格为为每每字字节节0.10.1元元人人民民币币，并并且且在在未未来来两两年年会会下下降降。平平均均每每次次会会话话的的长长度度为为10001000秒秒，传传输输200200分分组组；分分组组平平均均需需传传4 4个个站站段段。试试问问子子网网内内部部采采用用虚虚电电路或数据报哪个更便宜？便宜多少？路或数据报哪个更便宜？便宜多少？n答：每个分答：每个分组经过组经过4 4段段链链路意味路意味链链路上包括路上包括5 5个

18、路由器。个路由器。n虚虚电电路路实实现现方方案案：需需在在10001000秒秒内内固固定定分分配配5 58=40bytes8=40bytes存存储储空空间间，n存存储储器器使使用用的的时时间间是是2 2年年，即即2 25252（一一年年5252个个星星期期）4040（每星期工作（每星期工作4040个小个小时时）3600=1.53600=1.510107 7sec sec n每字每字节节每秒的每秒的费费用用=0.1/=0.1/（1.51.510107 7）=6.7=6.71010-9-9元元 n总总 费费 用用 即即 10001000秒秒 4040字字 节节 的的 费费 用用=1000=1000

19、40406.76.71010-9 9=2.7=2.71010-4-4元元 n数数据据报报实实现现方方案案：比比上上述述虚虚电电路路实实现现方方案案需需多多传传(15-(15-3)3)4 4200=9600bytes200=9600bytes，n每字每字节节每每链链路的路的费费用用=1/10=1/106 6=10=10-6-6元元 n总费总费用，即用，即96009600字字节节每每链链路的路的费费用用=9600=96001010-6-6=96=961010-4-4元元 n96-2.7=93.396-2.7=93.3毫分毫分 n可可见见，本本题题中中采采用用虚虚电电路路实实现现方方案案更更为为经经

20、济济，在在10001000秒秒的的时间内便宜时间内便宜93.393.31010-4-4元。元。5.2路由选择路由选择n考核要求：考核要求：n识记：最优化的定义识记：最优化的定义n领会：静态路由选择策略：泛射路由选择算法。领会：静态路由选择策略：泛射路由选择算法。动态路由选择策略：链路状态路由算法。移动主动态路由选择策略：链路状态路由算法。移动主机的路由选择。广播路由选择。多播路由选择。机的路由选择。广播路由选择。多播路由选择。n简单应用：最短路有选择算法，距离矢量路由算简单应用：最短路有选择算法，距离矢量路由算法。法。5.2路由选择路由选择n网络节点在收到一个分组后后，要确定向下一节点网络节点

21、在收到一个分组后后，要确定向下一节点传送的路径，这就是路由选择。传送的路径，这就是路由选择。n在数据报方式中，网络节点要为每个分组路由做出选择；在数据报方式中，网络节点要为每个分组路由做出选择；n在虚电路方式中，只需在连接建立时确定路由。在虚电路方式中，只需在连接建立时确定路由。n路由选择的两个基本操作：最佳路径的判定和网间路由选择的两个基本操作：最佳路径的判定和网间信息包的传送（交换）。信息包的传送（交换）。n确定路由选择的策略称路由选择算法。确定路由选择的策略称路由选择算法。n设计路由算法时要考虑诸多技术要素。设计路由算法时要考虑诸多技术要素。WhatdoesaRoutingTableLo

22、okLike路由选择路由选择n路由算法有两类：路由算法有两类：非自非自适应适应自自适应适应静态路由静态路由动态路由动态路由路由表固定路由表固定路由表定时刷新路由表定时刷新路由协议路由协议简便、可靠、易行，适用于负荷稳定、拓扑结构变化不大的网络简便、可靠、易行，适用于负荷稳定、拓扑结构变化不大的网络算法复杂，会增加网络负担，但能够改善网络的性算法复杂，会增加网络负担，但能够改善网络的性能，并有利于流量控制能，并有利于流量控制5.2.1最优化原则最优化原则n如果路由器如果路由器J J在从路由器在从路由器I I到到K K的最佳路由上，那么的最佳路由上，那么从从J J到到K K的最佳线路就会在同一路由

23、之中。的最佳线路就会在同一路由之中。n假设称假设称从从I I到到J J的路由为的路由为r1r1，而路由其余部分成为而路由其余部分成为r2r2。如如果果J J到到K K还有在一条比还有在一条比r2r2更好的路由，那么它可以同更好的路由，那么它可以同r1r1联联系起来，以改进系起来，以改进I I到到K K的路由，这与的路由，这与r1r2r1r2是最优路由的断是最优路由的断言相悖。言相悖。IJKBB一个子网路由器B的汇集树汇集树（汇集树（sink treesink tree）n从所有源端到目的端的最佳路由集合，形成了以目的地为根的树。从所有源端到目的端的最佳路由集合，形成了以目的地为根的树。n汇集树

24、不包含任何循环汇集树不包含任何循环n最优化原则和汇集树为路由选择算法提供了一种衡量标准最优化原则和汇集树为路由选择算法提供了一种衡量标准AEDCFIJOLMKGHN5.2.2静态路由选择算法静态路由选择算法n静态路由选择策略不用测量也不需利用网络静态路由选择策略不用测量也不需利用网络信息，这种策略按某种固定规则进行路由选信息，这种策略按某种固定规则进行路由选择；择；n可分为最短路由选择法、扩散法和基于流量可分为最短路由选择法、扩散法和基于流量的路由选择法。的路由选择法。1.最短路由选择法最短路由选择法（简单应用）（简单应用）n基本思想基本思想:建立一个子网图建立一个子网图,图中的每个节点图中的

25、每个节点代表一台路由器代表一台路由器,每条弧线代表一条通信线每条弧线代表一条通信线路路(链路链路),弧上的数字代表该线路的权重。弧上的数字代表该线路的权重。n为了在一对给定的路由器之间选择一条路由为了在一对给定的路由器之间选择一条路由路径，路由算法只需在图中找到这对节点之路径，路由算法只需在图中找到这对节点之间的最短路径即可。间的最短路径即可。n最著名的最著名的Dijkstra算法算法Dijkstra算法算法n算法要求每个节点用从源节点沿已知最佳路径到本算法要求每个节点用从源节点沿已知最佳路径到本节点的距离来标注。节点的距离来标注。n1、开始所有节点标注为无穷大、开始所有节点标注为无穷大n2、

26、改变与源点相邻节点的标注、改变与源点相邻节点的标注n3、找到新标注点中的最小的点、找到新标注点中的最小的点Mn4、以、以M为新工作点，标注其相邻节点（若某点曾为新工作点，标注其相邻节点（若某点曾经标记过，并且新标记小于老标记，则更新其标记）经标记过，并且新标记小于老标记，则更新其标记）n5、返回第、返回第3步步利用利用Dijkstra算法求算法求A到到D的最短通路的最短通路ABCEFGHD22164273223AB(2,A)E(,-)G(6,A)C(,-)F(,-)H(,-)D(,-)AB(2,A)E(4,B)G(6,A)C(9,B)F(,-)H(,-)D(,-)AB(2,A)E(4,B)G(

27、5,E)C(9,B)F(6,E)H(,-)D(,-)AB(2,A)E(4,B)G(5,E)C(9,B)F(6,E)H(9,G)D(,-)AB(2,A)E(4,B)G(5,E)C(9,B)F(6,E)H(8,F)D(,-)AB(2,A)E(4,B)G(5,E)C(9,B)F(6,E)H(8,F)D(10,H)AB(2,A)E(4,B)G(5,E)C(9,B)F(6,E)H(8,F)D(10,H)AB(2,A)E(4,B)G(5,E)C(9,B)F(6,E)H(8,F)D(10,H)最短通路为：A-B-E-F-H-D，权值为10ABEGHFCD22617422233最短路由选择最短路由选择练习练习

28、n找出找出V0到到V3的最短距离的最短距离v5v4v3v2v1v0 100 6030101020 5 5052.扩散法扩散法n又称为：泛射路由选择法又称为：泛射路由选择法n一个网络节点从某条线路收到一个分组后，再向除该线路一个网络节点从某条线路收到一个分组后，再向除该线路外的所有线路重复发送收到分组。外的所有线路重复发送收到分组。n结果，最先到达目的的节点的一个或若干个分组肯定经过结果，最先到达目的的节点的一个或若干个分组肯定经过了最短的路径，而且所有可能的路径都被尝试过。了最短的路径，而且所有可能的路径都被尝试过。n没有考虑网路负载没有考虑网路负载n应用：应用：n强壮性要求很高的场合强壮性要

29、求很高的场合，只要源、目间有一条信道存在，仍能保证，只要源、目间有一条信道存在，仍能保证数据的可靠传送数据的可靠传送。n也可用于广播式数据交换中。也可用于广播式数据交换中。n进行网络的最短路径及最短传输延迟的测试。进行网络的最短路径及最短传输延迟的测试。n无线网络中无线网络中扩散法扩散法n产生大量的重复分组，解决办法：产生大量的重复分组，解决办法：n每个分组头包含站计数器，每经过一个站点计数每个分组头包含站计数器，每经过一个站点计数器减一。当计数器为器减一。当计数器为0时就扔掉分组。时就扔掉分组。n记录下分组扩散的路径，防止第二次再扩散到已记录下分组扩散的路径，防止第二次再扩散到已扩散的路径中

30、扩散的路径中n改进成选择扩散法，仅发送到与正确方向接近的改进成选择扩散法，仅发送到与正确方向接近的那些线路上。那些线路上。3.基于流量的路由选择基于流量的路由选择n是既考虑拓扑结构又兼顾网络负载的静态路由算法。是既考虑拓扑结构又兼顾网络负载的静态路由算法。n基本思想：基本思想：n对对某某一一给给定定的的线线路路，如如果果已已知知负负载载与与平平均均流流量量，那那么么可可以以根根据据排排队队理理论论计计算算出出该该线线路路上上的的平平均均分分组组延延迟迟。由由所所有有的的线线路路平平均均延延迟迟可可直直接接计计算算出出流流量量的的加加权权平平均均值值，从从而而得得到到整整个个网网络络的的平平均均

31、分分组组延延迟迟，这这样样路路由由选选择择问问题题就就归归结结为为如如何何找找出出产产生生网网络络最最小小平平均均延延迟迟的的路路由由算法。算法。n需要预知的信息：需要预知的信息：n网络的拓扑结构网络的拓扑结构n通信量矩阵通信量矩阵n线路容量矩阵线路容量矩阵n选定一种路由算法选定一种路由算法5.2.3动态路由选择算法动态路由选择算法n节点的路由选择要依靠网络当前的状态来决节点的路由选择要依靠网络当前的状态来决定的策略。定的策略。n也称为自适应路由选择算法也称为自适应路由选择算法n特点：特点：n能较好的适应网络的流量、拓扑结构的变化，有能较好的适应网络的流量、拓扑结构的变化，有利于改善网络环境利

32、于改善网络环境n算法复杂算法复杂n距离矢量路由算法和链路状态路由算法距离矢量路由算法和链路状态路由算法1.距离矢量路由算法（简单应距离矢量路由算法（简单应用）用）n每个路由器维护一张路由表，以子网中的每个路由器为索每个路由器维护一张路由表，以子网中的每个路由器为索引，表中列出当前已知的路由器到每个目标路由器的引，表中列出当前已知的路由器到每个目标路由器的最佳最佳距离距离，以及所使用的，以及所使用的线路线路。通过在邻居之间交换信息，路。通过在邻居之间交换信息，路由器不断地更新他们内部的路有表。由器不断地更新他们内部的路有表。n解释解释:n每个节点都定期地将它们的路由表传送给所有相邻节点，这里的路

33、每个节点都定期地将它们的路由表传送给所有相邻节点，这里的路由表所包含的内容有：由表所包含的内容有：n每条路径的经过的节点每条路径的经过的节点线路线路n本节点到该目的地址的代价本节点到该目的地址的代价距离距离n每个节点根据收到的相邻节点的路由信息更新自己的路由表每个节点根据收到的相邻节点的路由信息更新自己的路由表AJKXI435 距离矢量路由算法举例810126距离矢量路由算法的应用距离矢量路由算法的应用n距离矢量路由算法（距离矢量路由算法（distancevectorrouting）是现代计算机网络两个最常使用的）是现代计算机网络两个最常使用的动态路由选择算法之一。动态路由选择算法之一。n最初

34、是最初是ARPAnet使用的路由算法；使用的路由算法；nInternet的一种路由信息协议的一种路由信息协议RIP（RouteInformationProtocol）；）；2.链路状态路由算法链路状态路由算法n链路状态路由算法于链路状态路由算法于1979年出现在年出现在ARPAnet上，上，作为一种用来取代距离矢量路由算法的动态路由选作为一种用来取代距离矢量路由算法的动态路由选择算法，得到了广泛的应用。择算法，得到了广泛的应用。n算法描述（每个路由器需要完成的工作）：算法描述（每个路由器需要完成的工作）：n发现它的相邻节点，并且知道其网络地址；发现它的相邻节点，并且知道其网络地址；n测量到各邻

35、居节点的延迟或者开销；测量到各邻居节点的延迟或者开销；n构造一个分组，分组中包含所有它刚刚知道的信息；构造一个分组，分组中包含所有它刚刚知道的信息；n将这个分组发送给所有其他的路由器将这个分组发送给所有其他的路由器n计算出到每一个其他路由器的最短路径计算出到每一个其他路由器的最短路径链路状态路由算法步骤链路状态路由算法步骤n发现邻居结点，并学习它们的网络地址；发现邻居结点，并学习它们的网络地址；n路由器启动后，通过发送路由器启动后，通过发送HELLO包发现邻居结点；包发现邻居结点；n测量到每个邻居结点的延迟或开销；测量到每个邻居结点的延迟或开销；n一种直接的方法是：发送一个要对方立即响应的一种

36、直接的方法是：发送一个要对方立即响应的ECHO包，来回时间除以包，来回时间除以2即为延迟。即为延迟。n将所有学习到的内容封装成一个分组；将所有学习到的内容封装成一个分组；n分组以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；分组以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；n列表中对应每个邻居结点，都有发送方到它们的延迟或开销；列表中对应每个邻居结点，都有发送方到它们的延迟或开销；n链路状态分组定期创建或发生重大事件时创建。链路状态分组定期创建或发生重大事件时创建。n将这个分组发送给所有其它路由器；将这个分组发送给所有其它路由器；n基本思想：扩散法发布状态分组，为控制洪泛

37、，每个分组包含一个序号，每基本思想：扩散法发布状态分组，为控制洪泛，每个分组包含一个序号，每次发送新分组时加次发送新分组时加1。路由器记录信息对（源路由器，序号），当一个链路。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；记录中的最大序号小，则认为过时而丢弃；n计算到每个其它路由器的最短路径。计算到每个其它路由器的最短路径。n根据根据Dijkstra算法计算最短路径；算法计算最短路径；子网 链路状态分组链路状态路由算法应用链路

38、状态路由算法应用nInternet中广泛使用的中广泛使用的OSPF（OpenShortestPathFrist）开放最短路径优先协议）开放最短路径优先协议DistanceVectorvs.LinkStaten距离矢量路由算法距离矢量路由算法n节点节点向相邻节点向相邻节点告诉它告诉它所知道的所有节点所知道的所有节点的路由信息的路由信息n节点根据相邻节点的路由信息更新自己的路由表节点根据相邻节点的路由信息更新自己的路由表n链路状态路由算法链路状态路由算法n节点节点向所有节点向所有节点告诉告诉其相邻节点其相邻节点的状态信息的状态信息n每个路由器利用收到的路由信息画出一张完整的子网拓每个路由器利用收到

39、的路由信息画出一张完整的子网拓扑结构图扑结构图5.2.4移动主机的路由选择移动主机的路由选择n固定主机固定主机n永远不会动的主机，常通过有线介质连入网络永远不会动的主机，常通过有线介质连入网络n迁移主机迁移主机n基本上是固定的，移动到另一个固定点后，连接基本上是固定的，移动到另一个固定点后，连接到网络才使用主机到网络才使用主机n移动主机移动主机漫游主机漫游主机n希望在移动的时候还能保持与网络的连接希望在移动的时候还能保持与网络的连接把移动主机连入网络把移动主机连入网络n路由算法的目标：路由算法的目标：n在包含移动主机的系统中，能够做到用移动主机的地址在包含移动主机的系统中，能够做到用移动主机的

40、地址给他们发送分组，而不管这些主机在哪里，这些分组都给他们发送分组，而不管这些主机在哪里，这些分组都能够被递交给它们。能够被递交给它们。n问题的解决：问题的解决：n将空间划分成区域将空间划分成区域n每个区域有一个或多个每个区域有一个或多个外地代理外地代理，用来，用来管理所有来到当管理所有来到当地的移动主机地的移动主机（负责对外接待）（负责对外接待）n还有一个还有一个主代理主代理，用来，用来管理原本属于本区域管理原本属于本区域，但当时在，但当时在外地的用户外地的用户（负责对内管理）（负责对内管理）网络结构示意图网络结构示意图移动用户进入一个新区域移动用户进入一个新区域n必须首先向外部代理注册必须

41、首先向外部代理注册n外地代理定期广播一个分组，声明自己的存在和地址，外地代理定期广播一个分组，声明自己的存在和地址，新到达的移动主机接收该信息；若移动用户未能收到该新到达的移动主机接收该信息；若移动用户未能收到该信息，则移动主机广播包，询问外地代理的地址；信息，则移动主机广播包，询问外地代理的地址；n移动主机向外地代理注册，告知其原来所在的地址、目移动主机向外地代理注册，告知其原来所在的地址、目前的数据链路层地址和一些安全信息；前的数据链路层地址和一些安全信息；n外地代理与移动主机的主代理联系，告知移动主机的目外地代理与移动主机的主代理联系，告知移动主机的目前位置、自己的网络地址和一些安全信息

42、；前位置、自己的网络地址和一些安全信息；n主代理检查安全信息，通过，则给外地代理确认；主代理检查安全信息，通过，则给外地代理确认；n外地代理收到确认后，在登记表中加入一项，并通知移外地代理收到确认后，在登记表中加入一项，并通知移动主机注册成功。动主机注册成功。移动用户的路由转发过程移动用户的路由转发过程n当一个分组发给移动用户时，首先被转发到用户的主局当一个分组发给移动用户时，首先被转发到用户的主局域网；域网；n该分组到达移动用户的主局域网后，被主代理接收，主该分组到达移动用户的主局域网后，被主代理接收，主代理查询移动用户的新位置和与其对应的外地代理的地代理查询移动用户的新位置和与其对应的外地

43、代理的地址；址；n主代理将收到的分组作为净荷封装到一个新分组中，发主代理将收到的分组作为净荷封装到一个新分组中，发给外地代理；给外地代理；n主代理告诉发送方，发给移动用户的后续包作为净荷封主代理告诉发送方，发给移动用户的后续包作为净荷封装成分组直接发给外地代理，再由外地代理发送给移动装成分组直接发给外地代理，再由外地代理发送给移动主机，这样随后的分组就可以绕过主代理直接通过外地主机，这样随后的分组就可以绕过主代理直接通过外地代理路由到移动主机。代理路由到移动主机。发送者发送者外地代理外地代理主代理主代理广播路由选择广播路由选择n广播（广播（broadcasting）：）：同时发送一个分组给所有

44、目的同时发送一个分组给所有目的地。地。n实现广播路由的方法实现广播路由的方法n1、源主机给每个目标单独发送一个分组，通过多个点到点通、源主机给每个目标单独发送一个分组，通过多个点到点通信实现，缺点：浪费带宽，源主机需要知道所有目的地；信实现，缺点：浪费带宽，源主机需要知道所有目的地；n2、扩散法，缺点：浪费带宽、扩散法，缺点：浪费带宽n3、多目标路由（、多目标路由（multidestinationrouting）n每个分组包括一个目的地列表或一个目的地位图；每个分组包括一个目的地列表或一个目的地位图；n路由器根据目的地做路由选择，在相应输出线路上复制一个分组，路由器根据目的地做路由选择，在相应

45、输出线路上复制一个分组，并将该线路对应的目的地填入分组中。并将该线路对应的目的地填入分组中。n4、广播算法（使用汇集树或者生成树）、广播算法（使用汇集树或者生成树）n5、逆向路径转发、逆向路径转发广播算法广播算法n利用汇集树（利用汇集树（sinktree）或生成树（或生成树（spanningtree）n生成树是通信子网的一个子集，能将所有路由器连接起来，并生成树是通信子网的一个子集，能将所有路由器连接起来，并且没有回路；且没有回路；n汇集树是汇集树是最佳路由集合最佳路由集合n如果每个路由器知道它的哪些线路属于生成树，则将收到的广如果每个路由器知道它的哪些线路属于生成树，则将收到的广播包拷贝到输

46、入线路以外的所有其它生成树线路上；播包拷贝到输入线路以外的所有其它生成树线路上；n算法评价算法评价n优点：最优利用带宽，产生最小数目的分组优点：最优利用带宽，产生最小数目的分组n缺点：每个路由器都需要构造生成树缺点：每个路由器都需要构造生成树n链路状态路由算法可以使用链路状态路由算法可以使用n距离矢量路由算法不可以使用距离矢量路由算法不可以使用逆向路径转发逆向路径转发n当广播分组到达一个路由器时，路由器对它当广播分组到达一个路由器时，路由器对它进行检查，查看它到来的那条线路是否是通进行检查，查看它到来的那条线路是否是通常用来给广播源发送分组的那条线路，如果常用来给广播源发送分组的那条线路，如果

47、是，该路由器将把这个广播分组复制转发到是，该路由器将把这个广播分组复制转发到除输入线路外的所有线路。如果不是，则这除输入线路外的所有线路。如果不是，则这个分组将被废弃。个分组将被废弃。n优点：效率相对合理，而且容易实现优点：效率相对合理，而且容易实现逆向路径转发逆向路径转发n汇集树汇集树n第一跳：第一跳：F,H,N,J;第二跳：第二跳：A,D,M,O,G；第三跳；第三跳:C,E,K；第四跳；第四跳:B,Ln逆向路径转发逆向路径转发n第一跳：第一跳：F,H,N,J;第二跳：第二跳：A,D,E,K,G,O,M,O；第三跳；第三跳:E,C,G,D.N,K；第四跳；第四跳:H,B,L,H;第五跳：第五

48、跳：L,B汇集树H5.2.6多播多播路由选择路由选择n能够给一些有明确定义的组发送消息称为多点播送，简称能够给一些有明确定义的组发送消息称为多点播送，简称多播，又称组播，它的路由算法称为多播路由选择。多播，又称组播，它的路由算法称为多播路由选择。n实现多点播送需要有良好的小组管理机制；实现多点播送需要有良好的小组管理机制；n创建或销毁组，允许加入或离开组创建或销毁组，允许加入或离开组 n为了实现多点播送路由选择，每个路由器需要计算出一棵为了实现多点播送路由选择，每个路由器需要计算出一棵覆盖整个子网的生成树；覆盖整个子网的生成树；n修剪生成树修剪生成树 n生成树的修剪工作可以从树的端点开始，向树

49、根发展，除去所有不生成树的修剪工作可以从树的端点开始，向树根发展，除去所有不属于相应小组的路由器属于相应小组的路由器 n修剪方法：链路状态路由算法修剪方法：链路状态路由算法多播多播路由选择路由选择1,21,22221111,21,22221111111122222一个子网一个子网最左边路由器的生成树最左边路由器的生成树小组小组1的多点播送树的多点播送树小组小组2的多点播送树的多点播送树拥塞控制拥塞控制考核要求考核要求n识记：拥塞现象的原因，流量控制和拥塞控识记：拥塞现象的原因，流量控制和拥塞控制的差异。拥塞控制的必要性。制的差异。拥塞控制的必要性。n领会：拥塞控制的基本原理，拥塞控制方法。领会

50、：拥塞控制的基本原理，拥塞控制方法。5.3拥塞控制拥塞控制n什么是网络的拥塞什么是网络的拥塞n当大量分组进入通信子网，超出了网络的处理能力时，当大量分组进入通信子网，超出了网络的处理能力时，就会引起网络局部或整体性能下降，这种现象称为就会引起网络局部或整体性能下降，这种现象称为拥塞拥塞。n严重时导致网络通信业务陷入停顿，出现严重时导致网络通信业务陷入停顿，出现死锁现象死锁现象。n拥塞会导致什么后果拥塞会导致什么后果n拥塞使许多分组重传拥塞使许多分组重传n导致更多的业务量，直至崩溃导致更多的业务量，直至崩溃拥塞控制图 当通信量太大时,会发生拥塞,性能显著降低.发送的分组发送的分组提提交交的的分分