第五章 数据链路层与局域网

网络层数据报封装在数据链路层帧中，在物理线路之上的逻辑数据通路中传送
典型硬件实体：网络适配器
结点：数据链路的端点
链路：结点间信道
提供的服务：

• 组帧：
  • 帧头：发送与接收结点的地址信息
  • 帧尾：差错编码
  • 帧定界：在头和尾，用于识别帧的开始和结束
• 链路接入：
  • 点对点链路：独占通信链路，控制简单
  • 广播链路：通信链路被多个结点共享，彼此会干扰，因此必须运行媒介访问控制MAC协议，用于协调
• 可靠交付：
  • 有线链路：没必要，所以不提供可靠传输服务
  • 无线链路：参考传输层可靠传输方式
• 差错控制：控制由信噪比等导致的误比特率高造成的影响

差错控制

噪音分类：

• 随机噪音：引起随机差错或独立差错
• 冲击噪音：突发差错
  突发长度：突发错误第一位到最后一位长度

基本方式

• 检错重发：
  • 发送方对数据进行差错编码
  • 接收方利用差错编码判断数据是否有错
  • 有错则要求重发
  • 例如等停协议，滑动窗口
• 前向纠错 FEC：
  • 发送方对数据进行纠错编码
  • 接收方通过纠错编码，定位错误位置并纠正
  • 适用于单工链路与对实时性要求高应用
• 反馈校验：
  • 接受端将数据原封不动发给发送方
  • 原理简单，易于实现，不需要差错编码
  • 传输效率差，实时性差
• 检错丢弃：
  • 发现错误直接丢弃
  • 适合实时性要求高的应用
• 混合差错控制：
  • 检错重发与前向纠错结合

基本原理

香农信道编码定理：可以通过编码使数据传输过程不发生错误
差错编码基本原理：待传输的数据加上冗余信息，接收端检测冗余信息与原数据关系是否存在
比如发送 01 时将数据变为 0101，但这个方式无法实现纠错

检错与纠错

汉明距离 dc ：两个等长码之间，对应位不同的数量
编码集的汉明距离 ds：其中任意两个编码汉明距离最小值

• 对于检错编码：
  • 如果 ds=r+1 ，则可以检测 r 位差错
• 对于纠错编码：
  • 如果 ds=2r+1，则可以纠正 r 位差错
  • 发生错误时恢复成距离最近的正确编码
• 例题见 P180

典型差错编码

异或运算 XOR：

• 符号为圈中加号
• 相同为 0 否则 1
• 相当于加法没进位

奇偶校验码

• 1 位冗余信息，放在 a0，使 1 的位数为奇数（偶数）
• 即满足各位 XOR 结果为 1（0）
  • 其中式子为监督关系式
  • 结果为校正因子 S
• 50% 检错率
• 编码简单，开销小
• 用于低速串行链路

汉明码

当信息足够长时编码效率高

纠错原理

在k 位信息位增加r 位冗余位，得到码字长度n为k+r，以增加r 个校正因子与监督关系式
如有两个校正因子，比如 10，则有四种情况，其中一种表明正确，其余三种可以指明出错的位置
为实现纠错，要求：
2^r >= n+1
因此 k 越大，编码效率越高
缺点： 只能纠正一位错误
例题见 P181

循环冗余码CRC

在现代网络数据链路层广泛使用于检错，也称为多项式编码
将二进制串看成多项式
如：100101 看成 x^5+x^2+1
发送方与接收方商定一个多项式 G(x)，其中最高最低位必须是 1，长度必须比数据帧短
在帧的尾部附加一个校验和使帧对应的多项式 M（x)能被 G(x)除尽，如果结果为 0 则没出错
例题见 P183

优点

• 检错能力强：能 100% 检查出 16 位以下错误
• 编码效率高：冗余位与数据位数无关，信息位长时，开销很小

多路访问控制协议MAC

对于广播通信方式，信道上有很多结点，需要 MAC 协议来协调结点的数据发送
主要分为 3 种

信道划分MAC

通过多路复用技术，将信道划分并分配给不同结点，各结点只使用被分配的资源

频分多路复用FDM

对应的多路复用 MAC 协议为后方加 A，即 FDMA，下同
常用于模拟传输的宽带网络
将信号调制到互不重叠的频带上
往往每路语音信号占4kHz，其中 3.1kHz 为语音频带，两侧各留 0.45kHz保护频带

• 优点：分路方便，在模拟通信领域应用广泛
• 缺点：
  • 串扰：各路信号之间相互干扰
  • 所需设备随输入路数增大而增多，不易小量化
  • 不提供差错控制

时分多路复用TDM

将信号在时域内划分为多个等长时隙，每路信号占用不同时隙，实现信道共享

• 同步时分多路复用 STDM
  • 按固定顺序，把时隙分配给n路信号
  • 发送端以 n 为周期，将 n 路信号的采样构成一个时分复用帧
  • 接收端采样严格同步的时隙分割方式，完成分离与还原
  • 缺点：可能出现空闲时隙，造成信道资源浪费
