计算机网络复习——Ch3点到点数据链路层

知识点

1. 点到点数据链路层要解决的主要问题

• 设计数据链路层的主要目的是在有差错的物理线路的基础上，采取差错控制与流量控制等方法，将有差错的物理线路改进成无差错的数据链路，向网络层提供高质量的数据传输服务。

• 数据链路(data link) 除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路

  • 现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。
  • 一般的适配器都包括了数据链路层和物理层这两层的功能

2. 常见的帧管理（帧定界）方法

• 将比特流分成离散的帧，并计算每个帧的校验和。

  • 帧到达目标机器的时候，目标机器重新计算校验和，如果两个检验和不同，则发生了错误。

• 成帧方法：

  1. 字符计数法
  • 在帧头中用一个域来表示整个帧的字符个数
  • 缺点：若计数出错，对本帧和后面的帧有影响
  2. 带字符填充的首尾字符定界法
  • 每一帧都会用一些特殊字节作为开始和结束
    • 过去，开始和结束字节不同
    • 最近几年，大多数协议采用相同的字节，称为标志字节（FLAG byte）作为起始和结束分界符。
  • 问题：标志字节出现在数据中
  • 解决方法：在数据中的标志字节前面加上一个主义字节ESC—字符填充
  • 缺点：局限于8位字符和ASCII字符传送
  3. 带位填充的首尾标记定界法
  • 帧的起始和结束都用一个特殊的位串“01111110”，称为标记(flag)
  • “0”比特插入删除技术
  4. 物理层编码违例法
  • 只适用于物理层编码有冗余的网络
  • 802 LAN：曼彻斯特编码或差分曼彻斯特编码用high-low pair/low-high pair表示1/0，high-high/low-low不表示数据，可以用来做定界符

• 注意： 在很多数据链路协议中，使用字符计数法和一种其它方法的组合。

3. CRC的计算

• 计算CRC的步骤：
  • 商：长度一样，商为1
  • 差：做异或，不一样就为1
    
    接收方收到的帧除以生成多项式
  • 余数为零则没有出错
  • 余数不为零则有差错

4. 流量控制的基本原理

理想化的协议
- 两个假定
- 传输信道是完美的，所传送的任何数据既不会出差错也不会丢失—不需要差错控制
- 接收端资源无限，不管发送端以多快的速率发送数据，接收端总是来得及收下，并及时上交主机—不需要流量控制
- 去掉上述的第二个假定，但是保留第一个假定，即
- 主机 A 向主机 B传输数据的信道仍然是无差错的理想信道—不需要错误控制
- 不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率—需要流量控制
- 由接收端控制发送端的数据流，是计算机网络中流量控制的一个基本方法

5. 常见错误及其处理机制

• 数据帧校验出错

  • 发送端发送数据帧后，等待接收端的应答帧
  • 接收端收到数据帧后，进行帧校验
    如果没有差错，回送一个确认帧ACK (Acknowledgement)
    否则，不回任何确认
  • 发送端收到ACK，则发送下一帧

• 常见错误及其处理机制

  • 死锁：当数据帧出错或丢失时，接收端不会回送任何应答帧，按照停止/等待的机制，则发送端会永远等待下去
  • 解决方法：超时计时器+主动重传
  • 数据帧重复：如果确认帧丢失，则按照超时重发的机制，发送端会主动重传数据帧，导致接收端收到重复的数据帧
  • 解决方法：给每个数据帧附加不同的序号，如果接收端收到序号相同的数据帧，则认为是重复帧，丢弃，并再次回复一个ACK

6. 滑动窗口的概念、形式及工作原理

