第3章 数据链路层

3.1数据链路层的几个共同问题

数据链路层使用的信道主要有以下两种类型:

• 点对点信道。这种信道使用一对一的点对点通信方式，两个结点之间有专属的传输介质，不用抢。
• 广播信道。这种信道使用一对多的广播通信方式，多个结点需争抢传输介质的使用权【总线型拓扑】。

3.1.1 数据链路和帧

(物理)链路(link)： 是从一个节点到相邻节点的一段物理线路(有线或无线)，而中间没有任何其他的交换节点。链路只是一条路径的组成部分
数据/逻辑链路： 是结点间的逻辑通润道。除了物理线路以外，还必须有通信协议来控制这些数据的传输。即把实现这些协议的硬件和软件加【网络适配器】到链路上，就构成数据链路。

数据/逻辑链路 = (物理)链路 +协议

帧: 链路层协议数据单元，封装【网络层的协议数据单元 - IP数据报(或简称为数据报)】。IP数据报作为数据，在其前后分别添加首部和尾部。

数据链路层:

• 负责把网络层交下来的数据构成帧发送到链路上，以及把接收到的帧中的数据取出并上交给网络层。

• 负责通过一条链路从一个结点向物理链路直接相连的相邻结点传送数据报。

3.1.2 三个基本功能

封装成帧、透明传输和差错控制。

• 封装成帧(framing)： 负责将网络层传递下来的数据包（Packet）封装成帧（Frame）【IP数据报封装成帧】
  实际操作：
  就是在一段数据的前后分别添加首部和尾部然后就构成了一个帧。首部和尾部的一个重要作用就是进行帧定界，确定帧的界限 。

  数据部分长度上限–最大传送单元 MTU (Maximum Transfer Unit)

  

• 透明传输

  • 透明传输：
    在数据传输过程中，数据不会被传输路径上的设备或协议修改，确保数据能够按照原样到达目的地

例如：当数据是由可打印的 ASCII 磅组成的文本文件时，帧定界可以使用特殊的帧定界符。

组帧：

• 控制字符 SOH (Start Of Header)放在一帧的最前面，表示帧的首部开始。
• 控制字符 EOT(End Of Transmission)表示帧的结束。
• 只有首部开始符SOH而没有传输结束EOT，必须丢弃

帧定界的错误：

如果数据中的某个字节的二进制代码恰好和SOH或EOT这种控制字符一样，数据链路层就会错误地“找到帧的边界”，把部分帧收下(误认为是个完整的帧)，而把剩下的那部分数据丢弃(这部分找不到定界控制字符SOH)。

帧定界的错误解决办法：

字节填充(byte stuffing)或字符填充(character stuffing)

• 发送端的数据链路层在数据中出现控制字符“SOH“或“EOT”的前面插入一个转义字符“ESC”;
• 接收端的数据链路层在将数据送往网络层之前删除插入的转义字符:
• 如果转义字符也出现在数据当中，那么应在该转义字符前面插入一个转义字符 ESC。当接收端收到连续的两个转义字符时，就删除其中前面的一个

• 差错控制

  • 传输差错可分为两大类:

    • 比特差错：比特在传输过程中可能会产生差错:1可能会变成0，而0也可能变成1。【位错】

    • 帧丢失、帧重复或帧失序【帧错】

  • 传输差错两个解决方案:

    • 接收方发现比特差错后丢弃帧，并通知发送方重传帧 【检错编码】
    • 接收方发现比特差错后，纠正比特错误 【纠错编码】

  • 误码率 BER(Bit Error Rate) 在一段时间内，传输错误的比特占所传输比特总数的比率。提高信噪比就可以使误码率减小

  • 差错检测【检错】措施 、解决位错 ——①奇偶校验码

    奇偶校验码原理：

    在信息位 (有效数据) 的首部或尾部添加一个校验位 (冗余位)

    • 奇校验:整个校验码(信息位和校验位)中“1"的个数为奇数
    • 偶校验:整个校验码(信息位和校验位)中"1"的个数为偶数 - 更常用

    将“偶校验”的信息位、校验位全部异或，若结果为1说明有错误

    

    特点：

    • 只能检测单比特错误，无法检测多比特错误。
    • 无法纠正错误，只能检测错误。
    • 对偶数个错误（如两个比特同时出错）无法检测。

  • 差错检测【检错】措施 、解决位错 ——②循环冗余检验 (Cyclic Redundancy Check, CRC)

    CRC原理：

    在发送端，先把数据划分为组。假定每组k个比特假设待传送的一组数据M=101001(现在k=6)。我们在数据M 的后面再添加供差错检测用的n位冗余码一起发送。

    • n位冗余码的计算:
      • M 后面添加n个0【左移n位】;
      • 得到的(k+n)位的数 除以 事先选定好的长度为(n+1)位的除数P 得出商是 Q 而余数是 R，
        余数 R 比除数P少1位，即R是n位;
      • 将余数 R 作为冗余码 【这种为了进行检错而添加的冗余码常称为帧检验序列 FCS (Frame Check Sequence) - CRC 并非用来获得FCS 的唯一方法】 拼接在数据 M 后面。

    在接收端，把接收到的数据以帧为单位进行CRC检验: 把收到的每一个都除以同样的除数P(模2运算)，然后检查得到的余数R。

    • 若余数R=0，则判定这个帧没有差错，就接受(accept)。
    • 若余数R≠0，则判定这个帧有差错(但无法确定究竟是哪一位或哪几位出现了差错)，就丢弃。

    

    一般用生成多项式表示CRC的除数：
    $$\begin{gathered} P(X)=X^3+X^2+1=>1\ast X^3+1\ast X^2+0\ast X^1+1\ast X^0 \\ 以上的系数则组成了除数P=1101 \\ 最高次幂为3，则冗余码为3位 \end{gathered}$$

    $$\begin{gathered} 广泛使用的生成多项式： \\ CRC-16=X^{16}+X^{15}+X^2+1 \\ CRC-CCITT=X^{16}+X^{12}+X^5+1 \\ CRC-32=X^{32}+X^{26}+X^{23}+X^{22}+X^{16}+X^{12}+X^{11}+X^{10}+X^8+X^7+X^5+X^4+X^2+X+1 \end{gathered}$$

    注意：

    K个信息位，R个校验位，若生成多项式选择得当，且2^R ≥ K+R+1，CRC码可纠正1位错 【有纠错能力，但实际应用中一般只用来检错】

    有以下特点:

    • 可检测出所有奇数个错误;
    • 可检测出所有双比特的错误;
    • 可检测出所有小于等于校验位长度的连续错误;

    仅用循环冗余检验 CRC 差错检测技术和奇偶校验码 只能做到无差错接受(accept)。
    “无差错接受” :“凡是接受的帧(即不包括丢弃的帧)，都以非常接近于1的概率认为这些帧在传输过程中没有产生差错”;—— “凡是接收端数据链路层接受的帧都没有传输差错”(有差错的帧就丢弃而不接受)

  • 差错纠正【纠正】措施 、解决位错 ——①海明(汉明)校验码

    海明(汉明)校验码原理：

    将信息位分组进行偶校验 ，需要多个校验位去校验

    n 个信息位，k 个校验位 :

    • 共 n + k 位，则 n + k 位中的任何一位都会出错
    • k个校验 -> 有 2^k 种状态
    • 1 种正确状态

    2^k ≥ n + k + 1

    n	1	2-4	5-11	12-26	27-57	58-120
    k	2	3	4	5	6	7

    

    海明码有1位纠错，2位检错能力：

    为了区分1位错和2位错，还需添加“全校验位”对整体进行偶校验

    

