六、链路层，《计算机网络》，谢希仁 《计算机网络（自顶向下方法 第7版，James F.Kurose，Keith W.Ross）》

---

一、数据链路层的功能

1.1 数据链路层所处的地位

• 主机H1向主机H2发送数据，路径上经过三个路由器和电话网、局域网以及广域网等多种网络。
• 主机具有体系结构中的各层
• 路由器只需具有体系结构中的网络层、链路层、物理层
• 各设备通过传输媒体进行互联
• 主机将发送数据逐层封装后，通过物理层将构成数据包的各比特转换为电信号，发送到传输媒体，进入路由器后逐层解封装到网络层然后向下逐层封装，并经过物理层将数据包发送到传输媒体。
• 最终到达H2，向上逐层解封装，得到主机H1发送的数据

从数据链路层来看，上述通信是在4段链路上进行的。

• 链路(Link)：就是从一个结点到相邻结点的一段物理线路，而中间没有任何其他的交换结点。
• 数据链路(Data Link)：是指把实现通信协议的硬件和软件加到链路上，就构成了数据链路。
• 数据链路层以帧为单位传输和处理数据。

数据链路层的功能

• 封装成帧

  • 应用层PDU下交给运输层，运输层加上运输层协议首部成为本层PDU下交给网络层，网络层添加网络层协议首部成为本层PDU下交给链路层，链路层对其加上一个帧头一个帧尾，封装成帧
  • 

• 差错检测

  • 传输媒体传输过程中很容易发生比特跳变，接收方如何判断帧在传输过程中发生错误呢？
  • 发送方发送帧之前，基于发送数据和检错算法计算出检错码，并将其封装在帧尾。在接收方根据检错码和检错算法，对比即可知道是否出错。

• 可靠传输

  • 尽管误码是不能完全避免的，但若能实现发送方发送什么，接收方就能收到什么，就称为可靠传输。

• 流量控制

  • 控制发送方发送帧的速率别太快，让接收方“来得及"接受

• 上面举例是使用点对点信道的数据链路层。

• 使用广播信道的数据链路层(共享式局域网)

  • 

  • BDE如何知道数据不是发给他们的。

  • 自然要进行编址

  • 当总线上多合主机同时使用总线来传输帧时，传输信号会发生碰撞，这不可避免。

  • 以太网采用的协调方法是CSMA/CD媒体接入控制协议，也就是载波监听多点接入/碰撞检测。

• 使用点对点链路和链路层交换机的交换式局域网

  • 

• 无线局域网

  • 

• 它们的工作原理又是怎样的呢？

• 上述都是本章要解决的问题

二、封装成帧

2.1 组帧

• 封装成帧是指数据链路层给上层交付的协议数据单元添加帧头和帧尾使之成为帧。

  • 帧头和帧尾中包含有重要的控制信息。

  • 帧头和帧尾的作用之一就是帧定界：如何让接收方确定帧的界限

  • 

  • 那么接收方可以根据一个个帧定界标志来提取出一个个帧

  • 

  • 但并非每一种链路层协议都有帧定界标志，实际上，以太网的数据链路层封装好MAC帧后，将其交付给物理层，物理层在MAC帧前面加上8字节的前导码，然后再将比特流转换成电信号发送。

  • 前导码前7字节为前同步码，作用是使接收方的时钟回步，之后的1字节为帧开始定界符，代表其后就是MAC帧。

  • 以太网还规定了帧间间隔为96比特的发送时间。因此MAC帧不需要帧结束定界符。帧间间隔的其他作用在后面介绍。

  • 

• 透明传输：接收方要能够去除“帧定界”的附加信息，把帧“恢复原貌”

2.2 组帧方法

2.2.1 字符计数法

• 原理：在每个帧开头，用一个定长计数字段表示帧长
• 最大缺点：任何一个计数字段出错，都会导致后续所有帧无法定界

2.2.2 字节填充法

• 思路很简单，在帧头帧尾分别插入控制字符SOH 和 控制字符 EOT
• 数据中可能会有 SOH 和 EOT，那么我们可以将原数据中的SOH 和 EOT 前面加上转义字符
• 原数据中也可能有转义字符，那么我们可以将原数据中的转义字符前面也加上转义字符

对于数据接收方，遇到SOH，说明一个帧的开始，遇到转移字符，那么说明转义字符后面紧跟的这个字节是数据，那么往前移动两个字节即可。遇到SOT，说明帧末尾。

2.2.3 零比特填充法

用 01111110 作为帧的开始和结束。

但是原数据中可能有 01111110，我们的处理策略：每5个连续的1后面填充一个0，对于接收方，把所有连续5个1后面紧跟的0拿掉即可。

零比特填充法的正确性不难理解。

2.2.4 违规编码法

曼彻斯特编码（IEEE标准）中间必跳变，中间下跳为1，上跳为0。

如果中间不跳变，我们称之为违规曼彻斯特编码。

违规编码法需要和物理层配合，用违规编码来表示帧的开始和结束：

例题

原来的比特流：0111110001111110

填充后：011111000011111010

故选A

• 为了提高帧的传输效率，应当使帧的数据部分的长度尽可能大些。
• 考虑到差错控制等多种因素，每一种数据链路层协议都规定了帧的数据部分的长度上限，即最大传送单元MTU(Maximum Transfer Unit)

三、差错检测

• 实际的通信链路都不是理想的，比特在传输过程中可能会产生差错：1可能会变成0，而0也可能变成1。这称为比特差错。
• 在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率BER(Bit Error Rate)
• 使用差错检测码来检测数据在传输过程中是否产生了比特差错，是数据链路层所要解决的重要问题之一。

比如上面两种帧格式，分别有4、2字节的FCS字段来检验是否出现了误码。

3.1 奇偶校验

在待发送的数据后面添加1位奇偶校验位，使整个数据(包括所添加的校验位在内)中**“1”的个数**为奇数(奇校验)或偶数(偶校验)。

• 如果有奇数个位发生误码，则奇偶性发生变化，可以检查出误码
• 如果有偶数个位发生误码，则奇偶性不发生变化，不能检查出误码(漏检)

3.2 循环冗余校验CRC(Cyclic Redundancy Check)

• 收发双方约定好一个生成多项式G(x)；
• 发送方基于待发送的数据和生成多项式计算出差错检测码(冗余码)，将其添加到待传输数据的后面一起传输；
• 接收方通过生成多项式来计算收到的数据是否产生了误码；

生成多项式

任何一个二进制数都可以表示成一个生成多项式。

直接举例：
$$\begin{array}{rl}& G(x)=x^4+x^2+x+1\\ & 1\ast x^4+0\ast x^3+1\ast x^2+1\ast x+1\\ & 对应10111\end{array}$$

CRC算法要求生成多项式必须包含最低次项。

只得说明的是，这里的除法是模2除，加法不进位，减法不借位，在这种情况下，就相当于异或。

练习

待发送信息101001，生成多项式G(x) = x^3 + x^2 + 1，计算余数

3.3 小结

• 检错码只能检测出帧在传输过程中出现了差错，但并不能定位错误，因此无法纠正错误。
• 要想纠正传输中的差错，可以使用冗余信息更多的纠错码进行前向纠错。但纠错码的开销比较大，在计算机网络中较少使用。
• 循环冗余校验CRC有很好的检错能力**(漏检率非常低)，虽然计算比较复杂，但非常易于用硬件实现**，因此被广泛应用于数据链路层。
• 在计算机网络中通常采用检错重传方式来纠正传输中的差错，或者仅仅是丢弃检测到差错的帧，这取决于数据链路层向其上层提供的是可靠传输服务还是不可靠传输服务。

四、流量控制与可靠传输

4.1 基本概念

• 使用差错检测技术(例如循环冗余校验CRC)，接收方的数据链路层就可检测出帧在传输过程中是否产生了误码(比特错误)。
• 数据链路层向上层提供的服务类型
  • 不可靠传输服务：仅仅丢弃有误码的帧，其他什么也不做:
  • 可靠传输服务：想办法实现发送端发送什么，接收端就收到什么
