第三章数据链路层

第一节数据链路层功能

「数据链路层」为网络层提供的服务

无确认的无连接服务
- 丢失数据不负责，交给上层处理
- 用于实时通信和误码率较低的通信信道，如以太网。
有确认的无连接服务
- 丢帧重传，提高可靠性。
- 用于误码率较高的通信信道，如无线通信。
有确认的面向连接服务
- 每帧都确认，确认后发送下一帧。
- 可靠性最高。

TIP

有连接就一定有确认，不存在无确认的面相连接的服务。

「数据链路层」链路管理

数据链路层连接的建立、维持和释放过程。

「数据链路层」帧定界、帧同步、透明传输

两台主机传输信息，网络层分组封装成帧。
帧的构成：一段数据的前后分别添加首部和尾部。
帧长 = 数据长度 + 首部和尾部的长度。
帧定界：使用帧的首部和尾部界定帧的界限。
帧同步：接收方能从接收到的二进制比特流中区分出帧的起始与终止。
最大传送单元(MTU)：数据链路层协议规定的帧数据部分的长度上限。
透明传输：传输的数据中恰好出现与帧界定符相同的比特组合，导致丢弃后面传输的数据。

HDLC帧格式

当接收方检测到帧标识位F就认为是帧的起始。

「数据链路层」流量控制

流量控制：限制发送方的发送能力，使其发送速率不超过接收方的接受能力。
流量控制不是数据链路层特有的功能，高层协议中也有控制其他对象的流量控制功能。
- 对数据链路层，控制的是两个相邻结点之间数据链路上的流量。
- 对传输层，控制的是源端到目的端之间的流量。

TIP

OSI体系中，数据传输层具有流量控制功能。
TCP/IP体系中，流量控制功能被移到了传输层。

「数据链路层」差错控制

差错控制：使发送方确认接收方是够正确收到其发送的数据的方法。

两种差错

位错：帧中某些位出现了错误。
- 通常采用循环冗余校验(CRC)发现位错。
- 通过自动重传请求(Automatic Repeat reQuest, ARQ)方式重传出错的帧。
- ARQ法：只需返回很少的控制信息就可检错。
  - 发送方将数据帧中附加一定的CRC冗余检错码一起发送，接收方根据检错码进行错误检测，错误则丢弃，发送方超时重传。
帧错：帧的丢失、重复、失序等错误。
- 引入定时器和编号机制，保证最终有且仅有一次正确交付。

第二节组帧

组帧：发送方通过一定的规则将网络层递交的分组封装成帧。
为什么要组帧？
- 在出错时只需重发出错的帧而不是所有数据。

「组帧」字符计数法

字符计数法：在帧头部使用一个计数字段表明帧内字符数（计数字段提供的字节数包含自身所占的一个字节）

字符计数法的问题

如果计数字段出错，就失去了划分帧边界的依据，接收方无法判断该帧结束位和下一帧开始位，双方失去同步，造成灾难性后果。

「组帧」字符填充的首尾定界符法

控制字符SOH放在帧的最前面，表示帧的首部开始。
控制字符EOT放在帧的最后面，表示帧的结束。
在信息位中出现的特殊字符前面填充一个转义字符('ESC'，非字母'E''S''C')
- 接收方接收到转义字符时，会判断后面紧跟的是数据信息而非控制信息，并自动删除这个插入的转移字符 ESC。
- 如果转义字符 ESC 也出现在传输数据中，则在 ESC 前面插入一个 ESC。

「组帧」零比特填充的首尾标志法

用 01111110标志帧的开始和结束。
信息位中为了避免误判
- 发送方在信息位中连续五个 1 中的后面 自动插入一个 0。
- 接收方在接受到连续五个 1 后面的 0自动剔除掉。
很容易由硬件实现，性能优于字符填充法。

「组帧」违规编码法

因为“高-高”电平对和 “低-低”电平对在数据比特中是违规的，故用这些违规编码序列来定界帧的起始和终止。

TIP

由于字符计数法中计数字段的脆弱性、字符填充法实现上的复杂性和不兼容性，目前较常用的是零比特填充法和违规编码法。

第三节差错控制（比特差错）

通常利用编码技术进行差错控制
- ARQ 自动重传请求：检测到差错自动重发，直到正确。
- FEC 前向纠错：能发现差错还可确定比特错误的位置。

「检错编码」奇偶校验码

奇校验码和偶校验码的统称，最基本的检错码，由n-1位信息元和1位校验元组成。
奇校验码：附加一个检验元后，码长为 n 的码字中 1 的个数为奇数；
偶校验码：附加一个检验元后，码长为 n 的码字中 1 的个数为偶数；
只能检错奇数位的出错情况，不能发现偶数位的出错情况，且不能确定错误位置。

「检错编码」循环冗余码

循环冗余吗(Cyclic Redundancy Code, CRC)又称多项式码。

循环冗余码的原理

