0


【计算机网络】第七话·计算机网络的流量控制

🌕写在前面


Hello🤗大家好啊,我是kikokingzz,名字太长不好记,大家可以叫我kiko哦~

从今天开始,我将正式开启一个新的打卡专题——【计算机网络·宇宙计划】,没错!这是今年上半年的一整个系列计划!本专题目的是通过百天刷题计划,通过题目和知识点串联的方式刷够1000道题!完成对计算机网络相关知识的全方位复习和巩固;同时还配有专门的笔记总结和文档教程哦!想要搞定,搞透计算机网络的同学

🎉🎉欢迎订阅本专栏🎉🎉

🍊博客主页:kikoking的江湖背景🍊


🌟🌟往期必看🌟🌟

🔥【计算机网络】第一话·计算机网络的基本概念

🔥【计算机网络】第二话·计算机网络的体系结构

🔥【计算机网络】第三话·浅谈OSI和TCP/IP模型

🔥【计算机网络】第四话·深入理解物理层の细节

🔥【计算机网络】第五话·物理层的底层设备❥超详解

🔥【计算机网络】第六话·数据的传输方式(上)

🍺知识点7:计算机网络的流量控制

🥝7.1 流量控制简介


🍊1.什么是流量控制?

流量控制涉及对链路上的帧的发送速率的控制,以使接收方有足够的缓冲空间来接收每个帧。例如,在面向帧的自动重传请求系统中,当待确认帧的数量增加时,有可能超出缓冲存储空间而造成过载。

流量控制的基本方法是由接收方控制发送方发送数据的速率,常见的方式有两种:停止等待协议和滑动窗口协议。


🍊2.停止-等待流量控制基本原理

发送方每发送一帧, 都要等待接收方的应答信号,之后才能发送下一帧;接收方每接收一帧,都要反馈一个应答信号,表示可接收下一帧, 如果接收方不反馈应答信号,那么发送方必须一直等待。每次只允许发送一帧, 然后就陷入等待接收方确认信息的过程中,因而传输效率很低。


🍊3.滑动窗口流量控制基本原理

在任意时刻,发送方都维持一组连续的允许发送的帧的序号,称为发送窗口;同时接收方也维持一组连续的允许接收帧的序号,称为接收窗口。发送窗口用来对发送方进行流量控制,而发送窗口的大小W代表在还未收到对方确认信息的情况下发送方最多还可以发送多少个数据帧。同理,在接收端设置接收窗口是为了控制可以接收哪些数据帧和不可以接收哪些帧。在接收方,只有收到的数据帧的序号落入接收窗口内时,才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外,则一律将其丢弃。

滑动窗口有以下重要特性:

(1)只有接收窗口向前滑动(同时接收方发送了确认帧)时,发送窗口才有可能(只有发送方收到确认帧后才一定)向前滑动。

(2)从滑动窗口的概念看,停止等待协议、后退N帧协议和选择重传协议只在发送窗口大小与接收窗口大小上有所差别:

  • 停止等待协议:发送窗口大小=1,接收窗口大小=1。
  • 后退N帧协议:发送窗口大小>1,接收窗口大小=1。
  • 选择重传协议:发送窗口大小> 1,接收窗口大小>1。

(3)接收窗口的大小为1时,可保证帧的有序接收。

(4)数据链路层的滑动窗口协议中,窗口的大小在传输过程中是固定的(注意与第5章传输层的滑动窗口协议的区别)。


🍊4.可靠传输机制与流量控制的关系

数据链路层的可靠传输通常使用确认和超时重传两种机制来完成。确认ACK是一种无数据的控制帧,这种控制帧使得接收方可以让发送方知道哪些内容被正确接收。有些情况下为了提高传输效率,将确认捎带在一个回复帧中,称为捎带确认。超时重传是指发送方在发送某个数据帧后就开启一个计时器,在一定时间内如果没有得到发送的数据帧的确认帧,那么就重新发送该数据帧,直到发送成功为止。

