【计网笔记】数据链路层

标签：发送窗口确认笔记计网信道发送窗口接收链路层

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

向上网络层接口

无确认的无连接服务
- 以太网
- 无需逻辑连接
- 双方无需确认
有确认的无连接服务
- 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

逻辑链路控制LLC子层

链路利用率

$utilization\ rate = \dfrac{nT_s}{T_s+2BD+T_a}$

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

最大数据传输速率

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

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

$max\ data\ transfer\ rate = \min\left\{\dfrac{bits\ in \ the\ window}{T_s+2BD+T_a},bandwidth\right\}$

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

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

【《计算机网络》第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

$\displaystyle \frac{8000b \times 1000}{\frac{8000b}{100\times 10^6 b/s}+2\times 50ms} \simeq 80Mb/s$

【2017-408】

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

A. 4

B. 5

C. 6

D. 7

$\displaystyle \frac{512sb}{\frac{512b}{1.536\times 10^6 b/s}+2\times 18ms} = 1.536\times 10^6 b/s, s=109$

采用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位。

介质访问控制MAC子层

信道分配

静态信道分配

信道复用

不适合突发性流量

动态信道分配

竞争系统：多个用户在共享一个信道的过程中可能发生冲突的系统

多路访问协议

总线拓扑下

ALOHA

纯ALOHA

有数据立刻发送
如果帧没有传过去（不管任何原因），等待随机时间后重新发送
- 两帧冲突必然导致两帧都传不过去
站在发送帧前并不侦听信道

帧时：传输一个帧的时间=帧长度/比特率

一个帧在链路上的时间

吞吐量=每帧时产生帧的平均数量G×成功传输概率P

当G太小时，成功传输率高，帧与帧之间有时间间隔，吞吐量有进一步上升空间
当G充分大时，冲突率增高，P下降
- 极端情况没有任何一个帧可以传过去，吞吐率为0

最大吞吐量1/2e

分槽ALOHA

时间槽长度等于帧时
任何帧的发送都填充一个时间槽

最大吞吐量1/e

载波侦听多路访问CSMA协议

1-坚持型CSMA

当站想发送帧时首先侦听信道
如果信道空闲，立刻发送帧
- 空闲时以概率1发送帧
如果信道忙，就等待直至信道空闲
如果冲突，就随机等待一段时间后再侦听信道

减少信道空闲
增加冲突概率
- 传播时延越大，冲突率越高

p-坚持型CSMA

信道需要带时间槽

当站想发送帧时首先侦听信道
如果信道空闲，以概率p在当前时间槽发送帧
- 以q=1-p的概率延迟至下一个时间槽发送
如果信道忙，就等待一个空闲的时间槽
如果冲突，就随机等待一段时间后再侦听信道

减少信道空闲
增加冲突概率
- 传播时延越大，冲突率越高

非坚持型CSMA

当站想发送帧时首先侦听信道
如果信道空闲，立刻发送帧
如果信道忙或者冲突，就随机等待一段时间后再侦听信道

减小冲突概率
增大信道空闲
- 可能发现忙之后短时间内信道变为空闲

带冲突检测的载波侦听多路访问CSMA/CD协议

在CSMA基础上，如果检测到冲突，立刻停止传输该帧
- 发出一个干扰信号在信道上广播，所有站点都知道发生了冲突
- 等待一段随机时间后重新尝试传输

竞争槽：2×传播时延

最好情形：两边同时发送，在中点处冲突，1倍传播时延
最坏情形：在一边帧即将到达时另一边发送，2倍传播时延
不能同时双向通信
- 半双工通信

【2013-408】下列介质访问控制方法中，可能发生冲突的是（B）

A. CDMA
B. CSMA

C. TDMA
D. FDMA

【2015-408】下列关于CSMA/CD协议的叙述中，错误的是（B）

A. 边发送数据帧，边检测是否发生冲突
B. 适用于无线网络，以实现无线链路共享
C. 需要根据网络跨距和数据传输速率限定最小帧长
D. 当信号传播延迟趋近0时，信道利用率趋近100%

【2019-408】假设一个采用CSMA/CD协议的100Mb/s局域网，最小帧长是128B，则在一个冲突域内两个站点之间的单向传播延时最多是（B）
A. 2.56us
B. 5.12μs
C. 10.24us
D. 20.48us

【2019-912】以太网中最短帧长1000bit，最远两点相距离100m，数据在光纤中的传播速率为2×10^8m/s，最大发送速率为（A）
A. 1Gb/s

B. 2Gb/s

C. 100Mb/s

D. 200Mb/s

传播时延5×10^{-7}s，竞争槽10^{-6}s，最大发送速率10^{9}b/s=1Gb/s

无冲突协议

位图协议

令牌传递

二进制倒计数

有限竞争协议

结合竞争协议与无冲突协议

竞争协议
- 轻负载下发送延迟小
- 重负载下信道利用率低
无冲突协议
- 轻负载下发送延迟大
- 重负载下信道利用率高

自适应树遍历协议

初始状态下在根节点下的叶节点（即所有叶节点）可以竞争时间槽

如果无冲突，按广度优先遍历分配下一时间槽
- 时间槽均匀分布
如果发生冲突，按深度优先遍历分配下一时间槽
- 减小组内站

系统负载重时，从根节点开始冲突率很高，按就绪站点数决定试探层数

设共有均匀分布的q个站就绪
那么高度为k的节点上有q/2^k个站就绪
要使冲突率低且利用率高，应有q/2^k=1

无线局域网

隐藏站点问题：竞争者距离太远，导致两个竞争者互相感知不到对方

暴露站点问题：非竞争者距离太近，导致非竞争者误以为信道被占用

冲突避免多路访问MACA协议

发送方发一个请求发送帧RTS给接收方
- 发送方附近的站点一段时间内静默
接收方发一个允许发送帧CTS向发送方
- 接收方附近的站点一段时间内静默
发送方开始发送
如果接收方同时收到了多个RTS
- 这些RTS都是损坏的
- 接收方没法回应CTS
- 发送方一段时间内没有收到CTS，等待随机时间后重新尝试

【2023-912】无线局域网面对暴露站问题可采用RTS/CTS解决。（√）

标签：发送,窗口,确认,笔记,计网,信道,发送窗口,接收,链路层
From： https://blog.csdn.net/Resurgence03/article/details/143020695