• 一般情况下，有线链路的误码率比较低，为了减小开销，并不要求数据链路层向上提供可靠传输服务。即使出现了误码，可靠传输的问题由其上层处理。
• 无线链路易受干扰，误码率比较高，因此要求数据链路层必须向上层提供可靠传输服务。

流量控制、可靠传输 两种功能都可以基于滑动窗口机制来实现。

前面传输层介绍过rdt了，所以可靠传输部分相当于回顾了。

4.2 滑动窗口机制

窗口“向前滑动”的条件

由接收方通过**“确认机制"控制发送方的窗口向前滑动，从而实现“流量控制”**

接下来的几种协议我们关注：

• 滑动窗口协议：发送窗口$W_T$，接收窗口$W_R$大小
• 确认机制
• 重传机制
• 帧编号

4.3 停止-等待协议(S-W)

• 滑动窗口机制：发送窗口$W_T$ = 1，接收窗口$W_R$ = 1
• 确认机制
  • 确认帧：ACKi，若接收方收到 i 号帧，且没有检测出“差错”，需要给发送方返回确认帧 ACK_i
• 重传机制
  • 超时重传：若发送方超时未收到ACK_i，则重传i号帧
• 帧编号
  • 仅需要1bit 给帧“编号”
  • 要求： $W_T+W_R\le 2^n$

数据帧：首、尾主要是一些控制信息，如：帧定界信息，校验码，帧类型，帧序号等。

确认帧：确认帧的数据部分很短，甚至可以认为为空。

示例：

正常情况下：

发送方发送数据帧0，接收方差错控制没有问题，那么返回一个确认帧0，窗口向右滑动

发送方发送数据帧1，接收方差错控制没有问题，那么返回一个确认帧1，窗口向右滑动

异常情况：数据帧丢失

发送方发送数据帧0同时启动计时器，若计时器超时，就自动重传

超时重发后，在下一次超时之前，收到了确认帧

异常情况：确认帧丢失

确认帧自然也会丢失

然后发送方自动超时重传，此时在接收方的视角：收到了重复的数据帧

那么接收方会丢弃重复帧并且返回重复帧的ACK

思考：为什么要给帧编号？

答：接收方无法判别重复帧!

由于接受窗口和发送窗口的距离不超过1，因此用 1 bit 表示帧序号 足矣

异常情况：数据帧出错

那么接收方自然不能发送ACK，紧接着发送方会超时重发

4.4 滑动窗口协议：后退N帧协议(GBN)

• 滑动窗口机制：发送窗口$W_T$ > 1，接收窗口$W_R$ = 1
• 确认机制
  • 确认帧：ACKi，若接收方收到 i 号帧，且没有检测出“差错”，需要给发送方返回确认帧 ACK_i
• 重传机制
  • 超时重传：若发送方超时未收到ACK_i，则重传i号帧
• 帧编号
  • 至少需要nbit 给帧“编号”
  • 要求： $W_T+W_R\le 2^n$
• GBN的特殊规则
  • 关于确认帧：接收方可以“累积确认”，即连续收到多个数据帧时，可以仅返回最后一个帧的ACK
  • 关于 超时重传：若发送方超时未收到ACK_i，则重传 i 号帧，及其之后的所有帧

示例

正常情况

接收放正常接收了0、1、2号帧，然后发送ACK2，发送窗口向右滑动，接收窗口向右滑动。

异常情况：数据帧丢失

发送方发送数据帧3、0、1，但是1号丢失

此时1号帧犹豫在接受窗口外，直接丢弃，这会导致发送方超时。

GBN协议下 接收窗口接收到窗口之外帧时，会返回目前已正确接收的最后一个帧的ACK

发送方接收到ACK3后窗口相应右移

Data0超时，然后重置计时器，重传 0号帧以及后续所有帧

异常情况：确认帧丢失

比如下面这种情况，接收方发送ACK2，但是ACK2丢失

发送方重传 0及0以后的所有帧，并重置计时器。此时在接收方的视角来看，收到了一个窗口外的帧，会返回最后一个正确接收帧的ACK

如果不满足 $W_T+W_R\le 2^n$ 会有什么问题？

看下面这个示例：$n=4，W_T=4，W_R=1$

接收方的ACK3丢失了

然后发送方重发0以及0以后的帧，此时接收方因为累计确认了0、1、2、3，此时又收到一个0，则接收方会错误的接收0，此时就出错了。

**GBN的缺点：**如果接收方接收帧的速度很慢，或在道误码率很高高的情况下，可能会导致发送方的发送进度经常需要“后退”，传输效率低下

4.5 滑动窗口协议：选择重传协议(SR)

• 滑动窗口机制：发送窗口$W_T$ > 1，接收窗口$W_R$ > 1
• 确认机制
  • 确认帧：ACKi，若接收方收到 i 号帧，且没有检测出“差错”，需要给发送方返回确认帧 ACK_i
• 重传机制
  • 超时重传：若发送方超时未收到ACK_i，则重传i号帧
• 帧编号
  • 为了支持以上机制正确运行，至少需要nbit 给帧“编号”
  • 要求： $W_T+W_R\le 2^n$
• GBN的特殊规则
  • 否定帧：NAK_i，若接收方收到i号帧，但检测出i号帧有“差错”，需要丢弃该帧，并给发送方返回否认帧 NAK_i
  • 请求重传：若发送方收到NAK_i，则重传 i 号帧
  • 要求：$W_R\le W_T$，即 接受窗口不能大于发送窗口

如果接受窗口大于 发送窗口的大小，在顺利发送接受的正常情况下性能没有被充分利用。

SR运行示例：

正常情况

异常情况：数据帧丢失

发送方数据帧5丢失

接收方正确接收4、6、7，发送、接收窗口可以向右滑动一格

此时帧5的计时器超时，然后重传：

异常情况：数据帧差错而被丢弃

接收方帧5检测出错

发送方接收到NAK，然后重发

异常情况：确认帧丢失

发送方超时重发：

接收方收到重复帧立即返回ACK

4.6 三种协议的信道利用率分析

术语补充：ARQ（自动重传请求）协议：S-W，GBN，SR

连续ARQ协议：GBN和SR

4.6.1 S-W协议的信道利用率

假设：信道的数据传输速率 =1 kbps
数据帧长度 = 4 kb
确认帧长度 = 1 kb
信道单向传播时延 = 7s

理想情况下（没有帧丢失，比特错误等异常情况），信道利用率 = $U=\frac{T_D}{T_D+RTT+T_A}$

有时候，确认帧ACK非常短，那么我们可以忽略TA

那么上面的例子忽略TA后为：4 / （4 + 2 * 7） = 22.2%

例题

x/3000 / （x/3000 + 0.4）= 0.4

x = 800

4.6.2 GBN、SR协议的信道利用率

GBN和SR 都是发送窗口的大小可以大于1，理想情况下因为不用考虑异常情况，所以二者计算方式相同。

理想情况下，信道利用率 = $U=\frac{N{T}_D}{T_D+RTT+T_A}$

分母解释：发送出去 帧0: TD，然后一个RTT，然后一个TA（其实之前传输层的图会更直观些）

例题：

1000 * 1000 * 8 / 100000000 / （1000 * 8 / 100000000 + 0.1）= 80Mbps

例题

N * 8000 * 128k ≥ 0.8 * （8000 * 128k + 0.5）

N ≥ 7.2，即WT≥7.2，而WR≥1，故至少4bit

五、信道划分、介质访问控制

5.1 什么是介质访问控制

介质访问控制(Medium Access Control，MAC)：多个节点共享同一个“总线型”广播信道时，可能发生“信号冲突”。

应该怎么控制各节点对传输介质的访问，才能减少冲突，甚至避免冲突?

5.2 信道划分（电路交换实现方式）

5.2.1 时分复用TDM

一个现实例子：

时分复用(Time Division Multiplexing, TDM)——将时间分为等长的“TDM帧”，每个“TDM帧”又分为等长的m个“时隙”，将m个时隙分配给m对用户(节点)使用。而且，每个帧在一个TDM帧中的位置时不变的。

TDM的缺点：