3.1.3 其他功能 - 滑动窗口机制

流量控制： 控制发送方发送帧的速率别太快让接收方"来得及"接受

可靠传输： 解决帧错

滑动窗口机制：

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

发送窗口W_T： 发送方当前允许发送的帧

接收窗口W_R： 接收方当前允许接收的帧

三种协议 - 本质上都是滑动窗口机制：

• 停止-等待协议（S-W） - 发送窗口 = 1；接收窗口 = 1

  滑动窗口机制：W_T=1，W_R=1

  确认机制：确认帧ACK_i —— 若接收方收到i号帧，且没有检测出“差错”，需要给发送方返回确认帧 ACK_i

  重传机制：超时重传 —— 若发送方超时未收到ACK_i，则重传i号帧

  帧编号：1 bit 编号 且 W_T + W_R ≤ 2ⁿ

  

• 后退N帧协议（GO-BACK-N，GBN） - 发送窗口 ＞ 1；接收窗口 = 1

  滑动窗口机制：W_T＞1，W_R=1

  确认机制：确认帧ACK_i —— 若接收方收到i号帧，且没有检测出“差错”，需要给发送方返回确认帧 ACK_i

  重传机制：超时重传 —— 若发送方超时未收到ACK_i，则重传i号帧

  帧编号：至少 n bit 编号 且 W_T + W_R ≤ 2ⁿ

  特殊规则：

  • 关于 确认帧: 接收方可以“累积确认"。即连续收到多个数据帧时，可以仅返回最后一个帧的ACK
    【ACK_i表示接收方已收到i号帧及其之前的所有帧】
  • 关于 超时重传: 若发送方超时未收到ACK_i，则重传i号帧，及其之后的所有帧

  

• 选择重传协议（SR） - 发送窗口 ＞ 1；接收窗口 = 1

  滑动窗口机制：W_T＞1，W_R＞1

  确认机制：确认帧ACK_i —— 若接收方收到i号帧，且没有检测出“差错”，需要给发送方返回确认帧 ACK_i【不支持“累计确认”，必须一帧一确认】

  重传机制：超时重传 —— 若发送方超时未收到ACK_i，则重传i号帧

  帧编号：至少 n bit 编号 且 W_T + W_R ≤ 2ⁿ

  特殊规则：

  • 否认帧 NAK_i：若接收方收到 i 号帧，但检测出i号帧有“差错”，需要丢弃该帧，并给发送方返回否认帧 NAK_i
  • 请求重传 : 若发送方收到NAK_i，则重传i号帧
  • 要求 : 接收窗口不能大于发送窗口 W_R ≤ W_T 实际应用通常 W_R = W_T

  

满足 W_T + W_R ≤ 2ⁿ 的原因:

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

• 停止-等待协议（S-W）的信道利用率：

  

• GBN 和 SR的信道利用率：

  

• 术语补充：

  • 滑动窗口协议： 停止-等待协议不属于“滑动窗口协议”范畴，GBN 和 SR【发送窗口大于1】属于“滑动窗口协议”范畴

  • ARQ协议: 即Automatic repeat request，通常译为“自动重传清求”协议，包含 S-W、GBN、SR三种协议

  • 连续ARQ协议： GBN 和 SR【发送窗口大于1】属于“连续ARQ协议”范畴

    

3.2 点对点协议PPP(Point-to-Point Protocol)

3.2.1 PPP 协议的特点

PPP协议定义：

PPP协议就是用户计算机和ISP进行通信时所使用的数据链路层协议，且只支持全双工链路

PPP 协议应满足的需求：

• 简单
• 封装成帧
• 透明性
• 多种网络层协议——必须能够在同一条物理链路上同时支持多种网络层协议(如IP和IPX等)的运行。
• 多种类型链路
• 差错检测(error detection)
• 检测连接状态——自动检测出链路是否处于正常工作状态。
• 最大传送单元——必须对每一种类型的点对点链路设置最大传送单元MTU 的标准默认值。
• 网络层地址协商——互相通信的实体能够通过协商知道或能够配置彼此的网络层地址。
• 数据压缩协商——必须提供一种方法来协商使用数据压缩算法。但不要求将数据压缩算法进行标准化。

PPP协议组成：

• 一个将IP数据报封装到串行链路的方法。
• 一个用来建立、配置和测试数据链路连接的链路控制协议LCP(Link Control Protocol)
• 一套网络控制协议NCP(Network Control Protocol)，其中的每一个协议支持不同的网络层协议

3.2.2 PPP协议的帧格式

字节填充: 转义符定义为0x7D(即01111101)

