第三章 数据链路层

基本概念

 - 数据链路层使用物理层提供的“比特传输”服务

• 数据链路层为网络层提供服务，将网络层的IP数据报（分组） 封装成帧 传输给下 个相邻结点
• 物理链路： 传输介质(0层)+物理层(1层)实现了相邻结点之间的“物理链路”
• 逻辑链路： 数据链路层需要基于“物理链路”，实现相邻结点之间逻辑上无差错的“数据链路 （逻辑链路）

功能

• 封装成帧
  • 帧定界：确定帧的界限
  • 透明传输：网络层不知道其SDU（服务数据单元，也就是IP数据报）被数据链路层封装成帧的过程
• 差错控制（位错误）
  • 丢弃帧+重传帧（仅需采用检错编码）
  • 接收方发现并纠正比特错误（需要采用纠错编码）
• 可靠传输（帧错误）
  • 帧丢失、重复、失序
• 流量控制
  • 控制发送速度，让接受方来得及接受
• 介质访问控制
  • 广播信道（总线型）需要实现该功能（多点争抢传输介质的使用权）
  • 点对点信道不需要（两节点之间有专属的传输介质）

组帧

把IP数据报封装成帧的过程就是组帧

帧定界

• 字符计数法
  • 帧开头用一个定长计数字段（1B），用来表示帧长（计数字段+帧数据长度）
  • 一旦字段出错，导致误认，会使得后续帧都无法定界
• 字节填充法
  • SOH（01H） start of header
  • EOT（04H）end of transmission
  • 引入转义字符（Escape Character，1CH）来标识中间数据中出现的控制字符，当接受方收到数据时，由于已知帧的界限，在界限之内看到ESC，就可以直接去掉，得到真正的数据
  • 如果中间有转义字符呢？再加一个转义字符来转义转义字符
• 零比特填充法
  • 特殊比特串表示帧开始/结束（01111110）
  • 当数据部分可能出现时，采取每5个1加1个0的策略，使得数据中不可能出现六个1
  • 接受方逆处理，看到5个1就去掉后面的1个0
• 违规编码法（物理层配合）
  • 例如曼彻斯特编码（上跳0，下跳1），违规编码就是中间不跳
  • 用违规的编码做界限标识

差错控制

位错误

奇偶校验

• 加1之后保证有奇数/偶数个1
• 冗余位，仅查是否有错

循环冗余校验码(CRC)

• 约定一个除数，如果除后数值不同，则认为是出错

• 为了方便硬件，所以希望构造一个被除数可以被整除，通过K个信息位+R个校验位作为“被除数”，添加校验位之后保证除数余数为0

• 生成多项式，幂次为对应位置，有幂次则说明该位为1

• 生成余数

  • 信息码左移R位（R就是余数位数，最高幂次），低位补0
  • 进行模二除法（模2除法实际上是不借位的二进制除法，每一位做模2减法（也就是异或）），产生余数，由于模2除的性质，可以保证最后的余数只比除数少一位，也就是R位
  • 出错后的余数存在一定的规律，但是并不一一对应，可以看到出错位数2和位数9余数相同，所以不一定能纠错，除非余数的位数能表示的位数大于CRC码的位数

海明码（检验码+信息位）

• 分组，每组一位检验码
• 由于有信息位n+校验位k，所以表示的状态应该得有$2^k\ge n+k+1$ ，1表示正确的状态
• 校验位放在$2^{i-1}$位置上
• 这样一来k位校验位就可以表达出信息位的正确与否，
  • 通过分组，将信息位的位置序号对应的二进制码的不同数位，对应一个校验位
  • 例如信息位的位置可以用3位二进制码表示，那么位置编码中第一位为1的信息位分给最低位的校验码对应的分组，以此类推
  • 对每个分组做一个偶校验，得到的偶校验位可以表达为该位是否有错 因为编码之间相互交错，当某一位出错时，分组的偶校验结果可以直接指明是哪一位出的错
  • 这个纠错能力只对只有一位的出错有效
  • 检错能力有两位 一般会增设一位全校验位做偶校验，如果失败说明有1位错，可以纠正，如果成功，且分组校验成功，说明没有错；如果分组校验失败，则有多位错，需要重传

