流量控制

2022.08.13

知识点

资料：

图解回退N帧协议（GBN）- 窗口为什么是2^N-1？

停止等待与滑动窗口流量控制原理

1. 停止等待是窗口=1的滑动窗口
2. 窗口大小固定（传输层不固定）

可靠传输机制

1. 停止等待ARQ
2. 后退N帧ARQ
3. 选择重传ARQ
4. 2与3统称连续ARQ

单帧滑动窗口与停止等待协议

1. 0，1帧用ACK0，ACK1确认（确认收到的帧而不是下一帧）
2. 接收端重复接受n：表明发送端进行了超时重传
3. 发送端重复接受ACKn：表明接收端接到了重复帧

多帧滑动窗口与后退N帧协议

1. 累计确认

2. 接收方只能按序接受

3. 窗口大小

   $$\begin{array}{}\text{(1)}& 1\le W_T\le 2^n-1\end{array}$$

多帧滑动窗口与选择重传协议

1. 选择重传ARQ协议；错误传NAK（否定帧）

2. 窗口大小（用nbit对帧编号）

   $$\begin{array}{}\text{(2)}& \begin{array}{c}{W}_T+W_R\le 2^n\\ W_T=W_R=2^{n-1}\end{array}\end{array}$$

计算题要领

1. 链路层流量控制：接受方式不下就丢弃

2. 传输层流量控制：接受端返回发送方一个窗口公告

3. 要重发的“帧数”不是“帧的序号”

4. 小结

   

   • 确认帧发送时间：可能被忽略，可能是与发送帧等长，可能返回也是数据帧
   • 非受限协议下不需要确认帧，就没有确认帧发送时间和传输时间了

计算题

1. 【窗口的定义】 对于窗口大小为n的滑动窗口, 最多可以有( )帧已发送但没有确认 答案：n-1。窗口大小是指2^k=n，发送窗口大小最大=窗口大小-1

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

   A.5

   B.4

   C.3

   D.2

   网友回答

   信道利用率最高，在发送某种帧一定量的情况下达到某吞吐量，为了达到吞吐量，要考虑最坏的情况——全是128B帧。

   $$\begin{array}{rl}{t}_{\text{双}\text{方}\text{发}}& =2\ast \frac{128\cdot 8b}{16kb/s}=128ms\\ RTT& =540ms\\ T& =668ms\\ N& =\frac{668ms}{64ms}=10.4375\to 11\\ N& =2^n-1\to n\ge 4\end{array}$$

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

   A. 10Mb/s

   B. 20Mb/s

   C. 80Mb/s

   D. 100Mb/s

   

   $$\begin{array}{rl}{t}_{\text{发}}& =\frac{8000b}{100Mb/s}=80\mu s\\ t_{\text{发}\text{全}\text{部}\text{窗}\text{口}}& =80ms\\ RTT& =100ms\\ c& =100Mb/s\cdot 80\mathrm{\%}=80Mb/s\end{array}$$

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

   A.3

   B.4

   C.7

   D.8

   $$\begin{array}{rl}{t}_{\text{发}1\text{个}}& =\frac{8000b}{128kb/s}=62.5ms\\ T& =t_{\text{发}1\text{个}}+RTT=562.5ms\\ N& =\frac{562.5}{62.5}\cdot 0.8=7.2\\ N& \le 2^n-1\to n\ge 4\end{array}$$

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

   A.240比特

   B.400比特

   C.480比特

   D.800比特

   $$\begin{array}{rl}t& =\frac{Lb}{3kb/s}=\frac{L}{3}ms\\ T& =\frac{L}{3}+400ms\\ 0.4& =\frac{\frac{L}{3}}{\frac{L}{3}+400}\to L=800b\end{array}$$

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

   A.2 B.3 C.4 D.5

   $$\begin{array}{r}{2}^3-5=3\end{array}$$

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

   A.80%

   B.66.7%

   C.44.4%

   D.40%

   $$\begin{array}{rl}{t}_{\text{发}}=t_{\text{回}}& =\frac{8000b}{10kb/s}=0.8s\\ \eta & =\frac{0.8s}{1.6s+0.4s}=40\mathrm{\%}\end{array}$$

8. 假定卫星信道的数据率为100kb/s,卫星信道的单程传播时延为250ms,每个数据帧的长度均为2000位,并且不考虑误码、确认帧长、头部和处理时间等开销,为达到传输的最大效率,试问帧的顺序号应为多少位?此时信道利用率是多少?

   为达到传输的最大效率采用GBN协议！

   $$\begin{array}{rl}{t}_1& =\frac{2000b}{100kb/s}=20ms\\ T& =520ms\\ N& =520/20=26\\ N& \le 2^n-1\to n\ge 5\\ \eta & =\frac{20\cdot min(26,31)}{520}=100\mathrm{\%}\end{array}$$

9. 在数据传输速率为50kb/s的卫星信道上传长度为1kbit的帧,假设确认帧总由数据帧捎带,帧头的序号长度为3bit,卫星信道端到端的单向传播延迟为270ms。对于下面三种协议,信道的最大利用率是多少?

   1)停止-等待协议

   坑：虽然是捎带确认，往返的都是数据帧，但是分母还是一个RTT😭，原来返回来的数据帧是确认的意义，所以对于前一个数据帧也算成确认帧发送时间的一部分

   $$\begin{array}{r}{t}_1=\frac{1kb}{50kb/s}=20ms\\ \eta =\frac{20ms}{20\cdot 2ms+540ms}=3.45\mathrm{\%}\end{array}$$

   2)后退N帧协议。

   $$\begin{array}{rl}{N}_{max}& =2^3-1=7\\ \eta & =\frac{7\cdot 20}{20\cdot 2+540}=24.14\mathrm{\%}\end{array}$$

   3)选择重传协议(假设发送窗口和接收窗口相等)

   $$\begin{array}{rl}{N}_{max}& =2^{3-1}=4\\ \eta & =\frac{4\cdot 20}{20\cdot 2+540}=13.79\mathrm{\%}\end{array}$$

