综述

通过这一章的学习，我们需要：
理解数据链路层服务原理。

差错检测和纠正
共享广播信道: 多址接入
链路层编址
可靠传输、流量控制：done!
了解链路层的实现。
以太网
点对点协议 PPP

链路层简介

网络层：

选路：确定从源路由器到目的路由的路径
转发：路由器将数据报从一个端口转移到另一个端口

链路层：

将数据报从一个结点传输到相邻的下一个结点。

源主机->源路由器 -> 下一跳路由器 -> … -> 目的路由器 -> 目的主机

一些术语：

节点（nodes）：主机和路由器都统称为节点
链路（links）：连接相邻节点的通信信道

包括：有限链路，无线链路，局域网
帧（frame）：链路层分组称为帧。

链路层服务：

组帧（framing）：

封装数据报构成数据帧（添加首部和尾部）

以及从帧中解封装数据报
链路接入（link access）：

在广播信道上协调各个节点的发送行为。

帧首部的 MAC 地址，用于标识帧的源和目的（不同于 IP 地址）
相邻结点间的可靠交付：

通过确认、重传等机制确保接收节点正确收到每一个帧。
流量控制：

协调相邻的发送节点和接收
差错检测:

接收端检测到差错：通知发送端重传或者直接丢弃帧。
差错纠正：

接收端直接纠正比特差错。
全双工和半双工通信控制：

全双工：链路两端节点同时双向传输。

半双工：两路两端节点交替双向传输。

链路层在哪实现？

路由器：链路层内在线卡中实现。
主机：链路层主体部分在网络适配器（网卡）中实现。

网卡连接物理媒体，所以兼具物理层功能。
链路层由硬件和软件实现：
- 网卡中的控制器芯片：组帧、链路接入、检错、可靠交付、流量控制等。
- 主机上的链路层软件：与网络层接口，激活控制器硬件、响应控制器中断等。

差错检测和纠正

如何检测与纠正错误？

码字（codeword）：由 m 比特的数据加上 r 比特的冗余位（校验位）构成
有效编码集：由 2m 个符合编码规则的码字组成
检错：若收到的码字为无效码字，判定出现传输错误
海明距离（Hamming Distance）：两个码字的对应位取值不同的位数
纠错：将收到的无效码字纠正到距其最近的有效码字

检错码与纠错码的能力都是有限的！
编码集的海明距离：编码集中任意两个有效码字的海明距离的最小值。
检错能力：为检测出所有 d 比特错误，编码集的海明距离至少应为 d+1
纠错能力：为纠正所有 d 比特错误，编码集的海明距离至少应为 2d+1

奇偶校验

单比特奇偶校验：检测单比特错误。

二维奇偶校验：

检测奇数位差错、部分偶数位差错。

纠正同一行/列的奇数位错。

Checksum 校验和

发送端：

将数据（校验内容）划分为 16 位二进制序列
求和：如果遇到最高位进位 1，则返回最低位继续加
校验和 = 和的反码
放入分组 UDP/TCP/IP 的校验和字段

接收端：

与发送端相同算法计算
得到的 checksum ：

16 位全 0 （或 sum 16 位为 1）：无措

否则有错

循环冗余校验码 CRC

CRC 是一种多项式编码，它将位串看成一个一元多项式的系数。

信息多项式 M(x)：由 m 个信息比特为系数构成的多项式

冗余多项式 R(x)：由 r 个冗余比特为系数构成的多项式

码多项式 T(x)：在 m 个信息比特后加上 r 个冗余比特构成的码字所对应的多项式，表达式为 $T(x) = x^r·M(x) + R(x)$

模 2 除法 == 按位异或 XOR == 相同为 0 ，不同为 1

生成多项式 G(x)：双方确定用来计算 R(x) 的一个多项式，最高 r 次幂。

编码方法：$R(x) = x^r·M(x) ÷ G(x) $的余式

检验方法：若 $T(x) ÷G(x)$ 的余式为 0，判定传输正确

CRC码检错能力极强，可用硬件实现，是应用最广泛的检错码。

每个 CRC 标准都能检测小于 r+1 比特的突发差错。