**自动重传请求(Automatic Repeat reQuest, ARQ)**通过接收方请求发送方重传出错的数据帧来恢复出错的帧,是通信中用于处理信道所带来差错的方法之一。传统自动重传请求分为三种,即停止等待(Stop and-Wait) ARQ、后退N帧(Go-Back-N) ARQ和选择性重传(Selective Repeat)ARQ。后两种协议是滑动窗口技术与请求重发技术的结合,由于窗口尺寸开到足够大时,帧在线路上可以连续地流动,因此又称其为连续ARQ协议。

注意:在数据链路层中流量控制机制和可靠传输机制是交织在一起的。

** ✨✨✨我是分割线✨✨✨**

🥝7.2 停止等待协议


🍊1.什么是停止等待协议?

在停止等待协议中,源站发送单个帧后必须等待确认,在目的站的回答到达源站之前,源站不能发送其他的数据帧。从滑动窗口机制的角度看,停止等待协议相当于发送窗口和接收窗口大小均为1的滑动窗口协议。


🍊2.研究停等协议的前提?

(1)虽然现在常用全双工通信方式,但为了讨论问题方便,仅考虑一方发送数据(发送方),一方接收数据(接收方)。

(2)因为是在讨论可靠传输的原理,所以并不考虑数据是在哪一个层次上传送的。

(3)停止等待就是每发送完一个分组就停止发送,等待对方确认,在收到确认后再发送下一个分组。


🍊3.停等协议有几种应用情况?

(1)无差错情况

(2)有差错情况

在该情况中,到达目的站的帧可能已遭破坏,接收站利用前面讨论过的差锴检测技术检出后,简单地将该帧丢弃。为了对付这种可能发生的情况,源站装备了计时器。在一个帧发送之后,源站等待确认,如果在计时器计满时仍未收到确认,那么再次发送相同的帧。如此重复,直到该数据帧无错误地到达为止。

另一种可能的差错是数据帧正确而确认帧被破坏,此时接收方已收到正确的数据帧,但发送方收不到确认帧,因此发送方会重传已被接收的数据帧,接收方收到同样的数据帧时会丢弃该帧,并重传一个该帧对应的确认帧。发送的帧交替地用0和1来标识,确认帧分别用ACK0和ACK1来表示,收到的确认帧有误时,重传已发送的帧。对于停止等待协议,由于每发送一个数据帧就停止并等待,因此用1bit 来编号就已足够。在停止等待协议中,若连续出现相同发送序号的数据帧,表明发送端进行了超时重传。连续出现相同序号的确认帧时,表明接收端收到了重复帧。

Q1:发送一个帧后,为什么需要保留它的副本呢?

A1:因为当帧丢失或出错后,发送方需要重传该帧,由于发送方保留了它的副本,因此可以将该副本进行重传;如果没有保留该帧的副本,则无帧可传,只有当发送方收到了对于该帧的确认帧时,才可以将该副本丢弃。

Q2:数据帧和确认帧为什么要编号?

A2:因为如果连续出现了相同发送序号的数据帧,说明发送方进行了超时重传;当连续出现了相同序号的确认帧,说明接收方收到了相同的重复的帧;使用编号就可以解决帧的丢失、帧的重复等问题。

111.在简单的停止等待协议中,当帧出现丢失时,发送端会永远等待下去,解决这种死锁现
象的办法是( )。
A.差错校验
B.帧序号
C.NAK机制
D.超时机制

kiko🎃:在停止-等待协议中,发送端设置了计时器,在一个帧发送之后,发送端等待确认,如果在计时器计满时仍未收到确认,那么再次发送相同的帧,以免陷入永久的等待;因此本题选D。


🍊4.停等协议的性能分析

Q1:什么是信道利用率?

A1:信道利用率指的是在一个发送周期内,发送数据的时间占整个发送周期的比率。

