数据链路层和局域网

数据链路层：
负责通过一条链路，从一个结点向另一个物理链路直接相连的相邻结点，传送网络层数据报，中间不经过任何其他交换结点

数据链路：
网络中两个结点之间的逻辑通道。实现控制数据传输协议的硬件（网卡）和软件加到链路上构成的

数据链路层服务

数据链路层的传输单元：帧。

数据链路层提供的服务内容

组帧（成帧）：
帧头：发送结点和接收结点的地址信息、定界字符
帧尾：用于差错检测的差错编码

链路接入：
物理链路可以分为：点对点链路 和 广播链路

可靠交付：
无线链路（出错率高）：支持可靠数据传输
光纤、双绞线（出错率低）：不提供可靠数据传输服务

差错控制：
数据链路层帧在物理媒介上的传播过程，可能会出现比特翻转的差错
误比特率：出现差错的比特数 / 传输比总数

差错控制

通过 差错编码 技术，实现对信息传输差错的检测，并基于某种机制运行差错纠正和处理

差错编码：检错码、纠错码

信号在信道传输过程中，会受到各种噪声的干扰，从而导致传输差错。具体可分为：

随机噪声：随机差错或独立差错（传输介质本身）
冲击噪声（主要原因）：突发差错（打雷），冲击噪声引起的第一位错误与最后一位错误之间的长度称为 突发长度

差错控制的基本方式

检错重发（检错编码）

发送端：对数据进行 检错编码，然后发送
接收端：利用差错编码检测数据是否出错。若出错，接收端请求发送端重发数据加以纠正

前向纠错 FEC（纠错编码）

发送端：对数据进行 纠错编码，然后发送
接收端：收到数据，利用 纠错编码 进行差错检测，且纠错

适用：单工链路

反馈校验（不用编码）

接收端：将接收到的数据 原封不动 发回发送端
发送端：通过对比接收端返回的数据与发送的数据确认接收端是否正确接收的已发送数据。若有不同，立即重传数据

优点：原理简单，易于实现，无须差错编码
缺点：需要相同传输能力的反向信道，传输效率低，实时性差

检错丢弃（检错编码）

网络应用对可靠性要求不高，可以采用不纠正出错数据，直接丢弃错误数据

适用：实时性高的系统

差错编码的基本原理

在待传输数据信息基础上，附加一定的 冗余信息

冗余信息：与数据信息建立某种关联关系。（复制一次，复制二次）

差错编码的检错和纠错能力

编码集的汉明距离

编码集：
差错编码的所有有限码字的集合。（编码方式：复制一次）
例子：
{1010, 0101, 1111, 0000}

汉明距离：
两个等长码字之间，对应位数不同的位数
例子：
码字1：01100101
码字2：10011101
汉明距离：d_c = 5

编码集的汉明距离：
编码集中任意两个码字之间汉明距离的最小值，记为：d_s
例子：
编码集：{1010, 0101, 1111, 0000}
编码集的汉明距离：d_s = min{4, 2, 2, 2, 2, 4}
编码集的汉明距离：d_s = 2

检错编码

编码集的汉明距离 d_s = r + 1 ，则该检错编码可以检测 r 位的差错

例子：
发送2位数据信息，冗余信息是数据的一次复制
编码集：{0000, 0101, 1010, 1111}
编码集汉明距离：d_s = 2 = 1 + 1
因此，可以检测出来 1 位差错

纠错编码

编码集的汉明距离 d_s = 2r + 1 ，则该纠错编码可以纠正 r 位的差错

例子：
发送2位数据信息，冗余信息的数据的两次复制
编码集：{000000, 010101, 101010, 111111}
编码集汉明距离：d_s = 3 = 2 * 1 + 1
因此，可以检测出来 1 位差错

典型的差错编码

奇偶校验码

最简单的校验码。利用1位冗余信息实现差错检测

奇数：
不能被2整除的数

奇校验码：
1位冗余位，取值为 “0” 或 “1”，使得 编码后 的码字中的 1的个数为奇数
例如：
数据 10110111，编码后：101101111
数据 10110110，编码后：101101100