任何一个有二进制数位串组成的代码都可以与一个只含有0和1两个系数的多项式建立一对一关系。
给定一个 m bit 的帧或报文，发送方生成一个 r bit 的序列，称为帧检验序列(FCS)。
形成长度为 m+r 比特的帧。
发送方和接收方事先商定一个多项式 G(x) （最高位和最低位必须为1），使这个带检验码的帧刚好能够被预先确定的多项式 G(x) 整除。
若接收方能够用收到的帧除以相同的多项式，且无余数，则无差错。

循环冗余码的计算步骤

加 0。假设 G(x) 的阶为 r，在帧的低位端加上 r 个 0。
模 2 除。利用模 2 除法，用 G(x) 对应的数据串除 步骤1 中计算出的数据串，得到的余数就是冗余码（共 r 位，前面的 0 不可省略）。
- 模 2 运算规则：加法不进位，减法不借位，刚好是异或操作。
- 异或运算：同 0 异 1； $\frac{10100}{11010} = 01110$
- 多项式的加减法使用模 2 运算，乘除法使用类似二进制的运算。
数据末尾加上 r 位余数。

循环冗余码的计算举例

要发送的源数据为 101001000，采用 CRC 校验，生成多项式为 1101，则最终发送数据为？

生成多项式为4位，则在数据后补上3个0；101001000 000
进行异或运算
在发送的源数据的末尾加上 R（余数，FCS）；101001000 001

TIP

数据链路层通过循环冗余码的检错技术做到了对帧的无错接收。
循环冗余码 CRC 是具有纠错功能的，但是数据链路层只使用了它的检错功能。

「纠错编码」海明码

海明码的原理

有效信息位中加入几个校验位形成海明码，并把海明码的每个二进制位分配到几个奇偶校验组中。
当某一位出错后，会引起有关的几个校验位的值发生变化，可发现错位并定位位置。

TIP

海明码只能检验一位比特的错误。

「纠错编码」海明码的编码原理和过程

确定海明码的位数（海明码的信息位为 1010）（存在争议）

信息位 n 位和校验位 k 位满足 $n + k \leq 2^{k} - 1$ （检验两位错，需增一位检验位， $k + 1$ 位）
- 海明码位数为 $n + k = 7 \leq 2^{3} - 1$ ；
- 信息位为 $D_{4} D_{3} D_{2} D_{1} (1010)$ ，共4位。
- 检验位为 $P_{3} P_{2} P_{1}$ ，共3位。
- 对应的海明码为 $H_{7} H_{6} H_{5} H_{4} H_{3} H_{2} H_{1}$ ，共7位。

确定校验位的分布

规定校验位 $P_{i}$ 海明位号为 $2^{i - 1}$ 的位置上，其余位置为信息位。

位数	7	6	5	4	3	2	1
计算检验位位置	1	0	1	$P_{3}$	0	$P_{2}$	$P_{1}$

分组以形成校验关系

每个数据位用多个校验位进行校验，被校验数据位的海明码等于校验位各校验位海明码之和。
校验位不需要再被校验。

位置编码	7	6	5	4	3	2	1
计算检验位位置	1	0	1	$P_{3}$	0	$P_{2}$	$P_{1}$
校验位组合	$7 = 4 + 2 + 1$ $P_{3} + P_{2} + P_{1}$	$6 = 4 + 2$ $P_{3} + P_{2}$	$5 = 4 + 1$ $P_{3} + P_{1}$	$P_{3} = 2^{2}$	$3 = 2 + 1$ $P_{2} + P_{1}$	$P_{2} = 2^{1} + 2^{0}$	$P_{1} = 2^{0}$

校验位组合为信息位的位置编码用校验位的位置编码组合表示。

校验位取值

校验位 $P_{1}$ 的值为第 i 组（由该校验位校验的数据位）所有为求异或。
- $P_{1} = D_{1} \oplus D_{2} \oplus D_{4} = 0 \oplus 1 \oplus 1 = 0$
- $P_{2} = D_{1} \oplus D_{3} \oplus D_{4} = 0 \oplus 0 \oplus 1 = 1$
- $P_{1} = D_{2} \oplus D_{3} \oplus D_{4} = 1 \oplus 0 \oplus 1 = 0$
故信息位 1010 对应的海明码为 1010010。

海明码的校验原理

每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查，构成 k 个校验方程。
- $S_{1} = P_{1} \oplus D_{1} \oplus D_{2} \oplus D_{4}$
- $S_{2} = P_{2} 1 \oplus D_{1} \oplus D_{3} \oplus D_{4}$
- $S_{3} = P_{3} \oplus D_{2} \oplus D_{3} \oplus D_{4}$
若 $S_{3} S_{2} S_{1} = 000$ 说明无错，否则出错，结果就是错误的位号。
如 $S_{3} S_{2} S_{1} = 001$ 说明第 1 位出错，直接取反就可纠错。

第四节流量控制和可靠传输机制

「流量控制」停止-等待

发送方每发送一帧，都要等待接收方应答信号，若接受方无应答，发送方一直等待。

「流量控制」滑动窗口

发送窗口：发送方维持一组连续的允许发送的帧的序号。
接收窗口：接收方维持一组连续的允许接收的帧的序号。
发送窗口的大小：代表还未收到对方确认信息的情况下发送方最对还可以发送多少个数据帧。
若接收方接收的数据帧序号在接收窗口之外，则丢弃。