在适当的假设下，长度大于 r+1 比特的突发差错以概率 $1- 0.5^r$ 被检测到。

循环码性质：

⑴由任何多于一项的生成多项式g(x)产生的循环码能够检测所有单个错误；

⑵每个被(1+x)除尽的多项式都具有偶数项。若生成多项式g(x)具有偶数项，则由它产生的编码就能检测所有奇数个错误；

⑶若码长n不大于生成多项式g(x)的指数e(即n≤e)，则由g(x)产生的码能够检测所有单个和两个错码；g(x)的指数e：e是使g(x)能除尽xe+1的最小正整数；

⑷若码长n不大于g1(x)的指数，则由生成多项式g(x)=(x+1)g1(x)产生的码能检测所有单个、两个及三个错误；

⑸由(n-m)次多项式产生的任一循环码，能检测所有长度不超过(n-m)的突发错误；

⑹ 长度为b>(n-m)的突发错误中：若b=n-m+1，则不能检测部分占2 ^-(n-m-1) ；若b>n-m+1，则不能检测部分占2^ -(n-m) 。

为什么 G = 1011 能够检测出任何单比特错误？

某一位出错相当于在二进制的那一位+1，对于整个接收到的二进制数来说相当于+2^i ，2^i 不能被 G= 1001 = 9 整除，因此能检测出单比特错误

上述 G 能检测任何奇数比特错误吗？为什么？

奇数个 1 是不能被 (11)_2 整除的（异或运算）,例如 10101 不能被 11 整除，但是 G=1001 可以被奇数个 1 整除。

多路访问控制（MAC）协议

链路的两种类型：

点到点链路：

仅连接了一个发送方和一个接收方的链路。
广播链路：

连接了许多节点的单一共享链路，任何一个节点发送的数据可被链路上的其它节点接收到。

多址接入（Multiple Access）

冲突：

在广播链路上，若两个或多个节点同时发送，发送的信号会发生干扰，导致接收失败。
多址接入协议：

规定节点共享信道（谁可以发送）的方法
多址接入协议也称媒体接入控制（Medium Access Control，MAC）协议

理想的多址接入协议：

在速率为 R bps 的广播信道上

当只有一个节点发送时，它应能以速率 R 发送
当有 M 个节点发送时，每个节点应能以 R/M 的平均速率发送
协议是完全分布式的:

不需要一个特殊的节点来协调发送
不需要时钟或时隙同步
简单

MAC （多址接入）协议的分类

**信道划分 **

将信道划分为若干子信道，每个节点固定分配一个子信道，不会发生冲突。
包括时分多址 TDMA，频分多址 FDMA 和 CDMA 码分多址

随机接入

不划分信道，节点可自行决定何时发送；
允许出现冲突，发生冲突后设法恢复。

轮流使用信道

不划分信道，有数据要发送的节点在信道上轮流发送，不会出现冲突

随机访问 MAC 协议

随机访问 MAC 协议需要定义：

如何检测冲突
如何从冲突中恢复（e.g. 通过延迟重传）

时隙 ALOHA 协议

假定：

所有帧大小相同
时间被划分为等长的时隙，每个时隙可以传输一个帧
结点只能在时隙开始时刻发送帧
节点间时钟同步
如果2 个或 2 个以上结点在同一时隙发送帧，结点即检测到冲突

运行：

当结点有新的帧时，在下一个时隙发送

如果无冲突，该节点可以在下一个时隙继续发送新的帧

如果有冲突，该节点在下一个时隙以概率 p 重传该帧（1-p 不发帧），直至成功

优点：

单个节点活动时，可以连续以信道全部速率传输数据
高度分散化：只需同步时隙
简单

缺点：

冲突 -> 浪费时隙
空闲时隙
节点也许能以远小于分组传输时间检测到冲突，从而可以终止传输
要求节点之间时钟同步

效率：当网络中存在大量活跃节点时，长期运行过程中成功时隙所占的比例

假设 N 个结点有很多帧等待传输，每个节点在每个时隙均以概率 p 发送数据。
对给定一个结点，在一个时隙将帧发送成功的概率 $p(1-p)^{N-1}$

这个数据帧选择发送，其余 N-1 个结点选择不发送
给定时隙中有节点发送成功的概率 = $Np(1-p)^{N-1}$