流量控制，可靠传输

• 滑动窗口机制
  • 停止-等待机制
    • 发送窗口1，接收窗口=1
  • 后退N帧机制
    • 发送>1，接收=1
  • 选择重传机制
    • 发送>1，接收>1

发送窗口之外不发送，接收窗口之外不接受

接收方控制发送方窗口，通过确认机制，从而实现流量控制

三个协议

停止等待（S-W）协议

• 发送窗口1，接收窗口=1

帧发送时需要在首部或尾部设置帧定界信息，校验信息，帧类型，帧序号等

• 帧序号
  • 用一个bit编号
  • 要满足 $W_T+W_R\le 2^n$ 其中n为用多少bits来编号
  • 所选的帧编号循环的表示帧中的每一位的序号

1. 发送数据帧长度受限于窗口，如果发送0号数据帧，接收方接到之后检错，如果没错，则会发送0号确认帧（ACK0）
2. 接收方窗口右移一位，发送方发送窗口也右移
3. 循环反复

如果数据帧丢失：

• 发送方设置一个计时器
• 如果一段时间没有手收到确认帧，则重发
• 称为超时重传
  • 如果是接收方的确认帧没发送成功，接收方其实会下移一位窗口
  • 此时超时重传，会发送重复帧
  • 接收方会接收帧，丢弃重复帧再返回ACK
  • 发送方下移一位，继续发送
  • 此时序列号起到区分当前发送帧的归属关系作用，否则会陷入混乱

如果有差错：

• 超时重传

不存在数据帧失序问题

后退N帧协议(GBN)

• 发送>1，接收=1
• $W_T+W_R\le 2^n$

发送方的帧大于1，每次接收方发ACK信号时会等到发送方一次发送的所有帧都发完再回复，回复ACKn，n表示n号帧之前的所有帧都接收到

如果中途出现错误，会发生：

• 帧接收的序号不对
• 帧信息错误等

此时会拒绝接收，并在最后一次正确的接收帧发送一个ACK，让发送方窗口移动并重发

这样可以实现流量控制，当速度过快导致接收方无法接收时回退重发

缺点：在接收帧的速度很慢，或误码率很高的情况下，可能发送方发送的进度经常需要后退，导致传输效率低下

选择重传协议

• 发送>1，接收>1
• $W_T+W_R\le 2^n$
• $W_R\le W_t$ 因为这种情况性能会比较好

每次接到都会返回一个ACK，然后窗口各自移动

如果出错：

• 数据帧丢失：例如中间漏了某个，那么窗口移动之后还必须包含那个在内，其余已经发送完成，发送ACK，确认
• 数据帧错误：如果某个帧出错，那么接收方会发送一个否认帧，请求再次发送，而不是等到超时重发
• 确认帧丢失：等到超时重发之后，接收方受到重复帧，然后再发一次

信道利用率

• S-W协议

  • 考虑数据帧长度，确认帧长度，传播时延
  • 利用率为 信道有数据的时间 / 信道总耗时
  • 只考虑数据帧的信道利用率：$U=\frac{T_D}{T_D+RTT+T_A}$ ，其中$T_D$是数据帧传输时延，$T_A$是确认帧传输时延，$RTT$是两倍传播时延
  • 

• GBN，SR

  • 周期性变化，当接收到一个帧就可以移动窗口到下一个帧，计算利用率只看周期内即可
  • 利用率为：$U=\frac{N\ast T_D}{T_D+RTT+T_A}$ N是发送窗口的大小
  • 另外在这种情况下，我们使用第一个ACK接收的时间来确定周期的（因为此时窗口就可以往后移动），其实不一定，如果窗口大小更大的话，在每个帧发送结束之前就可能收到ACK接收帧，此时周期却没有结束，但是在这种情况下，信道上一直都有会有数据帧（因为当窗口发送结束之后不需要等ACK，而是已经接收了一些ACK），这种情况不能直接代入到公式，而是将利用率定为1
  • 