• 每个节点最多只能分配到信道总带宽的1 / m
• 如果某节点暂不发送数据，会导致被分配的“时隙”闲置，信道利用率低

5.2.2 统计时分复用STDM

统计时分复用(Statistic Time Division Multiplexing，STDM)——又称异步时分复用，在TDM的基础上，动态按序分配时隙。

如上图，A在某段时间获得了所有的信道带宽资源。

STDM的优点：

• 如果需要时，一个节点可以在一段时间内获得所有的信道带宽资源
• 如果某节点暂不发送数据，可以不分配“时隙”，信道利用率更高

5.2.3 频分复用FDM

同样通过生活中的例子，如果多个节点共享一个声音信道，若同时发送声音信号，则会互相干扰。

那么如果分辨出我们想要的声音信号呢？

让声音信号使用不同频率的频带即可。

频分复用(Frequency Division Multiplexing，FDM)是将信道的总频带划分为多个子频带，每个子频带作为一个子信道，每对用户使用一个子信道进行通信。

FDM的优缺点：

• 优点：各节点可同时发送信号；充分利用了信道带宽(Hz)
• 缺点：FDM技术只能用于模拟信号的传输

5.2.4 波分复用WDM

波分复用(Wavelength Division Multiplexing，WDM)——即光的频分复用。

• 根据高中物理选修部分：C = λf，C 代表光速，λ代表波长，f代表频率
• 光的频率和波长负相关
• 因而波分复用本质就是光的频分复用
• 光信号的频带范围(带宽)非常大，因此很适合采用波分复用技术，将一根光纤在逻辑上拆分为多个子信道

5.2.5 码分复用CDM

背景：2G、3G移动网络时代，节点和节点之间的通信常使用CDMA(CodeDivisionMultiple Access)技术

• 底层原理就是码分复用(Code Division Multiplexing，CDM)

码分复用

• 给各节点分配专属“码片序列”
  • “码片序列"包含m个码片(信号值)，可看作“m维向量"(m维向量的分量通常取1或-1)
  • 要求：各节点的“m维向量"必须相互正交
  • Tips：相互通信的各节点知道彼此的“码片序列
• 发送方如何发送数据
  • 节点发出m个信号值与**"码片序列"相同**，表示比特1
  • 节点发出m个信号值与**"码片序列"相反**，表示比特0
• 信号在传输过程中“叠加”
  • 当多个发送方同时发送数据时，信号值会叠加(注：本质是多个 m维向量的加法)
• 接收方如何接收数据
  • 接收方收到的是“叠加"信号，需要从中“分离"出各发送方的数据
  • 叠加信号 与 发送方的码片序列作“规格化内积”
    • 结果为1，表示比特 1
    • 结果为-1，表示比特 0

如下图，节点A、B、C的码片序列已知，A向C发送数据

然后更复杂的情况，A、B同时向C发送数据：

C 分离出 A、B 数据的方式：将接收到的叠加信号 与 各节点的码片序列进行”规格化内积“：

比如 Da = 1 / m * a * (a - b) = 1 / m * a * a = 1，原理显然，因为向量组组内两两正交，我们可以轻易分理处各节点数据。

例题

根据A的码片序列做规格化内积：101

故选B

5.3 随机访问介质访问控制

5.3.1 发展

• 1968年，ALOHA(Additive Links On-line Hawaii Area)协议，夏威夷大学的一群人想要构建一个可以连接夏威夷地区的网络
  • 纯ALOHA
  • 时隙ALOHA
• CSMA协议
  • 1-坚持CSMA
  • 非坚持CSMA
  • p-坚持CSMA
• CSMA/CD 协议，用于早期的有限以太网（总线型）
• CSMA/CA 协议，用于IEEE 802.11 无线局域网（WiFi）

5.3.2 纯ALOHA，时隙ALOHA

纯ALOHA：准备好数据帧，就立刻发送

示例：

• 上图中出现了几次冲突，冲突的节点都会随机等待一段时间后再次重发

时隙ALOHA：同步各站点的时间，将时间划分为一段段等长的时隙(Slot)，规定站点只能在每个时隙开始时才能发送帧，发送一帧的时间必须小于或等于时隙的长度。

示例：

• 上图中还是有可能冲突的，那么冲突后同样也要随机等待一段时间后再次重发

5.3.3 CSMA

CSMA(Carrier sense Multiple Access)协议，即 载波监听多路访问协议

CSMA协议在ALOHA协议基础上提出改进：在发送数据之前，先监听信道是否空闲，只有信道空闲时，才会尝试发送。

• ALOHA协议——一群无礼匹夫的对话，有话就说，完全不管别人是不是在说话
• CSMA协议——一群有礼貌的人的对话，说话前先听听别人是否在说话

5.3.3.1 1-坚持CSMA协议

工作机制：

优点：信道利用率高，信道一旦空闲，就可以被下个节点使用。

缺点：当多个节点都已准备好数据时，一旦信道空闲会有多个节点同时发送数据，冲突概率大。

5.3.3.2 非坚持CSMA 协议

工作机制：

优点：当多个节点都已准备好数据时，如果信道不空闲，则各节点会随机推迟一段时间再尝试监听，从而各节点“错开”发送数据，降低冲突概率。

缺点：信道刚恢复空闲时，可能不会被立即利用，导致信道利用率降低

5.3.3.3 p-坚持CSMA协议

工作机制：

**优点：**属于 1-坚持CSMA、非坚持 CSMA 的折中方案，降低冲突概率的同时，提升信道利用率

5.3.4 CSMA/CD协议

CSMA/CD协议 用于早期有线以太网（总线型）

• 注：现在的有线局域网也是用”以太网“技术，但不一定都是“总线型”
• 如：用同轴电缆连接多个节点组成的有线局域网；用集线器连接多个节点组成的有线局域网

5.3.4.1 协议要点

CSMA：Carrier sense Multiple Access，载波监听多路重发

CD：Collision Detection，冲突检测

• 先听后发，边听边发，冲突停发，随机重发
• 如何随机重发
  • 截断二进制指数退避算法：
  • 随机等待一段时间 = r 倍 争用期，其中 r 是随机数
  • 如果 k <= 10，在 [0, (2^k - 1)] 区间随机取一个整数
  • 如果 k > 10，在 [0, (2^10 - 1)] 区间随机取一个整数
• 特别注意：
  • 第10次冲突，是“随机重发”的分水岭
  • 第16次冲突，直接躺平，放弃传帧，报告上级(网络层)

5.3.4.2 CSMA/CD 协议的“争用期”

争用期 = 2 × 最大单向传播时延（考虑距离最远的两个节点）

• 若争用期内未发生冲突，那么本次传输不可能冲突，因为争用期是最远两个节点的单向传播时延 * 2
• CSMA/CD没有ACK机制，若发送过程中未检测到冲突，就认为帧发送成功

通过一个例子来理解争用期设置的合理性：

A、B、C、D 依次相距 2000m
即A、B两个节点相距最远，6000m
信号的传播速度 = 2 x 10^8m/s，即 200m/us →最大单向传播时延=30us
信道带宽 =10Mbps，即 10b/us

问题1：若A节点往信道上发送数据，最多需要多久可以被其他所有节点“监听”到信号? => 30us

问题2：显然，A节点往信道上发送的数据可能与其他节点发生“冲突”。那么在最极限的情况下从A节点发出数据开始，最多需要多久，A节点一定可以检测到冲突?

A 节点向B发送数据，30us后占领整个信道，此时所有节点都监听到忙碌，不会发送，最极限的情况：29.99999… us 的时候B向A发送了数据，那么 A 要在 2 x 30us = 60us 的时候才会监听到冲突。

冲突碰撞检测示例：

5.3.4.3 CSMA/CD 协议“最短帧长” 限制

最短帧长 = 2 × 最大单向传播时延 × 信道带宽——若收到的帧小于最短帧长，视为无效帧

假设：

A、C、D、B依次相距 2000m，即A、B两个节点相距最远，6000m，信号的传播速度=2x10^8m/s，即 200m/us
=> 最大单向传播时延=30us
信道带宽=10Mbps，即 10b/us