Q2:停等协议的信道利用率怎么样?

A2:由下图可见,停等协议的信道利用率太低!


🍊5.流水线技术(pipeline)

Q1:流水线技术为什么会出现?

A1:停等协议的信道利用率太低,为使其性能进一步提高,进而推出了“流水线技术”,即不以停等方式运行,允许发送方发送多个分组而无须等待确认。

Q2:为什么叫流水线技术呢?

A2:因为许多从发送方向接收方输送的分组可以被看成是填充到一条流水线中,故这种技术称为流水线技术。

Q3:流水线技术与停等协议的区别有哪些?

A3:如下图可见,流水线协议中,发送方可以在等待确认之前发送3个报文,其利用率相比停等操作提高了3倍,其与停等协议的区别主要有以下2点:

  • 必须增加序号范围:因为每次输送有多个分组,所以只有0,1两个序号不够用了。
  • 发送方和接收方需缓存多个分组:发送方最低限度应当能缓存那些已发送但没有得到确认的分组。

📜习题检测


📜112.题目难度 ⭐️

112.一个信道的数据传输速率为4kb/s,单向传播时延为30ms,如果使停止-等待协议的信道
最大利用率达到80%,那么要求的数据帧长度至少为( )。
A.160bit
B.320bit
C.560bit
D.960bit

🍊详细题解:

✅正确答案:D


📜113.题目难度 ⭐️

113.【2020统考真题】假设主机甲采用停-等协议向主机乙发送数据帧,数据帧长与确认帧长
均为1000B,数据传输速率是10kb/s,单项传播延时是200ms。则甲的最大信道利用率为( )。
A.80%
B.66.7%
C.44.4%
D.40%

🍊详细题解:

✅正确答案:D


📜114.题目难度 ⭐️

114.【2018统考真题】主机甲采用停止-等待协议向主机乙发送数据,数据传输速率是3kb/s,
单向传播时延是200ms,忽略确认帧的传输时延,当信道利用率等于40%时,数据帧的长度为( )。
A.240比特
B.400比特
C.480比特
D.800比特

🍊详细题解:

✅正确答案:D


📜115.题目难度 ⭐️

115.假设一个信道的数据传输速率为5kb/s,单向传输时延为30ms, 那么帧长在什么范围内,
才能使用于差错控制的停止等待协议的效率至少为50%?

🍊详细题解:

** ✨✨✨我是分割线✨✨✨**

**🥝7.3 **后退N帧协议(GBN协议)


🍊1.什么是后退N帧协议?

在后退N帧式ARQ中,发送方无须在收到上一个帧的ACK后才能开始发送下一帧,而是可以连续发送帧。当接收方检测出失序的信息帧后,要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧;或者当发送方发送了N个帧后,若发现该N个帧的前一个帧在计时器超时后仍未返回其确认信息,则该帧被判为出错或丢失,此时发送方就不得不重传该出错帧及随后的N个帧。换句话说,接收方只允许按顺序接收帧。

最大的特点:采用累积确认的方式

116.【2009统考真题】数据链路层采用了后退N帧(GBN)协议,发送方已经发送了编号为0~7的帧。
计时器超时时,若发送方只收到0、2、3号帧的确认,则发送方需要重发的帧数是( )。
A.2
B.3
C.4
D.5

kiko🎃:在后退N帧协议中,当接收方检测到某个帧出错后,会简单地丢弃该帧及所有的后续帧,发送方超时后需重传该数据帧及所有的后续帧。这里应注意,在连续ARQ协议中,接收方一般采用累积确认的方式,即接收方对按序到达的最后一个分组发送确认,因此本题中收到3的确认帧就表示编号为0, 1, 2, 3的帧己接收,因此需要重传的帧为编号是4, 5, 6, 7的帧;因此本题选C。


🍊2.GBN协议中的滑动窗口

发送窗口:如下图所示,窗口长度N表示可发送的帧数最大为N。


