数据链路层¶

约 10938 个字预计阅读时间 55 分钟

功能¶

数据链路层利用物理层提供的位流服务，向网络层提供了明确的服务接口。其主要功能如下：

<1> 封装成帧
- 在一段数据前后添加首部和尾部，构成 Frame，是数据链路层的 PDU
<2> 差错检测
- 因为信道噪声等原因，帧在传输过程中可能出现错误
- 1) 位错: 帧中某些位出现差错
- 2) 帧错: 帧丢失、帧重复或帧失序等，属于传输差错
<3> 流量控制
- 链路两端的工作速率和缓存空间存在差异，可能存在发送方的发送能力大于接收方的接收能力，因此流量控制通过某种反馈机制限制发送方的发送速率

封装成帧¶

发送方依据一定规则，将网络层递交下来的分组封装成帧。组帧主要需要解决帧定界、帧同步、透明传输等问题。

实现组帧的方法主要有以下四种：

字节计数法 Byte Count

字节计数法在帧首部设置一个计数字段，记录该帧含有的字节数（包括计数字段本身占用的 1 字节）。当接收方读取帧首部的字节计数值时，就知道后面跟随的字节数从而确定结束位置。

但是如果传输过程中出现差错，例如计数字段错误，则帧边界划分依据被破坏，造成灾难性的后果：

字节填充定界符法 Flag bits with Byte Stuffing

使用特定字节 SOH 表示帧的开始，EOT 表示帧的结束。为了确保数据本身出现的特殊字符不被误判位首尾定界符，我们在特殊字符前填充转义字符 ESC 来加以区分。

若转义字符 ESC 也出现在数据中，则在其前面再添加一个 ESC 即可

比特填充定界符法 Flag bits with Bit Stuffing

比特填充法使用一个特定的比特串 01111110 (0x7E) 标志一个帧的开始和结束。为了不使数据字段中出现的比特流被误判为首尾标志，发送方会先扫描整个数据字段，每遇到 5 个连续的 1 就自动在后面插入一个 0，保证数据字段中不会出现 6 个连续的 1。

比特填充更容易被硬件实现，其性能优于字节填充。

物理层编码违例 Physical layer conding violations

物理层编码违例确保选择的定界符不会在数据部分出现。

例如对于物理层选用了 4B/5B 编码方案，则 5-bit 编码中有一半码字（16）未使用，可以用作帧定界符。

对于曼彻斯特编码/差分曼彻斯特编码，持续的高电平/低电平为违例码，也可以用作定界符。

违例编码法不采用任何填充计数就实现了数据的透明传输，但只适用于冗余编码的环境

差错控制¶

比特在传输过程中可能出现差错，我们通常利用编码技术来进行差错控制，可分为检错编码和纠错编码。

此处，码字（code word）指一个包含 \(m\) 个数据位和 \(r\) 个校验位的 \(n=m+r\) 位单元，描述为 \((n,m)\) 码。

码率即为码字中不含冗余部分所占的比率，可以用 \(m/n\) 来计算。

检错编码¶

为了实现检错，我们必须在传输时增加冗余校验信息。接收方根据收到的码字是否符合规则来判断传输是否发生错误。

奇偶校验码

奇偶校验码是一种最基本的检错码，它由 n-1 位数据和 1 位检验位组成：

奇检验码: 附加一个检验位后，n 位码字中 1 的个数为奇数
偶检验码: 附加一个检验位后，n 位码字中 1 的个数为偶数

奇偶校验码可以检测奇数位错误，即如果存在 1, 3, 5,... 个比特位传输错误，则可以发现错误。

循环冗余码

Cyclic Redundancy Code, CRC 是数据链路层广泛使用的检错技术。

<1> 发送方依据一个约定的多项式 \(G(x)\) 和待发送的数据，计算冗余码，将冗余码附加到数据后面一起发送
<2> 接收方收到数据和冗余码后通过 \(G(x)\) 计算数据和冗余码是否产生差错，做除法运算，若余数为 0，则未检测出错误

CRC 有四个国际标准生成式 \(G(x)\)，其中以太网、无线局域网均采用 CRC-32 生成多项式

对于一个待传送的 \(m\) 位数据，CRC 运算产生一个 \(r\) 位的冗余码，这样形成的帧长度为 \(m+r\) 位。

CRC 的检错能力很强，对于小于 \(r\) 位的错误，一定能够检测出；对于大于 \(r\) 位的错误，能检测出的概率为 \(1-2^{-r}\)，这个值非常接近于 1。

CRC 计算与检验方法

冗余码计算步骤对收到数据和冗余码检错

CRC 其实也具有纠错功能，但数据链路层只是用了它的检错功能

纠错编码¶

海明码是最常见的纠错编码，其特点是将有效信息和检验位分配到几个奇偶校验组中，若某一位出错，会引起有关的几个检验位改变，从而找出错位所在的位置。