同时是信道空闲的比例（对那个成功发送出去的帧来说，信道是空闲的）
最大效率
1. 找到令 $Np(1-p)^{N-1}$ 最大的概率 $p^* = \frac{1}{N}$
2. 带入 $Np(1-p)^{N-1}$ ，并令N 趋于无穷
  
  $lim_{N-> \infty} (1-\frac{1}{N})^{(N-1)} = lim_{N-> \infty} (1+\frac{1}{-N})^{(-N)(-1)} = \frac{1}{e} $
3. 得到，最大效率 $E = 1/e = 0.37$
最好的情况下，信道平均被成功利用（占所有的带宽）的时间占 37%

此时，成功发送一个帧需要的发送次数为 $1/E = e = 2.71828... = 2.72$

纯 ALOHA 协议

非时隙：更加简单，无需同步

当有新的帧生成时，立即发送数据

冲突可能性增大：

所以，纯 aloha 协议的效率肯定比 aloha 协议低。

载波侦听多址协议 CSMA

发送前监听信道：

信道空闲：发送整个帧
信道忙：推迟发送

冲突仍然有可能发生：

存在传输延迟，所以节点可能没有监听到其他结点正在发送
一旦发生冲突，整个帧的传输时间被浪费

带冲突检测的 CSMA – CSMA/CD

通过测量收到的信号强度检测冲突：

冲突信号的强度较大。

仅适用于有线网络，如 以太网
检测到冲突之后立即停止传输损坏的帧：

减少信道浪费。
需要满足的条件：

假设网络带宽 $R~bps$ 数据帧最小长度 $L_{min}(bits)$ ，信号传播速度 $V(m/s)$ ，源到目的结点的最远距离 $d_{max}$

需满足公式： $\frac{L_{min}}{R} = RTT_{max} = \frac{2d_{max}}{V}$
效率：

Tprop = LAN 中两个节点间的最大传播延迟

$t_{trans}$ = 最长帧传输延迟

效率 = $1/(1+5t_{prop}/t_{trans})$

prop 趋于 0，或者 trans 趋于无穷时，效率趋于 1

远优于 aloha 协议，且更加简单、分散。

轮转访问 MAC 协议

综合 信道划分 MAC 协议 和 随机访问 MAC 协议 的优点：

数据传输过程中不会出现冲突
数据传输时利用链路的全部带宽

轮询 polling：

主结点轮流邀请从属结点发送数据
问题：
1. 轮询开销
2. 等待延迟
3. 单点故障风险（如果主结点宕机，则网络瘫痪）

令牌传递 token passing：

控制令牌依次从一个结点传递到下一个结点
令牌：特殊帧，获得令牌的结点可以发送数据
问题：
1. 令牌开销
2. 等待延迟
3. 单点故障（令牌丢失）

MAC 协议比较

信道划分MAC协议:

TDMA / FDMA / CDMA

重负载下高效：没有冲突，节点公平使用信道
轻负载下低效：即使只有一个活跃节点也只能使用1/N的带宽

随机接入MAC协议：

ALOHA / CSMA / CSMA-CD （以太网） / CSMA-CA（802.11 无线局域网）

轻负载时高效：单个活跃节点可以使用整个信道
重负载时低效：频繁发生冲突，信道使用效率低

轮流协议（试图权衡以上两者）

蓝牙、FDDI、令牌环网

按需使用信道（避免轻负载下固定分配信道的低效）
消除竞争（避免重负载下的发送冲突）

局域网 LANs

局域网 LAN（Local Area Network）

将小范围内的计算机及外设连接起来的网络，范围在几公里以内

城域网 MAN（Metropolitan Area Network ）

通常覆盖一个城市的范围（几十公里），如有线电视网、宽带无线网等
城域网要能支持数据、音频和视频在内的综合业务，服务质量好，支持用户数量多

广域网 WAN（Wide Area Network）

通常覆盖一个国家或一个洲（一百公里以上），规模和容量可任意扩大

链路层编址（MAC 地址）和 ARP 协议