发送端
- 每收到一个确认帧，发送窗口向向前滑动一个帧的位置。
- 当发送窗口内没有可以发送的帧（帧已发送但未收到确认），发送方停止发送。
接收端
- 收到数据帧，窗口向前移动一个位置，发回确认帧。
- 若收到的数据帧落在接收窗口之外，全部丢弃。

滑动窗口的特性

接收窗口向前滑动后（接收方发送确认帧），发送窗口才会向前滑动。
从滑动窗口的概念上看，停止等待、后退N帧协议和选择重传协议只在发送窗口和接收窗口的大小上有区别：
- 停止-等待协议：发送窗口大小 = 1，接收窗口大小 = 1。
- 后退N帧协议：发送窗口大小 > 1，接收窗口大小 = 1。
- 选择重传协议：发送窗口大小 > 1，接收窗口大小 > 1。
接收窗口大小为1时，可以保证帧的有序接收。
数据链路层的滑动窗口协议中，窗口的大小在传输过程中时固定的。

「流量控制」可靠传输机制

通常使用确认和超时重传两种机制完成。
确认：是一种无数据的控制帧，可以使接收方让发送方知道那些内容被正确接收。
捎带确认：为提高传输效率，将确认捎带在一个回复帧中。
超市重传：指发送方在发送某个数据帧后就启动一个计时器，在指定时间内没有得到发送的数据帧的确认帧，则重新发送数据帧。
自动重传请求 ARQ ：通过几首放请求发送方重传出错过的数据帧来回复出错的帧。
传统自动重传请求：
- 停止-等待（Stop and Wait) ARQ
- 后退 N 帧 (Go Back N) ARQ
- 选择性重传 (Selective Repeat) ARQ
连续 ARQ 协议：将窗口尺寸开到足够大，帧可以在线路上连续地流动。
数据链路层中的流量控制机制和可靠传输机制是一起使用的。

「流量控制」单帧滑动窗口与停止-等待协议

什么是停止-等待协议？

发送方发送一个帧后必须等待到接收方发送的该帧的确认帧 ACK后，才可以继续发送下一帧。
停止-等待协议相当于滑动窗口大小为 1 的滑动窗口协议。

停止-等待协议可能出现的三种差错

数据帧丢失。
数据帧出错：利用差错检测技术出比特错误，简单地将数据帧丢弃，发送方未收到确认帧，超时重传，直到数据帧无错误到达。
数据帧正确，确认帧被破坏：发送方收到有误的确认帧则重发数据帧，接收方接收到重复的数据帧会丢弃并重传一个确认帧。

帧缓冲区：为了超时重发和判定重复帧。
- 发送端发送完数据帧后，必须在发送缓存中保留被发送的数据帧的副本，这样才能超时重传，直到接收到接收方发来的确认帧ACK时，才能清除副本。
- 接收端使用其检验接收到的重复数据帧。

TIP

在停止-等待协议中
- 若连续出现相同序号的数据帧，表明发送端进行了超时重传。
- 若连续出现相同序号的确认帧，表明接收端收到了重复帧。
停止-等待协议的通信信道的利用率很低，为克服这种缺点产生了后退 N 帧协议和选择重传协议。

「流量控制」多帧滑动窗口与后退 N 帧协议(GBN)

什么是后退N帧式 ARQ？

发送方无需接收到上一个帧的ACK就可以连续发送下一帧。
接收方检测到接收帧失序后，要求发送方重新发送最后一个正确接收之后的所有未被确认的帧。
接收方只允许按顺序接收帧。

后退N帧协议的原理？

发送方每发送一帧后就为该帧设置一个超时计时器。
累计确认：接收方对某一数据帧的确认表明该数据帧和此前所有的数据帧均已正确无误地收到
若接收方收到了未按序到达的数据帧 2~n，将重复发送已发送的最后一个确认帧 $A C K_{1}$ （防止确认帧丢失）。
发送方收到确认帧 $A C K_{1}$ 后，重发数据帧 2~n。

发送窗口大小的限制

后退N帧协议的接收窗口为1，可以保证数据帧的按序到达。
若采用 n 比特对帧编号，则发送窗口的大小 $W_{T}$ 应该满足 $1 < W_{T} \leq 2^{n} - 1$ 。
若发送窗口大小大于 $2^{n} - 1$ 会造成接收方无法分辨新帧和旧帧。

TIP

因为重传时会把正确传送的数据帧再次重传，导致利用率降低。
若信道传输质量很差导致误码率较大，不一定优于停止-等待协议。

「流量控制」多帧滑动窗口和选择重传协议(SR)

什么是 选择重传 ARQ 协议?

加大接收窗口，先收下发送序号不连续但仍然处于接收窗口中的那些数据帧，等所缺序号的数据帧到达后一并提交给主机。
选择重传协议可以避免重复传送那些本已正确到达接收端的数据帧，但是需要大容量的缓冲区来缓存那些为未按序正确接收的帧，不可接收序号落在窗口之外的帧，缓冲区大小等于窗口大小，而不是序号数目。