• 把信息字段中出现的每一个 0x7E 字节转变成为2字节序列 (0x7D,0x5E)
• 把信息字段中出现一个0x7D的字节,则把0x7D转变成为2字节序列**(0x7D,0x5D)**
• 把信息字段中出现ASCII码的控制字符(即数值小于0x20的字符)，则在该字符前面要加入一个 0x7D 字节，同时将该字符的编码加以改变。例如，出现 0x03(在控制字符中是“传输结束”ETX)就要把它转变为2字节序列(0x7D,0x23)。

零比特填充：

PP协议用在SONET/SDH链路时，使用同步传输(一连串的比特连续传送)而不是异步传输(逐个字符地传送)。在这种情况下，PPP协议采用零比特填充方法来实现透明传输。

• 发送端，先扫描整个信息字段(通常用硬件实现，但也可用软件实现，只是会慢些)。只要发现有5个连续1，则立即填入一个0。保证在信息字段中不会出现6个连续1。
• 接收端，在收到一个帧时，先找到标志字段F以确定一个帧的边界，接着再用硬件对其中的比特流进行扫描。每当发现5个连续1时，就把这5个连续1后的一个0删除，以还原成原来的信息比特流

3.2.3 PPP 协议的工作状态

• 当用户拨号接入 ISP 时，路由器的调制解调器对拨号做出确认，并建立一条物理连接。
• PC 机向路由器发送一系列的 LCP 分组(封装成多个 PPP 帧)
• 这些分组及其响应选择一些 PPP 参数，并进行网络层配置，NCP给新接入的 PC 机分配一个临时的 IP 地址，使 PC 机成为因特网上的一个主机。
• 通信完毕时，NCP 释放网络层连接，收回原来分配出去的IP地址。接着，LCP 释放数据链路层连接。最后释放的是物理层的连接

PPP 链路的起始和终止状态永远是“链路静止”(Link Dead)状态，在用户个人电脑和ISP 的路由器之间并不存在物理层的连接。

当用户个人电脑通过调制解调器呼叫路由器时，路由器就能够检测到调制解调器发出的载波信号。双方建立了物理层连接。

PPP 进入“链路建立”(Link Establish)状态，其目的是建立链路层的 LCP 连接

LCP 协商一些配置选项，即发送LCP的配置请求帧(Configure-Request)。这是个PPP帧，其协议字段置为LCP对应的代码，而信息字段包含特定的配置请求。

链路的另一端可以发送以下几种响应中的一种:
(1) 配置确认帧(Configure-Ack): 所有选项都接受。
(2) 配置否认帧(Configure-Nak): 所有选项都理解但不能接受,
(3) 配置拒绝帧(Configure-Reject): 选项有的无法识别或不能接受，需要协商。

LCP配置选项包括链路上的最大帧长、所使用的鉴别协议(Authentication protocol)的规约(如果有的话)，以及不使用PP帧中的地址和控制字段(因为这两个字段的值是因定的,没有任何信点量，可以省略)。

协商结束后双方就建立了LCP链路，接着就进入“鉴别”(Authenticate)状态

开始鉴别，此时只允许传送LCP协议的分组、鉴别协议的分组以及监测链路质量的分组，
若使用口令鉴别协议 PAP(Password Authentication Protocol)，则需要发起通信的一方发送身份标识符和口令。系统可允许用户重试若干次。
如果需要有更好的安全性，则可使用更加复杂的口令握手鉴别协议CHAP(Challenge-Handshake Authentication Protocol)。

若鉴别失败，则转到“链路终止”(Link Terminate)状态。
若鉴别成功，则进入“网络层协议”(Network-Layer Protocol)状态。

PPP链路两端的网络控制协议NCP根据网络层的不同协议互相交换网络层特定的网络控制分组。
PPP协议两端的网络层可以运行不同的网络层协议，但仍然可使用同一个 PPP 协议进行通信。

当网络层配置完毕后，链路就进入可进行数据通信的“链路打开”(Link Open)状态。

链路的两个PPP端点可以彼此向对方发送分组。
两个 PPP 端点还可发送回送请求LCP分组(Echo-Request)和回送回答 LCP 分组(Echo-Reply)，以检查链路的状态。
数据传输结束后，可以由链路的一端发出终止请求LCP分组(Terminate-Request)请求终止链路连接，在收到对方发来的终止确认LCP分组(Terminate-Ack)后，转到“链路终止”状态。
如果链路出现故障，也会从“链路打开”状态转到“链路终止”状态。

当调制解调器的载波停止后，则回到“链路静止“状态。

3.3 使用广播信道的数据链路层

广播信道可以进行一对多的通信

3.3.1 局域网的数据链路层

局域网最主要的特点是: 网络为一个单位所拥有，且地理范围和站点数目均有限。

• 覆盖较小的地理范围
• 较低的时延和误码率
• 局域网内的各节点之间以“帧”为单位进行传输
• 支持单播、广播、多播
  • 单播(一对一发送帧):如 A→B
  • 广播(一对全部发送帧):如 A→B+C+D+E+F+G
  • 多播(一对部分发送帧):如 A→B+D+E

共享信道，解决冲突的方式：

使用一对多的广播通信方式时，共享信道要着重考虑的一个问题就是如何使众多用户能够合理而方便地共享通信媒体资源。有两种方法:

• 静态划分信道，如频分复用、时分复用、波分复用和码分复用等。用户只要分配到了信道就不会和其他用户发生冲突。但这种划分信道的方法代价较高，不适合于局域网使用。

• 动态媒体接入控制，它又称为多点接入(multiple access)，其特点是信道并非在用户通信时固定分配给用户。又分为以下两类:

  • 随机接入，特点是所有的用户可随机地发送信息。但如果恰巧有两个或更多的用户在同一时刻发送信息，那么在共享媒体上就要产生碰撞(即发生了冲突)，使得这些用户的发送都失败。因此，必须有解决碰撞的网络协议。- CSMA/CD协议
  • 受控接入，受控接入的特点是用户不能随机地发送信息而必须服从一定的控制。这类的典型代表有 [ 分散控制的令牌环局域网和集中控制 ] 的多点线路探询(polling)，或称为轮询。【目前在局域网中使用得较少】

  轮询访问：令牌传递协议

  核心特点: 环形拓扑结构，各节点“轮询访问”信道【持有令牌才能访问】，不会发生信道冲突

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

  