偶校验码：
1位冗余位，取值为 “0” 或 “1”，使得 编码后 的码字中的 1的个数为偶数
例如：
数据 10110111，编码后：101101110
数据 10110110，编码后：101101101

优缺点：
优点：编码简单、编码效率高、开销最小的检错编码
缺点：检错率不高

循环冗余码

Cyclic Redundancy Check, CRC码，在数据链路层广泛应用的差错编码（检错码）

基本思想：
将二进制位串看成是系数为0或1的多项式的系数

系数：
4x²，其中的 4 为系数

例子1：
100101有6位，写成一个多项式。位串的二进制数就是每个多项式的系数

多项式拆解	x⁵	x⁴	x³	x²	x¹	x⁰
位串	1	0	0	1	0	1
相乘	1 * x⁵	0 * x⁴	0 * x³	1 * x²	0 * x¹	1 * x⁰

整理后得出多项式：1x⁵ + 0x⁴ + 0x³ + 1x² + 0x¹ + 1x⁰
化简后：x⁵ + x² + 1

“异或” 逻辑运算：
1异或0 = 1
1异或1 = 0
0异或0 = 0
0异或1 = 1

二进制相除：
位数足够商1，同等位数使用“异或”运算求余

编码过程：
第一步：写出多项式对应的位串
第二步：在待编码位串后面添加0（添加0的个数：多项式对应位串的位数 - 1）
第三步：用新的待编码位串除以多项式对应的位串，求得余数
第四步：求得的余数添加在待编码位串后，即为CRC编码后的码

例子2：
假设CRC编码采用的生成多项式 G(x) = x⁴ + x + 1，请为位串10111001进行CRC编码

第一步：G(x) = x⁴ + x + 1 多项式对应的位串：10011
第二步：位串 10111001 待编码位添加0：101110010000
第三步：求得余数：1001
第四步：余数添加在待编码位：101110011001

如果判断接收到CRC码的帧是否出错：
用收到的位串除以多项式对应的位串。余数为0，无措；余数不为0，有错，丢弃。

多路访问控制协议

MAC协议的根本任务：解决信道的 共享问题

信道划分MAC协议

含义：
利用多路复用技术实现信道共享的MAC协议

多路复用的基本思想：
将 信道资源 划分后，分配给不同的结点，各结点通信时只使用分配到的资源，避免多节点通信时的相互干扰

频分多路复用

Frequency-division Multiplexing, FDM，在频域内将信道带宽划分为多个子信道，将原始信息调整到对应的某个子信道的载波信号上，使同时传输的多路信息在整个物理信道带宽的允许范围内 频谱不重叠，从而共用一个信道

时分多路复用

Time-Division Multiplexing, TDM，将通信信道的传输信号划分为多个等长的时隙，每路信号占用不同的时隙。使多路信号合用单一的通信信道在时域上不重叠，从而实现信道共享

按照固定顺序把时隙分配给各路信号：
同步时分多路复用，Synchronism Time-Division Multiplexing, STDM

时隙和用户间没有固定的对应关系：
异步时分多路复用，Asynchronism Time-Division Multiplexing, ATDM
统计时分多路复用，Statistic Time-Division Multiplexing, STDM

波分多路复用

Wave Division Multiplexing, WDM，广泛应用于 光纤通信。

在光纤通信中，为了实现长距离的高速传输，通常采用 波分多路复用 和 光纤放大器。

码分多路复用

Code Division Multiplexing, CDM，通过利用 相互正交 的码组分别编码各路原始信息的每个码元，使得编码后的信号在同一信道中混合传输。

是一种扩频的通信方式。

相互正交：
对应位数相乘之后，再相加后，等于0

随机访问MAC协议

所有用户都可以根据自己的意愿随机地向信道发送信息。

没有其他用户：发送成功
有两个及以上用户：产生 冲突或碰撞，用户发送信息失败。每个用户随机退让一段时间后，再次尝试，直至成功

ALOHA协议

最早的、最基本的 的无线数据通道协议