海明距离（Hamming Distance）是两个码字之间对应比特不同的数目，例如 00001111 和 00000000 的海明距离为 4；而 00000000, 00001111, 11110000, 11111111 是一组海明距离为 4 的编码。

如果两个码字的海明距离为 \(d\)，则我们需要 \(d\) 个比特错误才可以把一个码字转换成另一个码字。据此，我们有理论：

为了检查出 \(d\) 个比特错，我们可以使用海明距离为 \(d+1\) 的编码
为了纠正 \(d\) 个错，我们可以使用海明距离为 \(2d+1\) 的编码

检错纠错

假设有 \(m\) 个信息位，\(r\) 个校验位，为了设计一个可以纠正单比特错误的纠错码，我们需要考虑码字可以表示的有效信息个数。

\(m\) 个信息位对应了 \(2^m\) 个有效信息，对于每个有效信息，共有 \(n\) 个与其距离为 1 的可纠错非法码字，再加上它自己共 \(n+1\) 个位模式。

我们需要保证码字的可表示的信息 \(2^n\) 大于所有位模式个数之和，即有 \((n+1)2^m \le 2^n\)。又 \(n=m+r\)，我们有不等式：

\[ (m+r+1) \le 2^r \]

即在已知 \(m\) 的前提下可以计算纠错单比特错误校验位数 \(r\) 的下界。

如果要纠错两比特错误，则共有 \(C_n^2\) 个距离为 2 的可纠错非法码字

\[(C_n^1 + C_n^2 +1)2 ^m \le 2^n\]

为了理解海明码编码过程，我们以 \((15,11)\) 海明码为例，它设置了如下奇偶校验组：

图中已经填入数据位 01011001101，根据设置的校验组计算校验位的值如上，得到最后的码字 100110101001101。

那么此时如果有 1 bit 数据发生错误，那么我们根据这四组校验可以确定该位处于哪一列哪一行，从而实现纠错。

PPT 中还讲了 Reed-Solomon Code，此处暂时不写

流量控制¶

流量控制是由接收方控制发送方的发送速率，使接收方有足够缓冲空间来接收每个帧。

停止-等待协议

停止-等待协议是一种简单的流量控制方法，发送方每次只允许发送一个帧，发送后暂停，等待确认到达后发送下一帧；接收方接收到一帧后，需要回复确认接收。

确认帧也被称为哑帧 dummy frame

一个帧在传输过程中损坏，此时接收方可以通过差错控制检测；但一个帧也有可能在传输过程中丢失，为了解决这个问题，发送方需要增加超时机制，在计时器达到一定时间后仍然没有收到确认时，自动重发该帧。

有了超时机制，就可能出现接收方多次收到同一个帧的情况，此时我们需要在帧头部设置序列号 SEQ，以判断这个是新帧还是应该丢弃的重复帧。

在这个协议中，唯一不明确的地方只有相邻两个帧的比对，因此此处只需要使用 1-bit 的序列号即可。

滑动窗口协议

数据链路层和传输层在流量控制上均用到了滑动窗口协议，它们区别如下

数据链路层控制的是相邻节点之间的流量；而传输层控制的是端到端的流量
数据链路层的控制手段是接收方收不下时就不返回确认；传输层的控制手段是接收方通过确认报文段中的窗口值来调整发送方的发送窗口

滑动窗口流量控制是一种更高效的流量控制方法，发送方维护一组连续的允许发送帧的序号，称为发送窗口，大小为 \(W_T\)；接收方维护一组连续的允许接收帧的序号，称为接收窗口，大小为 \(W_R\)。

发送方每收到一个按序确认的确认帧，就将发送窗口向前滑动一个位置。序号落入发送窗口内的数据帧可以继续发送，当窗口内全是已发送但还未收到确认的帧时，发送方就停止发送。

接收方只允许接收接收窗口之内的帧，并且每收到一个序号落入接收窗口的数据帧时，就将接收窗口向前滑动一个位置，并为该帧发回一个确认。

据此，只有接收方发送了确认，接收窗口向前滑动后，发送窗口才能向前滑动

根据滑动窗口的大小不同，我们设计了不同的可靠传输方案：

停止-等待协议: 发送窗口 \(W_T=1\)，接收窗口 \(W_R=1\)
后退N帧协议: 发送窗口 \(W_T\gt 1\)，接收窗口 \(W_R=1\)
选择重传协议: 发送窗口 \(W_T\gt 1\)，接收窗口 \(W_R\gt 1\)

可靠传输¶

可靠传输服务并不局限于数据链路层，其它层也可选择实现

可靠传输指发送方发送的数据都能被接收方正确接收，通常采用确认和超时重传两个机制完成，这种协议也被称为自动重传请求（ARQ）。

在 ARQ 协议中，数据帧和确认帧都需要编号，以区分数据帧和确认帧的对应关系。