最短帧长 = 2 × 30μs × 10Mbps = 600bit

如果A节点发送的数据帧长度小于 600bit，可能会导致A节点**“误以为”发送过程中没有发生冲突，但实际上已经发生了冲突**

如果实际要发送的数据很少，可“填充”至合法长度后再发送

5.3.4.4 CSMA / CD 协议（接收方）

5.3.4.5 CSMA/CD 协议 “最长帧长” 限制

最长帧长：规定最长帧长可防止某些节点一直占用信道

以太网规定：最短帧长 = 64B，最长帧长 = 1518B

5.3.5 CSMA/CA 协议

CA：Collision Avoidance，冲突避免

什么是AP(Access Point)

AP(Access Point)：接入点，即平时连接的无线WiFi热点

而校园网其实就是 路由器 + n 个交换机 + n*m 个AP，这也是为什么我们在校园的很多地方都能连到校园网。

无线局域网（WiFi）面临的新问题

AP(Access Point)——接入点，也就是你平时连接的无线WiFi热点

注：所有移动站点(A~D)都需要和固定站点AP进行通信

为什么不采用 CSMA/CD 协议?

1. 硬件上很难实现“边听边发，冲突检测”——因为接收信号的强度往往远小于发送信号的强度，且在无线介质上信号强度的动态变化范围很大。

2. 存在“隐蔽站”问题——在无线通信中，并非所有站点都能够听见对方。发送结点处没有冲突并不意味着在接收结点处就没有冲突。

   eg：A和B、C都向AP发送信号，在接受节点处冲突，而A无法监听到B、C的信号，B、C对于A而言就是“隐蔽站”

5.3.5.1 协议要点

• 发送方：先听后发，忙则退避
  • 若信道空闲，间隔DIFS后，再发送帧(一口气发完，发送过程中不用检测冲突)
  • 若信道不空闲，则进行“随机退避”
    • 随机退避原理：
      • 用二进制指数退避算法确定一段随机退避时间(倒计时)
      • 发送方会保持监听信道，只有信道空闲时才"扣除倒计时"，倒计时结束后立即发送帧(此时信道“听起来”一定空闲)
• 接收方：停止等待协议
  • 每收到一个正确数据帧都返回ACK；若发送方超时未收到ACK，则进行“随机退避”

帧间间隔IFS

• DIFS（分布式协调IFS）：最长的IFS——每次“帧事务“开始之前需要等待的时间
• SIFS（Short，短帧间间隔）：最短的IFS——用来分隔开属于一次对话的各帧，收到一个帧后需要预留的一段处理时间（如完成差错控制等）。一个站应当能够在这段时间内从发送方式切换到接收方式。
• PIFS(Point，点协调功能帧间间隔)：中等长度的IFS，是为了在开始使用 PCF 方式时（在 PCF 方式下使用，没有争用）优先获得接入到媒体中。PIFS 的长度是 SIFS 加一个时隙(slot)长度。
• 时间长度：DIFS > PIFS > SIFS

5.3.5.2 无线局域网：CSMA/CA

先不考虑“隐蔽站”问题（无线局域网：CSMA/CA）：

发送方：

1. 如果站点侦测到信道空闲持续DIFS长，则 传输整个帧
2. 如果侦测到信道忙碌，那么 选择一个随机 回退值，并在信道空闲时递减该值；如果 信道忙碌，回退值不会变化。递减到0，发送整个帧。如果没有收到ACK，那么选择随机回退值，重复2。

5.3.5.3 IEEE 802.11 MAC 协议：CSMA/CA

解决“隐蔽站”问题（IEEE 802.11 MAC 协议：CSMA/CA）：

思想：允许发送方“预约”信道，而不是随机访问该信道：避免长数据帧的冲突**（可选项，预约机制可选可不选）**

• 发送方首先使用CSMA向BS发送一个小的RTS控制帧（Request To Send，请求发送）

  • 它包含了源地址、目的地址、和这次通信所需持续时间
  • RTS可能会冲突（但是由于比较短，浪费信道较少）

• AP 通过 BS广播 CTS控制帧(Clear To Send)，作为RTS的响应

  • 它也包含了源地址、目的地址、和这次通信所需持续时间

• CTS能够被所有涉及到的节点听到

  • 发送方发送数据帧
  • 其它节点抑制发送

• 采用小的预约分组，可以完全避免数据帧的冲突

• 因而在IEEE 802.11 中会根据数据帧长度来决定是否启用预约机制，如果很短一般不会启动，因为短数据帧重传代价很小。

例题

显然是D

例题

IFS1是DIFS，是最长的帧间隔，所以选A

其余的 IFS2、3、4都是 SIFS，是比较短的那个。

5.3.5.4 为什么要等待空闲DIFS后才发送数据帧

如果B收到了来自A的数据帧，然后在一个SIFS时间内进行差错控制

此时D节点检测到空闲，如果我们不让其等待 DIFS > SIFS的时间，就会冲突。

以下图为例：

传播时延2ms + SIFS1ms = 3ms < DIFS4ms，规避了我们上面说的情况。

因而我们可以认为在DIFS内没有检测到信号的话，就可以认定是空闲的。

5.4 轮询访问：令牌传递协议

令牌环网技术：IBM公司于 1984 开发的一种局域网技术

• 竞争对手：Xeroc & Intel & DEC（以太网技术，总线型，同轴电缆或者集线器连接）
• 引入以太网交换机后，以太网技术（星型，彻底解决总线争用问题）
• 令牌环网技术被淘汰

核心特点：环形拓扑结构，各节点“轮询访问"道，不会发生信道冲突。

如何实现“介质访问控制”：令牌传递协议

5.4.1 协议要点

令牌帧

• 需指明当前获得令牌的节点编号
• 只有获得令牌(Token)的节点才能往信道上发送数据帧
• 如果获得令牌的节点没有数据要发送，就将令牌传递下一个节点

数据帧

• 需指明数据帧的源地址/目的地址、是否已被接收、获得令牌的节点编号

• 数据帧从源结点发出，"传递一圈"后回到源节点

• 数据帧“传递一圈”的过程中，会被目的节点复制一份数据，并将数据帧标记为"已接收"

• 数据帧回到源结点后，如果发现异常状况，就尝试重发；若无异常，就将令牌传递下一个节点

• 无论是令牌帧还是数据帧，都只能沿单向传递

• 获得令牌的节点，每次只能发一帧，发完就释放令牌

• 需要用专门的网络设备(MAU)实现集中控制

• 令牌传递协议很适用于负载高的网络(不会发生冲突，效率高)

数据帧示例：

1号主机向3发送数据帧，携带了源地址，目的地址，数据部分，已接受标志位

到达2号主机后，2号主机发现不是自己，所以传递给下一个主机，即主机3

主机3 检查发现是自己，复制数据，然后标记数据帧为已接收，然后继续传递数据帧

主机1拿到数据帧后进行检查，发现没有异常就不进行重发了。

令牌帧示例：

1号节点拿到令牌帧，但是没有发送需求，所以将令牌号+1，传递给下一个节点

2号节点同理……

5.4.2 令牌帧、数据帧

5.4.3 MAU——令牌环网的集中控制站

将多个主机接入MAU(Multisation Access Units，多站接入单元)组成一个“令牌环网”。

我们也可以通过多台MAU构建更大的令牌环网

六、MAC地址、IP地址以及ARP协议

• MAC地址是以太网的MAC子层所使用的地址；
• IP地址是TCP/IP体系结构网际层所使用的地址；
• ARP(Address Resolution Protocols)协议属于TCP/IP体系结构的网际层，其作用是已知设备所分配到的IP地址，使用ARP协议可以通过该IP地址获取到设备的MAC地址；
• 尽管IP地址和ARP协议属于TCP/IP体系结构的网际层(而不属于数据链路层)，但是它们与MAC地址存在一定的关系，并且我们日常的网络应用都离不开MAC地址、IP地址以及ARP协议。因此，我们将这三者放在一起讨论。

6.1 MAC地址