🍊3.GBN发送方与接收方必须响应的事

GBN发送方必须响应的三件事:

  • (1)上层的调用:上层要发送数据时,发送方先检查发送窗口是否已满,如果未满,则产生一个帧并将其发送;如果窗口已满,发送方只需将数据返回给上层,暗示上层窗口已满。上层等一会再发送。(实际实现中,发送方可以缓存这些数据,窗口不满时再发送帧)。
  • (2)收到了一个ACK:GBN协议中,对n号帧的确认采用累积确认的方式,标明接收方已经收到n号帧和它之前的全部帧。
  • (3)超时事件:协议的名字为后退N帧/回退N帧,来源于出现丢失和时延过长帧时发送方的行为。就像在停等协议中一样,定时器将再次用于恢复数据帧或确认帧的丢失。如果出现超时,发送方重传所有已发送但未被确认的帧。

GBN接收必须响应的二件事:

  • (1)如果正确收到n号帧,并且按序,那么接收方为n帧发送一个ACK,并将该帧中的数据部分交付给上层。
  • (2)其余情况都丢弃帧,并为最近按序接收的帧重新发送ACK。接收方无需缓存任何失序帧,只需要维护一个信息: expectedseqnum(下一个按序接收的帧序号)。


🍊4.滑动窗口的大小可以无限长吗?

若采用n个比特对帧编号,那么发送窗口的尺寸W_{T}应满足:1\leqslant W_{T}\leqslant 2^{n}-1。这是因为发送窗口尺寸过大时,就会使得接收方无法区别新帧和旧帧。我们在这里可以举个例子来说明这个问题:

例如用3比特可编出8个不同的序号:
1.设发送窗口W=8,发送端发送完0~7号共8个数据帧。因发送窗口已满,发送暂停。
2.假定这8个数据帧均已正确到达接收端,并且对每个数据帧,接收端都发送出确认帧。
下面考虑两种不同的情况:

情况1:所有确认帧都正确到达了发送端,因而发送端接着又发送8个新的数据帧,其编号应是0~7。
(注意,序号是循环使用的。因此序号虽然相同,但8个帧都是新的帧。)

情况2:所有确认帧都丢失了。经过一段由超时计时器控制的时间后,发送端重传这8个旧的数据帧,
其编号仍为0~7。

出现问题:当接收端第二次收到编号为0~7的8个数据帧时,就无法判定这是8个新的数据帧还是8个
重传的旧数据帧。因此,将发送窗口设置为8显然是不行的。
117.数据链路层采用了后退N帧的(GBN)协议,如果发送窗口的大小是32,那么至少需
要( )位的序列号才能保证协议不出错。
A.4
B.5
C.6
D.7

kiko🎃:在后退N帧的协议中,发送窗口的尺寸W_{T}应满足:1\leqslant W_{T}\leqslant 2^{n}-1,题中发送窗口的大小是32,那么序列号个数最少应该是33个。所以最少需要6位的序列号才能达到要求;因此本题选C。

118.若采用后退N帧的ARQ协议进行流量控制,帧编号字段为7位,则发送窗口的最大长
度为( )。
A.7
B.8
C.127
D.128

kiko🎃:发送窗口的尺寸W_{T}应满足:1\leqslant W_{T}\leqslant 2^{n}-1,本题告知n=7,因此计算可得发送窗口最大为127;因此本题选C。

📜习题检测


📜119.题目难度 ⭐️⭐️⭐️⭐️

119.【2012统考真题】两台主机之间的数据链路层采用后退N帧协议(GBN)传输数据,数据传输
速率为16kb/s,单向传播时延为270ms,数据帧长度范围是128~512字节,接收方总是以与数
据帧等长的帧进行确认。为使信道利用率达到最高,帧序号的比特数至少为( )。
A.5
B.4
C.3
D.2

🍊详细题解:

✅正确答案:B


📜120.题目难度 ⭐️