以太网已成为了局域网的同义词

以太网的两个标准

• DIX Ethernet V2【市面流行】
• IEEE 的 802.3 标准

IEEE 802 委员会：推进局域网技术的标准化工作【IEEE：电气电子工程师学会】

• 802.5 工作组 - 令牌环网技术 - 已解散
• 802.3 工作组 - 以太网技术（有线）
• 802.11 工作组 - Wi-Fi技术（无线）
  • 802.11b–WiFi1，1999年
  • 802.11a–WiFi2，1999年
  • 802.11g–WiFi3，2003年
  • 802.11n–WiFi4，2009年
  • 802.11 ac–WiFi5，2013年
  • 802.11 ax–WiFi6，2021年
  • 802.11 be–WiFi7，2024年

IEEE 802 负责物理层和数据链路层：

• 802将局域网的数据链路层拆成两个子层

  • 逻辑链路控制 LLC(Logical Link Control)子层——LLC 子层则与传输媒体无关

  • 媒体接入控制 MAC (Medium Access Control)子层——与接入到传输媒体有关的内容都放在 MAC 子层（如:组帧、差错检测、透明传输、介质访问控制等)

  • 不管采用何种传输媒体和 MAC 子层的局域网对 LLC 子层来说都是透明的。【现在市面一般不考虑 LLC 子层】

局域网分类：

• 有线局域网

  • 以太网/802.3(Ethernet) 【物理层 - 曼彻斯特编码】

    • 早期同轴电缆以太网 - 10Base5 【10Mbps，一根同轴电缆不超过500m，5-4-3原则：5个同轴电缆网段，4个中继器，3个网段挂接计算机】1982年
      • ①总线形 ②同轴电缆(可用中继器连接多个同轴电缆网段) ③CSMA/CD协议
    • 双绞线以太网 - 10BaseT 1990年
      • 集线器连接
        • ①物理上星形，逻辑上总线形 ②双绞线(用集线器连接) ③CSMA/CD协议
      • 交换机连接 - 1994年
        • ①物理上和逻辑上都是总线形 ②双绞线(用交换机连接) ③CSMA/CD协议或无协议【半双工模式下，采用 CSMA/CD 争抢信道全双工模式下，不用争抢信道，也就不需要使用CSMA/CD协议】
    • 光纤以太网 - 10 BaseF（Fiber） 1993年
      • ①点对点 【用于连接中间结点-中继器/集线器/交换机传输，不连接终端结点-计算机】②光纤 ③无协议 (用两条光纤实现全双工通信，无信道争用问题)

    同轴电缆只能半双工;

    双绞线速率<2.5Gbps可支持半双工or全双工(节点连接时协商); 速率>2.5Gbps仅支持支全双工;

    光纤只支持全

  • 令牌环网(Token Ring)1984~2000

    • ①环形
    • ②同轴电缆 或 双绞线
    • ③令牌传递协议

• 无线局域网

  • Wi-Fi/802.11
    • ①IEEE 802.11 定义为星形(1个AP+N台移动设备) ②无线(Wireless) ③CSMA/CA 协议

适配器：

计算机与外界局域网的连接是通过适配器(adapter)。适配器本来是在主机箱内插入的一块网络接口板(或者是在笔记本电脑中插入一块PCMCIA卡–个人计算机存储器卡接口适配器)。这种接口板又称为网络接口卡NIC(Network Interface Card)或简称为“网卡”。

适配器的重要功能:

• 进行串行/并行转换;
• 对数据进行缓存;
• 在计算机的操作系统中安装设备驱动程序;
• 实现以太网协议。

3.3.2 随机访问介质访问控制

ALOHA 协议

CSMA 协议

载波监听、多点接入(Carrier Sense Multiple Access )

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

CSMA/CD 协议 - 总线型 - 半双工

用于早期有线以太网（总线型）

最早的以太网是将许多计算机都连接到一根总线上。

以太网为了通信简便采取了两种措施：

• 不必先建立连接就可以直接发送数据

  • 适配器对发送的数据帧不进行编号，也不要求对方发回确认。

  • 以太网提供的服务是尽最大努力的交付，即不可靠的交付【信道质量产生差错的概率是很小】。

  • 在同一时间只能允许一台计算机发送数据，否则各计算机之间就会互相干扰，使得所发送数据被破坏。CSMA/CD协议【载波监听多点接入/碰撞检测(Carrier Sense Multiple Access with Collision Detection)】用来减少冲突发生的概率。

• 发送的数据都使用曼彻斯特编码

  • 缺点：频带宽度比原始的基带信号增加了一倍

CSMA/CD协议定义：

载波监听多点接入/碰撞检测(Carrier Sense Multiple Access with Collision Detection)

• 载波监听(CS): 是指每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据，如果有，则暂时不要发送数据，以免发生碰撞;

• 多点接入(MA): 表示许多计算机以多点接入的方式连接在一根总线上;

• 碰撞检测(CD): 边发送边监听【检测信道上的信号电压大小】，判断发送的数据是否与其他站发送的数据产生了冲突。

  当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大(互相叠加);
  当一个站检测到的信号电压摆动值超过一定的门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞:

​ 不管在想要发送数据之前，还是在发送数据之中，每个站都必须不停地检测信道。先听后发，边听边发，冲突停发，随机重发

电磁波在1km 电缆的传播时延约为5μs

争用期 / 碰撞窗口：

在发送数据帧后至多经过时间 2τ就可知道发送的数据帧是否最先发送数据帧的茫遭受了碰撞:
以太网的端到端往返时延 2τ称为争用期，或碰撞窗口:
经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞

最短帧长计算：
$$\begin{gathered} \frac{F_l}{D_s}\ge 2\tau =>F_{lmin}=2\tau \times D_s \\ {F}_l:帧长D_s:数据传输速率 \end{gathered}$$
以太网争用期为2τ=51.2μs —— 10 Mbit/s 以太网取 51.2μs为争用期的长度。对于10 Mbit/s 以太网，在争用期内可发送512 bit，即 64 字节。以太网最小有效帧长为64字节。长度小于 64 字节的帧都是由于冲突而异常中止的无效帧。

截断二进制指数退避(truncated binary exponential back off)算法来确定碰撞后重传的时机：

发生碰撞的站在停止发送数据后，要推迟(退避)一个随机时间【r倍的基本退避时间：2τ * r】才能再发送数据
2τ：争用期
r：从整数集合[0,1… (2^k-1)]中随机地取出一个数;
k = Min[重传次数, 10]

• 当k≤10 时，参数k等于重传次数，在[0,(2^k-1)]区间随机取一个整数r;
• 当 10<k<16时，在[0,(2¹⁰-1)]区间随机取一个整数r；
• 当k=16 次仍不能成功时即丢弃该帧，并向高层报告

CSMA/CD协议步骤总结：

• (1) 准备发送。从网络层获得一个分组，组成以太网帧，放入适配器的缓存中

• (2) 检测信道。若检测到信道忙，则应不停地检测，一直等待信道转为空闲。若检测到信道空闲，并在 96 比特时间【即发送 96 比特所需的时间）内信道保持空闲(保证了以太网帧间最小间隔96 比特时间)，就发送这个帧。

  【10 Mbps以太网：9.6 μs；100 Mbps以太网：0.96 μs】

• (3) 检查碰撞。网络适配器要边发送边监听。
  这里只有两种可能性:

  • ① 发送成功:在争用期内一直未检测到碰撞，发送成功。发送完毕后，其他什么也不做。然后回到(1)
  • ② 发送失败:在争用期内检测到碰撞。立即停止发送数据，并发送人为干扰信号，执行指数退避算法，等待 r 倍 512 比特时间【以太网争用期时间：512 比特时间】后，返回到步骤(2)。

  重传达 16 次仍不能成功，则停止重传而向上报错。

强化碰撞 - 人为干扰信号：

• 立即停止发送数据，再继续发送若干比特的人为干扰信号，让所有用户都知道现在已经发生了碰撞;
• B 也能够检测到冲突，并立即停止发送数据帧，接着就发送干扰信号，

CSMA/CA 协议

用于IEEE 802.11 无线局域网(WiFi)

载波监听多点接入/冲突避免(Carrier Sense Multiple Access with Collision Avoidance)

接入点（Access Point，AP）： 是无线网络中的关键设备，用于将无线设备（如智能手机、笔记本电脑、平板电脑）连接到有线网络。【手机热点（Mobile Hotspot） 本质上也是一个 无线接入点（AP），允许用户将手机的移动数据连接共享给其他无线设备，使这些设备能够通过 Wi-Fi 接入互联网】

家用路由器 = 路由器 + 交换机 + 接入点(AP)

为什么无线局域网不采用 CSMA/CD 协议?

CSMA/CA 协议两种模式：

帧间间隔IFS

• DIFS，最长的IFS： 每次“帧事务”开始之前需要等待的时间
• SIFS，最短的IFS： 收到一个帧后需要预留的一段处理时间
• PIFS，中等长度的IFS： 考研可不关注PIFS

DIFS（Distributed Interframe Space）

• 定义：DIFS 是分布式帧间隔时间，用于普通设备的通信竞争。
• 用途：适用于所有设备（如笔记本电脑、手机等）在无线网络中的正常数据传输。
• 优先级：较低，适用于大多数应用场景。

PIFS（PCF Interframe Space）

• 定义：PIFS 是点协调功能帧间隔时间，用于优先级较高的设备或数据传输。
• 用途：主要用于支持时间敏感的应用（如视频流、语音通信等），确保这些应用能够抢占信道。
• 优先级：较高，优先于 DIFS。

• 第一种【不考虑"隐蔽站"问题】

  • 发送方，先听后发，忙则退避

    • 若信道空闲，间隔DIFS后，再发送帧(一口气发完，发送过程中不用检测冲突)

    • 若信道不空闲，则进行“随机退避”

      “随机退避”原理:
      ①用二进制指数退避算法确定一段随机退避时间(倒计时)
      ②发送方会保持监听信道，只有信道空闲时才"扣除倒计时"倒计时结束后立即发送帧(此时信道“听起来”一定空闲)

    • 接收方:停止等待协议 – 每收到一个正确数据帧都返回ACK; 若发送方超时未收到ACK，则进行“随机退避”

      

• 第二种【解决"隐蔽站"问题】- 信道预约机制(可启用可不启用功能-先预约，再发送)

  RTS控制帧(Request To Send，请求发送) – 它包括源地址、目的地址和这次通信所需的持续时间。
  CTS控制帧(Clear To Send，允许发送) – 它也包括源地址、目的地址和这次通信所需的持续时间。

  • 发送方广播RTS控制帧（先听后发，忙则退避）【需在RTS中指明预约时长】

• AP广播CTS控制帧【需在CTS中指明预约时长】

  • 其他无关节点收到CTS后自觉“禁言"一段时间(即:虚拟载波监听机制)；发送方收到 CTS后，就可以发送数据帧

• AP收到数据帧后，进行CRC校验，若无差错就返回ACK帧

  • 如果超时未收到CTS,说明预约失败，则“随机退避”后再次RTS预约
    

3.3.3 使用集线器(hub)的星形拓扑

集线器的一些特点如下:

• 从表面上看，使用集线器的局域网在物理上是一个星形网，但在逻辑上仍是一个总线网，各站共享逻辑上的总线，各站中的适配器执行CSMA/CD协议【半双工方式】。网络中的各站必须竞争对传输媒体的控制，并且在同一时刻至多只允许一个站发送数据。
• 一个集线器有许多端口，像一个多端口的转发器。
• 集线器工作在物理层【只能识别电磁信号】，它的每个端口仅仅简单地转发比特——收到1就转发1，收到0就转发0，不进行碰撞检测。若两个端口同时有信号输入(即发生碰撞)，那么所有的端口都将收不到正确的帧
• 集线器采用了专门的芯片，进行自适应串音回波抵消。这样就可使端口转发出去的较强信号不致对该端口接收到的较弱信号产生干扰(这种干扰即近端串音)。每个比特在转发之前还要进行再生整形并重新定时。

