计算机网络——数据链路层（1）

专有名词解析

链路管理

数据链路层连接的建立、维持和释放的过程。

帧定界

将分组信息封装成帧，帧的首部和尾部含有很多控制信息，具有确认帧的界限的作用，所以叫帧定界。

帧同步

接收方从二进制比特流中能够区分出帧的开始和结束。

透明传输

无论什么样的比特组合都能够在链路上传输。即，即使数据中恰好出现与帧定界符相同的比特组合的情况，都能够很好地解决。

流量控制

对发送方的发送速率进行限制，使之适应接收方的接收能力。常见的方式有停止-等待协议和滑动窗口协议等：

停止-等待协议。一帧一帧的发送接收，发送方等到上一帧的响应信号后，才开始下一帧的发送，效率极低。
- 可能出现的差错：① 帧丢失；② 帧破坏（破坏的帧被接收端检出后直接丢弃，发送端的计时器被触发后重发相同的帧）；③ 数据帧正确但确认帧被破坏，发送端会重发相同帧，接收端拒收该帧，并重传确认帧。
- 为了超时重发和判定重复帧的需要，发送方和接收方都需要设置一个帧缓冲区。发送方在发送完一帧后，必须在帧缓冲区中保留此帧副本，若出差错则重传，若接收该帧的确认帧ACK则清除副本。
滑动窗口协议。
- 发送方维护的一组队列（存储着允许发送的帧的序号），称为发送窗口；对应的是接收窗口。两者的窗口大小不一定完全相同。
- 窗口大小即没有收到接收方的确认消息前，还可以发送多少帧。接收端收到一帧时，窗口滑动一帧（要求此帧落在接收窗口内，否则丢弃），同时响应一条确认消息；窗口发送端收到一条确认消息，则窗口滑动一帧。
- 特点：
  - 接收窗口向前滑动时，发送窗口才有可能滑动；
  - 当接收窗口为1时，可保证帧有序；
  - 两个窗口都为1时，等价于停-等协议；
  - 发送窗口>1，接受窗口=1，等价于后退N帧协议（接受帧只允许按顺序接受帧）；
  - 发送、接收窗口均>1，等价于选择重传协议；
  - 数据链路层的滑动窗口协议中，窗口的大小在传输过程中是固定不变的（区别于传输层的滑动窗口协议）。

可靠传输机制

采用确认和超时重传两种机制。传统的自动重传请求分为三种：停等式ARQ（配合停-等协议）、后退N帧ARQ、选择性重传ARQ。后两者配合滑动窗口协议。【可参考上一段“流量控制”，以下是扩展细节】

多帧滑动窗口与后退N帧协议（GBN）。当接受方检测出失序后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧。对某一数据帧的确认就表明该数据帧和以前所有的数据帧均被正确地收到了。（举例：1~~6帧发送出去，第1帧确认并且发送端接收ack1成功，但接收端发现第2帧有误，然后会拒收2~~6帧，并响应一个ack1告知发送端）。推荐阅读：后退N帧协议（GBN）
若采用n个比特对帧编号，那么发送窗口的尺寸要在[1-(2^n - 1)]之间，否则接收方无法分辨新旧帧
- 不设为2^n是为了错位，若n为2，则窗口最大设为3（正向举例），此时帧编号为0、1、2、3。
- 情况1：0、1、2三帧发到接收端，接收端依次返回ack，然后发送端发送新帧，编号3、0、1；
- 情况2：0、1、2三帧发到接收端，接收端返回的ack丢失，由于超时重发机制，发送端发送旧帧，编号0、1、2；
- 两种情况下新旧帧的编号不一致，接收方可以区分。
- 若窗口最大设为2^n，则无法区分新旧帧，造成严重后果。
后退N帧协议优点：提高了信道的利用率；缺点：重传时传送了部分正确数据帧。综上，若传输质量很差，其效率不一定优于停-等协议。
选择重传协议（SR）。推荐阅读：选择性重传。
- 接收窗口存储差错帧后继的所有正确帧；
- 发送方只重传差错帧；
- 接收方接收重传帧，按正确顺序将分组提交网络层。
- 特点：
  - 发送窗口和接收窗口大小相同，一般设为2^(n-1)，n为帧编号的比特数；
  - 接收方缓存区相对较大，因为要用来排序；
  - 每个发送缓存区对应着一个计时器；
  - 当接收方怀疑帧出错时，会发一个否定帧NAK给发送方，要求发送方对NAK中的指定帧进行重传。
  - 对比后退N帧，选择重传协议适合出错率较高的信道。

组帧

按照一定的规则，将网络层递交的分组组装成帧（组帧有首部和尾部，但分组/数据报是帧的data部，不需要尾部定界）。方式：

字符计数法（首部指明帧内字符个数）
字符填充的首尾定界法（特定字符来定界，data区若出现相同编码则加上转义符）
比特填充的首尾定界法（使用01111110即7E标定帧的始末，data区如果遇到5个连续的1则添一个0，接收方采用逆操作）
违规编码法（曼彻斯特编码中，采用高-高或低-低的违规方式来定界帧）

差错控制

传输中的差错都是由噪声引起的。噪声来源有两种：信道固有、持续存在的随机热噪声（可通过提高信噪比来尽量避免）；另一类是外界短暂出现的冲击噪声（难以避免）。差错分为位错和帧错：

位错：某些位出现差错，使用循环冗余校验（CRC）来发现位错，使用自动重传请求（ARQ）来重传该帧。
帧错：帧的丢失、重复和失序的问题。在数据链路层引入定时器和编号机制，可以保证每一帧都唯一正确地交付给目的结点。

差错控制

分为检错编码和纠错编码：

检错编码采用奇偶校验码（例如奇校验码：n-1个信息元和1个校验元，这n个码字中总共奇数个“1”）和循环校验码（CRC，m bit的帧和r bit的帧检验序列（FCS），此m+r能被某提前约好的多项式（例如1101，要求首尾必须是1）整除）。
纠错编码，常用海明编码，2的幂次位是校验码P（1，2，4，8…），其他是信息位D（3，5，6，7）。 P1=P1；P2=P2；D3=P1+P2；P4=P4；D5=P1+P4；D6=P2+P4；D7=P1+P2+P4。
- 发送时，已知信息为D，根据规则：P1与D3、D5、D7有关且异或为0；P2与D3、D6、D7有关且异或为0；类推规则。可以计算出P1、P2等。
- 纠错时，检查各校验码，若有3位校验码（P1、P2、P4），读出来是110，但是异或关系有误，则110==6，书名第6位（即D6有误，取反即可）。

信道效率和吞吐率

信道效率即信道利用率。发送方在一个发送时间周期内，有效地发送数据所需要的时间占整个发送周期的比率。
信道吞吐率为信道效率×发送方的发送速率。