120.【2014统考真题】主机甲与主机乙之间使用后退N帧协议(GBN)传输数据,甲的发送窗口尺寸
为1000,数据帧长为1000字节,信道带宽为100Mb/s,乙每收到一个数据帧立即利用一个短帧
(忽略其传输延迟)进行确认,若甲、乙之间的单向传播时延是50ms,则甲可以达到的最大平均数据
传输速率约为( )。
A.10Mb/s
B.20Mb/s
C.80Mb/s
D.10OMb/s

🍊详细题解:

✅正确答案:C

** ✨✨✨我是分割线✨✨✨**

**🥝7.4 **选择重传协议(SR)


🍊1.什么是SR协议?

为进一步提高信道的利用率,可设法只重传出现差错的数据帧或计时器超时的数据帧(不像GBN协议那么挑食),但此时必须加大接收窗口,以便先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。

在选择重传协议中,每个发送缓冲区对应以个计时器,当计时器超时时,缓冲区的帧就会重传。另外,该协议使用了比上述其他协议更有效的差错处理策略,即一旦接收方怀疑帧出错,就会发一个否定帧NAK给发送方,要求发送方对NAK中指定的帧进行重传,如图3.11所示。


🍊2.SR协议中的滑动窗口


🍊3.SR发送方与接收方必须响应的事

SR****发送方必须响应的三件事:

  • (1)上层的调用:上层要发送数据时,发送方先检查下一个可用于该帧的序号,如果序号位于发送窗口内,则发送数据帧;否则发送方只需将数据返回给上层,暗示上层发送窗口不可用,上层等一会再发送或将数据进行缓存,等到该帧的序号位于发送窗口中时再发送。
  • (2)收到了一个ACK:如果收到ACK对应的序号在发送窗口内,则SR发送方将那个被确认的帧标记为已接收。如果该帧序号是窗口的下界,则窗口移动到其后序最近的未确认帧处。如果窗口移动后有新的帧进入到发送窗口,则可以发送这些新帧。

  • (3)超时事件:每个帧都有自己的定时器,一个超时事件发生后只重传一个帧。

SR接收必须响应的一件事:

  • (1)对于接收窗口内的帧来者不拒:SR接收方将确认一个正确接收的帧,而不管其是否按序。失序的帧将被缓存,并返回给发送方一个该帧的确认帧【收谁确认谁】,直到所有帧(即序号更小的帧)皆被收到为止,这时才可以将一批帧按序交付给上层,然后滑动窗口。
  • 注意:如果收到了窗⼝序号外(⼩于窗⼝下界)的帧,就返回⼀个ACK。这种情况可能是接收方收到该帧后窗口后移,接收方发送的ACK帧可能发送了丢失或超时,导致发送方进行了超时重传,这时接收方只需要对该帧返回ACK即可。

121.【2011统考真题】数据链路层采用选择重传协议(SR)传输数据,发送方已发送0~3
号数据帧,现已收到1号帧的确认,而0、2号帧依次超时,则此时需要重传的帧数是( )。
A.1
B.2
C.3
D.4

kiko🎃:选择重传协议中,接收方逐个确认正确接收的分组,不管接收到的分组是否有序,只要正确接收就发送选择ACK分组进行确认,因此ACK分组不再具有累积确认的作用。对于这点,要特别注意与GBN协议的区别。此题中只收到1号帧的确认,0、 2号帧超时,由于对1号帧的确认不具累积确认的作用,因此发送方认为接收方未收到0、2号帧,于是重传这两帧;因此本题选B。


🍊4.滑动窗口的大小可以无限长吗?

在选择重传协议中,接收窗口和发送窗口的大小是相同的(选择重传协议是对单帧进行确认,所以发送窗口大于接收窗口会导致溢出,发送窗口小于接收窗口没有意义),且最大值都为序号范围的一半。若采用n比特对帧编号,则需要满足:W_{Tmax}=W_{Rmax}=2^{n-1}

