数据链路层

概述

• 以帧为单位处理、传输数据
• 封装成帧、差错检测、可靠传输（适用于点对点的链路）

封装成帧

• 帧头和帧尾含控制信息，作用之一为帧定界，但并非每一种数据链路层协议的帧都包含帧定界标志。

• 透明传输：数据链路层对上层交付的数据不作任何限制。

  • 也就是说数据链路层需要确保帧定界的唯一性
  • 面向字节的物理链路中，与标识符相同的数据后添加转义字符，其十进制值为27
  • 面向比特的物理链路中，使用比特填充法，在数据单元中每5个连续1后添加一个0，确保帧定界唯一性（HDLC协议中帧定界符值为01111110)。

• 可以通过使帧的数据部分的长度尽可能长来提升传输效率

  • 对于每一种协议都有最大传输单元MTU

差错检测

• 误码率：错误比特/总比特
• 使用差错检测码来检测数据是否发生比特差错

奇偶校验

​ 在待发送的数据后面添加1位奇偶校验码，使整个数据“1”的为奇数/偶数，这样在传输过程中发生奇数个误码必将导致数据的奇偶性发生改变。

• 然而若发生偶数位误码将无法检验是否出现错误。

• 漏检率高

循环冗余校验CRC

• 收发双方约定好一个生成多项式
• 发送方基于待发送数据和生成多项式计算差错检测码（冗余码），添加到数据后面一起传输.
  1. 将待传数据与生成多项式最高次个0拼接作为被除数
  2. 生成多项式一般为一元n次多项式，依次将第n次项从高到低一直到第0次的系数写出，就是除数
  3. 计算得到的余数叫差错检测码（冗余码），位数应与生成多项式最高次数相同，不够在前补0；
• 接收方通过生成多项式来计算收到的数据是否产生误码。
  1. 将接收到的数据+余数作为被除数
  2. 与生成多项式比特串作模2除法（余下位数与除数位数是否相等，相等商1，不等商0）
  3. 若余数为0，则无误

可靠传输

如果向上层提供不可靠传输服务,就丢弃有误码的帧。

如果向上层提供可靠传输服务，则试图实现发送端发送什么，接收端就收到什么。

停止等待协议-SW

• 发送方发送数据，接收方检测数据，检测无误，回传ACK。

  • 发送方接受ACK，继续发送数据。

• 发送方发送数据，接收方检测数据，检测有误，回传NAK。

  • 发送方接收到NAK，丢弃数据，重传。
  • 接收方检测无误，回传ACK。

发送方数据分组丢失

• 发送方由于某种原因导致接收方收不到数据，就无法回传ACK/NAK，

​ 发送方一般会在发送数据时启动超时计时器，到达时间若接收不到ACK/NAK，就重传，这个重传时间一般略大于发/接数据平均往返时间。

接收方ACK/NAK丢失

• 由于发送方超时计时器，有可能导致分组重复
• 需要给每个分组带上序号来解决，分组序号占1bit位。
  • 新分组数据序号与上组分组序号不同即可
  • 如果分组序号相同，说明分组重复，这时接收方丢弃收到的分组即可。

接收方ACK/NAK延时

• 接收方ACK/NAK由于某种原因延时，导致发送方无法正确判断ACK/NAK对应的分组。
• 对ACK/NAK进行编号即可，比特位数与数据分组所用编号一致
• 在数据链路层实现一般不用考虑ACK迟到的问题。

一般T_A远小于T_D，可忽略

T_D：发送方发送数据分组所耗费的发送时延

RTT： 收发双方的往返时延

回退N帧协议GBN

累积确认

1. 发送方取W_T大小$1<W_T\leq2^{n}-1$的发送窗口，按组发送数据分组，其中n为构成分组序号的比特数

   • 如果W_T超限，则接收方无法分辨新、旧分组

2. 接受方可以收到n个数据分组后（n由实际情况决定），对按序到达的最后一个数据分组发送确认

   • 如果收到未按序到达的数据分组，全部丢弃，对最近按序接受的数据分组发送确认

3. 发送方如果收到多个重复确认，则可在重传计时器超时前开始重传

4. 发送方发送窗口内的数据分组产生超时重传时，其后续在发送窗口内已发送的分组也必须重传。

• ACK_n代表序号n以前的数据分组全部正确接收

• 发送ACK_n以后接收方可以将正确接受的数据分组交付上层处理

• 可以减小接收方的开销，减少网络占用

• 无法及时向发送方反映，已接受正确的数据分组

选择重传协议SR

• 接收方不能累计确认，需要逐个确认接收到的数据分组，只有全部按序接受数据分组后，接受窗口才能向前滑动
• 同样地，发送方若没全部按序接收确认分组，也不能向前滑动窗口

点对点协议PPP

为各种协议数据报提供标准方法