堆叠式(stackable)集线器 由4~8个集线器堆叠起来使用。

3.3.4 以太网的信道利用率

参数 α，它是以太网单程端到端时延τ, 与帧的发送时间T₀之比： α = τ / T₀

α➡0 ，表示一发生碰撞就立即可以检测出来，并立即停止发送，信道利用率很高。

α越大，争用期所占比例越大，信道利用率越低。

当数据率一定时，以太网的连线的长度不能太长(否则τ的数值会太大)，同时以太网的帧长不能太短(否则T₀的值会太小，使α值太大)。

极限利用率：

在理想化的情况下，以太网上的各站发送数据都不会产生碰撞(这显然已经不是 CSMA/CD，而是需要使用一种特殊的调度方法)，即总线一旦空闲就有某一个站立即发送数据。
$$\begin{gathered} 极限信道利用率S_{max}=\frac{T_0}{T_0+\tau }=\frac{1}{1+\alpha } \\ {T}_0+\tau ：发送一帧占用线路的时间 \\ {T}_0：帧本身发送的时间 \end{gathered}$$
只有当参数 α 远小于1才能得到尽可能高的极限信道利用率

3.3.5 以太网的 MAC层

MAC 层的硬件地址：

定义：

• 在局域网中，硬件地址又称为物理地址或 MAC地址或适配器地址或适配器标识符 EUI-48：为一种 48位（6字节）的全球地址(一般都简称为“地址”)，即局域网上的每一台计算机中固化在适配器的 ROM 中的地址。
• 路由器、交换机都有MAC地址；集线器没有

特点：

• 随着适配器的变化而变化，适配器改变则地址改变。

• 如果连接在局域网上的主机或路由器安装有多个适配器，那么这样的主机或路由器就有多个“地址”。

组成：

​ 以太网MAC地址共6字节(48 bit):

• IEEE 的注册管理机构 RA(Registration Authority) 负责向厂家分配MAC地址的前三个字节(即高位 24 位)，称为组织唯一标识符OUl (Organizationally Unique ldentifier)；

• MAC地址的后三个字节(即低位 24 位)由厂家自行指派，称为扩展唯一标识符(extended identifier)，必须保证生产出的适配器没有重复地址。可以生成 2²⁴ 个不同的地址。这种 48 位地址称为MAC-48，它的通用名称是 EUI-48

  

分类一：

• 单播MAC地址:是指第一个字节的最低位是0的MAC地址,代表了一块特定的网卡。
• 组/多播MAC地址:是指第一个字节的最低位是1的MAC地址,代表了一组网卡
• 广播MAC地址:是指每一位都是1的MAC地址，广播MAC地址是组播MAC地址的一个特例，代表了所有网卡。（48个1）
• 广播/组播地址只能作为目的地址使用，不能作为源地址

分类二：

​ 第一字节的最低第 2 位规定为 G/L 位

• 当 G/L位=0 时，是全球管理(保证在全球没有相同的地址)，厂商向IEEE购买的 OUI都属于全球管理;
• 当 G/L位=1 时，是本地管理，用户可任意分配网络上的地址。

适配器从网络上每收到一个 MAC 帧就首先用硬件检查MAC 帧中的 MAC 地址:

• 如果是发往本站的帧则收下，然后再进行其他的处理，
• 否则就将此帧丢弃，不再进行其他的处理

发往本站的帧：

• 单播(unicast)帧(一对一)，即收到的帧的 MAC地址与本站的 MAC地址相同。
• 广播(broadcast)帧(一对全体)，即发送给本局域网上所有站点的帧(全1地址)。
• 多播(multicast)帧(一对多)，即发送给本局域网上一部分站点的帧。

所有的适配器都至少能够识别前两种帧，即能够识别单播地址和广播地址。有的适配器可用编程方法识别多播地址

混杂方式(promiscuous mode): 适配器只要“听到”有帧在以太网上传输就都悄悄地接收下来，而不管这些帧发往哪个站。这样做实际上是“窃听”其他站点的通信而并不中断其他站点的通信。网络上的黑客(hacker 或 cracker)常利用这种方法非法获取网上用户的口令。

以太网V2的MAC 帧格式：

以太网MAC帧由五个字段组成：

• 6字节长的目的地址字段

• 6字节长的源地址字段

• 2字节的类型字段，用来标志上一层使用的是什么协议，以便把收到的 MAC 帧的数据上交给上一层的这个协议。例如，当类型字段的值是 0x0800时，就表示上层使用的是IP数据报。

  【类型字段是V2标准MAC帧格式 和 802.3标准MAC帧的唯一区别，V2：协议（V2标准没有LLC层）；802.3：数据长度（因为802.3标准是有LLC和MAC，协议交给LLC层）】

• 数据字段，其长度在46到1500字节之间(46字节是这样得出的:最小长度64字节减去18字节的首部和尾部就得出数据字段的最小长度)。

• 4字节的帧检验序列FCS(使用CRC检验)。

从MAC子层向下传到物理层时还要在的前面插入8个字节(由硬件生成)，它由两个字段构成：

• 第一个字段是7个字节的前同步码(1和0交替码)，它的作用是使接收端的适配器在接收 MAC帧时能够迅速调整其时钟频率，使它和发送端的时钟同步,也就是“实现位同步”(位同步就是比特同步)。
• 第二个字段是1个字节帧开始定界符，定义为10101011。它的前六位的作用和前同步码一样，最后的两个连续的1就是告诉接收端适配器“MAC 帧的信息马上就要来了，请适配器注意接收。MAC 帧的FCS 字段的检验范围不包括前同步码和帧开始定界符。在使用SONET/SDH进行同步传输时则不需要用前同步码。

以太网上传送数据特点：