• 当多个主机连接在同一个广播信道上，要想实现两个主机之间的通信，则每个主机都必须有一个唯一的标识，即一个数据链路层地址;
• 在每个主机发送的帧中必须携带标识发送主机和接收主机的地址。由于这类地址是用于媒体接入控制
• MAC(Media Access Control)，因此这类地址被称为MAC地址;
  • MAC地址一般被固化在网卡(网络适配器)的电可擦可编程只读存储器EEPROM中，因此MAC地址也被称为硬件地址;
  • MAC地址有时也被称为物理地址。请注意：这并不意味着MAC地址属于网络体系结构中的物理层!
• 一般情况下，用户主机会包含两个网络适配器：有线局域网适配器(有线网卡)和无线局域网适配器(无线网卡)。每个网络适配器都有一个全球唯一的MAC地址。而交换机和路由器往往拥有更多的网络接口，所以会拥有更多的MAC地址。综上所述，严格来说，MAC地址是对网络上各接口的唯一标识，而不是对网络上各设备的唯一标识。

例题

MAC地址有时也被称为物理地址，故选C

IEEE 802局域网的MAC地址格式

• 以太网MAC地址6个字节
• 前三个字节：组织唯一标识符OUI，由IEEE的注册管理机构分配
• 后三个字节：网络接口标识符，由获得OUI的厂商自行随意分配
• 地址标识符称为扩展的唯一标识待EUI，对于48bit的MAC地址可称为EUI-48

标准表示法：每4个比特组成一个16进制数，每两个十六进制数组成一个字符，共6个字符，记为

XX-XX-XX-XX-XX-XX（Windows表示方法），例如：00-0C-CF-93-8C-92

其他表示法：XX:XX:XX:XX:XX:XX（Linux，IOS，Android），例如：00:0C:CF:93:8C:92

XX.XX.XX.XX.XX.XX（Packet Tracer），例如：000C.CF93.8C92

最高字节的第0、1位分别标记了单/多播 和 全球/本地管理

单播MAC地址举例

主机B以自己MAC地址为源MAC地址，主机CMAC地址为目标MAC地址发送单播帧

广播MAC地址举例

B以广播MAC地址为目标MAC地址发送广播帧，被主机A、C接收

多播MAC地址举例

因为最高字节的最低位为1说明是多播地址，所以只要第一个字节为奇数就说明一个MAC地址为多播地址

A发送多播帧，B、C因为在各自多播组列表中找到了该MAC地址，所以接受，D丢弃

拓展：随机MAC地址：

斯诺登爆料：美国国家安全局拥有一套系统，通过监听电子设备MAC地址来跟踪城市中每个人的行动。

因此，苹果率先在IOS设备中扫描网络时采用随机MAC地址技术，随后Windows10、Android6.0和内核版本3.18的Linux系统都开始提供随机MAC地址功能。

6.2 IP地址

• IP地址是因特网(Internet)上的主机和路由器所使用的地址，用于标识两部分信息：
  • 网络编号：标识因特网上数以百万计的网络
  • 主机编号：标识同一网络上不同主机(或路由器各接口)
• 很显然，之前介绍的MAC地址不具备区分不同网络的功能。
  • 如果只是一个单独的网络，不接入因特网，可以只使用MAC地址(这不是一般用户的应用方式)。
  • 如果主机所在的网络要接入因特网，则IP地址和MAC地址都需要使用。

数据包转发过程中IP地址与MAC地址的变化情况

• 数据包转发过程中源IP地址和目的IP地址保持不变
• 数据包转发过程中源MAC地址和目的MAC地址逐个链路(或逐个网络)改变
  • 网络层数据报中蕴含了源IP，目标IP，下交链路层
  • 链路层进行转发的过程中，向上解封装，查路由表，知道下一跳IP地址，知道往哪跳
  • 但是不知道对应MAC地址，如何根据IP地址找出对应MAC地址呢？（接下来的ARP协议会解决）

例题

H1要发给R，故H1发出的帧的目的MAC为R的相应接受接口MAC

R要发给H2，故H2发出帧的源MAC为R的相应发送接口的MAC地址

故选D

6.3 ARP协议

这一p 内容 参考的大黑书

MAC地址和ARP

• 32bitIP地址:
  • 网络层地址
  • 前n-1跳：用于使数据报到达目的IP子网
  • 最后一跳：到达子网中的目标节点
• LAN（MAC/物理/以太网）地址:
  • 用于使帧从一个网卡传递到与其物理连接的另一个网卡 (在同一个物理网络中)
  • 48bit MAC地址固化在适配器的ROM，有时也可以通过软件设定
  • 理论上全球任何2个网卡的MAC地址都不相同
  • e.g.: 1A-2F-BB-76-09-AD

6.3.1 网络地址和MAC地址分离

• IP地址和MAC地址的作用不同
  • a) IP地址是分层的
    • 一个子网所有站点网络号一致，路由聚集，减少路由表
      • 需要一个网络中的站点地址网络号一致，如果捆绑 需要定制网卡非常麻烦
    • 希望网络层地址是配置的；IP地址完成网络到网络的 交付
  • b) mac地址是一个平面的
    • 网卡在生产时不知道被用于哪个网络，因此给网卡一个 唯一的标示，用于区分一个网络内部不同的网卡即可
    • 可以完成一个物理网络内部的节点到节点的数据交付

分离好处

• 网卡坏了，ip不变，可以捆绑到另外一个网卡的 mac上
• 物理网络还可以除IP之外支持其他网络层协议， 链路协议为任意上层网络协议， 如IPX等

MAC地址如果和IP捆绑会产生的问题

• 如果仅仅使用IP地址，不用mac地址，那么它仅支持IP协议
• 每次上电都要重新写入网卡 IP地址；
• 另外一个选择就是不使用任何地址；不用MAC地址，则每到来一个帧都要上传到IP层次，由它判断是不是需要接受，干扰一次

6.3.2 LAN地址和ARP

局域网上每个适配器都有一个唯一的LAN地址

• 前面已经介绍了广播MAC地址为6个字节全1

• MAC地址由IEEE管理和分配
• 制造商购入MAC地址空间（保证唯一性）
• 类比:
  • (a)MAC地址：社会安全号
  • (b)IP地址：通讯地址
• MAC平面地址 ➜ 支持移动
  • 可以将网卡到接到其它网络
• IP地址有层次——不能移动
  • 依赖于节点连接的IP子网，与子网的网络号相同（ 有与其相连的子网相同的网络前缀）

6.3.3 ARP：Address Resolution Protocol

ARP（Address Resolution Protocol）：地址解析协议

我们前面的问题是：已知P地址，如何得知MAC地址？

如上图，已知B的IP地址，如何确定B的MAC地址？

• 在LAN上的每个IP节 点都有一个ARP表
  • ARP表：包括一些 LAN节点IP/MAC地址的映射
    • < IP address; MAC address; TTL>
    • TTL时间是指地址映射失效 的时间
    • 典型是20min

这样，我们再看前面帧传播的过程中，如何拿到下一个节点的MAC地址：

发送数据报：由A通过R到B， 假设A知道B的IP地址

• 在R上有两个ARP表，分别对应两个LAN
• 在源主机的路由表中，发现到目标主机的下一跳时111.111.111.110
• 在源主机的ARP表中，发现其MAC地址是E6-E9-00-17-BB-4B, etc

过程：

• A创建数据报，源IP地址：A；目标IP地址：B
• A创建一个链路层的帧，目标MAC地址是R，该帧包含A 到B的IP数据报

• 帧从A发送到R
• 帧被R接收到，从中提取出IP分组，向上解封装交给上层IP协议实体
• R转发数据报，数据报源IP地址为A，目标IP地址为B
• R创建一个链路层的帧，目标MAC地址为B，帧中包含 A 到B的IP 数据报

ARP 表如何建立？——广播帧

七、LANS

7.1 集线器与交换机

• 早期的总线型以太网

  • 最初用细同轴电缆连接节点
  • 后来改进为细同轴电缆，但是这种使用无源电缆和大量机械接头

• 使用双绞线和集线器HUB的星型以太网

  • 

  • 使用集线器的以太网在逻辑上仍是一个总线网，各站共享总线资源，使用的还是CSMA/CD协议;

  • 集线器只工作在物理层，它的每个接口仅简单地转发比特，不进行碰撞检测(由各站的网卡检测);

  • 集线器一般都有少量的容错能力和网络管理功能。例如，若网络中某个网卡出了故障，不停地发送帧。此时，集线器可以检测到这个问题，在内部断开与出故障网卡的连线，使整个以太网仍然能正常工作。

使用集线器HUB在物理层扩展以太网

Hubs 本质上是物理层的中继器

• 从一个端口收，转发到所有其他端口
• 速率一致
• 没有帧的缓存
• 在hub端口上没有CSMA/CD机制：适配器检测冲突
• 提供网络管理功能

物理层介绍过一个集线器HUB可以接入多台主机设备组成一个碰撞域（冲突域），一个集线器又可以接入多个HUB形成一个更大的碰撞域（冲突域）

以太网交换机

• 交换机是一种多接口网桥（网桥见后面的生成树部分）
• 交换机从某一节点收到一个帧后，立即在其内存中的地址表（端口号－MAC地址）进行查找，以确认该目的MAC的网卡连接在哪一个节点上，然后将该帧转发至该节点。
• 每个端口有各自的带宽，各端口之间并行工作，可以提高网络吞吐量。
• 交换机也被称为**“二层交换机“**（因为工作在物理层和链路层）

• 以太网交换机通常都有多个接口。每个接口都可以直接与一台主机或另一个以太网交换机相连。一般都工作在全双工方式。
• 以太网交换机具有并行性，能同时连通多对接口，使多对主机能同时通信，无碰撞(不使用CSMA/CD协议)
• 以太网交换机一般都具有多种速率的接口，例如：10Mb/s、100Mb/s、1Gb/s、10Gb/s接口的多种组合。
• 以太网交换机工作在数据链路层(也包括物理层)，它收到帧后，在帧交换表中查找帧的目的MAC地址所对应的接口号，然后通过该接口转发帧。
• 以太网交换机是一种即插即用设备，其内部的帧交换表是通过自学习算法自动地逐渐建立起来的。
• 帧的两种转发方式：
  • 存储转发
  • **直通交换：**采用基于硬件的交叉矩阵(交换时延非常小，速度快，但不检查帧是否右差错)

对比集线器和交换机

下面举例均假设：

• 忽略ARP过程
• 假设交换机的帧交换表已经“学习好了”

单播：

集线器下，单播帧通过总线传播到其他各主机中的网卡，根据帧的目的MAC地址决定是否接收。

交换机SWITCH下，帧到达交换机后，根据目的MAC地址和帧交换表，直接转发给目的主机。

广播：

集线器下，广播帧通过总线传播到其他各主机中的网卡，检测到目的MAC地址是广播地址，所以接收。

交换机SWITCH下，帧到达交换机后，检测到目的MAC地址是广播地址，所以发送给除了发送方的所有其他主机。

多台主机同时单播

HUB下，发生碰撞

SWITCH下，因为是存储转发，所以会暂存，不会碰撞。

扩展以太网发送单播帧

孰优孰劣显然

效果上来看一样。

产生碰撞的例子

HUB下碰撞，但是SWITCH下不碰撞

小结

7.2 以太网交换机自学习和转发帧

• 以太网交换机工作在数据链路层(也包括物理层)
• 以太网交换机收到帧后，在帧交换表中查找帧的目的MAC地址所对应的接口号，然后通过该接口转发帧
• 以太网交换机是一种即插即用设备，刚上电启动时其内部的帧交换表是空的。随着网络中各主机间的通信，以太网交换机通过自学习算法自动逐渐建立起帧交换表。
  • 帧交换表存储：<MAC addr，interface，TTL>，TTL即表项可以存活的时间。
  • 设置TTL：因为MAC地址与交换机接口的对应关系并不是永久性的!

自学习过程示例：（假设已经建立了ARP）

• 最初SWITCH1和SWITCH2帧交换表都空
• A向B发送帧，进入SWITCH1，写入A的MAC地址和SWITCH1接入端口1
• 查找BMAC无果，盲目泛洪、SWITCH2、B、C、E、F都会收到该帧，只有B接收成功，进入SWITCH2时写入A的MAC地址和对应的SWITCH2的2号接入端口
• B->A、E->A的过程类似

丢弃帧示例：（A和G间HUB没有画出）

G->A发送帧，通过集线器交给了A，但是集线器也会转发给SWITCH1，SWITCH1查帧交换表发现从1号端口进来的发送给1号端口下的设备，选择丢弃掉该帧。

例题

可以自己在纸上画一下

例题

A

链路层的PDU为帧，我们要转发，自然是要根据目的MAC来查

例题

第一次没有找到00-e1-d5-00-23-c1，所以进行盲目泛洪，所以是{2, 3}

第二次因为查表查到了，所以是{1}

故选B

7.3 以太网交换机的生成树协议STP

• 如何提高以太网的可靠性？
• 添加冗余链路可以提高以太网的可靠性
• 但是，冗余链路也会带来负面效应——形成网络环路
• 网络环路会带来以下问题：

  • 广播风暴

    • 一个广播帧在网络间反复的转发，下图H1发送一个广播帧在网络间反复转发
    • 

  • 主机收到重复的广播帧

    • 大量消耗主机资源

  • 交换机的帧交换表震荡(漂移)

    • 因为H1发出的帧反复进入SWITCH3，然后关于H1的表项反复修改为错误信息
    • 

以太网交换机使用生成树协议STP(Spanning Tree Protocol)，可以在增加冗余链路来提高网络可靠性的同时又避免网络环路带来的各种问题。

• 不论交换机之间采用怎样的物理连接，交换机都能够自动计算并构建一个逻辑上没有环路的网络，其逻辑拓扑结构必须是树型的(无逻辑环路)；
• 最终生成的树型逻辑拓扑要确保连通整个网络
• 当首次连接交换机或网络物理拓扑发生变化时(有可能是人为改变或故障)，交换机都将进行生成树的重新计算。

提到生成树协议STP，不得不提一下网桥的概念（网桥的概念很多教材已经废除，拿入了《深入理解计算机网络》课程中）

• 网桥(bridge)工作在数据链路层(包含其下的物理层)，因此网桥具备属于数据链路层范畴的相关能力。
  • 网桥可以识别帧的结构。
    • 网桥可以根据帧首部中的目的MAC地址和网桥自身的帧转发表来转发或丢弃所收到的帧。
• 网桥的接口数量很少，通常只有2~4个，一般只用来连接不同的网段。
• 交换机是多接口的网桥
• 网桥分为
  • 固定路由网桥
    • 帧转发表是固定的，手工配置
  • 透明网桥
    • 帧转发表是自学习的
  • 源路由网桥

透明网桥的自学习过程和 交换机一模一样，只不过网桥的接口比较少罢了，这里略。

• 前面提到，环路中由于广播风暴、重复的广播帧、帧交换表震荡等因素，我们需要使用生成树协议STP，这里着重介绍
• 交换机也是用生成树STP协议，一模一样

相关名词

• BPDU：STP的数据单元，在网桥局域网内传递信息。
• 根网桥：具有最小网桥ID的网桥被选作根网桥，网桥ID应为唯一的。
• 根端口：在指定网桥上面，到根网桥路径花费最小的端口为根端口
  • 如果指定网桥上面有几个端口，到根网桥路径花费一样小，那么选择端口id 最小的端口为根端口。
• 指定网桥：到根网桥路径花费最少的那个网桥为指定网桥
  • 如果有几个网桥到到根网桥路径花费一样，那么比较网桥id，id最小的被选作为指定网桥。
• 指定端口：指定网桥上面和局域网相连的端口叫做指定端口
  • 如果指定网桥上面有几个端口同时和局域网相连，那么选择端口id 最小的端口为所在局域网的指定端口。

STP中端口状态

• **禁用(Disabled)**状态
• **阻塞(Blocking)**状态—不转发数据帧，接收BPDU
• **侦听(Listening)**状态—不转发数据帧，侦听BPDU，并进入生成树构造过程
• **学习(Learning)**状态—不转发数据帧，学习地址
• **转发(Forwarding)**状态—转发数据帧，学习地址

