1. 「计算机网络笔记」第一章 概述
2. 「计算机网络笔记」第二章 物理层
3. 「计算机网络笔记」第三章 网络层
4. 「计算机网络笔记」第四章 介质访问控制子层
5. 「计算机网络笔记」第五章 网络层
6. 「计算机网络笔记」第六章 传输层
7. 「计算机网络笔记」第七章 应用层

3.1 概述

负责

• 差错检测和控制
• 流量控制
  • 基于速率
  • 基于反馈

成帧

• 字符计数法
  • 每帧的第一个字段，标识帧的长度
  • 一旦出错，后续的都出错
• 字节填充的标志字节法
  • 用帧界，特殊的一个字节，标记帧的开始和结束
  • 传输的数据中若是出现帧界，则在帧界前加上转义符
  • 帧，按字节为单位传递，任意比特数的帧不适用，必须是8位整数倍
• 比特填充的标志比特法
  • 以01111110为帧标记
  • 如果帧的内容中也出现了与帧标记相同的位串，则在传输中变成011111010
  • 5个1以后一定会插入一个0
• 物理层编码违例法
  • 帧界：冗余信号

作用

• DataLink Layer 位于物理层之上，网络层之下
• 提供有效的、可靠的帧传输

3.2 差错处理概述

错误的处理

• 纠错：恢复出正确的数据
• 检错：仅仅检查出错误，往往伴随重传

错误的种类

• 单个错误：分散在各个数据块
• 突发错误：整个块都是错误

纠错码

• 前向纠错技术
• 有线网中极少采用，主要用于无线网

检错码

• 局域网中主要采用

码字

• 包含数据位、检验位的 n 位单元（模式）
• 海明距离
  • 两个码字之间，不同位的数目
  • 可用异或计算，运算结果中1的个数
  • 如果海明距离为d，则一个码字需要发生d个1位错误才能变成另一个码字
  • 一组码字的海明距离：任意两个码字的海明距离中的最小值
• 海明距离为d+1的编码能检测出d位的差错
• 海明距离为2d+1的编码能纠正d位的差错
• 海明距离越大，纠错能力越强，合法码字减少，传输效率降低

3.3 纠1位错的海明码

冗余位和数据位的关系

• 冗余位：r
• 数据位：m
• 传输：n=m+r
• (m+r+1) ≤ 2^r

海明纠错码

• n从左到右编号
• 校验位：编号位为2的次幂
• 数据位：剩下的位
• 校验位的依据为包括自身在内的一些位的集合的奇偶值(采用奇校验/偶校验)

校验位的决定

• 将某一位数据位的编号展开成2的乘幂的和，则每一位所对应的位即为该数据位的校验位

• 如：m = 7，r = 4

  	B1	B2	B3	B4	B5	B6	B7	B8	B9	B10	B11
  	P1	P2	D1	P3	D2	D3	D4	P4	D5	D6	D7
  1=20	✔		✔		✔		✔		✔		✔
  2=21		✔	✔			✔	✔			✔	✔
  4=20				✔	✔	✔	✔
  8=23								✔	✔	✔	✔

编码

• 原数据：1001000，m = 7，r = 4，n = 11
• 使用偶校验

原数据：1001000

P3 = 只有一个1，校验码为1

纠错

• 对每一位校验位进行校验
• 出错的数据位 = 出错的校验位的和

3.4 检错码

分类

• 奇偶校验
• 互联网校验
• 循环冗余校验

循环冗余检错码CRC

• k位的帧 = k-1次的多项式，最末端视作0次

• 例：1011001 => X⁶+X⁴+X³+X⁰

• 生成多项式：G(x)，r阶

• m位帧的生成多项式：m > r，M(x) > G(x)

• 发方

  • X^rM(x)/G(x) = Q(x)+R(x)
  • (X^rM(x)-R(x))/G(x) = Q(x)
  • 编码后的码字：X^rM(x)-R(x)

• 收方

  • (X^rM(x)-R(x))%G(x)
  • 整除，说明接收正确

3.5 基本数据链路层协议

无限制的单工协议

• 假设
  • 数据单向传送
  • 收发双方的网络层都处于就绪状态
  • 处理时间忽略不计
  • 无限空间
  • 完美通道：信道不损坏、不丢帧
