Wings 的博客
归档 系列 分类 标签 关于 友链 开往
Wings 的博客

计算机网络 - 数据链路层

Wings  收录于  类别 计算机网络 和 系列 计算机网络笔记
     约 4293 字  预计阅读 9 分钟    次阅读     条评论  
/networking-data-link-layer/cover.jpg
系列 -

寄!

检错与纠错

海明码, CRC

数据链路控制Data Link Control

固定大小成帧, 计数即可确定帧边界

可变大小成帧, 需要在 封装了头部和尾部之后 的头尾加入分界标记

向物理层传递帧

当数据有标记字节时, 在前面加入一个转义字符 ESC. 与 \ 类似, 数据中的 \ 被转义成 \\.

标记是 011111110

封装时碰到数据有 0111111 (不是 01111110) 时, 在其后插入一个 0.

这样 011111110 被填充为 011111010. 而数据如果是 011111010, 则被填充为 0111110010.

解析碰到 0111110 时, 移除最后一个 0.

自动重复请求Automatic Repeat Request (ARQ) (大白话就是重发) 是控制的核心.

大概就是, 如果出现差错, 接收方没有收到, 或者接收方处理不过来, 直接丢弃这一帧, 则发送方重发这一帧.

帧按模 $2^k$ 依次递增编号, 称为 序列号Sequence. 以下运算均在模 $2^k$ 下.

窗口最大为 $2^k-1$, 表示不必等待对方收到的回应, 可以发送的帧个数.

两个指针, 左指针表示期待接收最小 ACK 序号, 右指针表示下一次将要发送数据帧序号.

需要保证 $l - r \le 2^k$, 否则会出错.

l 0 , r 1 2 3 4 5 i n 6 i t 7 8 0 … 0 l 1 s e 2 n t 3 0 4 r , 5 1 , 6 2 7 , 8 3 0 … 0 r e 1 c v 2 l A 3 C K 4 r 1 5 ( 6 n o 7 A 8 C K 0 0 … ) 0 t A 1 i C m K 2 l e o 3 3 u , t 4 r , r e 5 n s o e 6 n A t 7 C K 2 8 , 2 0 3 o … r

发送序号为 $S_r$ 的帧, 接收方收到后, 会发送 确认收到Acknowledgment (ACK) 帧. 这个帧也带一个序号, 表示期待接收到的数据帧.

如果收到 ACK $x+1$, 则表示 $S_l$ 到 $x$ 都收到了, $S_l$ 移动到 $x+1$ 处.

如果一段时间后, 没有收到任何处于 $[S_l, S_r)$ 之间的 ACK (数据帧/ACK帧损坏/丢失), 则重发窗口内的所有帧.

只有一个定时器, 时间到重发整个窗口的帧. 因为需要重发, 所以要保存副本. 接收到了就删除副本.

发送窗口大小为 1 的回退 N 帧.

接收方也使用窗口. 发送方和接收方的窗口最大都是 $2^{k-1}$.

发送方记录一下收到了窗口内哪些序号的 ACK, 不重发窗口内所有, 而是重发没收到 ACK 的. 那么这里对每一帧都需要一个定时器.

接收方的右指针 $r$ 定义为 $l + 2^{k-1}$. 如果收到的数据帧序号在 $[R_l, R_r)$ 之外, 则不理会这一帧. 否则记录收到了窗口哪些序号的数据帧, 并发送 ACK 或者 NAK (或者由于 NAK 已经发送过了而什么都不发). 一旦记录收到的是窗口的前缀, 则移动 $l$.

这里接收方如过接收到的不是 $R_l$, 则会发送 否定确认Negative Acknowledgment 帧 NAK $R_l$, 告诉发送方期待收到序号为 $R_l$ 的帧 (而不是 ACK $x+1$, 并且记录后也不会再发送 ACK $x$ 了), 而收到了其他帧. 说明这帧可能丢失. 或者收到了 $R_l$ 的数据帧, 但是损坏了, 接收方也发送 NAK $R_l$. 发送方收到了 NAK $y$ 后, 立即发送数据帧 $y$, 并重置该帧的定时器.

接收方在发送了某个 NAK $R_l$ 后, 假如又收到了非预期帧或者损坏帧, 不会再次发送 NAK $R_k$ (因为这是一样的).

如果 NAK 丢失或损坏也没关系, 有定时器会重发的. NAK 的意义在于提高通信的效率 (不能老等老长一段时间再重发).

发送方发送数据开始, 收到 ACK 结束为一个周期, 这一个周期中, 用来发送数据所用的时间占比, 就是链路利用率.

这里需要数据帧的传输延迟 $T_d$, ACK 的传输延迟 $T_a$, 传播延迟 $T_p$ (有些题会给数据帧的长度和发送速率, 需要自己算传输延迟, 有些题 ACK 和数据帧长度一致但他不说, 理解为捎带即可)