10. 对于下列给定的值,不考虑差错重传,非受限协议(无须等待应答)和停止等待协议的有效数据率是多少?(即每秒传输了多少真正的数据,单位为b/s

    R=传输速率(16Mb/s)

    S=信号传播速率(200m/us)

    D=接收主机和发送主机之间传播距离(200m)

    T=创建帧的时间(2μs)

    F=每帧的长度(500bit)

    N=每帧中的数据长度(450bit)

    A=确认帧ACK的帧长(80bit)

    非受限协议:不用加传输时延了😭

    $$\begin{array}{rl}{T}_{\text{发}\text{数}\text{据}}& =\frac{450b}{16Mb/s}=28.125\mu s\\ T_{\text{发}\text{送}\text{端}}& =\frac{500b}{16Mb/s}=31.25\mu s\\ T_{\text{传}\text{输}}& =\frac{200m}{200m/\mu s}=1\mu s\\ T_{\text{创}\text{建}}& =2\mu s\\ \eta & =\frac{28.125}{31.25+2+0[\text{不}\text{用}\text{加}\text{传}\text{输}\text{时}\text{延}\text{了},\text{没}\text{有}\text{确}\text{认}\text{帧}]}\\ c& =\eta \cdot 16Mb/s=13.53Mb/s\end{array}$$

停止等待协议:

11. 在某个卫星信道上,发送端从一个方向发长度为512B的帧,且发送端的数据发送速率为64kb/s,接收端在另一端返回一个很短确认帧。设卫星信道端到端的单向传播延时为270ms,对于发送窗口尺寸分别为1、7、17和117的情况,信道的吞吐率分别为多少?

    $$\begin{array}{rl}{t}_1& =\frac{512\cdot 8b}{64kb/s}=64ms\\ \eta & =\frac{[1,7,17,117]\cdot 64ms}{64ms+540ms}=[10.60\mathrm{\%},74.17\mathrm{\%},100\mathrm{\%},100\mathrm{\%}]\\ c& =\eta \cdot c_0=[6.78kb/s,47.47kb/s,64kb/s,64kb/s]\end{array}$$

12. 【2017统考真题】甲乙双方均采用后退N帧协议(GBN)进行持续的双向数据传输,且双方始终采用捎带确认,帧长均为1000B, $S_{x,y}\text{和}{R}_{x,y}$$S_{x,y}和R_{x,y}$分别表示甲方和乙方发送的数据帧,其中x是发送序号,y是确认序号(表示希望接收对方的下一帧序号),数据帧的发送序号和确认序号字段均为3比特。信道传输速率为100Mb/s,RTT=0.96ms。下图给出了甲方发送数据帧和接收数据帧的两种场景,其中$t_0$$t_0$为初始时刻,此时甲方的发送和确认序号均为0,1时刻甲方有足够多的数据待发送

    请回答下列问题

    

    1)对于图(a),t0时刻到t1时刻期间,甲方可以断定乙方已正确接收的数据帧数是多少?正确接收的是哪几个帧(请用S形式给出)?

    $$\begin{array}{r}GBN\to \text{累}\text{计}\text{确}\text{认}\\ \text{收}\text{到}\text{了}{R}_{3,3}\to \text{乙}\text{希}\text{望}\text{收}\text{到}3\\ \text{正}\text{确}\text{接}\text{受}3\text{个}:S_{0,0},S_{1,0},S_{2,0}\end{array}$$

    2)对于图(a),从t1时刻起,甲方在不出现超时且未收到乙方新的数据帧之前,最多还可以发送多少个数据帧?其中第一个和最后一个帧分别是哪个(请用$S_{x,y}$$S_{x,y}$形式给出)?

    $$\begin{array}{rl}& N=2^3-1=7\\ & \to 0\surd ,1\surd ,2\surd ,[3?,4?,5,6,7,0,1],2,3,4,5...\\ & ?:\text{待}\text{确}\text{认}\\ & \surd :\text{已}\text{确}\text{认}\\ & \text{还}\text{可}\text{以}\text{发}7-2=5\text{个}\\ & \text{第}\text{一}\text{个}\text{是}:S_{5,2}\\ & \text{最}\text{后}\text{一}\text{个}:S_{1,2}\end{array}$$

    3)对于图(b),从t1时刻起,甲方在不出现新超时且未收到乙方新的数据帧之前,需要重发多少个数据帧?重发的第一个帧是哪个帧(请用$S_{x,y}$$S_{x,y}$形式给出)

    $$\begin{array}{r}\text{甲}\text{发}\text{送}\text{窗}\text{口}:0\surd ,1\surd ,[2?,3?,4?,5,6,7,0],1,2,3...\\ \text{重}\text{新}\text{发}\text{送}3\text{个},\text{重}\text{发}\text{的}\text{是}\text{已}\text{经}\text{发}\text{过}\text{的}234,\text{第}\text{一}\text{个}\text{是}:S_{2,3}\end{array}$$

    4)甲方可以达到的最大信道利用率是多少?

    $$\begin{array}{rl}{t}_1& =\frac{8kb}{100Mb/s}=80\mu s\\ \eta & =\frac{7\cdot 80\mu s}{2\cdot 80\mu s+960ms}=50.45\mathrm{\%}\end{array}$$