• 概念及原理：
  • 发送端和接收端分别设定发送窗口和接收窗口
  • 发送窗口：一个序号区间，对应当前允许发送的数据帧
    • 发送窗口的大小 WS 表示在没有收到对方确认信息的情况下最多可以发送的数据帧个数，即发送出去但还没收到确认的数据帧的最大数目
    • 当窗口左边部分的确认收到，则窗口向右滑动
  • 发送窗口的功能：流量控制
  • 接收窗口：一个序号区间，对应当前被允许接收的数据帧
    • 只有当收到的数据帧的序号落入接收窗口内才允许将该数据帧收下。
    • 若接收到的数据帧落在接收窗口之外，则一律将其丢弃。
  • 当发送窗口和接收窗口的大小都等于 1时，就是停止等待协议
• 形式：
  • 1位窗口滑动协议
  • 连续ARQ协议(回退N协议)
  • 选择重传ARQ

7. ARQ(Automatic Repeat reQuest)协议工作原理：

• 发送方发送一帧，启动定时器，等待；
• 接收方收到数据帧后，校验，如果校验通过，则回送一个确认；
• 发送方收到确认，发送下一数据帧。
• 如果发送方的定时器超时且没收到确认（数据帧校验错、数据帧丢失或者确认丢失等原因），则主动重传；
• 为了防止数据帧重复，每个帧都有一个序号。

8. 连续ARQ(Go-back-N ARQ)工作原理（特别注意累计确认）：

• 连续 ARQ 又称为Go-back-N ARQ，意思是当出现差错必须重传时，要向回走 N 个帧，然后再开始重传。

  • 发送窗口大于1，接收窗口大小仍然是1；
  • 发送方可以连续发送多个数据帧。每帧都有一个定时器；
  • 接收方只按序接收，当收到一个序号正确的帧，校验通过则回送一个确认；
  • 发送方收到确认后，发送窗口滑动，发送新的数据帧；
  • 如果某帧超时，则发送方会重传从此帧开始的所有帧。
    发送方收到对序号是n的帧的确认，则意味着从0到n-1号帧统统正确到达

这种重传易造成严重资源浪费

• 连续ARQ发送窗口的最大值
  • 当用 n 个比特对帧进行编号，不同***的个数是2n：0,1,2，… 2n -1
  • 但只有在发送窗口的大小 WS <= 2n -1时，连续 ARQ 协议才能正确运行
    • 为使旧发送窗口和新接收窗口之间***不发生重叠，有WS＋WR≤2n
    • 而接收窗口WR的大小为 1，
• 例如，当采用 2 bit 编码时，发送窗口的最大值是 3 而不是 4。

9. 选择重传ARQ工作原理

• 工作原理
  • 加大接收窗口和接收缓存
  • 在某些数据帧出错的情况下，先收下后续的、序号处在接收窗口中的那些数据帧；等到所缺序号的数据帧收到后再一并送交主机
  • 可避免重复传送那些本来已经正确到达接收端的数据帧，提高带宽资源的利用率
  • 代价是在接收端要设置具有相当容量的缓存空间
• 目的：进一步提高信道利用率
• 方法：只重传出现差错的数据帧或超时的数据帧
• 要求：在接收方要设置具有相当容量的缓存空间

10. 了解(高级数据链路控制)HDLC协议和(点对点协议)PPP协议

例题

1. 数据链路层采用选择重传协议（SR）传输数据，发送方已发送了0～3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是
   A.1 B.2 C.3 D.4

解析：

• 选择重传只重传出现差错的数据帧或超时的数据帧
• 故重传0、2号帧

2. 数据链路层采用了后退N帧（GBN）协议，发送方已经发送了编号为0~7的帧。当计时器超时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是
   A．2 B.3 C.4 D.5

解析：

• 连续ARQ(后退N)如果某帧超时，则发送方会重传从此帧开始的所有帧
• 故重传4、5、6、7号帧

3. 待发送数据为1101011011，生成多项式为x⁴+x+1，则实际发送的数据是什么？
   
4. (3-2)某数据通讯系统采用CRC校验方式，且生成多项式G(x)的二进制比特序列为11001，目的主机接受二进制比特序列为110111001(含CRC校验码)。
   判断传输过程中是否出现了差错？为什么？