停止-等待协议 S-W

从滑动窗口角度来看，停止等待协议的发送窗口和接收窗口大小均为 1。

正如上面所说，停止等待协议每发送一个帧就等待，我们只需要保证连续的两个帧序号不同即可，采用 1-bit 来编码，发送帧交替使用 0 和 1 标识，确认帧交替使用 ACK0 和 ACK1 标识。

若连续出现两个相同序号的数据帧，则说明发送方进行了超时重传；若连续出现两个相同序号的确认帧，则说明接收方收到了重复帧。

发送方和接收方都起码有一个帧大小的帧缓冲区，以保存可能需要重传的帧副本

分析停止等待协议的信道利用率：

\[ U=\frac{T_D}{ T_D + RTT + T_A} \]

对于无线局域网，\(RTT\) 可能远小于 \(T_D\)，因此信道利用率接近 1；对于卫星等 \(RTT\) 较大的链路，可能更适合使用下面介绍的后退 N 帧协议或选择重传协议。

后退 N 帧协议 GBN

后退 N 帧指发送方发送 N 个数据帧后，若发现这 N 个数据帧的前一个数据帧在超时后仍未收到确认，则该帧被判出错或丢失，此时发送方需要重传该帧以及其后的 N 帧。

接收方仍然必须按顺序接收帧，但是 GBN 协议中还允许接收方进行累积确认，即允许接收方在连续收到多个正确数据帧后，只对最后一个数据帧返回确认，表示该帧及之前的帧均已正确收到。

GBN 协议中，发送窗口 \(W_T\) 的大小不应该超过帧编号的总个数，否则接收方有可能无法分辨新旧数据帧。例如如果采用 n-bit 帧编号，则发送窗口大小应该满足 \(1\le W_T \le 2^n-1\)。

n-bit 帧编号，为什么 \(W_T\) 最大值不能是 \(2^n\) ？

假设用 3 比特编号，设置发送窗口最大值为 8。发送方发送 0-7 号共 8 个数据帧后，暂停发送，假定这 8 个数据帧均到达接收方，且接收方对每个数据帧都发回了确认帧，此时存在如下情况：

所有确认帧均丢失。此时发送方超时后，重传这 8 个旧数据帧，其编号仍为 0-7
接收方第二次收到编号为 0-7 的数据帧，但无法判定这是 8 个新数据帧还是 8 个重传的旧数据帧

因此，将发送窗口设置为 8 显然是不行的。

选择重传协议 SR

选择重传协议进一步允许接收方乱序接收帧，此时接收方可以先确认失序但正确到达并且序号仍在接收窗口的数据帧，但此时并不递交给网络层。等到缺失的数据帧到达后，再将其及之后已确认的帧一并送交。

为了使发送方仅重传出错的帧，接收方不能再采用累积确认，只能对每个数据帧逐一确认。接收方还需要设置大小与接收窗口大小相当的帧缓冲区，以暂存那些失序的数据帧。

SR 协议还设置了一个更有效的重传策略，当接收方检测到某个数据帧出错，就立即向发送方发送一个否定帧 NAK，要求发送方立即重传指定的数据帧，而不用等超时。（注意上图的 10 号帧的处理）

对于 n-bit 帧编号，我们要求以下两点：

\(W_R + W_T \le 2^n\)
\(W_R\le W_T\)
- 否则接收窗口永远不会填满，多出的空间无意义

一般情况下会设置 \(W_R=W_T\le 2^{n-1}\)。

点对点协议¶

点对点协议 Point-to-Point Protocol 是现在最流行的点对点链路控制协议，常用于两台网络设备之间的直连专用线路或用户计算机与 ISP 通信时使用。

PPP 帧格式如下，首部有 4 个字段，尾部有 2 个字段：

标志字段 Flag: 值为 0x7E，PPP 帧的定界符，标志一个帧的开始和结束
地址字段 Address: 值为 0xFF，无意义
控制字段 Control: 值为 0x03，无意义
协议字段 Protocol: 0x0021 则数据为 IP 数据报；0xC021 则数据为 PPP 链路控制协议 LCP
帧检验序列 FCS: 占 2 字节，是使用 CRC 校验的冗余码

PPP 帧的透明传输

当 PPP 使用异步传输时，采用字节填充法，使用转义字符 0x7D
当 PPP 使用同步传输时，采用零比特填充法，每出现 5 个连续的 1，就填充一个 0

PPP 协议的特点如下：

<1> 虽然连接建立过程中使用了确认机制，但在数据帧发送过程中只保证无差错接收（通过 CRC 冗余码实现），但不使用序号和确认机制，因而是不可靠服务
<2> 只支持全双工的点对点链路，不支持多点链路
<3> 链路两端可以是不同的网络层协议
<4> PPP 是面向字节的，所有 PPP 帧长度都是整数个字节
- 数据载荷部分长度为 0 - 1500B，相比于后面介绍的 CSMA/CD 协议下的 46 - 1500B（最短帧长 64B，MAC 首部 14B，尾部 4B），没有最短帧长的限制
- 没有最短帧长限制是因为 PPP 协议不运行在总线形网络，而是点对点的，没有争用期