• 对各种协议数据报封装方法—封装帧
• 链路控制协议LCP—透明传输
• 一套网络控制协议NCPs

媒体接入控制MAC

协调多个发送站点与接受站点对一个共享信道的占用

分为：

• 静态划分信道
• 动态接入控制

提供无连接不可靠服务

信道复用

• 频分复用FDM
  • 同时占用不同的频带资源并行通信
• 时分复用TDM
  • 在不同的时隙中使用相同的频带资源通信
• 波分复用WDM
  • 光的频分复用，在光纤中传输
• 码分复用

码分复用

码分复用CDM：又称码分多址CDMA

• 可以在同样的时间使用同样的频带进行通信
• 各用户使用不同的码型，无相互干扰
• 每一个站被指派唯一一个mbit码片序列，若发送比特1，则发送码片序列本身，若发送比特0，则发送码片序列的反码。

码片序列的分配规则：

1. 每一个站的码片序列唯一
2. 每个站的码片序列必须相互正交（向量点乘/m等于0）
   • 将码片序列的0用-1代替即可向量化

接收站如何判断发送方发了1还是0：

• 将接收到的叠加后的向量与每个发送方的码片序列进行规格化内积运算

• 

• 算出1则发出bit1，算出0则未发送数据，算出-1则发出bit0

随机接入—-CSMA/CD协议

多应用于使用广播信道的有线局域网

• 多址接入MA：多个主机连接到一个总线

• 载波监听CS：监听总线是否占用，直到信道空闲96bit时间发送帧

  • 碰撞检测CD：在A发送帧的同时如果遇到碰撞，则B停止发送，退让一段随机时间，此刻A检测到碰撞，退避随机时间，重传帧。

• 争用期：以太网端到端往返传播时延2t，又称碰撞窗口

  • 经过争用期这段时间还没检测到碰撞，才能肯定这次发送不会产生碰撞

• 以太网最小帧长：64Byte，来源于争用期（512bit时间）

  • 若发送帧不满足条件，则需补充填充字节
  • 确保了主机在帧发送完成前就检测到该帧发生过程中是否遭遇碰撞

• 同样存在最大帧长，防止长时间占用总线以及接收方缓存区溢出

截断二进制指数退避算法

退避时间=争用期2t * 随机数r

• r从离散整数集合{0，1，…，(2^k-1)}随机选出，k=min(重传次数，10)

信道利用率

设：

• 各主机发送帧不产生碰撞
• 总线一旦空闲就有某个主机立即发送帧
• 发送一帧占用总线时间T₀+τ

则：

​ 极限信道利用率

全流程

CSMA/CA协议

适用于无线局域网

在CSMA基础上添加碰撞避免CA，不再实现碰撞检测CD

• 但碰撞不可能全部避免，所以802.11无线局域网在数据链路层使用了确认（停止等待协议）机制

• 分布式协调功能DCF：每个站点争用信道获取发送权

• 点协调功能PCF：在接入点AP集中控制发送全

帧间间隔IFS

所有站点必须在持续检测到信道空闲一段指定时间后才能发送帧。

• 帧间隔长短取决于帧的优先级
• 短帧间隔SIFS：28μs，用于站点发送/接受模式的切换
  • 分割开属于一次对话的各帧
  • ACK、CTS、分片数据帧、回复AP探询的帧、PCF方式下AP发送的所有帧
• 长帧间隔DIFS：128μs，DCF方式下发送数据帧和管理帧

信道预约

1. 发送数据帧前先发送短控制帧RTS，包含源地址、目的地址、通信所需持续时间
2. 目的站正确收到RTS，且媒体空闲，就发送CTS，包含通信所需时间
3. 收到CTS，等一个SIFS，发送数据帧
4. 收到数据帧，等待SIFS，发送ACK

由于直接发送数据帧由于发送延时大于传播延时，很容易碰撞导致数据重发，浪费更多时间，所以花费一定的代价发送较短的RTS\CTS帧预约信道效率要更高一些

虚拟载波监听

除RTS\CTS，数据帧同样可以携带通信所需持续时间，

站点只需监听到RTS\CTS\数据帧的其中一个，就可以直到信道被占用的持续时间，从而减少隐蔽站带来的碰撞问题

MAC地址

以太网的MAC子层所使用的地址，位于数据链路层

• 每个主机发送的帧中必须携带表示发送主机和接收主机的地址，用于媒体接入控制MAC。
• 固化在网卡中的电可擦可编程只读存储器EEPROM中，又称硬件地址，全球唯一，有线/无线网卡各对应一个MAC地址
• 交换机由于拥有更多网络接口，所以拥有更多MAC地址

随机MAC地址：目前大部分移动设备采用的技术

802.11MAC帧（无线）

分有MAC首部（30Byte），帧主体（0~2312Byte），FCS（4Byte）

IP地址（小引，其属于网络层）