选择重传 ARQ 协议 的原理？

每个发送缓冲区对应一个计时器，当计时器超时，缓冲区的帧重传。
一旦接收方怀疑帧出错就会发送一个否定帧 NAK 给发送方，要求发送方重传 NAK 中指定的帧。
接收窗口 $W_{R}$ 和发送窗口 $W_{T}$ 大小相同（若采用 n 比特对帧编号，窗口大小需要满足 $W_{T_{m a x}} = W_{R_{m a x}} = 2^{(n - 1)}$ ）
- 发送窗口大于接收窗口会导致溢出
- 发送窗口小于接收窗口没有意义
- 最大值都是序号范围的一半；
  - 若窗口大小小于小序号范围的一半，当数据帧丢失时，接收方无法分辨是新的数据帧还是发送方重传的数据帧。

信道相关

信道的效率（信道利用率）：从时间角度定义，信道效率是对发送方而言，发送方在一个发送周期内，有效发送数据所需时间占整个发送周期的比率。
发送周期 $T$ ：发送方从开始发送数据到接收到第一个确认帧为止。
信道利用率的计算
- 发送方在一个发送周期内共发送了 L 比特的数据，发送方的额数据传输速率为 C，则发送方用于有效发送数据的时间为 $L / C$ 。
- $信道利用率 = \frac{(L / C)}{T}$
信道吞吐率 = 信道利用率 $\times$ 发送方的发送速率

第五节介质访问控制

为什么要用介质访问控制？

当A、B、C、D、E使用广播信道传送消息，A与C通信，B与D通信，如果同时发送消息，可能互相干扰而发送失败。
介质访问控制就是为了避免互相干扰的情况。

介质访问控制(Medium Access Control, MAC)子层

数据链路层的一个子层，决定广播信道中信道分配的协议数据。

常见的介质访问控制方法

信道划分介质控制方式
随机访问介质控制方式
轮询访问介质访问控制

「介质访问控制」信道划分

将使用介质的每个设备与同一通信信道上的其他设备的通信隔离开，把资源合理分配给其他设备。
多路复用技术：
- 把多个信号组合在一条物理信道上传输，多设备共享信道资源，提高利用率。
信道划分介质访问控制分为4种：
- 频分多路复用 FDM
- 时分多路复用 TDM
- 波分多路复用 WDM
- 码分多路复用 CDM

频分多路复用 FDM

将多路基带信号调制到不同频率载波上，再叠加形成一个复合信号。
若物理信道的可用带宽超过单个原始信号所需带宽，将物理信道总带宽分割成若干与传输单个信号带宽相同（或略宽）的子信道，每个子信道传输一种信号。
每个子信道分配的带宽可不相同，但总和不超过信道总带宽。
防止子信道之间的干扰，相邻信道之间要加入“保护频带”、
优点：充分利用传输介质的带宽，系统效率较高，技术成熟，容易实现。

时分多路复用 TDM

将一条物理信道按时间分成若干时间片，轮流分配给多个信号使用。
每个时间片由复用的一个信号占用，不同于FDM，同一时间发送多路信号。
由于计算机数据的突发性，一个用户对分配到的子信道的利用率不高。

统计时分多路复用（STDM，异步时分多路复用）：是TDM的一种改进，采用STDM帧。
- STDM帧：不固定分配时隙，按需动态分配时隙。

波分多路复用 WDM

光的频分多路复用，在一根光纤中传输多种不同波长（频率）的光信号。
光的波长（频率）不同，各路光信号互不干扰。

码分多路复用 CDM

采用不同编码来区分各路原始信号。
和FDM和TDM不同，既共享信道的频率，又共享时间。
码分多址（Code Diavision Multiple Access，CDMA）：原理是每个比特时间再划分成 m 个短的时间槽，称为码片（Chip），m 一般为64或128。

形象描述各种复用

A站要向C站运输黄豆，B站要向C站运输绿豆，AC、BC之间有一条公共道路（类比广播信道）
- 频分复用、波分复用：公共道路划分为两个车道；共享时间，不共享空间。
- 时分复用：A到C走一趟，B到C走一趟，交替占用车道；共享空间，不共享时间。
- 码分复用：黄豆绿豆放在同一辆车上，到C后，由C站负责分开黄豆和绿豆；共享时间和空间。

「信道划分」码分多址 CDMA

码分多址 CDMA 的原理