ALOHA协议分类：

纯ALOHA协议：网络负载为 0.5 时性能最佳
时隙ALOHA协议：网络负载为 1 时性能最佳

载波监听多路访问协议

Carrier Sense Multiple Access, CSMA。

通过硬件装置（载波监听装置），在通信站发送数据之前，先监听信道上其他站点是否发送数据，如果在发送，则暂时不发送。

分类：根据监听策略不同

非坚持CSMA
1-坚持CSMA
P-坚持CSMA

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

Carrier Sense Multiple Access/Collision Detection, CSMA/CD。

通信站使用CSMA协议进行数据发送，在发送期间如果能检测到碰撞，立即 终止发送，并发出一个 冲突强化信号，使所有通信站点都知道冲突的产生。发出冲突强化信号后，等待一个随机时间，再重复上述过程。

使用 CSMA/CD 协议实现多路访问时，通过共享信道通信的两个通信站之间相距的最远距离D，信号的传播速度V，数据帧长度L，以及信道信息传输速率R之间满足以下约束：

$\frac{L~min~} {R} ≥ \frac{2D~max~} {V}$

受控接入MAC协议

集中式控制

系统有一个主机负责调度其他通信站接入信道，从而避免冲突。

方法：轮询（轮叫轮询、传递轮询）

分散式控制

方法：令牌技术

令牌：
一种特殊的帧，代表了通信站使用信道的许可。在信道空闲时一直在信道上传输。一个通信站想要发送数据就必须先获得令牌。

令牌环的操作过程：

网络空闲时，只有一个令牌在环路上绕行。
当一个站点要发送数据时，必须等待并获得一个令牌，将令牌的标志位置为“1”，随后便可发送数据。
环路中的每个站点转发数据，边检查数据帧中的目的地址，若为本站点的地址，便读取其中所携带的数据。
数据帧绕环一周返回时，发送站将其从环路上撤销。
发送站点完成数据发送后，重新产生一个令牌传至下一个站点，以使其他站点获取发送数据帧的许可权。

令牌环网上最严重的两种错误：令牌丢失 和 数据帧无法撤销

局域网

采用广播的方式，局部区域覆盖，覆盖面积小，网络传输速率高，传输的误码率低。

为了使数据链路层更好地适应多种局域网标准，将局域网的数据链路层拆分为两个子层：逻辑链路控制（Logical Link Control）LLC子层和 介质访问控制（medium access control）MAC子层

数据链路层寻址与ARP

MAC地址

MAC地址具有唯一性，每个 网络适配器 对应一个MAC地址。

网络适配器：
实现数据链路层功能的典型 硬件实体

MAC地址空间的分配：
由电气和电子工程师协会（IEEE）统一管理。IEEE分配前24位的MAC地址块。

以太网和IEEE 802.11无线局域网，使用的MAC地址长度为 6个字节（48位）

通常采用 十六进制 表示法，每个字节表示一个十六进制数，用 - 或 : 连接

MAC广播地址：FF-FF-FF-FF-FF-FF

地址解析协议

Address Resolution Protocol, ARP。

根据本网内目的主机或默认网关的 IP地址 获取其 MAC地址。

基本思想：
ARP查询分组：通过一个 广播帧 发送的
ARP响应分组：通过一个 单播帧 发送的
ARP是 即插即用 的：一个ARP表是自动建立的，不需要系统管理员来配置

ARP表:
在每一台主机中设置 专用内存区域，称为ARP高速缓存（也称ARP表）。存储该主机所在局域网中其他主机和路由器的 IP地址 与 MAC地址 的 映射关系。

存储时效大概为：15分钟

以太网

目前为止最流行的 有线局域网 技术。

以太网MAC协议提供的是 无连接不可靠服务。

经典的以太网 10Base-5

经典的以太网采用 粗同轴电缆 连接的总线型以太网。特点：

数据传输速率为10Mbit/s，无连接不可靠
MAC协议采用 CSMA/CD 协议
相距最远主机信号往返的传播时延为51.2μs，所以以太网的最短帧长为 64字节