其他术语

• 滑动窗口：
  • 其实只有GBN和SR有
• ARQ协议：
  • 自动重传

介质访问控制

控制各节点对传输介质的访问，减少冲突

信道复用

• 复用：在一条传输媒体上同时传输多路用户的信号
  • 充分利用传输媒体的带宽
  • 复用信道数量大时比较划算（通信成本的增加不亏）

频分复用FDM

• 子信道不同频带，信道之间有隔离频带
• 频分复用的所有用户同时占用不同的频带资源发送数据
  • 同时发送，充分利用带宽
  • 只能用于模拟信号的传输

波分复用WDM

• 光的频分复用，同时传输多个频率（波长）相近的光载波信号
• 也称为密集波分复用DWDM
• 由于频率很广，可以拆成多个子频道

时分复用TDM

• 在用户自己的时隙内使用信道
  • 时隙可能闲置，利用率低
• 一个周期帧称TDM帧
• 时分复用的所有用户在不同的时间占用同样的频带，是信道总带宽的1/m

统计时分复用STDM

• 统计每个节点对信道的使用需求，按需动态分配时隙
• 有需要时可以一个节点可以获得所有的信道带宽
• 利用率高

码分复用CDM

• 又称码分多址（CDMA）
• 相同时间相同频带，抗干扰能力强
• 将每个比特时间划分为m个更短的时间片，称为码片（chip）
  • 码片只有 0 1

原理：

• 每个站点指派一个唯一的m比特码片序列
• 发送 1，就发送自己的序列
• 发送0，就发送反码（规格化内积）
  • 每个序列不同（伪随机码序列），相互正交，规格化内积为0
  • 因此可以叠加传输，因为其他无关信息的接受结果会是0
  • 当接收后计算结果为 1，则比特1，如果 -1，则比特0

Link to original

随机访问

ALOHA协议

• 纯ALOHA：接收ACK，超时重传
• 时隙ALOHA：传输最长帧的时间作为时隙，超时重传
• 随机推迟

CSMA协议

• 监听是否空闲
• 超时重传，随机推迟
• 非坚持CSMA
  • 当不空闲就先放弃监听信道 ，随机等待一段时间
  • 如果刚恢复就用于实践，可能存在一段是
• p-坚持CSMA
  • 坚持监听
  • p的概率直接发，1-p等会再发

CSMA/CD协议

• 先听后发
• 边听边发
• 冲突停发
  • 当传输失败16次，停发
• 随机重发
  • 争用期：$2\times 最大单向传播时延$
    • 传播时延：距离 / 传播速度
    • 为什么是两倍呢？因为在极端情况，当A的数据发到B，B才发出数据，此时A用了一倍，B还得用一倍时间才传输得到A
  • 从$k\le 10$ ，在$[0,2^k-1]$里任取一个随机数，将这个值乘以争用期时间
  • $k>10$ ，取$10$
• 最短帧长
  • $2\times 最大单向传播时延\times 信道带宽$
  • 为什么要这么长？如果不这么长，在极端冲突的情况下，A已经发完了才收到B的信息，会认为没有冲突
  • 达不到就填充
• 总流程
  1. 发送
  2. 是否小于最小帧长
  3. 码分复用判断是否是自己的
  4. CRC校验，是否有错
  5. 接收并发给网络层
• 最长帧长
  • 防止一直被某个节点占用
• 以太网：最短64B，最长1518B

CSMA/CA协议

• CSMA/CD 早期有限以太网

• CSMA/CA IEEE 802.11 无线局域网