MAC 子层¶

在 OSI 参考模型下，数据链路层实际分为两个子层：

MAC 子层：介质访问
LLC 子层：承上启下

因此本节要讲的其实是介质访问控制相关的问题。

如果令 \(D_0\) 表示网络空闲时的时延，\(D\) 表示网络的当前时延，那么在适当的假定条件下，可以用如下公式表示 \(D,D_0\) 和网络利用率 \(U\) 的关系：

\[ D= \frac{D_0}{1-U} \]

假定 \(D_0\) 是一个微小的非零值，根据函数特性，我们知道：当网络利用率达到 50% 时，时延就要加倍；当网络利用率超过 50% 时，时延急剧增大。

因此，我们需要设计一些优秀的介质访问控制协议，以更好地满足需求，提高信道利用率。

三大类多路访问协议

以太网 MAC 帧¶

在讲解各个协议之前，我们需要先了解 MAC 地址和 MAC 帧的相关概念。

IEEE 802 标准为局域网规定了一种 48 位（6 Byte）的全球地址，即局域网上每台计算机中固化在网络适配器的 ROM 中的地址，称为物理地址或MAC地址。全世界所有的局域网适配器都具有不同的 MAC 地址。

我们通常用分隔的 12 个十六进制数表示长 6 Byte 的 MAC 地址，例如：02-60-8c-e4-b1-21，其中高 24 位为厂商代码，低 24 位位厂商自行分配的适配器序列号。

在这里我们给出以太网 MAC 的格式：

网络适配器每收到一个 MAC 帧，都要检查其中的目的地址字段。如果是发往本站的帧，则收下；否则丢弃该帧。其中“发往本站的帧”包括如下三种：

单播帧: 目的地址与本站的 MAC 地址相同
广播帧: 目的地址为 FF-FF-FF-FF-FF-FF
多播帧: 发送给本局域网上一部分站点的帧

实际传输以太网 MAC 帧时，我们会在其前面先传输长 8B 的前导码，其中前 7 个字节用于实现比特同步，最后 1 字节表示帧开始定界符。因此，MAC 帧本身并不需要定界符。

以太网使用曼彻斯特编码，数据链路层使用 CSMA/CD 协议

随机访问协议¶

ALOHA 协议

纯 ALOHA 协议的基本思想是，当总线形网络中的任何站点需要发送数据时，可以不进行任何检测就发送数据。若在一段时间内未收到确认，则认为传输过程中发生冲突，此时发送站点在等待随机时间后重新发送数据，直到成功。

总线形网络

只要两个帧在相同时间试图占用信道，就会发生冲突。冲突的帧被完全破坏，因此接收方不会返回确认。

纯 ALOHA 协议中一个帧传输过程中遇到冲突的概率符合泊松分布，概率为 \(P_0=e^{-2G}\)，其中 \(G\) 为帧发送时间 \(T\) 内所有通信站总共发送的帧数量平均值，包括原发和重发的分组。那么，每秒发送成功的分组数量 \(S\) 为已发送分组的数量 \(G\) 乘以 \(P_0\)，即：

\[ S=G\times P_0 = G\times e^{-2G} \]

