计算机网络

5. Data Link Layer

2019-01-28 08:00 CST
2020-01-04 15:27 CST
CC BY-NC 4.0

提供服务

  • 成帧
  • 链路接入
    • 点对点链路
      • HDLC: Bit-Oriented Protocols
      • PPP: Byte-Oriented Protocols
      • SONET: Clock-Based Framing
    • 广播链路
      • 以太网
      • 无线局域网
  • 可靠交付
  • 差错检验与纠正

差错检验

  • 奇偶校验
  • 因特网检验和:6比特
  • 循环冗余检测

多路访问协议

广播链路的链路接入,期望特性

  • 当仅有一个节点发送数据,$R$ bps 吞吐量
  • $M$ 个节点发送数据,$\frac{R}{M}$ bps 吞吐量
  • 协议是分散的
  • 协议是简单的

信道划分协议

  • TDM
  • FDM
  • CDMA

随机接入协议

ALOHA

发送$\rightarrow$等待确认$\rightarrow$超时$p$ 概率重传

  • 信道最大利用率约 18%
    • $Np(1-p)^{2(N-1)}$
  • 时隙 ALOHA:所有传输只允许在时隙的边界处开始,37%
    • $Np(1-p)^{N-1}$
  • 无法利用局域网和分组无线网的一个重要性质:帧的传播时延小于传输时延
    • 小的传播时延提供更好的网络状态反馈信息

CSMA (载波监听多点接入)

Carrier Sensing Multiple Access

监听信道$\rightarrow$发送$\rightarrow$等待确认$\rightarrow$超时重传

  • CS(载波检测):判断是否有AM/FM信号
  • LBT: Listen Before Talk
  • 监听算法
    • 非持续CSMA:忙则等待一段时间,该时间长度从一个概率分布中获得
    • $1$ 持续协议:忙则持续监听,空闲立即传输
    • $p$ 持续CSMA:空闲则有$p$概率直接传输,否则等待一段时间
  • 缺点:两个被破坏帧的传输时间内信道无法使用

CSMA/CD (带冲突检测的载波监听多点接入)

  • $1$ 持续 CSMA + 二进制指数退避
    • 发现信道空闲等待 96 比特时间
  • 干扰信号,帧间最小间隔
  • 检测冲突的时间不超过端到端传播时延两倍
  • CSMA/CD 效率:当有大量的活跃结点,且每个节点有大量帧要发送时,帧在信道中无碰撞传输的那部分时间在长期运行时间中所占比例
    • $d_{\text{prop}}$: 信号能量在任意两个适配器间传播的最大时间
    • $d_{\text{trans}}$: 传输一个最大长度的以太帧的时间
    • 效率 $=\frac{1}{1+5\frac{d_{\text{prop}}}{d_{\text{trans}}}}$
二进制指数退避(BEB)

检测到冲突后,节点停止传输,发送干扰序列(JAM序列),之后进行backoff,完成之后可以尝试再次重传

  1. 基本退避时间一般为端到端的往返时间 $2t$(冲突窗口或争用期)
  2. $k=\min($冲突次数$,10)$
  3. 从离散的整数集合${0,1,2,……,(2^k-1)}$中随机的取出一个数$r$,等待时延$2tr$ (等待 $512$ 比特时间)
  4. 当冲突次数超过$16$次后,发送失败,丢弃传输的帧,发送错误报告。

CSMA/CA (带冲突回避的载波监听多点接入)

  • IFS(帧间间隔): SIFS,PIFS,DIFS
  • 物理载波监听:信道忙则等待 IFS 时间
    • 能量检测
    • 载波侦听
  • 虚拟载波监听:NAV>0 则 NAV 减一
  • 算法
    • CSMA: 若空闲则等待 DIFS 时间后发送,否则
    • CA: 进行二进制随机退避,侦听到信道空闲递减该值,减到 0 则发送
    • 接受完成后 SIFS 对方发送 ACK
    • 超时则在第二步回退,成功从第二步开始

轮流协议

  • 轮询协议:主节点循环的方式轮询(poll)每个节点
    • 轮询时延
    • 主节点故障
    • 802.15 协议,蓝牙协议
  • 令牌传递协议
    • IEEE 802.5 令牌环协议
    • 光纤分布式数据接口协议 (FDDI)

ARP

Address Resolution Protocol, RFC 826, 地址解析协议

  • 链路层地址与网络接口相关联
    • 链路层交换机无链路层地址
    • LAN 地址/物理地址/MAC 地址
    • 长度 6 字节,共有 $2^{48}$ 个,十六字节表示法
    • MAC 广播地址:FF-FF-FF-FF-FF-FF
  • 将 IP 地址映射为 MAC 地址
    • 只为同一子网上的主机和路由器接口解析 IP 地址
  • ARP 表:局域网中每个系统维护一张已知IP与子网地址映射的表 arp -a
  • ARP 查询步骤
    • 构建 ARP 查询分组并广播
    • 其它主机监听 ARP 查询分组,匹配时答复 ARP 应答分组
    • 原始请求中包括发出请求的主机IP和子网地址,其它主机可将次信息复制到本地表