• 异步时分多路复用ATDM
  • 也称为统计时分多路复用 STDM
  • 给数据量大的用户分配较多时隙，数据量小…
  • 给每个时隙加上用户的标识
  • 主要用于高速远程传播，即广域网
  • 缺点：
    • 技术复杂性高
    • 信道共享冲突问题

波分多路复用WDM

用于光纤通信
通常用光的波长来代替频率讨论
在一根光纤中，传输多路不同波长的光信号
长距离传输需要光纤放大器 EDFA，两个之间 120km

密集波分复用 DWDM：

• 波长划分更密集，复用度更高，信道利用率更高
• 关键技术：光放大器
• 现代光纤通信网络的重要基础

码分多路复用CDM

扩频技术：利用更长的互相正交的码组分别编码原始信息，实现信道共享
两码组 X 和 Y 相互正交充分必要条件即 p(X,Y) = 0
例题见 P189

随机访问MAC协议

争用接入：所有用户随机地向信道上发送信息，胜利者暂时占用信道
如果同时一个以上用户在信道上发送信息，则产生冲突，发送失败，每个用户随机退让一段时间，再次尝试

ALOHA协议

最早最基本的无线数据通信协议
通信站点随机接入共享信道（天空），频率相同，任意两个同频率广播帧都会使双方失效
根本缺点： 发送前不判断信道是否空闲

纯ALOHA

发送站发出后侦听一段时间，等待应答信号，未收到则等待一个随机时间后再次发送
性能：

• 吞吐率 S：在一帧的发送时间 T0 内成功发送的平均帧数，0<S<1
• 信道利用率：S 接近 1 的程度
• 网络负载 G：T0 内发送的平均帧数，无论是否成功
• S = Ge^-2G
• G = 0.5 时,S最高

时隙ALOHA

需要所有通信站在时间上同步
把信道时间分成离散的时隙 Slot
每个时隙为发送一帧所需时间
在时隙开始时发送
如果出现冲突，下一时隙概率 P 重发
性能：

• S = Ge^-G
• G = 1时 S 最大
• 冲突危险区为纯的一半
• 冲突概率低

载波监听多路访问协议

先听后说：发送数据前，监听信道上其他站点是否在发送

非坚持CSMA

若发现信道忙，等待一个随机时间，然后重新开始侦听

• 优点：减少了冲突概率
• 缺点：信道空闲时间长，发送延迟大，容易被捷足先登

1-坚持CSMA

若发现信道忙，继续侦听，直至发现空闲

• 优点：减少了信道空闲时间
• 缺点：可能多个站点同时侦听，导致冲突概率大

P-坚持CMSA

坚持监听，发现空闲后，以概率 P在下一时隙侦听并发送数据

带冲突检测的载波监听多路访问协议

CSMA/CD 其中 CD 标识冲突检测，用于在发送数据的同时监听信道，发生冲突，立即停止发送，发出冲突强化信号，使所有通信站知道冲突发生，并等待随机时间，停止发送，避免冲突后继续发送导致信道资源浪费
即：先听后说，边听边说，不说不听
工作状态：

• 传输状态
• 竞争状态
• 空闲状态
  由于传播时延，仍然会产生冲突
  由于需要检测信号强度判断冲突，只适用于有线信道
  要使用 CSMA/CD，需要满足的物理要求，公式与例题见 P194

受控接入 MAC 协议

各个用户必须服从控制才能接入信道

集中式控制

一个主机通过轮询技术调度其他通信站接入信道
轮叫轮询：

• 按顺序逐个轮询
• 有数据则发给主机
• 缺点：轮询过程不停循环，开销较大
  传递轮询：
  每台主机两条输入线
• 接收主机发来的消息
• 接收允许发送数据的控制信息
  当 N 向主机发送数据时，其他站可以检测到线路上有数据在发送
  N 无信息或者发送完毕，将 N-1站地址给主机
  缺点：主机出问题，全网瘫痪

分散式控制

现代网络主要是用的方法
令牌Token： 通信站使用通信的许可，在信道空闲时在信道传输，通信站获取令牌后可以在一定时间内发送数据，发送完毕重新将令牌发送到信道上
令牌标志位 1：有站点正在占用
令牌环主要操作过程：

1. 网络空闲时，令牌在环路绕行，标志位为 0
2. 某站点等待并获取令牌，标志位置为1
3. 每个站点边转发边检测数据帧目的地址，接收发给自己的
4. 数据帧绕环一周后，发送站将其撤销，即自生自灭，并作差错检验
5. 重新产生令牌
   最严重两种错误：

• 设立主动令牌管理站
• 令牌丢失：设置超时时间，超过则由主动令牌管理站清理数据碎片，重发令牌
• 数据帧无法撤销：第一次经过主动令牌管理站会将监控位置为 1，发现有 1 的则清理数据碎片，重发令牌

局域网

主要是星型拓扑和树型
TCP/IP 体系结构的网络局域网是以太网
网络适配器上运行介质访问控制MAC协议

数据链路层寻址

ARP

实现网络层地址（IP 地址）与链路层地址映射的地址解析协议

链路层地址与MAC