若站点 A 的码片序列被指派为 00011011
- A 站发送 00011011 就表示发送比特 1
- A 站发送反码 11100100 就表示发送比特 0
为方便，惯例将码片中的 0 写为 -1，1 写为 +1
- 故站 A 的码片序列为 -1 -1 -1 +1 +1 -1 +1 +1
令向量 $S$ 表示 A 站的码片向量，令 $T$ 表示 B 站的码片向量。
两个不同站的码片正交(即S与T的规格化内积）必定为0。

S \cdot T = \frac{1}{m} \sum_{i = 1}^{m} S_{i} T_{i} = 0

任何一个码片向量和其自身规格化内积都是1，与其自身反码的向量规格化内积都是-1。
若向量 $T$ 为-1 -1 +1 -1 +1 +1 +1 -1
- 当 A 站向 C 站发送数据 1 时，就发送了向量 -1 -1 -1 +1 +1 -1 +1 +1
- 当 B 站向 C 站发送数据 0 时，就发送了向量 +1 +1 -1 +1 -1 -1 -1 +1
- 两个想来你到公共信道上叠加，就是线性相加，得到
  - $S + T$ = 0 0 -2 2 0 -2 0 -2
- 到达 C 站后，进行数据分离
  - 若得到 A 站数据，C 站就必须知道 A 站的码片序列，让 $S$ 与 $S + T$ 进行规格化内积；
    - 根据叠加原理，其他站点的信号都在内积的结果中被过滤掉了，内积的相关项都是 0，而只剩下 A 站发送的信号；
    - 得到 $S \cdot (S + T) = 1$ ，即 A 站发出的数据为 1。
  - 同理要得到 B 站发送来的数据，那么 $T \cdot (S + T) = - 1$ ，表示 B 站发送来的是一个反码向量，代表 0。

::: ::: info 码分多址的计算 :::

「介质访问控制」随机访问

不采用集中控制方式解决发送信息次序问题，为解决碰撞问题，每个用户按照一定的规则反复重传它的帧，直到无碰撞通过，占用信道全部速率。
常用的协议CSMA、CSMA/CD、CSMA/CA协议，核心思想为：胜利者通过争用获取信道的使用权。
随机访问介质控制协议，又称争用型协议；既不共享空间，也不共享时间；本质上是将广播信道转化为点到点信道的行为。

「随机访问」CSMA协议

1-坚持CSMA

基本思想
- 一个结点要发送数据，先监听信道
  - 若信道空闲，立即发送。
  - 信道忙，则等待，继续监听直到信道空闲。
  - 若有冲突，随机等待一段时间，重新监听。
1-坚持含义：监听到信道忙，继续坚持监听；监听到信道空闲，发送帧的概率为1，立即发送。
特点
- 传播延迟对 1-坚持CSMA协议性能影响较大。
  - A 未发送完，B监听到信道空闲，发生冲突。
  - A 发送时，B、C同时监听信道忙；A发送结束，B、C同时发送，发生冲突。

非坚持CSMA

基本思想
- 一节点要发送数据，首先监听信道
  - 信道空闲，立即发送
  - 信道忙，放弃监听；随机时间后重复上述过程。
特点
- 降低了多结点等待信道空闲后同时发送数据导致的冲突。
- 增加数据在网络中的平均延迟。

p-坚持CSMA

用于时分信道。
基本思想
- 一结点要发送数据，先监听信道
  - 信道忙，持续监听，直到信道空闲。
  - 若信道空闲，以概率 p 发送数据，以概率 1-p 推迟到下一个时隙。
  - 若在下一个时隙仍然空闲，那么仍然以概率 p 发送数据，以概率 1-p 推迟到下一个时隙。
- 这个过程一直持续到数据发送成功，或因其他结点发送数据而检测到信道忙为止，若信道忙，则下一个时隙重新监听。
特点
- 概率 p 发送数据或概率 1-p 推迟发送的目的：降低 1-坚持CSMA 协议中多结点检测信道空闲同时发送数据导致的冲突的概率。
- 采用坚持监听的目的：试图克服非坚持CSMA协议中由于随机等待而造成的延迟时间较长的缺点。
- p-坚持CSMA协议是1-坚持CSMA和非坚持CSMA的折中方案。

三种不同类型的CSMA协议比较

「随机访问」CSMA/CD协议

CSMA/CD（Carrier Sense Multiple Access/Collision Detection) 载波监听多址接入/碰撞检测
- 是CSMA协议的改进方案。
- 适用于总线型网络或半双工网络；全双工网络采用双信道，无冲突，不适用。
多址接入 MA：多个站连接在一条总线，竞争使用总线。
载波监听 CS：每个站发送数据前，先检测总线上是否有其他站点在发送数据（先听后说）
- 若监听到总线上空闲96比特时间（最小帧间隔），则发送这个帧。
- 监听到总线忙，继续监听，直到满足条件，发送这个帧。
碰撞检测 CD：边发送边监听，监听到碰撞，立刻停发数据，等待随机事件，重发数据。
CSMA/CD工作流程：先听后发，边听边发，冲突停发，随机重发。

「随机访问」CSMA/CA协议

CSMA/CA（Carrier Sense Multiple Access/Collision Avoidance) 载波监听多址接入/碰撞避免
碰撞避免 CA：不是指完全避免碰撞，而是尽量降低碰撞发生的概率。

第六节局域网

「局域网」基本概念

局域网 LAN 的特性由三个要素决定

拓扑结构：星形、环形、总线性、星形和总线型结合的复合型结构
传输介质
- 有线局域网：双绞线（主流）、同轴电缆、光纤
- 无线局域网：电磁波
介质访问控制方式
- 用于总线型局域网：CSMA/CD、令牌总线（将一条总线上的设备变成一个逻辑环，顺序使用总线资源）
- 用于环形局域网：令牌环