状态机：

生成树算法描述（和数据结构中的 prim 算法很像）

• 首先选择一个网桥作为根网桥。根网桥是具有最小ID的那个网桥，根网桥是生成树的根节点。
  • 根网桥的选择是通过发送网桥协议数据单元BPDU—这样的特殊帧来完成的。每个网桥协议数据单元包含一个网桥的ID，帧首次被发送时的端口ID和接收该帧的端口的累计费用。
• 网桥开始时假定它自己是根网桥，向它的所有端口发送配置信息，把自己的ID作为根网桥和发送网桥，费用设为0。
• 当一个网桥接收到一个BPDU时，它将源网桥的ID和自己的ID比较，若自己的ID大，自己就不是根网桥。它记录下源网桥的ID和源网桥到达自己这儿路经费用，将路经费用加上接收端口的费用，然后通过所有的其它端口转发这个BPDU。
• **每个网桥确定其根端口，**确定依据：
  • 到根网桥的最低路径成本。
    • 一条链路的带宽越大，它的传输成本就越低。
  • 网桥ID最小
  • 端口ID最小
• 为每个局域网指定一个网桥，依据是：
  • 根路径成本较低
  • 所在的网桥ID值最小
  • 端口ID值最小

省流就是：选最小ID为根网桥，然后每个LAN选和自己相连到根最近的那个网桥为指定网桥，其余网桥断开，在指定网桥上选到根最近，ID最小那个端口为根端口，指定网桥和LAN的接入端口为指定端口，最后一定会得到一个树形结构，因为按照到根的代价选择指定网桥，隐含了指定网桥到根是可达的，保证最后会得到一棵树。

示例：

7.4 局域网与IEEE 802

IEEE 802 委员会：推进局域网技术的标准化工作。

• 某些科技公司出于商业目的开发局域网技术，某种局域网技术受到市场和技术专家的认可。

• 802.8工作组(已解散)：FDDI 光线分布数字接口

• 802.5工作组(已解散)：令牌环网技术（IBM）

• 802.3工作组：以太网技术（DEC、Intel、Xerox）

• 802.11工作组：Wi-Fi技术（AT&T、Nokia等）

• 802.3 局域网技术就是在说 以太网技术

• 802.11 局域网技术就是在说Wi-Fi 技术，有时也会加后缀：

• 

• 比如我们进入路由器管理后台界面，模式那里指明了支持的Wi-Fi技术

IEEE802 显然是负责物理层和链路层，他们将链路层又进行了细分：

• 

