【计网笔记】数据链路层

目录

向上网络层接口

向下物理层接口

封装成帧

字节计数法

字节填充的标志字节法

比特填充的标志比特法

物理层编码例外法

差错检测

数据链路层协议

停-等式协议

自动重传ARQ协议/带重传机制的肯定确认PAR协议

双向传输的捎带确认

滑动窗口协议

链路利用率

最大数据传输速率

滑动窗口协议实例

1位滑动窗口协议

回退N帧GBN协议

发送窗口长度选择

选择重传SR协议

发送与接收窗口长度选择

• 向上提供透明接口
• 向下将比特流拆分为若干个帧，为每个帧计算校验和
  • 接收端基于校验和检查帧内的比特差错

向上网络层接口

• 无确认的无连接服务
  • 以太网
  • 无需逻辑连接
  • 双方无需确认
• 有确认的无连接服务
  • IEEE802.11（WiFi）
  • 无需逻辑连接
  • 接收方确认收到帧
  • 发送方如果超时未确认，就重新发送帧
• 有确认的面向连接服务
  • 需逻辑连接
  • 每一帧都被编号
  • 每个帧确认收到，只被收到一次，所有帧按顺序收到

向下物理层接口

封装成帧

字节计数法

帧头放入该帧（包括帧头）的字节长度

稳定性差，很少使用

字节填充的标志字节法

用一些特殊字符FLAG表示帧的开始和结束

• 如果特殊字符在数据中出现
  • 发送方的数据链路层在来自网络层的数据前面插入转义字符ESC
  • 接收方的数据链路层删除转义字符再交给网络层
• 如果转义字符在数据中出现，就转义转义字符

• 帧长取决于数据字段内容
  • 最好情况下增加2字节
  • 最坏情况下翻倍

PPP使用

比特填充的标志比特法

开始和结束都用约定的比特模式标记：01111110（0x7E）

如果在数据字段识别到了连续的5个1，就立刻插入一个0

• 帧长取决于数据字段内容
  • 最好情况下增加2字节
  • 最坏情况下增加12.5%（每个字节+1bit）

USB使用

物理层编码例外法

利用物理层编码准备的标记信号来标识帧的开始和结束

• 4B/5B码的16个信号标识

以太网和WiFi使用

• 在帧前插入一个前导码
  • 这个码不会在物理层编码的数据字段中出现
  • 标识帧的开始
• 前导码后是帧长度字段
  • 计算帧的结束处

【2022-912】链路层成帧的方法不包括（A）
A. 偏移量法

B. 物理层编码违例法

C. 带位填充首尾字节标记法

D. 字符计数法

差错检测

• 纠错码：Hamming码
• 检错码：循环冗余校验CRC

【计组笔记】存储器

【2021-912】对于CRC产生式G(x)=x^2+x+1，下面信息正确的是（C）

A. 11101010

B. 11001111

C. 10001011

D. 11100011

数据链路层协议

链路利用率

• n为窗口大小
  • 即为发出的数据帧数量
• Ts为数据帧处理时间=数据帧位数/信道带宽
• Ta为确认帧处理时间=确认帧位数/信道带宽
• BD为传播时延
  • 数据帧去途需要1BD，确认帧返途需要1BD，共2BD
  • 只有整个帧都被收到了才会发出确认帧，有1帧的延迟

最大数据传输速率

最大在途帧数由带宽延迟乘积决定

• 带宽延迟乘积=带宽×传播时延

窗口内位数=单帧位数×窗口大小

• 要调节窗口大小使数据传输速率最大，令两项相等即可
• 当最大数据传输速率与带宽无关时，最大数据传输速率=链路利用率×带宽

【《计算机网络》第3章习题46】考虑在一个无错的64kb/s卫星信道上单向发送512字节长的数据帧，来自另一个方向反馈的确认非常短。对于窗口大小为1、7、15和127的情形，最大的吞吐量分别是多少？从地球到卫星的传播时间为270ms。

【2017-912】太空站到地球带宽为128kbps的无错信道上单向发送512字节的数据帧端到端的传播延迟300ms，确认帧长度忽略不计，接收窗口足够大，问发送窗口分别为1、15、27时，吞吐率（数据发送速率）是多少？若要使信道利用率达到最大，则帧序号至少为多少位？

4096b/128kbps=0.032s

窗口为1时，数据发送速率=min{4kb/(0.032s+0.6s),128kbps}=6.481kbps

窗口为15时，数据发送速率=min{60kb/(0.032s+0.6s),128kbps}=97.215kbps

窗口为27时，数据发送速率=min{108kb/(0.032s+0.6s),128kbps}=128kbps

信道利用率<=1，反解得到窗口大小n>=19.75

接收窗口足够大，认为是SR协议，那么序号空间的一半需要不小于20，需6位序号

停-等式协议

• 信道不出错
• 单向数据流量
  • 信道在每个时刻都是单向的
  • 帧仍然是可以双向传输的
    • 确认帧不算数据帧

发送方每发送一帧都需要等待接收方发送的确认帧，确认后才发下一帧

• 发送方只会收到确认帧
  • 因假设信道不出错