三种特殊的局域网拓扑实现

以太网（使用最为广泛）
- 结构：逻辑拓扑是总线性结构，物理拓扑是星形结构。
- 介质访问控制：CSMA/CD
- 标准： IEEE 802.3
令牌环（Token Ring）
- 结构：逻辑拓扑是环形结构，物理拓扑是星形结构。
- 标准：IEEE 802.5
FDDI（光纤分布数字接口)
- 结构：逻辑拓扑是环形结构，物理拓扑是双环结构。
- 标准：IEEE 802.2

数据链路层分为两个子层

LLC 子层（基本不用）：逻辑链路控制子层，为网络层提供服务
- 无确认无连接、面向连接、待确认无连接
- 高速传送
- 差错控制
- 给帧加序号
MAC 子层：介质访问控制子层
- 数据帧的封装/卸装
- 帧的寻址和识别
- 帧的接收与发送
- 竞争处理
- 比特差错控制

「局域网」以太网与IEEE 802.3

结构：
- 逻辑上采用总线型拓扑结构，所有计算机共享一条总线，信息以广播方式发送；
- 物理上采用星形拓扑结构。
介质访问控制：使用CSMA/CD协议对总线进行控制。
两个标准：
- DIX Ethernet V2
- IEEE 802.3 标准（是一种基带总线型的局域网标准，描述物理层和数据链路层的MAC子层的实现方法）
简化通信的两项措施：
- 提供无连接、不可靠的连接服务。
  - 无连接：不编号（数据帧），不确认（接收方）；
  - 不可靠：尽最大努力交付数据，差错纠正由高层完成。
- 发送的数据使用曼彻斯特编码的信号。

「以太网」以太网的传输介质与网卡

介质访问控制地址 MAC：全世界每块网卡在出厂时都有的一个唯一的代码，这个地址用于控制主机在网络上的数据通信。
网卡：控制主机对介质的访问；也工作在物理层，只关注比特，不关注任何地址信息和高层协议信息。

「以太网」以太网的MAC帧

前导码：不属于MAC帧，用于标识MAC帧的开始。
MAC帧：
- 目的地址、源地址：均为MAC地址，用6个十六进制表示的48位二进制数。
- 类型：表示数据使用何种协议。
- 数据：46~1500字节大小。
  - 46字节：以太网中最小帧长为64B，64-(6+6+2+4)=46。
  - 1500字节：以太网规定的最大帧长。
- FCS：CRC循环冗余校验使用。

「以太网」高速以太网

以太网	100BASE-T以太网	吉比特以太网	10吉比特以太网
传输介质	（屏蔽）双绞线	光纤、双绞线（5类线）	光纤
传输速率	100Mb/s	1Gb/s	10Gb/s
通信方式	全双工、半双工	全双工、半双工	全双工
介质控制方式	CSMA/CD（半双工）
拓扑结构	逻辑：总线型物理：星形
编码	曼彻斯特编码

「以太网」以太网卡

网卡实现的功能主要位于物理层和数据链路层
每个网卡之间使用曼彻斯特机制来进行同步
以太网卡具有的独一无二的代码，称为介质访问控制(MAC)地址

「局域网」无线局域网与IEEE 802.11

802.11 MAC帧头格式

RA：接收端所连接AP的MAC地址
TA：发送端所连接AP的MAC地址
DA：接收端的MAC地址
SA：发送端的MAC地址

不同的 MAC 帧头格式

	Add1	Add2	Add3	Add4	From DS	To DS
IBSS	DA	SA	BSSID	-	0	0
To AP	AP的地址	源地址	目的地址	-	0	1
From AP	目的地址	AP的地址	源地址	-	1	0
WDS	下一条地址	上一跳地址	目的地址	源地址	1	1

IEEE 802.11 标准

有固定基础设施的无线局域网
- 每台设备通过AP组成一个基本服务集（BSS）
- AP之间通过主干分配系统（DS） 相连接，构成扩展服务集（ESS）
无固定基础设施的无线局域网
- 设备之间自由组网，保持在一个网段内，没有AP等设备。

「局域网」VLAN

传统局域网的缺陷
- 缺乏流量隔离：广播流量会跨越整个机构网络（ARP、RIP、DHCP协议）。
- 一个单位的不同部门共享一个局域网，对安全不利。

VLAN

将局域网内的设备划分成与物理位置无关的逻辑组的技术
VLAN是通过软件的方式实现的，因此节点的位置不受物理位置的限制
每个VLAN是一个单独的广播域/不同的子网
实现
- 基于接口：交换机中除了转发表，还存在一张VLAN表，记录了各个端口号和它对应的VLAN号。
- 基于MAC地址：VLAN表中记录的是各个MAC地址和它对应的VLAN号。
- 基于IP地址：可以进行跨路由器扩展。
VLAN之间的通信：将帧上附加相应的VLAN标签。
优点：有效的共享资源、优化管理、提高了安全性。

IEEE 802.1Q 帧