为了实现最高信道利用率，我们对 \(S\) 求导得到 \(S' =e^{-2G} -2Ge^{-2G}=0\)，因此当 \(G=0.5\) 时 Pure ALOHA 协议取得最高信道利用率，此时 \(S=0.5\times e^{-1}=0.184\)。

我们通常用 \(S\) 接近 1 的程度来衡量信道利用率，即 Pure ALOHA 协议的最高信道利用率为 18.4%

纯 ALOHA 协议吞吐量很低，因此产生了时隙 ALOHA 协议，它同步了各站点的时间，将时间划分为一段段等长的时隙，时隙的长度大于等于一帧的传输时间，规定各站点只能在每个时隙开始时才能发送帧。

因此，冲突只可能发生在时隙的起点，冲突发生时只浪费一个时隙，此时冲突双方都等待随机时间后进行重传。

CSMA 协议

CSMA 的全称为载波监听多路访问 Carrier Sense Multiple Access，意指让每个站点在发送数据前都先对公用信道进行监听，确保信道此时空闲后再发送。

根据监听方式和监听到信道忙后的处理方式不同，CSMA 协议分为三种：

协议类型	信道空闲时行为	信道忙时行为	特点总结
1-持续 CSMA	立即发送	持续监听，并等待空闲后马上发送	如果两个以上的站在等待发送，一旦介质空闲就必定发生冲突
p-持续 CSMA	概率 p 发送，概率 1-p 推迟到下一个时隙	持续监听，直到空闲再按概率决策发送	只适用于时分信道
非持续 CSMA	立即发送	等待随机时间，再次监听	冲突可能性较低，但是延迟较高

从 1-持续到非持续，访问控制逐渐从激进变得保守

CSMA/CD (CSMA with Collision Detection) 是 CSMA 协议的改进方案，同时也属于 1-持续 CSMA，适用于总线形网络或半双工网络环境。

其中冲突检测指的是站点在发数据过程中也要持续检测信道，若检测到冲突，则立即停止发送数据，并等待随机时间后再次发送。

假设端到端传播时延为 \(\tau\)，那么一个站在发送数据后经过 \(2\tau\) 才能确定没有发生冲突，因此端到端往返传播时延 \(2\tau\) 称为争用期。以太网在发送数据时，如果争用期内没有发生冲突，则后续的数据就不会发生冲突，因此争用期内可发送的数据长度被规定为最短帧长，计算公式为：

\[ \text{最短帧长}=\text{最大单向传播时延} \times 2 \times \text{数据传输速率} \]

对于 10Mbps，争用期长度为 51.2\(\mu s\) 的以太网，最短帧长为 64B，其中 MAC 帧首尾共 18B

那么，在检测到冲突后，重发等待的随机时间具体怎么确定？CSMA/CD 使用二进制指数退避算法来确定冲突后重传的时机：

确定基本退避时间，一般取 \(2\tau\)
从离散集合 \([0,1,...,2^k-1]\) 中随机取一个数，记为 \(r\)，重传推迟时间即为 \(2\tau \times r\)
- 其中参数 \(k\) 取 \(\min [\text{重传次数},10]\)，即当重传次数超过 10 后，\(k\) 就一直取 10
当重传 16 次仍不成功，则认为该帧永远不会正确发出，抛弃该帧并向上层报告出错

以太网就采用了 CSMA/CD 协议：

吞吐量: 比 ALOHA 高，比 p-持续 CSMA 低
冲突率: 比 ALOHA 少，比 p-持续 CSMA 高

受控访问协议¶

位图协议 / 预留协议

分为竞争期和传输期。竞争期内发送竞争比特，示意自己将要发送数据，给它预留资源；传输期时按序发送，从而保证传输期内无冲突。

令牌传递协议

令牌（Token）是一个特殊的控制帧，仅用作控制信道使用，它会沿着环形总线在各站之间依次传递。

当环上的一个站希望发送帧时，必须等待令牌。站点只有取得令牌后才能发送帧，因为令牌只有一个，所有信道上不会发送冲突。站点发送完一帧后，应释放令牌，以便让其他站使用。

当网络空闲时，环路中只有令牌帧在循环传递。
当令牌传递到有数据要发送的站点时，该站点就修改令牌中的一个标志位，并在令牌中附加自己需要传输的数据，将令牌变成一个数据帧，然后将这个数据帧发送出去。
数据帧沿着环路传输，接收到的站点一边转发数据，一边查看帧的目的地址。若目的地址和自己的地址相同，则接收站就复制该数据帧，以便进一步处理。
数据帧沿着环路传输，直到到达该帧的源站点，源站点收到自己发出去的帧后便不再转发。同时，通过检验返回的帧来查看数据传输过程中是否出错，若出错，则重传。
源站点传送完数据后，重新产生一个令牌，并传递给下一站点，交出信道控制权。

Fiber Distributed Data Interface, FDDI

光纤分布式数字接口是用于在光缆上发送数字信号的一组协议，用于环形网，基于令牌环协议。

二进制倒计数协议

所有想要发送数据的站按照计数从高到低排序，序号高的站点优先发送数据。

有限竞争协议：自适应树¶

分时隙进行数据发送。将在某个时隙开头进行竞争的所有站点分为两半，一半在下一个时隙开头竞争，另一半在下下一个时隙开头竞争。

数据链路层设备¶

集线器是物理层扩充网络的设备，而网桥（或叫以太网交换机）是数据链路层扩充网络的设备，它将几个不同的冲突域连接在一起，并实现了交换转发的功能，它的接口工作在全双工方式，支持多对用户同时点对点通信。

此外，用集线器连接的共享式以太网所有用户共享带宽；但采用交换机连接时，每个用户通信时独占带宽。例如，对于 10Mbps 以太网，若有 10 个用户，则以集线器连接每个用户占有 1Mbps 带宽，而以交换机连接每个用户占有 10Mbps 带宽。

冲突域和广播域的区别

广播域是广播帧能够到达的范围；而冲突域是同一时间内只能有一台设备发送信息的范围，它们通过以太网交换机分割。

广播域范围通常大于冲突域，交换机本身用来隔离冲突域，不隔离广播；但是可以通过 VLAN 技术隔离广播域。

以太网交换机的每个端口都是一个独立的冲突域。如果所有设备都通过交换机全双工相连，而不是通过集线器半双工连接，那么每个冲突域内只有两台设备，且由于收发信道独立，物理上不再产生冲突。因此，在全双工以太网中，不再需要使用 CSMA/CD 等协议来管理介质访问，数据传输效率大幅提升。

另外与集线器有区别的是，集线器会将收到的帧直接转发到除了输入端口以外的所有端口，而交换机会根据自己的 MAC 地址表进行转发，具体如下：

为了实现交换功能，网桥可以自学习构建 MAC 地址表。任意一个站发送帧时，网桥也会收到一份相同的帧，此时发送站的 MAC 地址就会被学习。

一般设置自学习得到的动态表项老化时间为 300s，当老化时间到期时，该表项会被清除；不过我们也可以手动添加静态 MAC 地址表项，它不会老化，且优先级高于动态表项。

网桥对于收到的入境帧有三种处理：

forwarding: 转发，在 MAC 地址表完善时根据表项选择转发到哪个端口
filtering: 过滤，如果入境口等于出境口，说明该帧没有跨冲突域，丢弃该帧
flooding: 泛洪，类似广播，在找不到匹配表项时，将该入境帧向所有端口转发（除了入境口）
- 一个网段的数据被发送到无关网段，存在安全隐患；浪费网络资源

从交换方式（带宽）角度来看，可分为对称交换和非对称交换：

对称交换：出入带宽相同
非对称交换：出入带宽不相同

而从交换模式（转发时机）角度来看，可分为以下三种模式：

存储转发模式，Store and Forward: 转发前必须接收整个帧，并执行 CRC 校验
- 优点是不转发出错帧、支持非对称交换
- 缺点是延迟大
直通模式，Cut-through: 一旦接收到帧的目的地址，就开始转发
- 优点是延迟非常小
- 缺点是可能转发错误帧、不支持非对称交换
无碎片模式，Fragment-free: 接收到帧的前 64 字节后，才开始转发
- 优点是过滤了冲突碎片，延迟和转发错帧介于存储转发和直通交换之间
- 缺点是仍可能转发错误帧、不支持非对称交换

原先为了实现可靠传输，数据链路层曾使用冗余环状拓扑，但这种物理环路会造成以下几种问题：

广播风暴重复帧MAC 地址表不稳定

生成树协议 Spanning Tree Protocol 的目的是维护一个无环路的网络，当交换机发现一个拓扑环路时，它会自动在逻辑上阻塞一个或多个冗余端口，从而获得无环路拓扑。

原先物理环路中的交换机通过收发桥协议数据单元 BPDU，选举产生根桥 Root Bridge、根端口 Root Port、指定端口 Designated Port，形成生成树：

<1> 选举根桥
- 同一广播域中的所有交换机都参与选举
- 桥 ID 最小的网桥成为生成树的根，其它的均为非根桥
  - 这里桥 ID 首先考虑优先级，再考虑 MAC 地址
- 根桥的所有端口都处于转发状态，可以接收和发送数据帧
<2> 选举根端口
- 每个非根桥比较其每个端口到根桥的路径开销，选出最小开销的端口为根端口
  - 如果多个端口开销相同，则选端口 ID 最小的端口
  - 根路径开销为到根桥上所有端口开销之和，具体的开销值受端口的速率值影响
- 非根桥只有一个根端口，根端口处于转发状态
<3> 为每个网段确定一个指定端口
- 对于每个网段，在所有连接到它的交换机端口中选择一个最小根路径开销的端口作为指定端口
- 指定端口处于转发状态，负责该网段的数据转发
- 连接该网段的其它端口，如果既不是指定端口，也不是根端口，则被阻塞

判断题：根桥的所有连接端口都是指定端口

✔，因为根桥连接的所有网段中，都是根桥的连接端口具有最小根路径开销（即 0）。

当物理拓扑中某个交换机或者某个链路故障时，我们需要重新构造生成树。为了加快重新构建生成树的步骤，我们有了 STP 的优化版 Rapid Spanning Tree Protocol。

局域网¶

局域网 Local Area Network，LAN 指在一个较小地理范围内，将各种计算机、外部设备和数据库系统等通过双绞线、同轴电缆等介质互相连接起来，组成资源和信息共享的计算机互联网络。

	广域网	局域网
覆盖范围	较大	较小
连接方式	点对点	广播
OSI 参考模型层次	物理层+数据链路层+网络层	物理层+数据链路层

局域网的特性主要由拓扑结构、传输介质、介质访问控制方式来决定。

有线局域网¶

以太网是目前最流行的有线局域网技术，它的逻辑拓扑是总线形结构，物理拓扑是星形结构。以太网采用两项措施来简化通信：

<1> 采用无连接工作方式，既不对发送的数据帧编号，又不要求接收方发送确认，即以太网尽最大努力交付数据，提供的是不可靠服务
- 对差错的纠正由高层完成
<2> 发送的数据采用曼彻斯特编码，每个码元中间出现一次电压转换，接收方可以方便进行位同步

以太网常用的传输介质有四种，分别对应标准名称为：

标准名称	10BASE5	10BASE2	10BASE-T	10BASE-F
传输介质	同轴电缆（粗）	同轴电缆（细）	非屏蔽双绞线	光纤
拓扑结构	总线形	总线形	星形	点对点
				工作在全双工状态，不使用 CSMA/CD 协议

前缀 10 表示传输速率为 10Mbps，后缀 T 表示双绞线，F 表示光纤

CSMA/CD 协议设计的初衷是为了解决共享信道的冲突问题，而一条光纤线中起码具有收发两条光纤，即工作在全双工模式下。而全双工中发送和接收互不干扰，因此可以不使用 CSMA/CD。

事实上，对于使用其它传输介质的以太网标准，如果它们采用以太网交换机全双工连接方式，那么它们也可以不再使用 CSMA/CD。

CSMA/CD 的使用与否是自协商自动确定的

如果双方都支持 Full-Duplex，则达成共识“关闭 CSMA/CD 逻辑单元”
如果其中一方被迫工作在 Half-Duplex，则重新激活 CSMA/CD

Virtual LAN 技术可将一个较大的局域网分割成一些较小的，与地理位置无关的逻辑 VLAN，通过软件方式实现逻辑分组与管理。

同一 VLAN 的主机不一定连接到相同局域网，它们可以连接到相同的交换机，也可以连接到不同的交换机，只要这些交换机互连即可。

不同 VLAN 的计算机之间不能直接二层通信

属于同一 VLAN 的主机无论是否连接到同一交换机上，都能相互通信
属于不同 VLAN 的主机即便连接到同一交换机上，也不能直接在数据链路层进行通信

一个以太网是一个广播域，通过 VLAN，将一个较大局域网分割成一些较小的广播域

基于端口的 VLAN基于 MAC 地址的 VLAN基于协议的 VLAN基于子网（或 IP）的 VLAN

是最简单、最有效的 VLAN 划分方法，它按照设备端口来定义 VLAN 成员，将指定端口加入到指定 VLAN 中。该端口可以转发指定 VLAN 的数据帧：

基于 MAC 地址的 VLAN 中，当用户物理位置移动时（从原端口移动到另一个端口），不需要重新配置 VLAN Table：

根据端口接收到的数据包所属的协议类型来给数据报分配不同的 VLAN ID：

根据数据包源IP地址及子网掩码作为依据来进行划分的，设备从端口接收到数据包后，根据源IP地址，找到与现有VLAN的对应关系：

Trunk 端口用于交换机之间的连接，允许多个 VLAN 通过，从而实现跨交换机的 VLAN 实现：

VLAN 对以太网帧进行了扩展，它在源地址字段和类型字段之间插入了一个 4B 大小的 VLAN 标签，用以指明该帧的计算机属于哪个虚拟局域网。该扩展帧被称为 802.1Q 帧。

由于插入了 4B 标签，以太网帧的数据字段最小长度由 46B 变为了 42B，最长仍然是 1500B；而以太网帧整体的最大帧长由 1518B 变为了 1522B，最小仍然是 64B。

802.1Q 帧一般不由用户主机处理，而是由以太网交互机来处理：

当交换机收到一个在本交换机管理的 VLAN 中传递的帧时，不进行任何处理，而是像普通以太网那样直接转发帧
当交换机收到一个要发给不同 VLAN 的帧时，在转发前插入 VLAN 标签，告知别的交换机将该帧转发到哪个 VLAN
- 路径上最后一个交换机向目的主机交付帧时，将删除已插入的 VLAN 标签，因此用户主机收到的是标准以太网帧，而链路上传递的是 802.1Q 帧

存在更加复杂的情况，此处暂且不议（例如同一交换机连接的不同的 VLAN）

无线局域网¶

无线局域网指以无线信道作为传输介质的计算机局域网，可分为有固定基础设施的无线局域网和无固定基础设施的移动自组织网络。

无固定基础设施的无线局域网称为自组网络(ad hoc network)，是由一些平等状态的移动站相互通信组成的临时网络，各节点都具有路由器转发功能。

而对于有固定基础设施的无线局域网，IEEE 指定了 802.11 系列协议标准，包括 802.11a/b/h/n 等。802.11 标准使用星形拓扑，其中心为接入点(Access Point, AP)，在 MAC 子层使用 CSMA/CA 协议。

使用 802.11 系列协议的局域网也叫做 Wi-Fi

一个基本服务集(Basic Service Set, BSS)包括一个 AP 和若干移动站，是构成无线局域网的最小构件。各站在本 BSS 内通信或与外部站通信，都必须通过本 BSS 的 AP。

BSS 可以通过 AP 连接到 Distribution System, DS 上，然后再连接到另一个基本服务集，构成一个拓展的服务集（Extended Service Set, ESS）。

由于无线信道的高误码率、共享性，IEEE 802.11 采用停等协议逐帧确认，而不采用滑动窗口协议。

因为无线局域网不能在发送数据的同时检测信道上有无冲突，在 MAC 层上，802.11 标准广泛应用了 CSMA/CA 协议，它对 CSMA/CD 协议进行修改，从冲突检测变为了冲突避免，因此无线局域网中，一旦开始发送一个帧，在完全发送前就不会停下来，即便发送过程中出现了冲突。

“冲突避免”也并不是完全避免冲突，只是尽可能降低冲突的概率

为了尽量避免冲突，802.11 标准规定，所有站检测到信道空闲后还要等待一段很短时间才能发送帧，这段时间称为 InterFrame Space, IFS：

Short IFS, SIFS 短帧间间隔SIFS是最短的时间区段，用来间隔需要立即响应的帧，如控制帧（RTS/CTS/ACK）等
Point IFS, PIFS 集中协调功能帧间间隔，只能够由工作于 PCF 模式的站点来使用
Distributed IFS, DIFS 分布协调功能帧间间隔，只能够由工作于 DCF 模式的站点来使用
- DCF 是 802.11 的默认方式，必须实现；而 PCF 是可选的

三种帧间间隔时长上 SIFS ＜ PIFS ＜ DIFS

CSMA/CA 只有在“检测到信道空闲且这个数据帧是要发送的第一个数据帧”时，才不使用退避算法。其它所有必须使用退避算法的情况具体如下：

<1> 发送第一个帧前检测到信道忙；
<2> 每次重传
<3> 成功发送一帧后要发送下一帧

与 CSMA/CD 的退避算法不同的是，它的第 \(k\) 次退避会在 \([0,..., (2^{k+2}-1)]\) 个时隙中选择一个，但是到 \(k=6\) 时即达到最大值，对应了最大时隙数为 255（不同于 CSMA/CD 的 1023）。

CSMA/CA 算法归纳

<1> 若站点最初有数据要发送，且信道空闲，则等待时间 DIFS 后发送数据帧
<2> 否则，执行退避算法；
- 检测到信道忙时，退避计时器不减；只有空闲时减
<3> 当退避计时器降为 0 时，信道只可能是空闲的，站点发送数据帧并等待确认
<4> 发送站若收到确认，就可以发送第二帧，此时要先执行 <2> 中的退避算法
- 当然，若超时就要重传对应帧，此时也是要从 <2> 开始执行退避算法

为了避免长帧冲突，802.11 允许实现一个可选机制，即信道预约：

<1> 若源站最初要发送数据，且信道空闲，则等待时间 DIFS 后，广播请求发送控制帧 Request To Send, RTS，它包括源地址、目的地址、这次通信的持续时间
<2> 若 AP 正确收到 RTS 帧，且信道空闲，则等待时间 SIFS 后，广播允许发送控制帧 Clear To Send, CTS，它也包括源地址、目的地址、这次通信的持续时间
- AP 覆盖范围内其它站听到 CTS 帧后，将在 CTS 帧中指明的持续时间内抑制发送
<3> 源站收到 CTS 帧后，等待时间 SIFS 后，即可发送数据帧
<4> 若 AP 正确收到数据帧，则等待时间 SIFS 后就向源站发送确认帧 ACK

通信的持续时间

RTS 帧中，指 AP 收到 RTS 帧后，到目的站发送完 ACK 帧为止的时间
- SIFS + CTS + SIFS + 数据帧 + SIFS + ACK
CTS 帧中，指源站收到 CTS 帧后，到目的站发送完 ACK 帧为止的时间
- SIFS + 数据帧 +SIFS + ACK

802.11 有数据帧、控制帧和管理帧三种，由 MAC 首部、帧主体和帧检验序列 FCS 组成：

802.11 帧中首部共有四个地址字段，根据帧控制字段中的“去往 DS”和“来自 DS”位的不同，它们拥有不同的含义：

记忆时，只需要知道地址 1 是“物理接收者”，地址 2 是“物理发送者”，而地址 3 是没用到的那个地址即可。

Example

QuestionAnswer

主机 A 向主机 B 发送数据，在 MAC 帧从 AP2 转发到主机 B 的这段链路上，MAC 帧的地址 1、地址 2、地址 3 的值分别为多少？

MAC 帧从 AP 发往主机，因此字段"去往AP"=0，"来自AP"=1。参照上表，我们得到：

地址 1 = \(MAC_B\)
地址 2 = \(BSSID_2\)
地址 3 = \(MAC_A\)

Comments: