第四章网络层

1、第四章 网络层 网络层的功能与服务n路由选择n拥塞控制nX.25中的网络层 网络层的任务是要以分组为单位将数据信息从源节点传送到目的节点。第第一节一节 网络层的功能与服务网络层的功能与服务4.1.1 4.1.1 网络层功能及模型网络层功能及模型 网络层的作用：网络层的作用：在数据链路在数据链路层提供的在相邻两个节点之间层提供的在相邻两个节点之间透明、可靠的传送数据帧的功透明、可靠的传送数据帧的功能的基础上，进一步管理网络能的基础上，进一步管理网络中的通信，将从传输层交出的中的通信，将从传输层交出的数据以分组为单位，从源节点数据以分组为单位，从源节点通过通信子网沿适当的路径传通过通信子网沿适当的

2、路径传送到目的节点。送到目的节点。 网络层的功能：网络层的功能：向传输层提供服务、路由选择、向传输层提供服务、路由选择、拥塞控制、网络互联。拥塞控制、网络互联。第第一节一节 网络层的功能与服务网络层的功能与服务4.1.2 4.1.2 网络层提供的服务网络层提供的服务 面向连接的网络服务面向连接的网络服务 虚电路服务虚电路服务 无连接的网路服务无连接的网路服务 数据报服务数据报服务 虚电路服务虚电路服务 虚电路：虚电路：在通信之前，需要在通信之前，需要在源节点和目的节点间建立起在源节点和目的节点间建立起一条逻辑上的网络连接，我们一条逻辑上的网络连接，我们称之为虚电路

3、。称之为虚电路。 建立虚电路建立虚电路过程：过程： 建立连接建立连接 数据交换数据交换 拆除连接拆除连接H5BADECVC1VC2VC3H1H2H4H3(a)第第一节一节 网络层的功能与服务网络层的功能与服务每个节点都应保持一个每个节点都应保持一个虚电路表虚电路表，它的每一项记录了一个打开的虚电路它的每一项记录了一个打开的虚电路信息，包括虚电路号、前一节点和下信息，包括虚电路号、前一节点和下一节点的标识。一节点的标识。通常采用通常采用“动态动态”虚电路号码虚电路号码选取法：选取法：即总是选取当前尚未使即总是选取当前尚未使用的最低虚电路号。用的最低虚电路号。BADECH1H2H4H3H5 AEA

4、DCD(b) 虚电路的实现：虚电路的实现：建立虚电路时分配给该虚电路一个没用过建立虚电路时分配给该虚电路一个没用过的的虚电路号虚电路号，以区别于本系统中的其他虚，以区别于本系统中的其他虚电路。电路。传送数据时，每个数据分组含有分组号、传送数据时，每个数据分组含有分组号、校验和控制信息及其要经过的虚电路的号校验和控制信息及其要经过的虚电路的号码，以区别其它虚点路上的分组信息。码，以区别其它虚点路上的分组信息。 虚电路实现图例虚电路实现图例 （表示（表示5 5条虚电路建立的顺序以及所经过的节点）条虚电路建立的顺序以及所经过的节点） （5 5个节点的内存路由表）个节点的内存路由表） （表示沿虚电路（

5、表示沿虚电路H H1 1ABCEHABCEH5 5传送时，虚电路号的变换情况）传送时，虚电路号的变换情况） BADECH1H2H4H3H5 AEADCD(b)第第一节一节 网络层的功能与服务网络层的功能与服务 数据报方式数据报方式 数据报服务：数据报服务：没有虚电路建立的过程，每一没有虚电路建立的过程，每一个发出的分组（称为一个数据报）都携带了完个发出的分组（称为一个数据报）都携带了完整的目的地址信息，因而每一个分组都可以独整的目的地址信息，因而每一个分组都可以独立的选择路由。立的选择路由。 分组到达目的节点的顺序有可能与发送顺序分组到达目的节点的顺序有可能与发送

6、顺序不完全一致，甚至会失去某些分组。不完全一致，甚至会失去某些分组。 要求接收方主机具有重新排序、纠正重复或要求接收方主机具有重新排序、纠正重复或丢失分组的功能。丢失分组的功能。 数据报实现数据报实现在每个节点同样要有一个路由表，按照每个分组所携带的目的地址查找路由在每个节点同样要有一个路由表，按照每个分组所携带的目的地址查找路由表来决定应沿哪条链路转发分组。表来决定应沿哪条链路转发分组。 BADECH1H2H4H3H5 AEADCD(b)第第一节一节 网络层的功能与服务网络层的功能与服务 虚电路服务与数据报服务的比较虚电路服务与数据报服务的比较第第二节二节 路由

7、选择路由选择 4.2.1 4.2.1 理想的路由算法理想的路由算法 路由算法：路由算法：网络节点在收到一个分组后，决定在那一条输出链路上传送网络节点在收到一个分组后，决定在那一条输出链路上传送下去所使用的策略。下去所使用的策略。 理想的路由算法的一些特点：理想的路由算法的一些特点：(1)(1)正确性。正确性。必须是信息快速、正确的传输。必须是信息快速、正确的传输。(2)(2)简单性。简单性。计算简单可以减少时延。另外，路由选择的计算不应使网络的通信计算简单可以减少时延。另外，路由选择的计算不应使网络的通信量增加太多的额外开销。量增加太多的额外开销。(3)(3)坚固性。坚固性。算法应能适应通信量

8、和网络拓扑的变化，要有自适应性。有时称这算法应能适应通信量和网络拓扑的变化，要有自适应性。有时称这种自适应性为种自适应性为“健壮性健壮性”( (robustness)robustness)。(4)(4)稳定性。稳定性。当通信量和网络拓扑发生变化时，路由算法应收敛于一个可以接受当通信量和网络拓扑发生变化时，路由算法应收敛于一个可以接受的解，而不应产生过多的振荡。的解，而不应产生过多的振荡。 (5)(5)公平性。公平性。算法应对所有用户（除对少数优先级高的用户）都是平等的。算法应对所有用户（除对少数优先级高的用户）都是平等的。(6)(6)最佳性。最佳性。是指以最低的费用来实现路由算法。实际上，所谓

9、是指以最低的费用来实现路由算法。实际上，所谓“最佳最佳”只能是只能是相对于某一种特定要求下得出的较为合理的选择而已。相对于某一种特定要求下得出的较为合理的选择而已。 第第二节二节 路由选择路由选择4.2.2 4.2.2 最短通路路由选择最短通路路由选择 例：例：寻找从源节点寻找从源节点A A到网络中其他各节点的最短通路。到网络中其他各节点的最短通路。 令令D()D()为源节点为源节点( (节点节点A)A)到节点到节点的距离；的距离； 令令N N表示网络节点的集合，初始时令表示网络节点的集合，初始时令N NAA； 令令l(il(i，j)j)为节点为节点i i至节点至节点j j之间的距离。之间的距

