计算机网络数据链路层可靠传输

如何实现数据链路层帧的可靠传输

可靠传输指的是发送端发什么接收端就接收什么，而不可靠传输指的是在出现差错后丢弃帧。为了实现可靠传输，数据链路层实现了停止等待（SW）协议、后退N帧（GBN）协议、选择重传（SR）协议。具体到物理链路，有线网采用的是不可靠传输，无线网采用的是可靠传输。

可靠传输

传输差错：
- 出现在数据链路层的上层的：分组重复、分组失序、分组丢失
- 出现在数据链路层及其下层的：误码（比特差错）
不可靠传输和可靠传输服务：
- 使用CRC循环冗余差错校验，接收方的数据链路层可检测出帧在传输过程中是否出现误码
- 数据链路层向上层提供的服务：
  - 不可靠服务：丢弃有误码的帧
  - 可靠服务：发送方发送什么接收方就接收什么
- 有线链路误码率较低，为了减小开销不要求数据链路层向上层提供可靠传输服务，如果出现差错，可靠传输的问题由上层处理
- 无线链路误码率较高，必须向上层提供可靠传输的服务。
可靠传输并不局限于数据链路层（如 HTTP、 SMTP），但是可靠传输的实现比较复杂，开销比较大，是否使用可靠传输取决于应用需求。

停止——等待协议

每发送完一个数据帧必须停下来等接收方发来该数据帧的确认帧才能继续发送下一帧。
超时重传：一般可以将超时重传时间 RTO 设置为略大于首发双方平均往返时间RTT。
分组编号：如下图发送方发送数据帧，并启动超时重传计时器，接收方正确接收该数据帧并给发送方发送该数据帧的确认帧，但是很不幸该确认帧在传输过程中丢失了，接收方并不知道确认帧在传输过程中丢失了。发送方一直等待接收方发送的确认帧，当超时重传计时器倒计时结束后发送方重传数据帧，但是此时接收方此时无法区分该数据帧是上一个数据帧的重传还是新的数据帧。

为了解决上述问题，引入了数据帧的编号。对于停止等待协议，由于没发送一个数据帧就等待收到接收方发回的确认帧才能继续发送下一帧。因此，只需要一个 bit 对数据帧和确认帧进行编号。

但是，仅仅对数据帧进行编号是不够的，如下图。发送方发送一个数据帧 DATA0 并启动超时重传计时器，接收方收到该数据帧后发回该数据帧的确认帧。但是由于链路堵塞，导致该确认帧迟到了，发送方在超时重传计时器倒计时结束后重新发送 DATA0 数据帧，而后收到了迟到的 DATA0 数据帧的确认帧，发送方继续发送 DATA1 数据帧。接收方在收到重复发送的 DATA0 数据帧后，发回该数据帧的确认帧，但是发送方在收到该确认帧后悔误认为该确认帧是对 DATA1 数据帧的确认帧。

所以需要对数据帧和确认帧同时进行编号。
信道利用率：

信道利用率 \(U \approx \frac{T_D}{T_D+RTT+T_A }\) ，因为确认帧长度远小于数据帧长度 \(T_A << T_D\) \(U \approx\frac{T_D}{T_d+RTT}\)

如果出现超时重传信道利用率还要降低，在RTT较大的情况下为了提高信道的利用率可以采用GBN、SR

回退N帧协议

由于在停止等待协议中，发送方每发送完一个数据帧就要等待接收方发回该数据帧的确认帧才能继续发送下一个数据帧，由此引出了回退 N 帧协议，发送方维持一个发送窗口，发送方在接收到第一个数据帧的确认帧之前可以将落在发送窗口内的其余数据帧一并发送出去，直至发送窗口中的帧全部发送出去。N 的取值不能无限大，如果太大可能会使得网络中的交换节点来不及接收数据帧而造成数据帧的丢弃（如交换节点缓存耗尽等）。