因为如果不满足该条件,即窗口大小大于序号范围一半,当一个或多个确认帧丢失时,发送方就会超时重传之前的数据帧,但接收方无法分辨是新的数据帧还是重传的数据帧,如下图所示,用2bit对帧编号,而窗口大小为3,会出现无法区分新帧与旧帧的情况。

122.一个使用选择重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用
的最大接收窗口是( )。
A.15
B.16
C.31
D.32

kiko🎃:在SR协议中,若采用n比特对帧进行编号,为避免接收端向前移动窗口后,新的窗口与旧的窗口产生重叠,接收窗口的最大尺寸应不超过序号范围的一-半,即W_{Rmax}\leqslant 2^{n-1},即接收窗口最大为2^{5-1}=16;因此本题选B。

123.对无序接收的滑动窗口协议,若序号位数为n,则发送窗口最大尺寸为( )。
A.2^n-1
B.2n
C.2n-1
D.2^(n-1)

kiko🎃:本题并未直接告知使用的是选择重传协议,而是通过间接方式给出的。题目说无序接收的滑动窗口协议,说明接收窗口大于1,所以得出数据链路层使用的是选择重传协议,而选择重传协议的发送窗口最大尺寸为2^{n-1};因此本题选D。

📜习题检测


📜124.题目难度 ⭐️⭐️⭐️

124.【2015统考真题】主机甲通过128kb/s卫星链路,采用滑动窗口协议向主机乙发送数据,链路
单向传播时延为250ms,帧长为1000字节,不考虑确认帧的开销,为使链路利用率不小于80%,帧序
号的比特数至少是( )。
A.3
B.4
C.7
D.8

🍊详细题解:

✅正确答案:B


📜125.题目难度 ⭐️

125.【2019统考真题】对于滑动窗口协议,若分组序号采用3比特编号,发送窗口大小为5,
则接收窗口最大是( )。
A.2
B.3
C.4
D.5

🍊详细题解:

由于选项中没有“1”,因此可以排除停止等待协议、GBN协议,因为这两个协议中的接收窗口都为1。考虑到本题采用SR协议,SR协议要求:

  • 发送窗口大小+接收窗口大小\leqslant 2^{n}
  • 发送窗口大小和接收窗口大小尽量相同
  • 单个滑动窗口大小\leqslant 2^{n-1}

由于本题n=3,发送窗口大小为5,因此接收窗口最大为3。

✅正确答案:B


📜126.题目难度 ⭐️⭐️⭐️

126.对于窗口大小为n的滑动窗口,最多可以有( )帧已发送但没有确认。
A.0
B.n-1
C.n
D.n/2

🍊详细题解:

情况1:在连续ARQ协议中,发送窗口的大小≤窗口总数-1。例如,窗口总数为8,编号为07,假设这8个帧都已发出,下一 轮又发出编号07的8个帧,接收方将无法判断第二轮发的8个帧到底是重传帧还是新帧,因为它们的序号完全相同。

情况2:在GBN协议中,发送窗口的大小可以等于窗口总数-1,因为它的接收窗口大小为1,所有的帧保证按序接收。因此对于窗口大小为n的滑动窗口,其发送窗口大小最大为n- 1,即最多可以有n-1帧已发送但没有确认。

✅正确答案:B

🌕写在最后


计算机网络世界是相当丰富的,内容方向繁多,但只要一步一个脚印,跟随【宇宙计划】吃透、搞懂、拿捏住计算机网络内容是完全没有问题的!后期该系列还会有视频教程和经验分享,关于更多这方面的内容,请关注本专栏哦!

热爱所热爱的, 学习伴随终生,kikokingzz与你同在!❥(^_-)


本文转载自: https://blog.csdn.net/qq_54151955/article/details/124380683
版权归原作者 kikokingzz 所有, 如有侵权,请联系我们删除。

“【计算机网络】第七话·计算机网络的流量控制”的评论:

还没有评论