• 在以太网上传送数据时是以帧为单位传送的。
• 以太网在传送帧时，各之间还必须有一定的间隙。
  因此，接收端只要找到帧开始定界符，其后面的连续到达的比特流就都属于同一个MAC帧。
  以太网不需要使用帧结束定界符，也不需要使用字节插入来保证透明传输。

3.4 扩展的以太网

扩展原因：传统以太网的传输媒体是同轴电缆，粗缆500m，细缆185m，接入的计算机数量是有限的【覆盖的地理范围受限】

CSMA/CD协议主要应用于10 Mbps传统以太网，现代以太网使用交换机和全双工模式，CSMA/CD 已不再适用

3.4.1 在物理层扩展以太网 - 集线器 - 总线形

方法一：使用光纤扩展

主机使用光纤(通常是一对光纤)和一对光纤调制解调器连接到集线器。优点：传输距离远；缺点：成本高

方法二：使用集线器扩展

碰撞域/冲突域：物理层的概念，指任何一台设备发送数据，其他设备再发送数据会与之产生冲突，这些设备的集合，即为碰撞域或冲突域。

优点：

• 使原来属于不同碰撞域的以太网上的计算机能够进行碰撞域的通信;
• 扩大了以太网覆盖的地理范围

缺点：

• 碰撞域增大了，但总的吞吐量并未提高;
• 如果不同的碰撞域使用不同的数据率，那么就不能用集线器将它们互连起来。

3.4.2 在数据链路层扩展以太网 - 以太网交换机 - 星形

扩展以太网更常用的分法是在数据链路层进行

早期：

网桥： 网桥对收到的帧【可以识别帧】根据其MAC 帧的目的地址进行转发和过滤。
当网桥收到一个帧时，并不是向所有的端口转发此帧，而是根据此帧的目的 MAC地址，查找网桥中的地址表，然后确定将该帧转发到哪一个端口，或者是把它丢弃(即过滤)。

现在：

以太网交换机 / 交换式集线器 / 第二层交换机： 实质上就是一个多端口的网桥。每个端口都直接与一个单台主机或另一个以太网交换机相连，并且一般都工作在【全双工方式】。每个端口都是一个碰撞域，交换机起到了隔离碰撞域的功能。

广播域：是数据链路层的概念，任何一个站发送一个广播帧，所有能够收到这个广播帧的设备的集合; 每个端口是一个独立的碰撞域。

以太网交换机特点：

• 接口数量多：一个多接口的网桥，具有十几个或更多的接口，也支持多种不同类型的网络接口【以太网、ATM网、令牌环网】
• 全双工工作：接口与一台主机或另一个交换机相连，工作在全双工方式
• 具有并行性：能同时连通多对接口，使多对主机能同时通信
• 传输无冲突：相互通信的主机都是独占传输媒体，无碰撞地传输数据【不使用CSMA/CD协议】
• 接口存储器：接口有存储器，能在输出端口繁忙时把到来的帧进行缓存
• 能即插即用：即插即用设备，其内部的帧交换表是通过自学习算法自动地逐渐建立起来的
• 转发速率高：采用专用的交换结构芯片，硬件转发，转发速率比使用软件转发的网桥快很多

以太网交换机的优点：

• 用户独享带宽，增加了总容量。

  共享式以太网(10 Mbit/s)，若共有 N个用户，每个用户的平均带宽只有总带宽 的 1/N。
  交换式以太网(10 Mbit/s)，每个用户的独享带宽则还是10 Mbit/s，N个接囗的交换机的总容量为 2 x N/2 x 10 Mbit/s。该交机的背板带宽应该 ≥ 交换机的总容量。
  【 N/2：N个接口的交换机，连接了N个主机，即N/2对儿主机；2：全双工，双向同时】

• 共享总线以太网（集线器）转到交换式以太网（交换机），所有接入设备无需任何改动: 向下兼容。

• 支持有多种速率的接口。

以太网交换机的交换方式：

• 存储转发方式：数据帧先缓存，检验正确性，正确转发，错误丢弃。延迟大可靠性高，支持不同速率的端口交换。
• 直通(cut-through)方式：检查数据帧的目的 MAC 地址之后立即转发，延迟小，可靠性低，不支持不同速率的端口交换;有可能转发一些无效的帧。

以太网交换机自学习的功能：

步骤：

​ 交换机收到一顺后先进行自学习。查找交换表中与收到帧的源地址有无相匹配的项目:

• 没有：就在交换表中增加一个项目(源地址、进入的接口和有效时间);
• 有：则把原有的项目进行更新并转发帧，同时查找交换表中与收到帧的目的地址有无相匹配的项目:
  • 没有：则向所有其他接口(进入的接口除外)转发;
  • 有：则按交换表中给出的接口进行转发;
    若交换表中给出的接口就是该帧进入交换机的接口，则应丢弃这个帧(因为这时不需要经过交换机进行转发)

生成树协议：

增加冗余链路：将两个交换机用两条线连接起来，来增加网络的可靠性——如果其中一个交换机发生了故障，整个网络仍然是通的

增加冗余链路造成的问题：自学习的过程就可能导致以太网帧在网络的某个环路中无限制地兜圈子——广播风暴

解决此问题：生成树协议STP(Spanning Tree Protocol) ——不改变网络的实际拓扑，但在逻辑上则切断某些链路，使得从一台主机到所有其他主机的路径是无环路的树状结构，从而消除了兜圈子现象

集线器和交换机对比：

特性	集线器（Hub）	以太网交换机（Ethernet Switch）
工作层次	物理层 - 识别电磁信号	数据链路层 - 识别帧
传输方式	广播	点对点
工作方式	半双工	全双工
冲突域	共享 - 需使用CSMA/CD协议	独立 - 不使用CSMA/CD协议
带宽	共享	独享
延迟	高	低
错误处理	无	有
安全性	低	高
MAC 学习	不学习	学习

以太网的重要协议CSMA/CD都不使用了(相关的“争用期”也没有了)，还叫作以太网的原因：它的帧结构未改变，仍然采用以太网的帧结构。

3.4.3 虚拟局域网 - IEEE 802.1Q