主机或路由器的链路层地址来自其网络适配器（网卡）
每个网络接口对应一个
适配器的 MAC 地址无论到哪都不会改变，类似于身份证
而 IP 地址会随进入不同子网而变化，类似于邮政地址
也称为：

• MAC 地址
• 物理地址
• 局域网地址
  注意： 链路层交换机的接口没有 MAC 地址，交换机只透明地实现路由器与主机间的链路层帧转发
  特点：
• 长度 6 字节
• 第一个字节的倒数第二位为 G/L 位
  • 0：Global，全球管理，全球唯一
  • 1：Local，本地管理，由用户自行分配
  • 以太网不理会 G/L 位
• 16 进制表示
• 使用：或-连接
• 最初网卡的 MAC 地址不变
• 现在可以更改，但是在局域网内唯一
• 广播帧 MAC 地址：FF:FF:FF:FF:FF:FF

地址解析协议ARP

在所在子网内，根据 IP 地址获取 MAC 地址
在每台主机和路由器维护一个 APR 表，存储其他主机或路由器 IP 与 MAC 映射关系
每个映射设置一个寿命值 TTL 指示删除时间
ARP 表找不到映射时，广播询问局域网内所有主机和路由器
ARP 与 DNS 区别

• 解析内容不同
• 解析范围不同
• 实现机制不同

以太网

最流行有线局域网技术
IEEE 802.3以以太网为基础
本书中这两个词等价
无连接不可靠服务，直接丢弃检查出错的 MAC 帧，无差错控制，由上层协议（TCP等）实现差错控制

• 经典以太网：采用同轴电缆连接
• 总线型以太网 10Base-5:
  • 速率：10Mbit/s
  • 最短帧长 64 字节
  • 一个冲突域中最多 5 个网段，每个最长 500m
  • 网段之间有中继器
  • MAC协议采用 CSMA/CD
• 10Base-T
  • 采用非屏蔽双绞线 UTP
  • 速率：10Mbit/s
  • 连接到物理层集线器（几乎不再使用），集线器与集线器也能互连
  • 组网方便，故障隔离
• 快速以太网100Base-T：
  • UTP 或光缆（100Base-FX）
  • CSMA/CD
  • 100Mbit/s
• 千兆以太网
  • CSMA/CD
  • 1000Mbit/s
• 万兆以太网
  冲突域：在一个局域网内，多个结点往物理介质中发送信号，发生冲突导致发送失败，则这几个结点在一个冲突域
  广播域：接受得到互相广播帧的结点在一个广播域

交换机

网桥：

• 先检查接收到帧的目的 IP 地址，再确定转发到哪个端口
• 只适用于用通信量不大的局域网
• 否则因为广播风暴产生拥塞
• 对于结点透明
  交换机：
• 原理：多端口网桥
• 基本工作方式：存储转发
• 有多种速率端口
• 端口工作方式：
  • 混杂模式： 默认使用，无论帧 MAC 地址，都会接收，有差错控制
  • 直通交换：部分使用，接受到帧的第 6 个字节，就根据目的 MAC 地址转发，不差错控制

当一帧到达，以帧的目的 MAC地址为主键查询内部交换表

• 如果交换表内有对应项：
  • 对应端口与接收到该帧的端口相同：丢弃
  • 否则按查表结果转发
• 没对应项：泛洪：向除了接收到该帧的端口外所有其他端口转发

交换表由自学习构建：只在接收信息时记录来源端口与 源MAC 地址，无目的 MAC 地址对应表项则泛洪，每个表项存在有效时间
以此实现即插即用
通过生成树协议，即无环路，避免兜圈

交换机优点：

• 消除冲突
• 支持异质链路
• 易于网络管理

以太网络

交换以太网：

• 使用交换机代替集线器
• 交换机连接的主机不再属于同一个冲突域，一个冲突域只有一台主机，不会发生传统的冲突
• 通信时独占带宽，如 10 个用户，则总容量相当于翻了十倍
  传统共享式以太网：
• 不使用交换机
• 多个用户平均分配带宽，如 10 个用户，则每人带宽为 10 分之一

虚拟局域网 VLAN

如果广播域太大，广播帧会被大量复制，导致广播风暴
需要尽可能限定广播域规模
基本手段：利用路由器分割广播域
VLAN：

• 另一种分割广播域手段
• 设置在交换机上
• 软件的方式划分局域网中的工作组，以限制接收到广播的主机数
  三种方式：
• 基于交换机端口划分
• 基于 MAC 地址划分
• 基于上层协议类型或地址划分：有利于基于应用划分

点对点链路协议

MAC 协议都用于共享链路
点对点链路用于广域网，不存在介质共享，所以不需要 MAC 协议

PPP

使用最多
定界符： 在首尾，7E,即01111110
为实现透明传输：如果数据中含有相同的，在数据之后加上转义字节 01111101，如：0111111001111101

高级数据链路控制HDLC

应用于点对点和点对多链路
定界符同上
为实现透明传输： 位填充：每发现 5 个连续的 1 就插入一个 0，如：01111110 -> 011111010