以太网成功的原因

以太网 第一个 广泛部署的高速局域网
以太网 数据传输速率快
以太网硬件价格便宜，网络造价成本低
其他有线局域网技术复杂、昂贵，阻止了网络管理员改用其他技术

以太网帧结构

名称	大小（单位：字节）	作用
目的地址	6	MAC地址
源地址	6	MAC地址
类型	2	表示上层协议
数据	46 - 1500	封装上层协议的分组
CRC	4	校验采用循环冗余码

以太网帧最短：64字节
以太网帧除数据报部分：18字节
以太网帧的数据最短：46字节

以太网的发展

以太网帧技术	数据传输速率	标准	传输介质
10Base-T	10Mbit/s	-	双绞线，UTP
100Base-T	100Mbit/s	IEEE 802.3u	UTP，光缆
千兆位以太网	1000Mbit/s	IEEE 802.3 标准的扩展	光纤，双绞线
万兆位以太网	10Gbit/s	IEEE 802.3ae	光纤

交换机

根据接收到的数据链路层帧的目的MAC地址，选择性地转发到相应的端口。

应用最广泛的 数据链路层设备。

以太网交换机的自学习

以太网交换机有4个端口号，各连接一台计算机，其MAC地址分别是ABCD
开始，以太网交换机里面的 转发表 是空白的
当计算机A 向计算机B 发送一个帧，从端口1进入交换机
交换机查询转发表，没找到往哪里转发该帧
交换机把这个帧的 源MAC地址A 和 端口1 写入转发表，完成第一次学习
交换机除 端口1 以外的所有端口 泛洪（广播） 这个帧
计算B接收该帧，交换机保存 源MAC地址B 和 端口2 写入转发表

以太网交换机的优点

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

虚拟局域网

Virtual Local Area Netwrok, VLAN

一种基于 交换机 的 逻辑分割 广播域的局域网应用形式。

以软件的方式划分和管理局域网中的工作组，限制接收广播信息的主机数，不会因为传播过多的广播信息而引起性能的恶化。

划分虚拟局域网的方法

基于 交换机端口 划分
基于 MAC地址 划分
基于 上层协议类型或地址 划分

点对点链路协议

点对点协议

Point to Point Protocol, PPP。适合 单个发送方 和 单个接收方 的点对点链路

PPP主要提供的3种功能

成帧：确定一帧开始和结束，支持差错检测。开始和结束的标志字节：01111110
链路控制协议（LCP）：启动线路、检测线路、协商参数、关闭线路
网络控制协议（NCP）：协商网络层选项

PPP帧格式

名称	大小 / 字节
标志 01111110	1
地址 11111111	1
控制 00000011	1
协议	1、2
信息	可变长度
校验和	2、4
标志 01111110	1

PPP是面向字节的

PPP帧的长度都是 整数字节。

用在 同步传输链路 时，协议规定采用硬件来完成 位填充。

用在 异步传输 时，使用 字节填充技术。

字节填充技术：
当发送帧的数据中，恰好存在一个字节（01111110，非结束字节），则在此字节前插入特殊的控制转义字节 01111101。

例子：
发送方：Byte4 Byte3 01111110 Byte1
处理：Byte4 Byte3 01111110 01111101 Byte1
接收方：Byte4 Byte3 01111110 Byte1

高级数据链路控制协议

Hight-level Data Link Control, HDLC。应用于点对点链路和点对多链路

HDLC帧格式

名称	大小 / 字节	补充
01111110	1	帧定界符
地址	1
控制	1	序列号、确认等
数据	>=0
校验和	2	循环冗余码
01111110	1	帧定界符

根据 控制位 的不同，HDLC有3种类型的帧：

信息帧（I格式 Information）：传送数据
管理帧（S格式 Supervisory）：差错控制、流量控制
无序号帧（U格式 Unnumbered）：链路的建立、拆除

HDLC是面向位的

位填充技术：
当发送的数据中存在 连续的5个1 时，则在这5个1后添加0

HDLC的操作方式

正常响应方式
异步响应方式
异步平衡方式