以太网 IEEE 802.3

无连接,不可靠服务

以太网帧结构

前同步码 帧开始定界符(SFD) 目的地址 源地址 长度/类型 MAC客户数据(包含填充码) 帧检验序列 扩展
$7$ 字节 $1$ $6$ $6$ $2$ $46\sim1500/1540/1982$ $4$
01交替序列 10101011 基础帧,Q标志帧,包装帧 MTU CRC

以太网技术

数据率(Mbps)-信号编码方式-最大网段长度(百米)

10Mbps 100Mbps 1000Mbps 10Gbps
10BASE5 同轴电缆($50\Omega$) 100BASE-TX 2对STP/5类UTP 1000BASE-SX 多模光纤 10GBASE-S 多模光纤(300m)
10BASE2 同轴电缆($50\Omega$) 100BASE-FX 2根光纤 1000BASE-LX 多模光纤 10GBASE-L 单模光纤(10km)
10BASE-T 无屏蔽双绞线 100BASE-T4 4对3/4/5类UTP 1000BASE-CX 屏蔽双绞线 10GBASE-E 单模光纤(40km)
10BASE-FP 850nm光纤对 1000BASE-T 4对5类UTP 10GBASE-LX4 单模/多模(10km)
  • IEEE 802.3 100Gbps 规约
    • 多通道分发:物理链路多条并行
    • 物理媒体附件子层(PMA):物理层上,数据链路层下
    • 虚通道:物理媒体附件子层的通信通道

局域网数字信号编码

运用 编码方式 Remark
4B/5B-NRZI 100BASE-X 4比特编码为5个码比特+NRZI 光纤上高效,双绞线上信号能量太过集中,产生不利辐射
MLT-3 100BASE-TX 4B/5B+NRZ+扰码+扰码后的比特流用 MLT-3 编码
8B6T 100BASE-T4 每个8比特映射到6个三进制符号上
8B/10B 光纤通道与千兆位以太网
64B/66B 10Gbps 100Gbps

VLAN

虚拟局域网

  • VLAN 交换机连接
    • 每个虚拟局域网相接:$N$
    • VLAN 干线连接:$1$
  • IEEE 802.1Q VLAN 标准 (扩展以太网帧格式)
    • 干线发送侧交换机添加,干线接受侧交换机删除
    • 源地址与类型间 4 字节 VLAN 标签
      • VID: 1~4094
      • TCI(标签控制信息):802.3 MAC帧长度/类型=0x8100,则有两个八位组的 TCI字段
用户优先级 规范格式指示 VLAN标识符
3bit 1bit 12bit

MPLS

多标签交换网络

  • 固定长度标签,与 IP 协同工作
  • MPLS 首部:增加在第二层首部与第三层首部之间
    • 标签
    • 预留的 3 比特实验字段
    • 1 比特 S 字段:用于指示成栈
    • 寿命字段 TTL
标记值 流量类别 (TC) 栈底比特(S) TTL
20bits 3 1 8
仅有本地意义20比特,0~15保留 栈底置1
  • 仅能在两个均为 MPLS 使能的路由器间发送
    • 标签交换路由器
    • 基于标签执行交换,不必考虑分组的IP地址
  • 优点
    • 交换速度增加
    • 流量管理能力
    • 转发路径的快速恢复
  • 用来提供面向连接的且具有类似区分服务所提供的服务特征的QoS,支持流量管理以提高网络吞吐量,并保持基于IP组网方案的灵活性(2.5层)
    • 服务质量支持
    • 流量工程:动态地定义路由,在需求已知的情况下规划资源投入,优化网络的使用之类的能力
    • 支持虚拟专用网络
    • 多协议支持
术语
标记交换路由器 Label Switching Router LSR
转发等价类 Forwarding Equivalence Class FEC 一组以相同方式转发的分组
标记交换通路 Label Switched Path LSP 一定特定的FEC的所有分组经过一个或多个LSR的路径
标记信息库 Label Information Base LIB LSR用以指明一个分组如何被处理的表
MPLS 域 一个相互连接的支持MPLS路由器的集合
  • 基于MPLS VPN
    • 客户边缘(CE):连接到 MPLS 网络的客户设备
    • 提供者边缘(PE):MPLS 边缘路由器
    • 附着电路(AC):CE和PE 间工作在链路层的链路
    • Layer 2 VPN(L2VPN):基于链路层地址
    • Layer 3 VPN(L3VPN):基于IP地址

LDP 标记分发协议 (Label Distribution Protocal, RFC 5036)

  • 报文类型
    • 发现:LSR周期性发送 Hello 报文指示存在
    • 会话建立和维持
    • 通告:创建、更改和删除 FEC 标记映射
    • 通知报文
      • 差错通知
      • 建议通知
  • LDP 报文 = 首部+多个报文
  • 首部
版本 PDU 长度 LDP 表示符
1 标志 LSR 的唯一性
  • 报文
U比特 报文类型 报文长度 报文ID 必选参数 可选参数
指示如何处理一个位置类型的报文(转发或丢弃) 识别特定报文类型