每一块网络适配器（网卡）固定分配一个地址，称为 MAC地址 ，也称物理地址、硬件地址、链路层地址、以太网地址、局域网地址等。

MAC 地址长 6 个字节，一般用由 “ : ” 或 “ - ” 分隔的 6 个十六进制数表示：

e.g. 1A-2F-BB-76-09-AD

MAC 地址由 IEEE 负责分配，每块适配器的地址是全球唯一的：

网卡生产商向 IEEE 购买一块 MAC 地址空间（前 3 字节）
生产商确保生产的每一块网卡有不同的 MAC 地址
MAC地址固化在网卡的 ROM 中
MAC 地址（链路层） == 身份证号（可携带）用于标识帧；
IP 地址（网络层） == 邮政地址，存在上下级的归属关系（不可携带）用于标识数据报；

现在用软件改变网卡的 MAC 地址也是可能的

MAC 地址类型

目的 MAC 地址有三种类型：

单播地址：适配器的 MAC 地址，地址最高比特为0
多播地址：标识一个多播组的逻辑地址，地址最高比特为 1
广播地址：ff:ff:ff:ff:ff:ff

网络适配器仅将发送给本节点的帧（单播，广播，多播）交给主机

若将适配器设置成混收模式，适配器将收到的所有帧交给主机

ARP：地址解析协议

问题：在同一个 LAN 内，如何在已知目的节点的 IP 地址前提下确定其 MAC 地址？

ANS：LAN 中每个 IP 结点（主机、路由器）维护一个表 – ARP 表。

用来存储 LAN 结点的 IP/MAC 地址的映射关系：<IP 地址; MAC 地址;TTL>

TTL： time to live

经过这个时间以后该映射关系会被遗弃（典型值为 20min）

ARP 的解析（获得与 IP 地址对应的 MAC 地址）过程：

同一个局域网里的结点：

假设 A 想知道 B 的 MAC 地址：

A 构造一个 ARP 请求，在发送方字段填入自己的 MAC 地址和 IP 地址，在目标字段填入 B 的 IP 地址。
A 将 ARP 请求封装在广播帧中发送

目的 MAC 地址（广播地址） = FF-FF-FF-FF-FF-FF
每个收到 ARP 请求的节点用目标 IP 地址与自己的 IP 地址比较，地址相符的节点进行响应（B响应）。
B 构造一个 ARP 响应，交换发送方与目标字段内容，在发送方硬件地址字段填入自己的 MAC 地址，修改操作字段为 2
B 将 ARP 响应封装在**单播帧（目的地址为A的MAC地址）**中发送。
A 在其 ARP 表中，缓存 B 的 IP-MAC 地址对，直到超时；超时后，再次刷新。
ARP 是即插即用的协议：结点自主创建 ARP 表，无需干预。

不同局域网中的结点：

以太网 ETHERNET

以太网是第一个广泛应用的局域网技术，也是目前占主导地位的有线局域网技术。

比其他局域网技术简单、成本低，且能满足网络速率需求。

以太网：物理拓扑

总线型拓扑（共享式以太网）：

以同电缆作为共享传输媒体（总线）
所有节点通过特殊接口连接到这条总线上
所有节点在同一冲突域（collision domain）（可能彼此冲突）

星型拓扑：

基于集线器（hub）的星型拓扑（共享式以太网）：是一个物理层设备，把从一个端口进入的物理信号（光，电）放大后立即从其它端口输出
基于交换机（switch）的星型拓扑（交换式以太网）： 是一个链路层设备。

主机通过双绞线或光纤连接到交换机；

交换机在端口之间存储－转发帧；

各节点仅与中心节点直接通信，各节点之间不直接通信，所以每个节点和交换机之间单独冲突域，结点间彼此不冲突。

如果没有源和目的地址之间的冲突，其总带宽为单个以太网段带宽的 N 倍，此时这些主机之间能够同时进行双工通信，而不会产生干扰。

无连接、不可靠的传输

无连接：

发送帧的网卡与接收端的网卡没有握手过程。

不可靠：

接收网卡不向发送网卡进行确认
差错帧直接丢弃，丢弃帧中的数据恢复依靠高层协议（如，TCP），否则，发生数据丢失。