VLAN标记共4个字节
- 前两个字节表明这是一个IEEE802.1Q帧
- 之后4位无用
- 后12位是VLAN标识符VID
802.1Q帧是由交换机处理的，主机和交换机间交换的就是普通的MAC帧。

第七节广域网

「广域网」广域网与局域网的差别

	广域网	局域网
协议	网络层、数据链路层、物理层	数据链路层、物理层
强调	资源共享	通信子网采用分组交换技术
连接	点到点连接	通信子网采用分组交换技术
通信子网	分组交换技术

「广域网」PPP协议

点对点协议
只支持全双工通信

PPP协议的特点

PPP协议应当满足
- 简单：对于链路层的帧，无需纠错，无需序号，无需流量控制。
- 封装成帧：添加帧定界符
- 透明传输：与帧定界符一样比特组合的数据应该如何处理
  - 异步线路用字节填充
  - 同步线路用比特填充
- 多种网络层协议：封装的IP数据报可以采用多种协议。
- 多种类型链路：串行/并行，同步/异步，电/光...
- 差错检测：错就丢弃。
- 检测连接状态：链路是否正常工作。
- 最大传送单元：数据部分最大长度MTU。
- 网络层地址协商：知道通信双方的网络层地址。
- 数据压缩协商
PPP协议无需满足
- 纠错
- 流量控制
- 序号：为帧编号
- 不支持多点线路

PPP协议的组成要素

一个将IP数据报封装到串行链路（同步串行/异步串行）的方法
链路控制协议LCP：建立并维护数据链路连接（物理连接）
网络控制协议NCP：PPP可支持多种网络层协议，每个不同的网络层协议都要一个相应的NCP来配置，为网络层协议建立和配置逻辑连接（逻辑链接）

PPP协议的连接流程

设备之间建立物理链路
设备之间建立LCP链路
- 进行鉴别成功，连接建立
- 鉴别失败，链路关闭
通过已建立的LCP链路建立NCP链路

PPP协议的帧格式

PPP协议是一种面向字符的协议

帧定界符：标识帧的开始和结束
地址字段A、控制字段C：无用
协议：信息部分的数据类型
- IP数据报
- LCP的数据
- 网络层控制数据
数据部分：使用转义字符区分与帧定界符相同的数据字
FCS：CRC循环冗余校验用

「广域网」HDLC协议

高级数据链路控制（High-Level Data Link Control或简称HDLC）：采用全双工通信，所有帧采用CRC检验，对信息帧进行顺序编号。

HDLC的站

主站
- 发送命令（包括数据信息）帧
- 接收响应帧
- 负责对整个链路的控制系统的初启、流程的控制、差错检测或恢复等
从站
- 是接收由主站发来的命令帧
- 向主站发送响应帧
- 配合主站参与差错恢复等链路控制
复合站：既能发送，又能接收命令帧和响应帧

HDLC的数据操作方式

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

HDLC的帧格式

帧中比特采用零比特填充法实现透明传输

标志字段：标志帧的开始和结束
地址字段：取决于采用何种数据操作方式
- 正常响应方式、异步响应方式：从站的地址
- 异步平衡方式：应答站的地址
控制字段：HDLC协议的类型
- 信息帧
- 监督帧
- 无编号帧

「广域网」PPP与HDLC的比较

	PPP协议	HDLC协议
面相	面向字节	面相比特
协议标志	有2B的协议字段	通过控制字段标志协议
序号与确认机制	无序号和确认机制	有序号和确认机制
是否可靠	不可靠	可靠

「广域网」广域网、局域网、互联网的关系

互联网可以连接不同类型的网络，使用路由器连接
广域网是类型单一的网络，使用节点交换机连接
从互联网的角度，广域网和局域网是平等关系
以太网是局域网的一种实现形式，逻辑拓扑是总线型结构，物理拓扑是星型

第八节数据链路层设备

「集线器」物理层扩展以太网

使用光纤连接使得传输距离更远
使用集线器等将多台电脑组合成一个冲突域
使用主干集线器连接多个冲突域形成新的更大的冲突域

冲突域

连接在同一个物理层设备上的电脑中，同时只能有一台电脑进行通信，称为一个冲突域
冲突域变大会导致通信效率变低

「网桥」网桥的作用

网桥：根据MAC帧的目的地址对帧进行转发和过滤。当网桥收到一个帧时，并不向所有接口转发此帧，而是先检查此帧的目的MAC地址，然后再确定将该帧转发到哪一个接口，或者是把它丢弃（即过滤）。
网桥一般来说只有两个接口（可能有更多）。
通过网桥将多个冲突域连接起来形成一个广播域，则每一个原来的冲突域就是一个网段。

广播域

网络中能接收任一设备发出的广播帧的所有设备的集合

网段

一般指一个计算机网络中使用同一物理层设备（传输介质，中继器，集线器等）能够直接通讯的那一部分。

网桥的优点

过滤通信量，增大吞吐量
扩大了物理范围
提高了可靠性
可互连不同物理层、不同MAC子层和不同速率的以太网

「网桥」透明网桥