• 网络编号：标识因特网上数以百万计的网络
• 主机编号：标识同一网络上不同主机（或路由器各接口）

显然，MAC地址不具备区分不同网络的功能

源MAC地址和目的MAC地址通常不在同一个链路(网络)下，往往会经过几次路由转发，源/目的MAC地址逐个链路改变

• 从IP地址推断出MAC地址则是ARP协议将处理的事情

地址解析协议ARP

1. 主机中含ARP高速缓存，首先会根据IP地址在缓存表中查找MAC地址

2. 如果没有，则广播ARP请求报文：

   • 本主机IP地址与MAC地址
   • 请求IP地址为/*目的IP地址*/的MAC地址
   • 由于是广播形式，目的地址为FF-FF-FF-FF-FF-FF

3. 当主机发现自己是目的主机时：

   1. 将源主机的IP地址与MAC地址记录到ARP缓存中
   2. 给源主机发送ARP响应（单播），告知MAC地址
   3. 在同一网络的其他主机也会收到ARP响应，发现自己MAC地址与响应中的MAC地址不匹配，网卡会丢弃该帧

ARP协议只能在同一个链路/网络下使用，无法跨网，只能逐段链路使用。

设备

集线器与交换机

集线器：

• CSMA/CD协议，半双工方式

• 使用集线器的以太网在逻辑上仍是一个总线网

• 集线器只工作在物理层，只转发比特

• 集线器一般都有少量容错、网络管理功能

交换机：

• 全双工方式，不使用CSMA/CD协议
• 通常由多个接口
• 工作在数据链路层与物理层，收到帧后再帧交换表中查找帧目的地址所对应接口进行转发（重要）
• 帧交换通过自学习算法自动建立

以太网交换机自学习

设有两台以太网交换机相连，在初始状态，即帧交换表中基本为空数据时：

1. 先将源MAC地址以及接口号写入到交换机1的帧交换表中
2. 进行泛洪算法（转发该帧至除源接口以外的所有接口），也就是说，该帧会进入到以太网交换机2中，向2的帧交换表写入MAC地址以及接口号。（如果有多台交换机相连，其余的交换机帧交换表也会被写入）

如果帧交换表中已经记录了相对充分的数据后：

1. 查找目的主机的MAC地址是否包含在交换表中，有就登记MAC地址与接口号并直接转发（明确转发），不会盲目转发

交换机丢弃帧的情况：

• MAC地址不同，接口相同，即帧发送与帧接收的接口冲突，直接丢弃

交换表中的记录存在有效时间，到期将自动删除

因为MAC地址与交换机的接口对应关系非永久性！

以太网交换机生成树协议STP

提高以太网可靠性的方法：

• 添加冗余链路

然而冗余链路将有可能生成网络环路：

• 产生广播风暴：大量消耗网络资源，无法正常转发其他数据帧。
• 主机收到重复的广播帧
• 交换机的帧交换表震荡

STP协议就是用来解决网络环路带来的问题

• 网络逻辑拓扑结构必须为树形
• 交换机可以自动计算并构建一个逻辑上没有环路的网络

虚拟局域网VLAN

除路由器以外，另一种切割广播域的方法

其将局域网内的设备划分成与物理位置无关的逻辑组的技术，这些逻辑组具有某些共同的需求

IEEE802.1Q帧

在IEEE 802.1Q帧中对以太网MAC帧进行了扩展，插入了4字节的VLAN标记

• VLAN标记的最后12bit称为VID，唯一标志了以太网帧属于哪一个VLAN
• 0和4095都不用来表示VLAN，所以VID的有效取值范围为1~4094

其在交换机来处理，而非用户主机处理，

• 当交换机收到普通的以太网帧时，会将其插入4字节的VLAN标记转为802.1Q帧
• 当交换机转发802.1Q帧时，可能会删除VLAN标记转为普通帧

根据交换机端口的类型，交换机将采取不同的行为模式

交换机端口类型

• Access、Trunk、Hybrid
• 交换机个端口的缺省VLAN ID
  • 思科交换机称为Native VLAN，本征VLAN
  • 华为交换机上称为Port VLAN ID，即PVID，通常使用这个标准

Access端口

• 一般用于连接用户计算机与交换机
• 只能属于一个VLAN
• PVID值与端口所属VLAN的ID相同，默认为1

接收帧：

• 只接受未打标签的帧，MAC帧VID取值与接收端PVID值相等

转发帧：

• 若帧中的VID与端口的PVID相等，则去标签并转发该帧，否则不转发

Trunk端口

• 一般用于交换机之间或交换机与路由器之间互联
• Trunk端口可以属于多个VLAN
• 用户可以设置Trunk端口的PVID值，默认为1

行为模式：

• 对VID=PVID的帧，去标签转发
• 对VID!=PVID的帧，直接转发