• 乌托邦协议

单工停/等协议

• 半双工的协议

• 取消了收方无限空间的假设

• 收方收到数据后，如果有能力处理，回发一个哑帧给发方

• 发方收到哑帧，可以再次发送下一帧数据

有噪声信道的单工协议

• 肯定确认重传 PAR

• 取消了完美信道、收方无限空间的假设

• 特点：确认帧，定时器

• 收方收到的帧通过校验，向发方发送确认帧

• 发方收到了确认帧，才会发送下一帧

• 发方在发送数据以后，启动一个定时器，期望在超期前，收到确认帧

• 发方在定时器超期以后，重传帧

• 区别帧和重传帧：帧的序号

提高效率

• 全双工：不再区别收方、发方，可以互发数据
• 捎带确认：确认帧可以稍带到发送给对方的数据里
  • 外发的数据帧(s.ack)
  • 捎带确认的定时器，超期则单独发送确认帧
• 批量发送：利用停/等的空闲时间

3.6 滑窗协议

两个窗口

• 发送窗口：已经发送，未确认
• 接收窗口：期望被接收的帧的序列号

滑窗技术的原理

• 窗口数：1
• 帧的序号seq：只用一个比特，0/1，交替出现
• 确认帧ack：指对面发送的seq

窗口滑动的条件

• 接收方
  • 收到帧的序列号，是期待接收的帧号
  • frame_expected+1
• 发送方
  • ack(收到的确认帧) = next_frame_to_send(曾经发出的帧号)
  • next_frame_to_send+1

重复帧的问题

在接收到确认帧之前，定时器超时，重新发送帧给对面，对面发现帧重复，再次发送确认帧回来。导致重复帧很多，但是正常工作。

合适的窗口数 W

• 信道容量：一帧发出到目的期间，信道上能够容纳的帧的数量
• 带宽-延迟积：B×D
• 窗口值：2DB+1

3.7 回退N帧

• 连续的发送好多数据帧，其中一个帧出错，则丢弃错帧及后续的帧，后续全部重传
• 需要发送方付出更多的缓存代价
• 适合出错率较少的高速信道

发送方的重传策略

• 出错帧以及所有的后续帧，缓存在发送窗口中
• 发送方连续发送至发送窗口满
• 对帧编号，未被确认的帧缓存
• 收到确认，释放确认帧所占用的缓冲区，滑动发送窗口
• 定时器超时，回退到超时的帧，顺序重传最后被确认帧以后 的缓存区中缓存的帧

接收方

• 每收到期望的正确帧，上交网络层，回送确认

• 收到出错帧，丢弃，回送对接受的最后正确帧的确认(无法使用捎带确认)

累计确认

• 发送seq = 0~7，回发ack = 7

• 暗含着对第7帧，及其之前所有的帧的确认

• 发送窗口

  • W ≤ MAX_SEQ
  • 防止出错时，无法区分ack是哪一个窗口的
  • 即每次发送的窗口的seq不能顺序排列相同，如：0_7，07，应为0_7，86，7~5

• 接收窗口：W = 1

3.8 选择性重传

• 适用于通信环境质量糟糕，出错率较大的情况

接收方

• 正常接收：上交网络层，回送确认ack，滑动接收窗口

• 丢弃出错帧，如果后续帧正确，缓存下来，回送对接收的最后正确帧的确认

• 收到重传帧：将缓存帧排序上交，回送确认ack，滑动接收窗口

• 避免等待发送方的出错帧超时，接收方在遇到出错帧时，使用nak（Negative-Acknowledgment)

发送方

• 正常发送：对帧编号，等待确认的帧缓存
• 收到确认：释放确认帧所占缓冲区，滑动发送窗口
• 出错/超时：重传缓存的最后被确认帧的后面那一帧

滑动窗口长度 W 的选择

• 发送窗口：W = (MAX_SEQ + 1)/2
• 避免前后两个窗口里的序列号出现重复
• 第一次回送的确认帧，如果丢失，发送方超时重新发送，此时如果接收方期待的帧里的序列号(后一个窗口)和发送方重发的帧里的序列号(前一个窗口）重复，则会出错
• 即：重传帧被当作新帧被接收

三种协议的窗口大小