• 冲突避免（Collision Avoidance） 监听后发送，发送之前避免冲突，发送之后不检测冲突

• AP(Access Point)：接入点，WiFi热点，在多个AP之间切换，称为漫游

[!为什么不用CSMA/CD] 有线设备上很容易检测是否有站点正在占用信道

• 无线设备有强弱干扰，不同的传播方向，离得远就弱，离得近就强，强的信号干扰弱的信号，如果在发送是采用监听策略，那么自己的信号会盖过别人的信号，或者信号不稳定，导致监听受影响
• 隐藏站，信号有有效范围，不同站之间可能都能发送给AP，但是相互之间可能超过范围，导致检测不到对方的信号

随机退避：

• 发送方：先听后发， 忙则退避
• 信道空闲，间隔DIFS后，发送帧
• 不空闲就退避
• 二进制指数退避算法设置退避时间
• 发送方保持监听，当信道空闲时扣除倒计时，计时结束发送帧
• 接收方采用停止-等待协议，接收到信号就放回ACK，发送方超时未收到则随机退避，在重传数据帧

帧间间隔(IFS)：

• DIFS：最长的IFS，每次帧事务开始之前等待的时间，也就是这个事务最初发送时需要等待的时间，后续都不需要这个间隔
• SIFS：最短的IFS，收到一个帧之后的预留处理时间
• PIFS：中等长度

[!为什么要等DIFS呢] 如果一旦检测到信道是空闲的就发送出去，其实可能是在接收方接收到信号之后的SIFS阶段，此时时不应该发的，所以设置了一个最长的等待时间(大于SIFS+传播时延)来避免这种冲突情况

隐藏站问题：

• 信道预约机制：发送时先预约
  • 发送RTS控制帧，包括源地址，目的地址，持续时间
  • AP发送CTS控制帧，允许发送，广播发送，包括源地址目的地址持续时间，告知可以发送，同时通知其他站点被占用
• 发送RTS也需要先听后发，忙则退避
• 一般比较长的帧才会启用预约功能

有无连接，可靠

轮询访问

环状网络结构，一次只有一个节点可以获得令牌，有令牌才能发送自己的数据，带有源地址和目的地址，数据，令牌号，是否接收等，顺着环状网路发送，每个站点检查是否是自己的数据，是的话修改已接受部分，再往下传递，一直到回到发送方（如果False则可以重发）

当发完数据（只有一次）之后，令牌往下传递

实际上并不是直接接到一起，而是需要使用到MAU设备

局域网的基本概念和体系结构

局域网

• 较低时延和误码率
• 校园网
• 以帧为单位传输
• 单播（一对一）、广播（一对全）和多播（一对多）
• 同一局域网属于同一广播域

有线局域网

重点关注：

• 拓扑结构
• 传输介质
• 介质访问控制方式

令牌环网

• 环形
• 同轴电缆 或 双绞线
• 令牌传递协议

以太网

• 同轴电缆（10Base5）
  • 总线
  • 同轴电缆（中继器连接不同网段）
  • CSMA/CD
• 双绞线以太网（10BaseT）
  • 集线器连接时为总线（逻辑）星型（物理），半双工
  • 交换机连接时物理和逻辑都是星型 可以全双工
    • 当速率小于 2.5Gbps支持全双工或半双工（节点间协商确认，如果都支持全双工，像PC机，交换机就可以，如果有集线器等仅支持半双工的就半双工）
    • 大于2.5Gbps则只支持全双工
  • 双绞线
  • CSMA/CD协议 或 NULL
• 光纤以太网（10BaseF）
  • 点对点
  • 光纤
  • NULL（两天光纤全双工）

无线局域网

• 拓扑结构
  • 星型结构
• 传输介质
  • 无线
• 介质访问控制方式
  • CSMA/CA协议

硬件架构

以太网适配器中ROM存放了唯一的MAC(Medium Access Control) 地址（WiFi网络适配器也有，MAC地址不同） 占48bit