利用率 = $\frac{T_d}{T_d + T_a + 2T_p}$

面向位的协议

语法记不住, 放弃. 要真考每一位表示啥, 那你电真的太会出题了.

面向字节的协议

同上

多路访问

多个信号需要发送, 但是只有一个介质, 所以需要一个方法来分配介质的使用权. (又有点像 CUP 分配给进程)

发, 收不到 ACK 就是冲突了, 等 $\mathrm{Rand}(2^k) T$ 再发, 然后 k++ (截断型二进制指数退让算法). $T$ 可取帧传输时间 $T_{fr}$ 或者传播时间 $T_p$.

脆弱时间Vulnerable Time是 $2 T_{fr}$, 意思是在这一帧发之前的Tfr和开始发之后的 $T_{fr}$ 内都有可能有人再发, 这时候发就会干扰这一帧.

发送的时刻离散掉, 为 $T_{fr}$. 这样脆弱时间就变成了 $T_{fr}$. (画个图就懂了)

先听后发. 听不到有人在说话, 我就说话. 可能别人说的话还没有传过来, 但是我发了, 也会冲突. 所以脆弱时间是 $T_p$.

如果有人在发, 有如下三种方法:

  1. 1 - 持续: 一直监听, 空了就发
  2. p - 持续: 空了就以 p 的概率发, 否则等到离散的时间点再监听
  3. 非持续: 空了就发, 否则就等 $\mathrm{Rand}(2^k) T$ 再监听

解决 CSMA 的冲突问题

我在说话的时候听到别人说话, 我就闭嘴, 随机延迟以后再重发

最小帧长度:

A 传播到 B 的一瞬间, B 开始发送, 同时检测到冲突, B 停止发送, 但是有一点信息传播到 A, A 知道冲突了, 停止发送 (画图时空图易得)

$$T_{fr} \ge 2T_p \Longrightarrow \frac{L}{N} \ge 2T_p \Longrightarrow L \ge 2T_pN$$

半双工的线才要 CD, 全双工本来就可以两边发而不冲突.

检测到空闲通道, 等待 一段时间 (称 帧间间隔Interframe Space , IFS) 后再检测一下, 依然是着的, 那就再等待 通道空闲 的 $R = \mathrm{Rand}(2^k)$ 个单位时间 (单位时间称为时隙, $R$ 个单位时间称为竞争窗口) (用 1/0 表示单位时间序列, 通道空闲的状态, 比如 $R = 6$, 111000101001, 计数到第六个 1, 发送, 而不是等连续六个 1)

然后等待 ACK, 没等到的话 k++, 按上述规则重发.

  1. 预约Reservation: 发送预约帧, 预约了的设备在其预约的时间内发送信号.
  2. 轮询Polling: 一个主站负责问, 你要不要发, 不发就发个 NAK 告诉我, 我问下一个, 要发就发 ACK 告诉我. 主站也可以主动发, 发送一个 SEL 给目标站点, 问你有没有准备好收, 准备好了发个 ACK 告诉我, 我给你发数据.
  3. 令牌Token: 令牌在环里传递, 有令牌的人才能发. 发完了/不发就传令牌给下一个人.

就没考过, 考了就寄

标准以太网

背就完事了, 别人规定的东西, 理解不了

貌似只考标准以太网

介质访问控制层 (MAC) 协议: 1 - 持续 CSMA/CD 数字编码: 曼彻斯特

六个字节, 用 : 分割, 以 16 进制表示.

目的 MAC 地址的第一个字节如果是 FF, 则数据广播. 否则偶数 (最低位0) 是单播, 奇数是多播.

源地址永远是单播.

发送字节从左到右, 但是每个字节里位是从低到高发送的.

时隙定义为发送 512 位所需要的时间. 随着数据速率的不同而不同. 标准以太网是 10Mbps 的. 所以 $\tau = 51.2\mu s$

时隙也是发送干扰序列 (为了凑到定义的时间) 时间 + $2T_p$. 发完 512 位后没有冲突, 则说明整个通道都被我抢占了, 之后不用监听了. (画时空图可知)

无干扰序列, 时隙全部用于往返传播, 则 $T_p = \frac \tau 2$. 电磁波在介质中的传播速率 $v = 2 \times 10^8 m/s$, 有:

$$L_max = v T_p = \frac \tau 2 = 5120m$$

当然这是理论值, 忽略了中继器和接口的延迟.

  1. 10Base5 10Mbps, 线的长度500m
  2. 10Base2 线长 200m (185m)
  3. 10Base-T (双绞线)
  4. 10Base-F (Fiber, 光纤)

物理寻址