“透明” 指以太网上的站点并不知道所发送的帧将经过哪几个网桥。
每个网桥包含一张转发表，记录了地址和对应接口

数据在网桥的流转过程

A主机发送出一条数据到B主机
该数据经由网段传到网桥1号接口
网桥在转发表内查找A地址
- A地址不存在，则记录下A地址和对应的信息来源接口1
- A地址存在，则略过
网桥在转发表内查找B地址
- B地址存在，则将数据由B地址对应的端口发送出去
- B地址不存在，则将数据通过除了1接口之外的所有接口转发出去
其他网桥同理

「网桥」源路由网桥

在发送帧时，把详细的最佳路由信息（路由最少/时间最短）放在帧的首部中。

源路由网桥的实现方法

源站以广播的形式发送一个发现帧
发现帧通过不同的路由方式到达目的站，之后原路返回
源站根据返回情况选择最合适的路由链路
之后所有发向该目的站的信息都走这条路由

「交换机」以太网交换机

交换机相当于多口网桥
每一个端口都是一个冲突域
各个端口独享带宽
- 100M带宽，4台设备使用集线器，每台带宽为25M
- 100M带宽，4台设备使用交换机，每台带宽为100M

「交换机」直通式交换机

查完目的地址（6B）就立刻转发

优点：延迟小
缺点：可靠性低、无法支持具有不同速率的端口的交换

「交换机」存储转发式交换机

将帧放入高速缓存，并检查否正确，正确则转发，错误则丢弃

优点：可靠性高、可以支持具有不同速率的端口的交换
缺点：延迟大

「设备」各种设备的比较

	能否隔离冲突域	能否隔离广播域
物理层设备集线器、中继器	❌	❌
数据链路层设备网桥、交换机	✅	❌
网络层设备路由器	✅	✅

第八节疑难点

1.链路和数据链路区别、电路接通和数据链路接通区别

2.说明 n 比特进行编号，若接收窗口的大小为 1 ，则只有在发送窗口的大小 $W_{T} \leq 2^{n} - 1$ 时，连续ARQ协议才会正确运行。

3.证明：对于选择重传协议，若有 n 比特进行编号，则接收窗口的最大值为。

4.数据链路层使用PPP协议或CSMA/CD协议，既然不保证可靠传输，为什么对所传的帧进行差错检验？

5.为什么PPP协议不使用帧的编号和确认机制实现可靠传输？

7.局域网、广域网和因特网之间的关系总结

8.IEEE 802 局域网参考模型和OSI参考模型有什么异同？

13.冲突域和广播域的区别

14.关于物理层、数据链路层、网络层设备对于隔离冲突域和广播域的总结

17.交换机和网桥的区别

第三章 数据链路层 ​

第一节 数据链路层功能 ​

「数据链路层」为网络层提供的服务 ​

「数据链路层」链路管理 ​

「数据链路层」帧定界、帧同步、透明传输 ​

「数据链路层」流量控制 ​

「数据链路层」差错控制 ​

第二节 组帧 ​

「组帧」字符计数法 ​

「组帧」字符填充的首尾定界符法 ​

「组帧」零比特填充的首尾标志法 ​

「组帧」违规编码法 ​

第三节 差错控制（比特差错） ​

「检错编码」奇偶校验码 ​

「检错编码」循环冗余码 ​

「纠错编码」海明码 ​

「纠错编码」海明码的编码原理和过程 ​

第四节 流量控制和可靠传输机制 ​

「流量控制」停止-等待 ​

「流量控制」滑动窗口 ​

「流量控制」可靠传输机制 ​

「流量控制」单帧滑动窗口与停止-等待协议 ​

「流量控制」多帧滑动窗口与后退 N 帧协议(GBN) ​

「流量控制」多帧滑动窗口和选择重传协议(SR) ​

第五节 介质访问控制 ​

「介质访问控制」信道划分 ​

「信道划分」码分多址 CDMA ​

「介质访问控制」随机访问 ​

「随机访问」CSMA协议 ​

「随机访问」CSMA/CD协议 ​

「随机访问」CSMA/CA协议 ​

第六节 局域网 ​

「局域网」基本概念 ​

「局域网」以太网与IEEE 802.3 ​

「以太网」 以太网的传输介质与网卡 ​

「以太网」以太网的MAC帧 ​

「以太网」 高速以太网 ​

「以太网」以太网卡 ​

「局域网」无线局域网与IEEE 802.11 ​

「局域网」VLAN ​

第七节 广域网 ​

「广域网」广域网与局域网的差别 ​

「广域网」PPP协议 ​

「广域网」HDLC协议 ​

「广域网」PPP与HDLC的比较 ​

「广域网」广域网、局域网、互联网的关系 ​

第八节 数据链路层设备 ​

「集线器」物理层扩展以太网 ​

「网桥」网桥的作用 ​

「网桥」透明网桥 ​

「网桥」源路由网桥 ​

「交换机」以太网交换机 ​

「交换机」直通式交换机 ​

「交换机」存储转发式交换机 ​

「设备」各种设备的比较 ​

第八节 疑难点 ​