帧数据存放RAM

网络适配器

• 负责把帧到局域网上
• 负责从局域网接收帧
• 实现数据链路层+物理层功能
• 串并行转换
• 帧缓冲

以太网与IEEE 802.3

• 大于100Mbps为高速以太网

常见的两种以太网标准

• DIX Ethernet V2标准
• IEEE 802.3

V2标准的MAC帧

6 6 2 N（46~1500） 4 收发协数验

将IP数据包封装成帧，发给物理层

其中

• 目的地址MAC是48bit，如果全1则为广播帧
• 源地址MAC是48bit
• 类型是 网络层协议 16bit，标明当前发送数据使用的是网络层中的哪个协议（在IEEE中这个部分表明了数据的长度，因为IEEE的MAC层不直接服务网络层，上面还有一个LLC层）
• 数据要求大于最短帧长（填充），小于最长帧长（分片）为什么呢？
• FCS是CRC检验码 所以MAC帧长度是64B~1518B

物理层会插入前导码

• 7B的前同步码（1010101……1010）是一种接收的频率
• 1B的帧开始定界符（10101011）11表示帧开始接收
• 称为 7同步 1定界 在结尾会采用违规编码法
• 留一段间隙
• 或者没有遵循编码规则（例如曼彻斯特编码）

交换机，路由器等都有MAC地址，因为要实现数据链路层等的功能，其中集线器会广播发送，交换机会选择发送

集线器不隔离冲突域和广播域（本身半双工），交换机不隔离广播域（本身全双工），路由器都隔离

VLAN

大型局域网面临

• 广播帧很多，可能带来很多的负载
• 安全节点暴露

解决方法是将大型的局域网分割成若干较小的VLAN，每个VLAN是一个广播域，对应一个VID，不同VID不在于广播域

可以用VLAN将一些敏感节点分开，需要使用支持VLAN的以太网交换机，这些交换机其实通过端口来划分VLAN，如果端口更改，则VLAN更改，这并不方便

Note

端口传输的话，怎么做到跨越交换机还能知道广播信号要给哪个VLAN？

发送的帧是 802.1Q帧(6 6 4 2 N 4 收发V协数验)，帧中包含了VID信息，指明当前数据所属的VID

又提出：

• 基于MAC地址的划分方法 交换机内部数据结构记录MAC与VLAN(VID)的对应关系
• 基于IP地址的划分 内部数据结构记录IP地址与VID之间的对应关系，甚至可以划分到不同网络

无线局域网

分为：

• 有固定基础设施无线局域网（802.11）
• 无固定基础设施移动自组织网络

有固定基础设施无线局域网

• 接入点(AP)，或者无线接入点(WAP) WiFi热点
• 基本服务集BSS（一个基站AP+多个移动站）
  • 服务集标识符SSID 无线局域网的名字，不超过32字节
  • 基本服务区BSA 一个基本服务集能覆盖的地理范围
• 扩展服务集ESS 多个AP连接到一个分配系统，组成更大的服务集
• 数据帧
• 控制帧
• 管理帧

三地址在发给AP和AP发出时含义不同

• 发给AP为 中间节点AP地址，起始地址，终点地址
• AP发出时为 终点地址，中间地址，起始地址

AP与移动站之间无线链路传输 AP与AP，AP与路由，AP与以太网之间为有线链路

以太网交换机

自学习功能

• 交换表（MAC和端口号之间的关系） 如何更新？
  1. 信号经过交换机，如果没见过就保存MAC和得到信息的端口
  2. 发送的目的MAC表里找不到，就广播发送，广播
  3. 有效时间，过期作废

两种交换方式

• 直通交换 只解析MAC帧中的目的地址（48bit），直接发送 转发时延低 不适用于需要速率匹配、协议转换或差错检测的线路（类似于接到什么发什么，像电路通信）
• 存储转发交换 完整接收到高速缓存 时延高 适用于速率匹配、协议转换