D e s t 6 M B A C A d d r S o u r c e 6 M B A C A d d r T y p e 2 / B L e n D a t a 4 6 w B i t - h 1 P 5 a 0 d 0 d B i n g C R C 4 - B 3 2

Type/Len 有两种情况, 会给出 (不给做个鬼). 如果是 Type, 指的是上层的协议. 如果是 Len, 指的是数据 (和填充) 的长度.

加上一个头 AAAAAAAAAAAAAAAB (二进制下是 1010 … 1011), 用于同步和表示帧开始. 最后一个字节 (AB) 称为起始帧分界符 (SFD)

无线局域网 IEEE 802.11

基本服务集Basic Service Set (BSS) 是一块能够相互访问的移动站 (和基站 访问点Access Point, AP)

拓展服务集Extened Service Set (ESS) 是几个 BSS 的 AP 链接到一条线上 (有点像 Bus), 这样不同 BSS 之间可以通信. 线可以在链接到服务器或者网关, 这样可以更远通信.

使用 CSMA/CA

A 要发数据时, 根据 CSMA/CA, 等待一个 IFS (称为分布式 IFS, DIFS) 后, A 发送请求发送帧 RTS 给 B, 同时 RTS 传输到 A 周围的站点, 它们开始不发送数据.

B 收到 RTS, 等待一个 IFS (称为短 IFS, SIFS) 后, 发送 CTS, 告诉 A 收到了, 同时告诉 B 周围的站点, 它们开始不发送数据.

A 收到 CTS 后, 等待 SIFS, 发送数据帧, B 收到后, 等待 SIFS, 发送 ACK.

如果在发送 RTS 或者 CTS 时, 其他人发送 RTS, 则冲突, 收不到 RTS 或 CTS. 根据 CSMA/CA, 等待 $\mathrm{Rand}(2^k)$ 个单位时间后重发.

AP 等待 PIFS 轮询, PIFS 比 DIFS 短, 于是 AP 有更高的优先级.

引用

A要发给B帧之前, 先发一个RTS, 让A旁边的傻逼们闭嘴.

B收到RTS之后, 再发一个CTS, 让B旁边的nt们小点声.

然后A和B就可以bb了.

摆烂 (指 IEEE 不管这个问题)

摆烂 (指我不管这个问题)

连接

无源集线器: 红石线 (线的一部分? 书上说物理层以下)

中继器Repeater: 红石中继器, 收到信号后解码再重新发信号, 而不是粗暴地放大信号

有源集线器Hub: 多端口中继器

链接网络. 有一个 地址 - 端口表, 可以过滤转发.

学习: 目的地址不在表中, 则广播. 从某个端口收到一个数据帧, 这个帧有地址, 那这个 地址-端口 就建立起来了.

循环问题: 网络里有多个网桥, 则广播可能会造成两个网桥之间一直在转发. 方法是求一个生成树, 当成只有树边, 这样就没有环了.

果果说不考

有一万个端口的网桥, 直接站点到站点进行转发.

交换机给每个用户的带宽是固定的.

半双工下, 总容量 = 用户数 * 带宽

全双工下, 总容量 = 用户数 * 带宽 * 2 (蛤? 为啥 * 2?)

果果说默认半双工, 除非题目说.

网络层再说.

利用交换机的功能, 将端口逻辑地划分虚拟局域网. 多台交换机链接到主干交换机上的话, 可以将两个局域网看成一个网络, 划分虚拟局域网.

虚电路网络

交换机维护数据输入端口和输入的点标号 (称为 虚电路标识符Virtual Circuit Identifier, VCI). 以及输出端口和输出的点的 VCI.

分组都带一个 VCI, 表示从哪发的 (最近的点, 不是源头), 这个 VCI 在传输的过程中会变.

发送方发送建立请求, 交换机学习 VCI 表 (像网桥那样, 只不过维护了输入对应的输出, 而网桥只是维护一个输出, 因为有了目的地址, 而虚电路交换机没有, 所以通过输入 VCI 和输出 VCI 唯一确定路径). 从某个端口输入的分组的 VCI 可能不一样, 目的地也可能不一样, 所以不是按照端口来转发, 而是按 VCI. 此时, 输入端口, 输入VCI, 输出端口可以确定, 而输出 VCI 无法确定.

接收方收到发送请求后, 发送 ACK, 并带上 VCI, 然后交换机就可以把输出 VCI 补全了.

按表传输即可. 交换机收到了数据, 要判断一下 VCI, 决定转发. (在电路交换中, 没有这一步, 因为电路交换直接在物理层面建立了一条链路, 直接传信号即可).

发送拆除, 并删表.

建立, 拆除, 分组到每个交换机需要收全再转发, 所以有发送次数个传输延迟. 当然还要加上传播延迟.

更新于 2022-06-13
返回 | 主页