【2018-408】主机甲采用停止-等待协议向主机乙发送数据，数据传输速率是3kb/s，单向传播时延是 200ms，忽略确认帧的传输时延。当信道利用率等于40%时，数据帧的长度为（）。
A. 240比特

B. 400比特

C: 480比特

D. 800比特

【2020-408】假设主机甲采用停-等协议向主机乙发送数据帧，数据帧长与确认帧长均为1000B，数据传输速率是10kb/s，单项传播延时是200ms，则甲的最大信道利用率为（）。

A. 80%

B. 66.7%
C. 44.4%
D. 40%

自动重传ARQ协议/带重传机制的肯定确认PAR协议

• 信道可能出错
  • 帧内比特出错
  • 整个帧丢失
• 单向数据流量

把帧加上0-1记号

• 发送方把帧按发送次序轮流标记为0或1
• 接收方接收到标记位符合的（正确）帧才收下并发送确认帧，否则丢弃帧并等待
  • 如果标记为0的帧传输中丢失，发送方超时重传
  • 如果标记为0的帧抵达接收方并被接收，上传给网络层
    • 接收方下一个期望收到标记为1的帧
    • 确认帧丢失
    • 发送方超时重传标记为0的帧
    • 标记为0的帧到达接收方，接收方拒绝该帧，并再次发送对标记为0的帧的确认

双向传输的捎带确认

接收方在接收帧的不久后就要发给发送方数据，对上一个帧的确认可以搭载在发过去的数据帧上

• 设置计时器
  • 时间结束前有网络层请求就捎带确认
  • 时间结束就发送单独的确认帧

滑动窗口协议

• 信道可能出错
• 全双工通信

• 帧序号0~MAX_SEQ
  • MAX_SEQ一般形如2^n-1（用n位存）
• 窗口上/下边界：应该被最后/先发送的帧
  • 换言之，窗口是自下而上移动的
  • 一旦从网络层收到新帧，上边界上移
  • 一旦从接收方收到确认帧，下边界上移

1位滑动窗口协议

与ARQ类似

回退N帧GBN协议

• 发送窗口尺寸为w>1
  • w=1时退化为停-等协议
  • 利用管道化实现帧连续发送
• 接收窗口尺寸为1

发送方在窗口填满前如果收到确认帧，就可以前移窗口，达到多帧在途

• 如果接收到的帧就是预期的帧且没出错，就收下并交给网络层，发送对这个帧的确认帧ACK，接收窗口向上移动
• 如果接收到的帧不是预期的帧或出错，与没收到帧处理相同，不发送确认帧
  • 接收方的出错帧将超时重传，出错帧的后续帧即使顺利送到，但也因无确认帧而超时重传
  • 累计确认：当第n号帧的确认到达时，第n号帧及其之前的帧都会被确认
    • 此时发送窗口的下边界变为n+1

发送窗口长度选择

发送窗口的长度和最大在途数据帧数相同（超时计时器不太短）

发送窗口的长度必须不超过MAX_SEQ

• 否则由于标号的循环性，会不知道接收到的确认帧是来自当前循环的标号还是上个循环的标号
• 发送窗口的长度+1<=2^n，n是序号位数

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

A. 10Mb/s
B. 20Mb/s
C. 80Mb/s
D. 100Mb/s

【2017-408】

【2018-912】两地相距3000公里（传播速度6us/公里）最大帧64字节，采用GBN协议，带宽为1.536Mbps，则若要最大限度发挥网络带宽，至少需要（D）比特的序号。

A. 4

B. 5

C. 6

D. 7

采用GBN协议，2^n>=110，n>=7

选择重传SR协议

• 发送窗口尺寸为w>1
• 接收窗口尺寸为v>1
  • v=1时退化为GBN
  • 接收窗口是缓存区，大小始终不变

接收方缓存丢失帧后续的几个帧，避免大量回退

• 如果接收到的帧标号在接收窗口下边界，就收下并交给网络层，发送对这个帧的确认帧ACK，接收窗口向上移动
• 如果接收到的帧标号在接收窗口内但不是下边界，就收下并缓存
  • 此时意味着接收窗口下边界的帧丢失了
  • 接收方发送一个针对接收窗口下边界的否定确认帧NAK
    • 或者发送一个接收窗口下边界前一个编号的确认帧
  • 发送方针对NAK重发帧或超时重传
• 发送方的发送窗口下边界如果被确认，下边界上移
• 累计确认

发送与接收窗口长度选择

一般发送窗口与接收窗口大小相同

• 发送窗口可以比接收窗口大
• 发送窗口比接收窗口小时，接收窗口存在浪费

发送窗口和接收窗口的长度和必须大于MAX_SEQ+1

• 否则由于标号的循环性，会不知道接收到的数据帧是来自当前循环的标号还是上个循环的标号
  • 当前循环的标号：新数据帧
  • 上个循环的标号：之前的确认帧全部丢失，接收方重传旧数据帧
• 如果两窗口尺寸相同，两窗口的长度*2<=2^n，n是序号位数

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

A. 3

B. 4

C. 7

D. 8

8000b/128kb/s=1/16s

利用率=(1/16s)n/(1/16s+0.5s)>=80%，n>=7.2，换言之，需要至少8帧在途，即发送窗口不小于8，那么需要16的序号空间，即4位。