10、离。 算法：算法：(1)(1)初始化初始化 D()= (A , ) D()= (A , ) 若节点若节点与节点与节点A A直接相连直接相连 若节点若节点与节点与节点A A不直接相连不直接相连(2)(2)寻找一个不在寻找一个不在N N中的节点中的节点，其，其D()D()值为最小，把值为最小，把加入到加入到N N中，然后对所中，然后对所有不在有不在N N中的节点，用中的节点，用D()D()和和D()+(D()+(，)中的较小的值去更新原有的中的较小的值去更新原有的D()D()值，即：值，即： D()D()minminD()D()，D()+(D()+(，) (3)(3)重复步骤重复步骤(2)(2)，

11、直到所有的网络节点都在，直到所有的网络节点都在N N中为止。中为止。 ECFABD1211223355图图4-6 4-6 求最短通路算法的网络举例求最短通路算法的网络举例 第第二节二节 路由选择路由选择ECFABD1211223355图图4-6 4-6 求最短通路算法的网络举例求最短通路算法的网络举例 步骤步骤N ND (B)D (B)D (C)D (C)D (D)D (D)D (E)D (E)D (F)D (F)初始化初始化AA2 25 51 11 1A,DA,D2 24 42 22 2A,D,EA,D,E2 23 31 14 43 3A,B,D,EA,B,D,E3 31 12 24 44

12、4A,B,C,D,EA,B,C,D,E2 21 12 24 45 5A,B,C,D,E,FA,B,C,D,E,F2 23 31 12 2第第二节二节 路由选择路由选择4.2.3 4.2.3 路由选择的不同策略路由选择的不同策略 1.1.非自适应路由选择非自适应路由选择简单、开销小简单、开销小(1)(1)洪泛法洪泛法( (flooding)flooding) 策略：策略：当某个网络节点从某条输入线路收到一个不是发给它的分组时，就向当某个网络节点从某条输入线路收到一个不是发给它的分组时，就向所有与此节点相连的其它链路转发出去。所有与此节点相连的其它链路转发出去。 优点：优点：算法简单，几乎不需要什

13、么计算；算法简单，几乎不需要什么计算；可以在最短的时间内接收方收到信息；可以在最短的时间内接收方收到信息；方便实现广播通信和多址通信，具有良好的健壮性，广泛应用于军事网中。方便实现广播通信和多址通信，具有良好的健壮性，广泛应用于军事网中。 缺点：缺点：造成分组无休止的传输；造成分组无休止的传输；使接收方收到多个重复的分组；使接收方收到多个重复的分组；网络中分组数目迅速增长，结果导致网络出现拥塞现象。网络中分组数目迅速增长，结果导致网络出现拥塞现象。 改进：改进：采用采用计数器计数器或或登记表登记表法控制网络中分组数目的增长。法控制网络中分组数目的增长。第第二节二节 路由选择路由选择(2)(2)

14、有选择的洪泛法有选择的洪泛法 策略：策略：仅在满足某些事先确定的条件的链路上转发分组。仅在满足某些事先确定的条件的链路上转发分组。 好处：好处：分组不会向不希望去的方向转发。分组不会向不希望去的方向转发。 (3)(3)固定路由法固定路由法 策略：策略：在每个节点上保存一张由此节点到网络中其他节点的固定路由表（由在每个节点上保存一张由此节点到网络中其他节点的固定路由表（由网络设计人员或管理人员根据网络拓扑结构、流量分布和其他因素编制的，并网络设计人员或管理人员根据网络拓扑结构、流量分布和其他因素编制的，并且在此后的一段相当时间保持固定不变），表中规定一条或多条输出线。且在此后的一段相当时间保持固

15、定不变），表中规定一条或多条输出线。 适用：适用：当网络拓扑固定不变并且通信量也相对稳定时。当网络拓扑固定不变并且通信量也相对稳定时。(4)(4)随机走动法随机走动法( (random walk)random walk) 策略：策略：当分组到达某个节点时就随机地选择应当走哪条链路作为转发的路由，当分组到达某个节点时就随机地选择应当走哪条链路作为转发的路由，因此又称为随机徘徊。因此又称为随机徘徊。 适用：适用：在非自适应的路由策略中，若可能发生节点或链路的故障，那么随机在非自适应的路由策略中，若可能发生节点或链路的故障，那么随机走动法巳被证明是非常有效的，它使得路由算法具有较好的健壮性。走动法巳

16、被证明是非常有效的，它使得路由算法具有较好的健壮性。 第第二节二节 路由选择路由选择(5)(5)分散通信量法分散通信量法( (traffic bifurcation)traffic bifurcation)或或查表选择路由查表选择路由( (directory routing)directory routing) 策略：策略：事先在每个节点的内存中设置一个路由表，路由表中给出几个可供采事先在每个节点的内存中设置一个路由表，路由表中给出几个可供采用的输出链路，并且对每条链路赋予一个概率；当一个分组到达该节点时，此用的输出链路，并且对每条链路赋予一个概率；当一个分组到达该节点时，此节点即产生一个从节

17、点即产生一个从0.000.00到到0.990.99的随机数，然后按此随机数的大小，查表找出相的随机数，然后按此随机数的大小，查表找出相应的输出链路。应的输出链路。H HB BA AC CI IE EJ JK KD DG GF FL L（a a）目的目的节点节点最佳选择最佳选择次佳选择次佳选择最差选择最差选择输出线输出线概率概率输出线输出线概率概率输出线输出线概率概率B BA A0.460.46H H0.310.31I I0.230.23C CA A0.380.38I I0.340.34H H0.280.28D DH H0.500.50A A0.250.25I I0.250.25E EA A0.

18、400.40I I0.400.40H H0.200.20F FA A0.370.37H H0.330.33I I0.300.30G GH H0.460.46A A0.310.31K K0.230.23H HH H0.630.63K K0.210.21A A0.160.16I II I0.650.65A A0.220.22H H0.130.13K KK K0.670.67H H0.220.22A A0.110.11L LK K0.420.42H H0.400.40A A0.180.18A AA A0.630.63I I0.210.21H H0.160.16第第二节二节 路由选择路由选择2 2自适

19、应路由选择自适应路由选择 当网络拓扑发生变化时及网络某个节点或链路发生故障时，在网络的某个当网络拓扑发生变化时及网络某个节点或链路发生故障时，在网络的某个局部范围做出调整路由的决定。局部范围做出调整路由的决定。(1)(1)孤立的路由选择策略孤立的路由选择策略 策略策略：只根据本节点的状态来选择路由，而不和其它节点交换状态信息。：只根据本节点的状态来选择路由，而不和其它节点交换状态信息。 “热土豆热土豆”算法：算法：当收到一个分组时，不管其目的地址如何，把刚收到的当收到一个分组时，不管其目的地址如何，把刚收到的分组以最快速度发往各链路中等待队列长度最短的等待队列中排队等候发送。分组以最快速度发往

20、各链路中等待队列长度最短的等待队列中排队等候发送。 缺点：缺点：不准确，有时队列最短的方向井非正确的转发路由。不准确，有时队列最短的方向井非正确的转发路由。 改进：改进：令队列长度为令队列长度为Q Q，在每个队列增加，在每个队列增加一个对于某一目的地址的偏移数一个对于某一目的地址的偏移数B B，取，取Q+BQ+B值为最小的队列作为转发方向。值为最小的队列作为转发方向。 例如：例如：对应于对应于F F，E E，D D和和C C的的B B值若分别为值若分别为0 0，6 6，5 5和和8 8则算出相应的则算出相应的Q Q十十B B值分别为值分别为5 5，7 7，9 9和和1010，因此应把收到的分组

21、送到发往，因此应把收到的分组送到发往F F的队列中。的队列中。 至至C C至至F F从从A A来来节点节点J J至至D D至至E E第第二节二节 路由选择路由选择(2)(2)分布式路由选择策略分布式路由选择策略是目前应用最广泛的路由算法是目前应用最广泛的路由算法 特点：特点：适应性较好，每个节点周期性地从相邻的节点获得网络状态信息，同适应性较好，每个节点周期性地从相邻的节点获得网络状态信息，同时也将本节点做出的决定周期性地通知周围的各节点，以使这些节点不断地根时也将本节点做出的决定周期性地通知周围的各节点，以使这些节点不断地根据网络新的状态更新其路由选择决定。据网络新的状态更新其路由选择决定。

22、 例：例：ARPANETARPANET使用算法是在每一个节点保持两个向量，即：使用算法是在每一个节点保持两个向量，即： d dilil Di= Di= d dinin s silil Si= Si= s sinin DiDi节点节点i i的时延向量；的时延向量；d dijij节点节点i i至节点至节点j j的最小时延当前估值的最小时延当前估值( (d dijij=0)=0)；n n 网络中的节点数；网络中的节点数；S Si i节点节点i i的后继节点向量；的后继节点向量；S SIJIJ后继节点后继节点( (节点节点i i到节点到节点j j当前最小时延路由中的第当前最小时延路由中的第二个节点。二

23、个节点。 对于任一节点对于任一节点k k每隔每隔128ms128ms与其所有相邻节点交换时延向量，按以下方法对与其所有相邻节点交换时延向量，按以下方法对本节本节点的时延向量和后继节点向量点的时延向量和后继节点向量进行修改：进行修改： d dkiki ddkiki+d+dijij S Skiki=i i，用这个，用这个i i使使 d dkiki+d+dijij 为最小。为最小。 A A节点节点k k的所有相邻节点的集合；的所有相邻节点的集合； d dkiki节点节点k k到节点到节点i i的时延的当前估值。的时延的当前估值。 AiMin 第第二节二节 路由选择路由选择 例：例：536124121

24、21233552 20 03 32 23 35 53 33 30 02 21 13 31 12 22 20 01 13 3D2D4D3节点节点1 1收到收到3 3个时延向量个时延向量 目的节点目的节点延迟延迟下一个节点下一个节点1 10 02 22 22 23 35 53 34 41 14 45 56 63 36 68 83 3目的节点目的节点延迟延迟下一个节点下一个节点1 10 02 22 22 23 33 34 44 41 14 45 52 24 46 64 44 4更新后的路由表更新后的路由表 更新前在节点更新前在节点1 1的路由表的路由表 第第二节二节 路由选择路由选择(3)(3)集中

25、式路由选择策略集中式路由选择策略 策略：策略：利用利用网控中心网控中心NCCNCC，专门收集各节点定期发来的状态信息，然后由它，专门收集各节点定期发来的状态信息，然后由它根据这些状态信息及网络拓扑结构，动态的计算出每个节点现时的路由选择根据这些状态信息及网络拓扑结构，动态的计算出每个节点现时的路由选择表，再将新的路由选择表同时送回各个节点使用。表，再将新的路由选择表同时送回各个节点使用。 优点：优点：算法能算法能定期定期按拓扑结构和信息量变化按拓扑结构和信息量变化修改修改各节点的各节点的路由选择表路由选择表； 容易得到精确的路由，消除了分组在网内容易得到精确的路由，消除了分组在网内“兜圈子兜圈

26、子” 及路由及路由“振荡振荡”的的现象；现象； 可起到对进入网络通信量的某种可起到对进入网络通信量的某种流量控制流量控制作用。作用。 缺点：缺点：在在报告状态报告状态- -计算计算- -送回路由选择表送回路由选择表的过程中花费了不少时间，因的过程中花费了不少时间，因此在系统变化较快的网络中很难获得理想的控制效果；此在系统变化较快的网络中很难获得理想的控制效果；NCCNCC的工作量大的工作量大，因此需要采用速度快、可靠性高的机器；因此需要采用速度快、可靠性高的机器；由于采用集中控制，因而由于采用集中控制，因而NCCNCC工工作的可靠性尤为重要，所以应采用若干个级别的作的可靠性尤为重要，所以应采用

27、若干个级别的NCCNCC协同控制，一旦高一级协同控制，一旦高一级的的NCCNCC出现故障，低一级的出现故障，低一级的NCCNCC马上接替工作，但这种方法花费较大且仍不能马上接替工作，但这种方法花费较大且仍不能满足全部要求；满足全部要求；网中网中负载不平衡负载不平衡，靠近，靠近NCCNCC的链路负担重，而远离的链路负担重，而远离NCCNCC的链的链路负载较轻。路负载较轻。 (4)(4)混合式路由选择策略混合式路由选择策略第第三节三节 拥塞控制拥塞控制 拥塞：拥塞：当到达通信子网中某部分当到达通信子网中某部分的分组量过多时，就会造成网络性的分组量过多时，就会造成网络性能的下降的现象，称为拥塞。能的

28、下降的现象，称为拥塞。 网络性能下降的表现网络性能下降的表现：信息报传信息报传输延迟增加输延迟增加和和网络吞吐量下降网络吞吐量下降。 吞吐量吞吐量理想的拥塞控制理想的拥塞控制实际的拥塞控制实际的拥塞控制无拥塞控制无拥塞控制死锁死锁拥塞拥塞输入负载输入负载图图4-12 4-12 流量控制所起的作用流量控制所起的作用 4.3.1 4.3.1 拥塞产生的原因拥塞产生的原因 出现资源拥塞的条件：出现资源拥塞的条件： 对资源的需求可用资源对资源的需求可用资源 解决网络拥塞的办法解决网络拥塞的办法是采用是采用流量控制流量控制。 拥塞控制的主要功能拥塞控制的主要功能：(1)(1)防止网络因过载而引起吞吐量下

29、降和时延增加；防止网络因过载而引起吞吐量下降和时延增加；(2)(2)避免死锁；避免死锁；(3)(3)在互相竞争的各用户之间公平地分配资源。在互相竞争的各用户之间公平地分配资源。单纯的增加资源不单纯的增加资源不一定能解决拥塞问一定能解决拥塞问题，甚至可能更坏！题，甚至可能更坏！第第三节三节 拥塞控制拥塞控制4.3.2 4.3.2 拥塞控制方法拥塞控制方法 1 1缓冲区预分配法缓冲区预分配法适用于虚电路通信子网适用于虚电路通信子网 建立虚电路时建立虚电路时源节点源节点 相邻节点相邻节点 下一节点下一节点 目的节点目的节点呼叫分组呼叫分组 登记路径选择出入口表；登记路径选择出入口表； 单工停单工停等

30、信道：预定一个等信道：预定一个bufferbuffer； 双工停双工停等信道：预定两个等信道：预定两个bufferbuffer（每个方向一个（每个方向一个) )； 滑动窗口流水协议：预定数量等于滑动窗口尺寸大小个滑动窗口流水协议：预定数量等于滑动窗口尺寸大小个bufferbuffer。 传送分组时传送分组时源节点源节点 相邻节点相邻节点 下一节点下一节点 目的节点目的节点数据分组数据分组bufferbuffer满满? ?N NY Y改走其它路径改走其它路径 优点：可靠。优点：可靠。 缺点：可能造成浪费。缺点：可能造成浪费。第第三节三节 拥塞控制拥塞控制2 2抑制分组法抑制分组法可用虚电路或数据

31、报通信子网可用虚电路或数据报通信子网 策略：策略：在出现拥塞前兆时，对分组进行截流。在出现拥塞前兆时，对分组进行截流。 算法实现：算法实现：每个节点每个节点( (路由器路由器) )都监视其都监视其输出线路利用率输出线路利用率= = (0(0，1)1) 可用下列公式更新：可用下列公式更新：新新= =旧旧+ +（1-1-）f f f f反映线路瞬时利用率，取值为反映线路瞬时利用率，取值为0-10-1之间的常数；之间的常数；反映了更新速度。反映了更新速度。各节点各节点为每一条线路定义为每一条线路定义阀值阀值，当，当大于此值时，则该线路进入大于此值时，则该线路进入“告警告警”状状态。态。每新收到分组时

32、路由器要查看其输出线是否处于每新收到分组时路由器要查看其输出线是否处于“告警告警”状态，若是则状态，若是则发送发送一个抑制分组一个抑制分组到源主机，并在抑制分组中指明分组的目的地，并在原分组上加到源主机，并在抑制分组中指明分组的目的地，并在原分组上加一个标志，表示以后不用再产生抑制分组；发送端主机收到该抑制分组后，将一个标志，表示以后不用再产生抑制分组；发送端主机收到该抑制分组后，将发送速率降低一档，若继续发送抑制分组，则发送端继续降低速率。发送速率降低一档，若继续发送抑制分组，则发送端继续降低速率。近期实际数据速率近期实际数据速率最大数据速率最大数据速率第第三节三节 拥塞控制拥塞控制3 3分

33、组丢弃法分组丢弃法 策略：策略：当缓冲区满时，将到来的分组丢弃，丢弃分组后，发送端因得不到确认当缓冲区满时，将到来的分组丢弃，丢弃分组后，发送端因得不到确认而超时重发。而超时重发。 缓冲器分配规则：缓冲器分配规则： 为每个输入线分配一个能容纳一个分组的缓冲器为每个输入线分配一个能容纳一个分组的缓冲器先把到达的分组接收下来，检查该分组内有无对前面发送的信息报的应答，先把到达的分组接收下来，检查该分组内有无对前面发送的信息报的应答，如果应答表明前一次发送的信息包已经妥收，那么把此分组丢弃，准备接如果应答表明前一次发送的信息包已经妥收，那么把此分组丢弃，准备接收下一个分组。收下一个分组。 限制输出线

34、队列长度限制输出线队列长度N+1N+1个节点缓冲区除了分给个节点缓冲区除了分给输入线输入线(1(1个个) )以外，剩余的全分给以外，剩余的全分给输出线输出线(N(N个个) )。 分配给输出缓冲区的方法有分配给输出缓冲区的方法有 平分法平分法 最大分配法最大分配法 最小分配法最小分配法 最大最小分配法最大最小分配法第第三节三节 拥塞控制拥塞控制4 4许可证法许可证法 策略：策略：限制通信子网内的分组数目，使之不超过某一个固定值从而避免拥塞。限制通信子网内的分组数目，使之不超过某一个固定值从而避免拥塞。 实现方法：实现方法：在通信子网中有固定数目的许可证在网中随机巡航流动，任何一个在通信子网中有固

35、定数目的许可证在网中随机巡航流动，任何一个分组想进入网络必须先获得一个许可证；当分组到达终点时就释放许可证。分组想进入网络必须先获得一个许可证；当分组到达终点时就释放许可证。 许可证的分布原则：许可证的分布原则：尽量减少分组等待许可证的时间。尽量减少分组等待许可证的时间。平均分布；平均分布； 忙、闲不公平忙、闲不公平所有许可证在网内四处流动；所有许可证在网内四处流动； 付出等待时延付出等待时延每个节点上保存少量许可证，其它许可证在网内流动。每个节点上保存少量许可证，其它许可证在网内流动。 存在问题：存在问题： 能防止全局性拥塞，但仍不能完全消除局部拥塞；能防止全局性拥塞，但仍不能完全消除局部拥

36、塞； 需要需要防止许可证丢失。防止许可证丢失。 设网内节点数为设网内节点数为N N，则许可证数可选为，则许可证数可选为3 3N N，每个节点能拥有的许可证，每个节点能拥有的许可证L L 3 3为最佳为最佳分布。分布。第第三节三节 拥塞控制拥塞控制DTEDTEDCEDCEDTEDTEDCEDCE传输级传输级入口级到出口级入口级到出口级网段级网段级进网级进网级进网级进网级四种不同级别的流量控制四种不同级别的流量控制 .3流量控制流量控制 流量控制和拥塞控制的区别流量控制和拥塞控制的区别 拥塞控制拥塞控制: :必须保证通信子网能正常传输数据，包括流量控制，使全局性问题。必须保证通信子

37、网能正常传输数据，包括流量控制，使全局性问题。 流量控制流量控制: :根据接收端能承受的数据速率来调节发送端传输数据的速率，防止根据接收端能承受的数据速率来调节发送端传输数据的速率，防止到达接收端的数据速率超过接收端的处理速率，只与发送者与接收者之间的到达接收端的数据速率超过接收端的处理速率，只与发送者与接收者之间的点到点通信量有关。点到点通信量有关。 流量控制是流量控制是按级进行按级进行的，大致可以划分为四种不同级别。的，大致可以划分为四种不同级别。没有拥塞问题不没有拥塞问题不等于没有流量控等于没有流量控制问题！制问题！第第三节三节 拥塞控制拥塞控制1.1.网段级流量控制网段级流量控制需要解

38、决需要解决“存储存储转发转发”问题问题 目的：目的：在相邻两节点之间维持一个均匀的流量，以避免出现局部缓冲区拥塞和死锁。在相邻两节点之间维持一个均匀的流量，以避免出现局部缓冲区拥塞和死锁。 根据是对两节点间的流量还是对其中每条虚电路的流量进行控制可再划分为：根据是对两节点间的流量还是对其中每条虚电路的流量进行控制可再划分为：数据数据链路网段级流量控制链路网段级流量控制适用于虚电路、数据报两种业务适用于虚电路、数据报两种业务采用采用信道队列限制法信道队列限制法( (即即分组丢弃法分组丢弃法) )进行控制：监视每一个队列的缓冲区的占用情况并进行控制：监视每一个队列的缓冲区的占用情况并对其定义一个极

39、限对其定义一个极限( (固定的或动态可调的固定的或动态可调的) )，当某一队列中待转发的分组数超过此极限时，当某一队列中待转发的分组数超过此极限时即丢弃该分组。即丢弃该分组。特点：特点：能有效的避免吞吐量的降低，但无法解决能有效的避免吞吐量的降低，但无法解决间接死锁间接死锁的问题。的问题。虚电路虚电路网段级流量控制网段级流量控制适用于虚电路适用于虚电路DTEDTEDCEDCEDTEDTEDCEDCE传输级传输级入口级到出口级入口级到出口级网段级网段级进网级进网级进网级进网级四种不同级别的流量控制四种不同级别的流量控制 第第三节三节 拥塞控制拥塞控制 信道队列限制法信道队列限制法有以下四种变形：

40、有以下四种变形：平均分配平均分配设设N N为节点中输出队列的总数为节点中输出队列的总数, ,N Ni i为第为第i i个队列中的分组数个队列中的分组数, ,而而B B为缓冲区的大小为缓冲区的大小( (除除分配给输入线的之外），则约束条件为：分配给输入线的之外），则约束条件为：00N Ni iB/NB/N 这种这种固定分配固定分配方法，效率低，性能较差。方法，效率低，性能较差。 最长队列共享最长队列共享设设b bmaxmax为所允许的最长队列为所允许的最长队列( (此处此处b bmaxmaxB/N)B/N)，则约束条件为：，则约束条件为：00N Ni ib bmaxmax 以及以及 N Ni i

41、BB最小分配共享最小分配共享设设b bminmin为保证分配给每一队列的缓冲区大小为保证分配给每一队列的缓冲区大小( (当然当然binbin B/N) B/N)，则约束条件为：，则约束条件为：Max(0,Max(0, N Ni i - -b bminmin) )B-NbB-Nbminmin最小分配最长队列共享最小分配最长队列共享合并了前两种方式，即每合并了前两种方式，即每队列保证有一个最小的缓冲区队列保证有一个最小的缓冲区b bminmin供使用，同时其最供使用，同时其最大长度受大长度受b bmaxmax的限制。的限制。第第三节三节 拥塞控制拥塞控制 死锁：死锁：两个节点之间互相僵持，整个网络

42、不能传输分组，吞吐量为零的情况。两个节点之间互相僵持，整个网络不能传输分组，吞吐量为零的情况。1.1.存储存储转发死锁转发死锁直接直接存储存储转发死锁：转发死锁：互相占用了对方需要的资源而造成的死锁。互相占用了对方需要的资源而造成的死锁。间接间接存储存储转发死锁：转发死锁：每个节每个节点都试图向相临节点发送分组，但点都试图向相临节点发送分组，但没有一个节点有空闲缓冲区来接收没有一个节点有空闲缓冲区来接收分组导致产生死锁。分组导致产生死锁。2.2.重装死锁：重装死锁：发生在目的节点，因发生在目的节点，因缓冲区不足无法排序组装造成。缓冲区不足无法排序组装造成。R R4 4 R R3 3 R R1

43、1Q Q3 3 Q Q2 2 P P1 1 Q Q1 1P P3 3 P P2 2 Q Q4 4 R R2 2主机主机H H节点节点X X节点节点Y Y节点节点Z Z发往发往A A发往发往D DB BA AC CD D发往发往C C发往发往B Bb bmaxmax(b)(b)A AB B(a)(a)第第三节三节 拥塞控制拥塞控制信道队列限制法信道队列限制法无法解决无法解决间接死锁间接死锁的问题的问题！ 解决解决间接间接存储存储转发死锁转发死锁 采用采用结构化缓冲池策略结构化缓冲池策略或称为或称为缓冲区的有向图分配法缓冲区的有向图分配法给每个节点开辟给每个节点开辟M M十十1 1个缓冲区个缓冲区

44、( (每个缓冲区存放一个分组每个缓冲区存放一个分组) )，并从，并从0 0到到M M编上号码编上号码。 仅当与主机相连的源节点的缓冲区仅当与主机相连的源节点的缓冲区0 0空闲时分组才能发往源节点的缓冲区空闲时分组才能发往源节点的缓冲区0 0。接着，接着，仅当某个相邻节点中的缓冲区仅当某个相邻节点中的缓冲区1 1空闲时分组才能发往缓冲区空闲时分组才能发往缓冲区1 1，以后每转以后每转发一次，所到达的缓冲区的编号就增大一个号，发一次，所到达的缓冲区的编号就增大一个号，0 01 1 2 2 M M最终，分组的最坏结局一定是以下两种情况之一：最终，分组的最坏结局一定是以下两种情况之一： 传到所要到达的

45、目的节点，然后交付给主机；传到所要到达的目的节点，然后交付给主机； 传到编号为传到编号为M M的缓冲区，然后被丢弃，因而不再消耗网络的资源。的缓冲区，然后被丢弃，因而不再消耗网络的资源。第第三节三节 拥塞控制拥塞控制2 2源节点到目的节点级的流量控制源节点到目的节点级的流量控制需要解决需要解决“重装死锁重装死锁”问题问题 目的：目的：防止在输出节点出现由于目的节点到主机的连接线路过载或是由于主防止在输出节点出现由于目的节点到主机的连接线路过载或是由于主机接收数的速率太低而导致缓冲区拥塞。机接收数的速率太低而导致缓冲区拥塞。 当需要在目的节点把到达的分组重新装配成报文时有可能出现当需要在目的节点

46、把到达的分组重新装配成报文时有可能出现重装死锁重装死锁！ 在在ARPANETARPANET中使用的源节点到目的节点级的流量控制的方法是：中使用的源节点到目的节点级的流量控制的方法是：源节点发送报文时必须先发送一个源节点发送报文时必须先发送一个“请求缓冲空间请求缓冲空间”的分组；的分组；目的节点收到该分组后，即为此报文保留目的节点收到该分组后，即为此报文保留8 8个缓冲区并回答一个个缓冲区并回答一个“分配分配”分组。分组。当整个报文的当整个报文的8 8个分组都收齐并送交主机后，目的节点就发回一个个分组都收齐并送交主机后，目的节点就发回一个“准备下一报文准备下一报文”的确认分组。的确认分组。当源节

47、点无报文要发送但仍收到当源节点无报文要发送但仍收到“分配分配”分组时，须发回分组时，须发回“归还归还”分组以释放目的节分组以释放目的节点缓冲空间。点缓冲空间。DTEDTEDCEDCEDTEDTEDCEDCE传输级传输级入口级到出口级入口级到出口级网段级网段级进网级进网级进网级进网级四种不同级别的流量控制四种不同级别的流量控制 第第三节三节 拥塞控制拥塞控制3 3进网级流量控制进网级流量控制 目的：目的：控制网络外部的通信量进入网络从而防止整个网内的缓冲区产生拥塞。控制网络外部的通信量进入网络从而防止整个网内的缓冲区产生拥塞。 拥塞的测量：拥塞的测量：局部测量：局部测量：测量入口节点缓冲区的情况

48、；测量入口节点缓冲区的情况；全局测量：全局测量：测量全网所有缓冲区的占用程度；测量全网所有缓冲区的占用程度；选择测量：选择测量：测量某个目的节点的整条通路的拥塞情况。测量某个目的节点的整条通路的拥塞情况。 将测量结果报告进网节点，以控制从外部进入网内的通信量。将测量结果报告进网节点，以控制从外部进入网内的通信量。 最出名的进网级流量控制方案为最出名的进网级流量控制方案为许可证法许可证法。DTEDTEDCEDCEDTEDTEDCEDCE传输级传输级入口级到出口级入口级到出口级网段级网段级进网级进网级进网级进网级四种不同级别的流量控制四种不同级别的流量控制 第第三节三节 拥塞控制拥塞控制4 4传输

49、级流量控制传输级流量控制 目的：目的：在两个远程进程之间的虚电路连接中提供分组的可靠传送，即在进程在两个远程进程之间的虚电路连接中提供分组的可靠传送，即在进程级防止用户缓冲区出现拥塞。级防止用户缓冲区出现拥塞。 各层采取的流量控制：各层采取的流量控制： 数据链路层：数据链路层：进网级、网段级（数据链路网段级）进网级、网段级（数据链路网段级） 网络层：网络层：入口到出口级、网段级（虚电路网段级）入口到出口级、网段级（虚电路网段级） 传输层：传输层：传输级传输级DTEDTEDCEDCEDTEDTEDCEDCE传输级传输级入口级到出口级入口级到出口级网段级网段级进网级进网级进网级进网级四种不同级别的

50、流量控制四种不同级别的流量控制 第第四节四节 X.25X.25的网络层的网络层 4.4.1 X.254.4.1 X.25简介简介 1 1X.25X.25的层次结构的层次结构 由由CCITTCCITT制定，是关于用专用电路连接到公用数据网上的分组型数据终端制定，是关于用专用电路连接到公用数据网上的分组型数据终端设备设备（DTEDTE）与）与数据电路端接设备数据电路端接设备（DCEDCE）之间的接口标准）之间的接口标准。 版本：版本：19761976、19801980支持虚电路、数据报两种服务；支持虚电路、数据报两种服务；19841984取消了数据报服务；取消了数据报服务；19881988、199

51、21992只支持虚电路服务。只支持虚电路服务。 X.25X.25协议目前以协议目前以虚电路服务虚电路服务为基础。为基础。 分组级主要功能：分组级主要功能：向主机提供多逻辑信道的虚电路服务。向主机提供多逻辑信道的虚电路服务。 X.25X.25接口接口X.25X.25接口接口X.25X.25接口接口DTEDTEDCEDCEDTEDTEDCEDCEDCEDCEDTEDTEVCVC1 1VCVC2 2公用分组交换网公用分组交换网第第四节四节 X.25X.25的网络层的网络层F A C F A C 数据数据 FCS FFCS FTPDUTPDU数据数据比特流比特流LAPBLAPB数链层接口数链层接口分组层分组层数据链路层数据链路层物理层物理层高层高层分组层分组层数据链路层数据链路层物理层物理层至远程用户进程至远程用户进程多重信道接口多重信道接口X.21X.21物理层物理层 X.25X.25的三层层次结构的三层层次结构 物理层：物理层：数据传送单位是数据传送单位是“比特比特”，接口标准采用，接口标准采用X.21X.21建议书建议书。 数据链路层：数据链路层：数