虚拟局域网 VLAN(Virtual LAN)：部门内部可以相互访问，部门间不能相互访问，将各部门从单一的广播域隔离出来，以增加网络安全性。【大广播域划分成小的广播域，每一个VLAN都是一个广播域】

是由一些局域网网段构成的与物理位置无关的逻辑组：

• 这些组有共同需求；
• 每一个 VLAN 的帧都有一个明确的标识符VID，指明发送这个帧的计算机是属于哪一个 VLAN;
• 由以太网交换机实现 —— 需要使用支特WTAN功能的以太网交换机来实现;
• 虚拟局域网其实只是局域网给用户提供的一种服务，而并不是一种新型局域网。

虚拟局域网限制了接收广播信息的工作站数，使得网络不会因传播过多的广播信息而引起性能恶化。五种划分方法：

• 基于交换机端口：最简单、也是最常用的方法，属于在第一层划分虚拟局域网的方法。缺点：用户位置是固定的

• 基于用户计算机的MAC地址：属于在第二层划分虚拟局域网的方法，用户位置是可以改变的。缺点：需要输入和管理大量的MAC地址。如果用户的MAC地址改变了，则需要管理员重新配置VLAN。

• 基于协议类型：属于在第二层划分虚拟局域网的方法，根据以太网帧的第三个字段“类型”字段确定该类型的协议属于哪一个虚拟局域网。

• 基于IP地址：属于在第三层划分虚拟局域网的方法，根据以太网帧的第三个字段“类型”字段和IP分组首部中的源 IP 地址字段确定该 IP 分组属于哪一个虚拟局域网。【网络层，可以跨路由器】

• 基于应用层：根据高层应用或服务、或者它们的组合划分虚拟局域网

  

虚拟局域网使用的以太网帧格式：

在以太网的帧格式中插入一个4字节的标识符，称为VLAN 标记(tag)，用来指明发送该帧的计算机属于哪一个虚拟局域。
插入 VLAN 标记得出的帧称为 802.1Q 帧 或 带标记的以太网帧 —— 交换机和交换机之间传输使用的帧【6 6 4 2 N 4 收发V协数验】

VLAN优点：

• 便于网络管理，具有相似需求的用户共享同一VLAN
  • 增强网络的安全性，把敏感用户与普通用户隔离。
  • 减少了不必要的网络流量。
  • 限制了广播报文的洪泛，抑制广播风暴。
  • 减少网络拓扑变更成本。
  • 降低计算机CPU的开销。

3.5 高速以太网

3.5.1 100BASE-T 以太网

100BASE-T是在双绞线上传送100Mbit/s基带信号的星形拓扑以太网，仍使用IEEE802.3的 CSMA/CD协议，它又称为快速以太网(Fast Ethernet)

• 允许在100Mbit/s下以全双工和半双工两种方式工作。
• 使用IEEE802.3协议规定的帧格式。
• 在半双工方式下使用CSMA/CD协议，而在全双工方式不使用CSMA/CD 协议。

帧最小间隔：

• 10 Mbps：9.6 μs
• 100 Mbps：0.96 μs

100 Mbit/s 以太网的物理层标准：

名称	媒体	网段最大长度	特点
100BASE-TX	铜缆	100 m	两对 UTP 5类线或屏蔽双绞线 STP
100BASE-T4	铜缆	100 m	4对UTP 3类线或5类线
100BASE-FX	光缆	2000 m	两根光纤，发送和接收各用一根

注：100BASE-TX和100BASE-FX合在一起称为100BASE-X；
100BASE-T4使用4对UTP3类线或5类线时，使用3对线同时传送数据(每一对线以33号Mbit/s的速率传送数据)，用1对线作为碰撞检测的接收信道。

3.5.2 吉比特以太网（Gigabit Ethernet, GbE）

吉比特以太网的标准 IEEE802.3z有以下几个特点:

• 允许在1Gbit/s下以全双工和半双工两种方式工作。
• 使用IEEE802.3协议规定的帧格式。
• 在半双工方式下使用CSMA/CD协议，而在全双工方式不使用CSMA/CD 协议。
• 与10BASE-T和100BASE-T 技术向后兼容。

吉比特以太网的物理层使用两种成熟的技术:

• 来自现有的以太网
• 美国国家标准协会 ANSI制定的光纤通道FC (Fiber Channel)。

吉比特以太网物理层标准：

名称	媒体	网段最大长度	特点
1000BASE-SX	光缆	5500m	多模光纤(50 和 62.5 μm)
1000BASE-LX	光缆	50000m	单模光纤(10μm)多模光纤(50和62.5 μm)
1000BASE-CX	铜缆	250m	使用2对屏蔽双纹线电缆STP
1000BASE-T	铜缆	100 m	使用4对 UTP5类线

1000BASE-X(包括表3-2中的前三项)的标准是IEEE802.3z，而1000BASE-T的标准是IEEE 802.3ab。

3.5.3 10吉比特以太网(10GbE)和更快的以太网

10GbE (10Gbit/s) 只工作在全双工方式，因此不存在争用问题，不使用CSMA/CD 协议。

10吉比特以太网(10GbE)物理层标准：

名称	媒体	网段最大长度	特点
1000BASE-SR	光缆	300 m	多模光纤(0.85 μm)
1000BASE-LR	光缆	10 km	单模光纤(1.3μm)
1000BASE-ER	光缆	40 km	单模光纤(1.5μm)
1000BASE-CX4	铜缆	15 m	使用4对双芯同轴电缆
1000BASE-T	铜缆	100 m	使用4对 6A类 UTP双绞线

前三项的标准是IEEE802.3ae，第四项的标准是IEEE802.3ak，最后一项的标准是IEEE802.3an。

40GbE/100GbE(即40吉比特以太网和100吉比特以太网)： 物理层标准 - IEEE 802.3ba-2010和802.3bm-2015；只工作在全双工方式

802.3bs 标准，共有两种速率，即200GbE(速率为200Gbit/s和 400GbE(速率为 400 Gbit/s)，全部用光纤传输(单模和多模)

---

参考：

教材：计算机网络（第8版） (谢希仁) (Z-Library).pdf

视频：

王道计算机考研 计算机网络