发送窗口和接收窗口：
- 采用 n 个bit 对发送窗口内的数据帧进行编号，则发送窗口 \(W_T\) 的取值范围为\(1<W_T \leq (2^n - 1)\)
- 接收方维护一个接收窗口\(W_R\)，只有正确到达接收方没有误码且落入接收方接收窗口\(W_R\)内的数据帧才能被接收，\(W_R\)的大小为1
滑动窗口：
- 接收方每接收到一个序号落入接收窗口的数据帧，就将接收窗口向前滑动一个位置，这样就有一个新的序号落入接收窗口，同时接收方向发送方发送该数据帧的确认帧。
- 发送方每接收到一个来自接收方的按序确认的确认帧，就将发送窗口向前滑动一个位置，这样就有一个新的序号落入发送窗口，可以被发送方继续发送。
回退 N 帧的含义：若序号落入发送窗口内的已发送数据出现超时，则该数据帧后的其余数据帧都要被重传。即一旦某一帧出现差错，就要退回去重传该帧之后已发送的N个数据帧。
累计确认：
- 接收方不必对收到的每一个数据帧都发送一个确认帧，而是可以在接收到几个序号连续的数据帧后对按序到达的最后一个数据帧发送确认帧。接收方何时发送累计确认帧由具体实现决定。确认帧\(ACKn\)表明序号为n及之前的数据帧全部正确接收。
- 使用累计确认的方式，减少了向网络中注入的数据帧的数量，即使确认帧丢失，也可能不必重传数据帧。
使用 n bit对发送方的数据窗口内的帧进行编号，则发送窗口的取值范围为\(1 < W_T \leq 2^n - 1\)，如果发送窗口的取值过大，会出现接收方无法区分新旧数据帧的情况。

以上图为例，用3 bit对发送方窗口中的数据帧进行编号，若发送方窗口设置为8，假设发送方连续发送了 0 - 7 共计8个数据帧，接收方按序正确接收 0 - 7 号数据帧后返回一个确认帧 ACK7，同时将接收窗口向前移动一个，那么落在接收方窗口中的帧序号就变为了 0 。很不幸该确认帧在传输过程中丢失了，数据帧0的超时重传计时器倒计时为0后重新发送0号数据帧，0号数据帧被接收方正确接收后，接收方无法区分该0号数据帧是之前0号数据帧的重传还是新的0号数据帧。

选择重传协议

选择重传协议：
- 后退N帧协议相比较停止等待协议信道利用率大大提高，但是某一帧的错误会引起已经发送该数据帧之后的其他帧重传，重传是对网络资源的浪费。
- 为了进一步提高新到的利用率，将接收方的接收窗口扩大，以便能够接收失序但是到达接收方且序号落入接收方接收窗口内的数据帧，等所缺帧全部到齐后再一并提交给上层，这就是选择重传协议。
串口编号：

使用n个比特对数据帧进行编号，发送窗口\(W_T\) 和接收方窗口\(W_R\) 关系如下
\[1 < W_R \leq2^{n-1}\begin{cases}1 < W_R \leq W_T \quad W_R超过W_T无意义\\W_T+W_R\leq2^n \quad 确保接收窗口向前滑动后，落入接收窗口内的新数据序号\\与之前的旧的数据序号没有重叠，避免无法区分新旧数据帧\end{cases}\]
当\(W_R\)取最大值\(2^{n-1}\)时候，\(W_T\)能取到的最大值也为\(2^{n-1}\)
收发双方：
- 发送方：在未收到接收方确认帧的情况下可以将落在发送窗口内的其余数据帧一并发送出去，只有在接收到按序发送的数据帧的确认帧后发送窗口才能向前滑动，如果接收到的确认帧不是按序到达的，则对该数据帧进行标记，不再对该数据帧进行超时重传。
- 接收方：可以接收未按序到达的但是帧序号落入接收方接收窗口内的数据帧，为了使发送方仅重传发生错误的数据帧，需要对接收的每一个数据帧返回一个该数据帧的确认帧，只有在按序接收数据帧后，接收窗口才能向前滑动。
发送窗口和接收窗口取值不合适的情况
- 当\(W_R > W_T\)显然没有意义
- \[W_T+W_R > 2^n\]
  
  如上图所示，用3个比特给数据帧进行编号，则数据帧的序号范围是 0- 7，取接收方窗口大小为4，发送方发送窗口为5，发送方首先发送0-5号数据帧，接收方接收正确接收每一个数据帧并返回每一个数据帧的确认帧，同时滑动窗口向前滑动至上图所示，但是很不幸ACK0在传输过程中丢失了，发送方正确接收了1-5号数据帧的确认帧，但是没有收到ACK0，直到数据帧0的超时重传计时器倒计时结束，发送方重传数据帧0，数据帧0正确到达接收方，但是此时接收方并不能正确区分该数据帧是之前数据帧的重传还是落在当前接收窗口内的新的数据帧。