以太网的 MAC 协议：采用二进制指数退避算法的 CSMA/CD

在发生冲突时，用该算法来计算下一个帧的传输等待时间。

算法在网卡（NIC）上实现并运行。

NIC 从网络层接收数据包，创建数据帧
监听信道：

如果 NIC 监听到信道空闲，则开始发送帧；

如果监听到信道忙，则一直等待到信道空闲，然后发送帧；
如果 NIC 检测到其他结点传输数据，则中止发送，并发送堵塞信号 jam signal。
中止发送后，NIC 进入二进制指数退避：

第 m 次连续冲突后：
- 取 n = Max(m,10)
- NIC 从 {0，1，2，…，2^n -1} 中随机选择一个数 K
- NIC 等待 K*512 比特的传输延迟时间，再返回第二步
连续冲突次数越多，平均等待时间越长。

连续 16 次冲突之后，不再尝试，直接向上级报错。

以太网交换机

链路层设备：

存储-转发以太网帧
检验到达帧的目的 MAC 地址，选择性向一个或多个输出链路转发帧
利用 CSMA/CD 访问链路，发送帧

透明：

主机感知不到交换机的存在

即插即用：

直接接入网络，通过自学习就可以使用。

自学习：

交换机无需配置

端口转发表

帧的过滤和转发

交换机收到帧的处理过程：

用帧的目的地址查找转发表（转发决策）：

若目的地址所在端口 = 帧的进入端口，丢弃帧

若目的地址所在端口 ≠ 帧的进入端口，转发帧

若目的地址不在转发表中，扩散帧

用帧的源地址查找转发表（更新转发表）：

若找到地址，将对应表项的生存期设为最大值

若没有找到该地址，添加源地址和进入端口到转发表，设置表项的生存期为最大值

交换机互联

交换机 VS 路由器

两者均为存储-转发设备：

交换机：链路层设备，检测网络分组首部，转发速度快，成本低（二层设备）

路由器：网络层设备，检测链路层帧首部，转发速度慢，成本高（三层设备）
二者均使用转发表：

交换机：利用自学习、泛洪构建转发表，依据 MAC 地址

路由器：利用路由算法（路由协议）计算，依据 IP 地址

虚拟局域网 VLAN

基本概念：

支持 VLAN 划分的交换机，在一个物理局域网上，配置、定义多个 VLAN。

每个 VLAN 在逻辑上是一个独立的 IP 子网：

每个 VLAN 是一个单独的广播域，一个 VLAN 中的所有帧流量被限制在该 VLAN 中
不同VLAN之间的通信要依赖于网络层路由

如何知道一个帧属于哪个 VLAN？

根据帧的到达端口、源 MAC 地址或源 IP 地址（由VLAN的划分方法确定），查找 VLAN的配置表获悉

为避免重复查找 VLAN配置表，帧头中携带其所属的VLAN标识

后续交换机通过检查帧头的VLAN标识得知这个帧所属的VLAN

802.1Q 规定了新的以太帧格式，帧头中包含一个 VLAN 标签（tag），用于指明帧属于哪个 VLAN。

三层交换机和路由器：

不同子网或 VLAN 之间通过路由器转发，太慢！太贵！

三层交换机：

具有部分路由功能、又有二层转发速度的交换机
专为加快大型局域网内部的数据交换而设计
但在安全、协议支持等方面不如专业路由器

三层交换机的使用：

通常用在机构网络的核心层，连接不同的子网或 VLAN

专业路由器：连接机构网络与外网

PPP 协议

点对点数据链路控制：一个发送端，一个接收端，一条链路：比广播链路容易。

PPP 是因特网中广泛使用的点到点数据链路协议，用于 PC 机到因特网的拨号连接，以及路由器到路由器之间的专线连接。

PPP 由以下三部分组成：

一种在串行通信线路上的组帧方式，用于区分帧的边界，并支持差错检测。
一个用于建立、配置、测试和拆除数据链路的链路控制协议 LCP。
一组网络控制协议（NCP），用以支持不同的网络层协议。

PPP 无需支持的功能：

无需差错纠正、恢复（一般由高层协议处理）
无需流量控制
不存在乱序交付
无需支持多点链路

PPP 数据帧：