• 链路层细分为：

  • 逻辑链路控制子层(LLC子层，Logical Link Control)：与访问传输介质无关的部分功能，由 IEEE 802.2 工作组(已解散)负责
    • LLC子层的存在是为了兼容各种局域网技术(LLC子层目前已名存实亡)
      有线局域网已被 802.3 垄断
      无线局域网技术已被 802.11 垄断
  • 介质访问控制子层(MAC子层，Medium Access Control)：与访问传输介质有关的部分功能(如:组帧、差错检测、透明传输、介质访问控制等

7.5 以太网

• 目前最主流的LAN技术：**98%**占有率
• 廉价：30元RMB 100Mbps！
• 最早广泛应用的LAN技术
• 比令牌网和ATM网络简单、廉价
• 带宽不断提升：10M, 100M, 1G, 10G

• Metcalfe 在餐巾纸上画的以太网的架构
• 收发器连接着同轴电缆，同轴电缆也连接了一些网卡，网卡在主机上

7.5.1 物理拓扑

从总线型到星型

• 总线：在上个世纪90年代中期很流行
  • 所有节点在一个碰撞域内，一次只允许一个节点发送
  • 可靠性差，如果介质破损，截面形成信号的反射，发送节点误认为是冲突，总是冲突
• 星型：目前最主流
  • 连接选择：hub 或者 switch
  • 现在一般是交换机在中心
  • 每个节点以及相连的交换机端口使用（独立的）以太网协议（不会 和其他节点的发送产生碰撞）

7.5.2 以太网帧结构

发送方适配器在以太网帧中封装IP数据报：或其他网络层协议数据单元。

前导码：

• 7字节的 10101010 + 1字节的 10101011

• 用来同步接收方和发送方的时钟速率

  • 使得接收方将自己的时钟调到发送端的时钟
  • 从而可以按照发送端的时钟来接收所发送的帧

• 地址： 6字节源MAC地址，6字节目标MAC地址

  • 如：帧目标地址=本站MAC地址，或是广播地址， 接收，递交帧中的数据到网络层
  • 否则，适配器忽略该帧

• 类型：指出高层协议(大多情况下是IP，但也支持其它网络层协议Novell IPX和AppleTalk)

• CRC：在接收方校验

  • 如果没有通过校验，丢弃错误帧

7.5.3 无连接、不可靠的服务

• 无连接：帧传输前，发送方和接收方之间没有握手
• 不可靠：接收方适配器不发送ACKs或NAKS给发送方
  • 递交给网络层的数据报流可能有gap
  • 如上层使用像传输层TCP协议这样的rdt，gap会被补上(源主机，TCP实体)
  • 否则，应用层就会看到gap
• 以太网的MAC协议：采用二进制退避的CSMA/CD介质访问控制形式

7.5.4 802.3 以太网标准：链路和物理层

• 很多不同的以太网标准
  • 相同的MAC协议（介质访问控制）和帧结构
  • 不同的速率：2 Mbps、10 Mbps 、100 Mbps 、 1Gbps 、 10G bps
  • 不同的物理层标准
  • 不同的物理层媒介：光纤，同轴电缆和双绞线

7.5.5 以太网 CSMA/CD 算法

• 没有时隙
• NIC如果侦听到其它NIC在发送就不发送：载波侦听 carrier sense
• 发送时，适配器当侦听到其它适配器在发送就放弃对当前帧的发送，冲突检测collision detection
• 冲突后尝试重传，重传前适配器等待一个随机时间，随机访问random access

1. 适配器获取数据报，创建帧

2. 发送前：侦听信道CS

   1. **闲：**开始传送帧
   2. **忙：**一直等到闲再发送

3. 发送过程中，冲突检测CD

   1. 没有冲突：成功
   2. 检测到冲突：放弃，之后尝试重发

4. 发送方适配器检测到冲突， 除放弃外，还发送一个Jam 信号，所有听到冲突的适配器也是如此

   强化冲突：让所有站点都知道冲突

5. 如果放弃，适配器进入指数退避状态

   在第m次失败后，适配器随机选择一个**{0，1，2， ， 2^{m - 1}}中K**，等待K*512位时 ，然后转到步骤2 exponential backoff 二进制指数退避算法

Jam Signal：使其它发送方明确知道发生碰撞，48bits

Bit time：10Mbps以太网 1/10M=0.1μs

对于K= 1023，大约等 50ms：最坏情况 1023 * 512 * 0.1μs=50ms

指数退避：

• 目标：适配器试图适应当前负载，在一个变化的碰撞窗口中随机选择时间点尝试重发
  • 高负载：重传窗口时间大， 减少冲突，但等待时间长
  • 低负载：使得各站点等待时间少，但冲突概率大
• 首次碰撞：在{0，1}选择K ；延迟K*512位时
• 第2次碰撞：在{0，1，2，3}选择K
• 第10次碰撞：在{0，1，2，3，……，1023}选择K

CSMA/CD 的效率

7.5.6 IEEE 802.3 推出的以太网标准(物理层)

7.6.5.1 各种传输介质

高速以太网：速率 > 100Mbps

重点关注：支持全双工or半双工?

同轴电缆只能半双工

双绞线

• 速率 < 2.5Gbps可支持半双工or全双工(节点连接时协商)
• 速率 >= 2.5Gbps仅支持支全双工
• 光纤只支持全双工，上面表格关于这一点有些误会，1Gbps 光纤以太网是全双工

下面是中继器连接的同轴电缆以太网的示意图：

我们发现不同的网段使用了不同的标准。同轴电缆网段仅支持半双工

下面是交换机/集线器连接的双绞线以太网示意图：

• 交换机连接的终端节点都可以全双工
• 集线器连接的节点，仅支持半双工模式
• 上图中交换机和集线器连接部分是半双工模式，也是需要CSMA/CD的

7.5.6.2 4b/5b编码

• 物理层介绍曼彻斯特编码可以看中间跳变来进行时钟同步

• 但是也有比较极端的情况：传送全1/0，那么传了一堆跳变信号过去，接收方提取时钟信号的会变得比较困难，一旦出了一点差错，后面乱完了。

• 所以有了4b/5b编码的思想：用5bit的二进制数来表示4bit二进制数，映射方式如下表所示

• 4位二进制共有16种组合，5位二进制共有32种组合，如何从32种组合种选取16种来使用呢？这里需要满足两个规则：

  • 每个5比特码组中不含多于3个“0”
  • 或者5比特码组中包含不少于2个“1”

• 虽然增加了一些带宽压力，但是保证了每若干bit都有一个跳变，从而保证接收方进行时钟同步。

值得一提的是：千兆以太网

• 采用标准的以太帧格式
• 允许点对点链路和共享广播信道
• 物理编码：8b10b编码（和4b/5b编码类似的思想）
• 在共享模式，继续使用CSMA/CD MAC技术，节点间需要较短距离以提高利用率
• 交换模式：全双工千兆可用于点对点链路
  • 站点使用专用信道，基本不会冲突，效率高
  • 除非发往同一个目标站点
• 10 Gbps now !

7.5.7 两种常见的以太网MAC层标准

V2标准下的 以太网MAC帧

前面已经介绍过了，不过看王道这个图挺详细的所以拿过来了

• 这个MAC帧需要记忆
• 8B前导码
• 6B目的地址，6B源地址，2B类型，N B数据部分（分片的IP数据报或者填充的IP数据报，网络层介绍过，46~1500B，即最短-最长，网络层也介绍过），4B的FCS
• 帧结尾定界采用“违规编码法”，且一个帧传完会留一段间隙

7.5.8 冲突域、广播域

冲突域：如果两个节点同时发送数据，会导致冲突，则二者处于同一个“冲突域”
广播域：如果一个节点发送广播帧，可以被另一个节点接收，则二者处于同一个“广播域”

之前说过这道题，现在可以完整的做了。

4个集线器管理的4个冲突域，交换机隔离了四个冲突域。

而路由器不会转发广播帧，所以它不会合并两个广播域为一个广播域。

7.6 VLAN

一个大型局域网(如校园网)面临的问题

• 局域网内任何一个节点发出的广播帧，都会被广播至所有节点。可能出现“广播风暴”
• 不安全局域网内可能会有一些敏感节点

为了解决上述问题，IEEE 802.1Q工作组提出了VLAN（虚拟局域网）

• 可将一个大型局域网分割成若干个较小的VLAN，每个VLAN是一个广播域

• 需要使用支持VLAN功能的以太网交换机来实现

• 每个VLAN对应一个VID，一个节点只能收到同一个VLAN内节点的广播帧

7.6.1 基于接口

交换机根据VID对应的端口号转发出去。

7.6.2 基于MAC地址

交换机根据VID 对应的MAC地址，知道这个广播帧该发送给哪些目标MAC地址，然后转发出去。

7.6.3 基于IP地址

• 注：这种方式可以让VLAN范围跨越路由器，让多个局域网的主机组成一个VLAN(需要网络层功能支持)
• 比如通过路由器连接多个交换机让多个局域网的主机组成一个VLAN

7.6.4 802.1Q 帧的作用

• 主机与交换机之间，传输标准以太网帧
• 交换机与交换机之间，传输 802.1Q 帧
  • 因为跨越交换机，你得知道哪个VLAN，所以要在标准以太网帧中插入VID，即802.1Q 帧

​ 在标准以太网帧的源地址之后，插入VLAN标签，得到802.1Q 帧

• 标准以太网帧——662N4，收发协数验
• 802.1Q帧——6642N4，收发V协数验

7.7 IEEE 802.11 无线局域网

无线局域网的分类

• 有固定基础设施（如无线路由器）无线局域网

  • 如 802.11无线局域网(WiFi)

• 无固定基础设施移动自组织网络

  • 如：苹果隔空投送(AirDrop)、华为分享(HUAWEI Share) 的多屏协同

    

7.7.1 基本概念

这部分王道的PPT很好，直接拿过来了

一个普通家用路由器的硬件架构

处于同一个扩展服务集ESS内的基本服务集BSS的SSID都是同一个 => Wi-Fi名 相同

7.7.2 802.11帧的分类

• 数据帧
• 控制帧：如 ACK、RTS、CTS帧
• 管理帧：如 探测请求/探测响应帧
  • 说人话：用于发现Wi-Fi

7.7.3 802.11 局域网的数据帧格式

地址1、2、3会因为 帧控制的第9、10bit 改变而改变

当表示去往AP时，代表中起止，即AP MAC地址，起代表源MAC，止代表目标MAC

当表示来自AP时，代表止起中，含义类似

例题

中起止：选B

AP通常具备"帧格式转换"功能。可以将在无线链路上传输的802.11帧格式，与有线链路上传输的以太网帧格式相互转换

7.8 广域网和PPP

广域网(WAN，Wide Area Network)，通常跨接很大的物理范围，所覆盖的范围从几十公里到几千公里，它能连接多个城市或国家，或横跨几个洲并能提供远距离通信，形成国际性的远程网络。

广域网的通信子网主要使用分组交换技术。广域网的通信子网可以利用公用分组交换网、卫星通信网和无线分组交换网，它将分布在不同地区的局域网或计算机系统互连起来，达到资源共享的目的。如因特网(Internet)是世界范围内最大的广域网。

7.8.1 PPP协议

PPP协议的特点

点对点协议PPP(Point-to-Point Protocol)是目前使用最广泛的数据链路层协议，用户使用拨号电话接入因特网时一般都使用PPP协议。

• 只支持全双工链路。

PPP协议应满足的要求

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

PPP协议无需满足的要求

• 纠错
• 流量控制（交给上层）
• 序号
• 不支持多点线路

PPP协议三个组成部分

1. 一个将IP数据报封装到串行链路(同步串行/异步串行)的方法。
2. 链路控制协议LCP：建立并维护数据链路连接。身份验证
3. 网络控制协议NCP：PPP可支持多种网络层协议，每个不同的网络层协议都要一个相应的NCP来配置，为网络层协议建立和配置逻辑连接。

PPP协议状态图

PPP协议帧格式

7.8.2 HDLC协议

高级数据链路控制(High-Level Data Link Control或简称HDLC)，是一个在同步网上传输数据、面向比特的数据链路层协议，它是由国际标准化组织(ISO)根据IBM公司的**SDLC(SynchronousData Link Control)**协议扩展开发而成的.

• 数据报文可透明传输，用于实现透明传输的“0比特插入法”易干硬件实现
• 采用全双工通信
• 所有帧采用CRC检验，对信息帧进行顺序编号，可防止漏收或重份，传输可靠性高。

HDLC的站

主站、从站、复合站

1. 主站的主要功能是发送命令(包括数据信息)帧、接收响应帧，并负责对整个链路的控制系统的初启流程的控制、差错检测或恢复等。

2. 从站的主要功能是接收由主站发来的命令帧，向主站发送响应帧，并且配合主站参与差错恢复等链路

   控制。

3. 复合站的主要功能是既能发送，又能接收命令帧和响应帧，并且负责整个链路的控制。

三种数据操作方式：

1. 正常响应方式
2. 异步平衡方式
3. 异步响应方式

HDLC的帧格式

1. 信息帧(I)第1位为0，用来传输数据信息，或使用捎带技术对数据进行确认;
2. 监督帧(S)10，用于流量控制和差错控制，执行对信息帧的确认、请求重发和请求暂停发送等功能
3. 无编号帧(U)11，用于提供对链路的建立、拆除等多种控制功能。

小结

• HDLC、PPP只支持全双工链路。
• 都可以实现透明传输。
• 都可以实现差错检测，但不纠正差错