计算机网络

• 1: 计算机网络体系结构
• 1.1: ISO/OSI和TCP/IP模型
• 1.2: 网络设备总结
• 1.3: 各层协议总结
• 2: 物理层
• 2.1: 通信概念
• 2.2: 编码和调制
• 2.3: 交换方式
• 2.4: 物理层设备
• 3: 数据链路层
• 3.1: 组帧
• 3.2: 差错控制
• 3.3: 流量控制
• 3.4: 介质访问控制
• 3.5: 局域网和广域网
• 3.6: 数据链路层设备
• 4: 网络层
• 4.1: IP
• 4.2: ICMP
• 4.3: DHCP
• 4.4: ARP
• 4.5: 路由算法
• 4.6: SDN
• 4.7: 网络层设备
• 5: 传输层
• 5.1: TCP
• 5.2: UDP
• 6: 应用层
• 6.1: 网络应用模型
• 6.2: DNS
• 6.3: FTP
• 6.4: 电子邮件
• 6.5: 万维网

1 - 计算机网络体系结构

学习思维导图：

# 计算机网络概述

## 基本概念

- 定义、组成和功能
- 分类
- 主要性能指标

## 体系结构

- 分层结构
- 网络协议、接口、服务等概念
- ISO/OSI参考模型和TCP/IP模型

1.1 - ISO/OSI和TCP/IP模型

ISO/OSI模型

ISO/ISO模型 也叫做 国际标准化组织/开放系统互联模型

• 物理层（Physical Layer）：负责物理介质传输数据比特流，涵盖了电压、电流、光信号等硬件细节。
• 数据链路层（Data Link Layer）：提供数据包的可靠传输，处理帧的传输和接收，错误检测和纠正。
• 网络层（Network Layer）：负责数据包的路由和寻址，以及数据包的跨越多个网络的传递。最著名的网络协议是IP（Internet Protocol）。
• 传输层（Transport Layer）：提供端到端的数据传输，负责数据的分段和重新组装。最常见的传输协议是TCP（Transmission Control Protocol）和UDP（User Datagram Protocol）。
• 会话层（Session Layer）：负责建立、管理和终止通信会话，处理会话控制和同步。
• 表示层（Presentation Layer）：处理数据的格式转换、加密解密和压缩解压缩等数据表示问题。
• 应用层（Application Layer）：最高层，包括各种应用程序和网络服务，例如电子邮件、文件传输和远程登录。

TCP/IP 模型

• 网络接口层（Network Interface Layer）：与ISO/OSI的物理层和数据链路层类似，处理物理介质和数据链路的细节。
• 互联网层（Internet Layer）：对应于ISO/OSI的网络层，包括了IP协议，用于路由和数据包交换。
• 传输层（Transport Layer）：与ISO/OSI的传输层相对应，包括了TCP和UDP协议。
• 应用层（Application Layer）：与ISO/OSI的应用层相对应，包括了各种应用程序和协议，如HTTP、FTP、SMTP等。

数据封装层次

应用层的数据通过计算机网络多个层次的封装发送至信道中，封装的过程如上图所示。

这里需要强调一下的是每一层的数据封装名称

首要的是掌握英文的名词表述，相比中文，这些表述更加统一和精准，中文翻译良莠不齐，常常有多种表述方式，但是表述的都是一个概念，能见词闻义即可。

• 传输层：UDP Datagram（UDP 数据包）、TCP Segment（TCP 数据段，TCP 分段）
• 网络层：IP Packet（IP 分组，IP 数据包，IP 报文）
• 数据链路层：Frame（帧）

1.2 - 网络设备总结

冲突域：在一个局域网段中，如果两台计算机在同一时间发送数据，则可能会发生数据冲突。冲突域是可能发生数据冲突的网络区域。交换机可以隔离冲突域，因为它仅向目标设备转发数据。

广播域：在一个局域网内，广播数据包会被所有设备接收。广播域是所有设备都会接收广播包的网络区域。路由器可以隔离广播域，因为它不会转发广播数据包。

1.3 - 各层协议总结

应用层协议

传输层

TCP, UDP

网络层

IP, ICMP

数据链路层

ARP, PPP, HDLC

2 - 物理层

学习思维导图：

# 物理层

## 通信基础

- 信道、信号、带宽、码元、波特、速率、信源与信宿等基本概念
- 奈奎斯特定理和香农定理
- 编码和调制
- 电路交换、报文交换与分组交换
- 数据报和虚电路

## 传输介质

- 双绞线、同轴电缆、光纤与无线传输介质
- 物理层接口的特性

## 物理层设备

- 中继器
- 集线器

2.1 - 通信概念

通信指标

1. 信道 (Channel)：
   • 是指进行信息传输的媒介或路径。这可能是一个物理的媒介，例如电缆，或者是无线的，如无线电波。
2. 信号 (Signal)：
   • 是载有信息的物理现象。例如，电信号、光信号或无线电波。
3. 带宽 (Bandwidth)：
   • 描述的是信号的频率范围，或者更具体地说，是通信信道所能传输的最大数据速率。在计算机网络中，带宽通常用来指代网络的数据传输速率，单位可能是比特/秒（bps）。
4. 码元 (Symbol)：
   • 在数字通信中，码元代表一个信号或符号的特定状态。例如，对于二进制信号，一个码元可能表示一个比特，其值可以是0或1。
5. 波特 (Baud)：
   • 表示每秒传输的码元数。波特率和比特率不一定相同。例如，如果每个码元代表2比特，那么比特率是波特率的两倍。
6. 速率 (Rate)：
   • 是指数据的传输速度。常见的单位有比特/秒（bps）、字节/秒（Bps）等。
7. 信源 (Source)：
   • 产生或发送信息的设备或实体。
8. 信宿 (Sink or Destination)：
   • 是指接收信息的设备或实体。

速率可以用两种指标来衡量：

• 比特率：每秒传输的比特数量
• 波特率：每秒传输的波特数量

一个码元可以包含多个比特，如果一个码元携带 $n$ 比特的信息量，则波特率M对应的比特率为 $Mn$ bit/s

奈奎斯特定理

奈奎斯特定理说明了在 理想低通（没有噪声、带宽有限） 的信道中的数据极限传输速率，当传输速率小于等于该速率时，不会产生码间串扰。

奈奎斯特定理的核心思想是，为了正确地重构一个连续信号，需要以足够高的采样率对该信号进行采样。具体来说，奈奎斯特定理提供了以下关键观点：

1. 最低采样率： 奈奎斯特定理规定，为了准确地采样和重构一个连续信号，采样率必须至少是信号中最高频率成分的两倍（或更高）。这就意味着，如果信号的最高频率成分是 f，则采样率应该至少为 2f。
2. 奈奎斯特频率： 最高频率成分的一半，也称为奈奎斯特频率，是一个重要的参考点。信号的频率成分高于奈奎斯特频率的部分将无法正确地重构，导致混叠（aliasing）效应，损害信号质量。
3. 混叠效应： 如果采样率低于奈奎斯特频率的两倍，那么高于奈奎斯特频率的信号成分将在采样后出现混叠，即被误识别为低于奈奎斯特频率的信号成分，从而导致信息丢失和失真。

若 $W$ 是理想低通信道的带宽，则极限波特率为 $2W$ （单位为baud/s），若用 $V$表示每个码元离散电平的数据（$V$ 种不同的电平可以最多表示 $log_2{V}$ 个比特），则极限传输率为 $2W \cdot log_2{V}$ （单位为b/s）

香农定理

香农定理说明了在 有噪音干扰、带宽有限 的信道中的数据极限传输速率，当实际传输速率小于等于改速率时，可以做到不产生误差。

香农定理的核心思想是：在一个通信系统中，如果你知道了消息的概率分布以及系统的信噪比（Signal-to-Noise Ratio，SNR），那么你可以计算出一种编码方式，使得在给定的信噪比下，消息可以以极高的可靠性进行传输，同时使得信息传输的速率最大化。

具体来说，香农定理提出了以下几个重要概念和结论：

1. 信道容量（Channel Capacity）：信道容量是一个通信信道所能传输的最大信息速率。它取决于信道的带宽和信噪比，通常以比特每秒（bps）为单位来表示。
2. 香农公式：香农定理提供了一个计算信道容量的数学公式，该公式将信道的带宽和信噪比与最大信息传输速率联系起来。公式如下：

$$C = B * log_2(1 + SNR)$$

其中，$C$ 表示信道容量，$B$ 表示信道的带宽（单位为赫兹），$SNR$ 表示信噪比。

信噪比 $SNR$ 的计算方式为 $10 * log_{10}(P_s / P_n)$，其中 $P_s$ 是信号的功率，$P_n$ 是噪声的功率。

3. 编码定理：香农定理还指出，存在一种编码方式，使得可以接近信道容量的极限。这意味着通过合适的编码方法，可以在接近理论最大速率的同时保持通信的可靠性。

2.2 - 编码和调制

编码类型

调制方法

了解如下4中调制方法：

1. ASK (幅度偏移键控 - Amplitude Shift Keying)
2. FSK (频率偏移键控 - Frequency Shift Keying)
3. PSK (相位偏移键控 - Phase Shift Keying)
4. QAM (象限幅度调制 - Quadrature Amplitude Modulation)

2.3 - 交换方式

交换

1. 电路交换（Circuit Switching）：
   • 电路交换是一种传统的通信方式，最常见的例子是电话网络。
   • 在电路交换中，通信的两端建立一个物理连接，这个连接在通信会话的整个过程中保持打开，即使没有实际数据传输。
   • 通信资源（带宽）在建立连接时分配给通信各方，因此在通话期间一直被占用，即使不说话也占用资源。
   • 电路交换适用于对通信质量要求高、稳定性重要的应用，但效率较低，不适合数据传输等需要灵活带宽分配的应用。
2. 报文交换（Message Switching）：
   • 报文交换是一种通信方式，其中消息以整个报文的形式从源节点传输到目标节点。
   • 在报文交换中，消息从源节点发送到中间节点（交换节点），然后中间节点决定将消息转发到哪个目标节点。
   • 报文交换通常用于电子邮件系统和一些数据通信应用中。
   • 报文交换效率相对较低，因为整个报文必须接收后才能进行处理和转发，而不是逐比特或逐分组进行转发。
3. 分组交换（Packet Switching）：
   • 分组交换是一种现代的通信方式，它将数据分成较小的数据包（分组）并独立传输。
   • 数据包在网络中独立传输，可能通过不同的路径到达目标，然后在目标处重新组装。
   • 分组交换适用于大多数现代数据通信，包括互联网，因为它具有高效的带宽利用率、灵活的路由、容错性和适应性。
   • 常见的分组交换协议包括IP（Internet Protocol）。

数据包和虚电路

数据报和虚电路是两种不同的通信服务模型，适用于不同的通信需求和网络类型。数据报适合于互联网等不保证可靠传输的环境，而虚电路适合于对可靠性要求较高的电路交换和ATM等网络。选择合适的通信模型取决于应用需求和网络设计。

2.4 - 物理层设备

集线器

定义：集线器（Hub）是一个简单的物理层设备，用于将多台计算机或其他网络设备连接在一起，从而形成一个单一的网络段。

工作方式：当一个设备通过集线器发送数据时，数据会被广播到集线器的所有其他端口。每个连接到集线器的设备都会收到这些数据，但只有目标设备才会处理它。集线器本身不会分析或查看传输的数据。

局限性: 由于集线器将数据广播到所有设备，所以它可能导致网络拥塞。因此，在大型或流量较大的网络中，集线器已经被交换机所取代，交换机能够智能地将数据转发到目标设备。

中继器

定义：中继器是一个物理层设备，用于放大或再生数字信号。

工作方式：在以太网或其他类型的网络中，数据在电缆上只能传输一定的距离，超过这个距离，信号会减弱或退化。中继器放置在这种距离的两端，用于接收退化的信号，放大或再生它，然后将它传输到下一段电缆。

应用：中继器被用于扩展网络的物理范围，超出了单一段电缆或物理媒体的限制。

网络适配器

定义：网络适配器 (Network Adapter)，也称为网络接口卡（NIC）或简称网卡，是一种硬件组件，用于连接计算机或其他设备到一个网络。

工作方式：网络适配器为计算机提供了一个或多个网络连接端口，它将计算机的数字数据转换为可以在物理媒体（例如双绞线、光纤或无线电波）上传输的信号。同样，当信号从网络到达网络适配器时，它会将这些信号转换回计算机可以理解的数字数据。

物理地址：每个网络适配器都有一个唯一的物理地址，称为MAC地址。这个地址在生产时被烧录到设备中，用于在局域网内唯一地识别设备。

电缆

• 双绞线 (Twisted Pair)：双绞线由一对绝缘的铜线组成，两线之间呈螺旋形地绞在一起。
• 光纤 (Fiber Optic)：光纤是由极细的玻璃或塑料纤维制成的，用于传输光信号。
• 同轴电缆 (Coaxial Cable)：同轴电缆由一个中心铜导线、一个绝缘层、一个金属屏蔽和一个外部的塑料或橡胶覆盖层组成。

3 - 数据链路层

学习思维导图：

# 数据链路层

## 数据链路层的功能

## 组帧

## 差错控制

- 检错编码
- 纠错编码

## 流量控制和可靠传输机制

- 流量控制、可靠传输和滑动窗口
- 停等协议
- 回退N帧
- 选择性重传协议

## 介质访问控制

- 信道划分
- 随机访问：ALOHA, CSMA, CSMA/CD, CSMA/CA
- 轮询访问

## 局域网

- 基本概念和体系结构
- 以太网和IEEE 802.3
- 无限局域网和IEEE 802.11
- VLAN

## 广域网

- 基本概念
- PPP协议

## 数据链路层设备

- 以太网交换机和工作原理

数据链路层功能

1. 封装数据帧（Frame Encapsulation）：
   • 数据链路层将来自网络层的数据包封装成数据帧，这包括将源和目标地址添加到帧头部，以便在物理介质上的传输。
2. 数据帧传输（Frame Transmission）：
   • 数据链路层负责将数据帧从一个物理节点传输到另一个物理节点。这可能涉及到点对点的传输（例如，以太网）或多点广播传输（例如，Wi-Fi）。
3. 物理地址寻址（Physical Addressing）：
   • 数据链路层使用物理地址（通常是MAC地址）来标识设备。这些地址用于确定数据帧的目标设备。
4. 帧同步和定界（Frame Synchronization and Framing）：
   • 数据链路层确保接收端可以正确识别和分离不同的数据帧。这通常通过在帧的起始和结束位置使用特殊的比特模式来实现。
5. 流量控制（Flow Control）：
   • 数据链路层可以控制发送端的数据传输速率，以防止接收端不堪重负而丢失数据。这确保了适当的数据流量管理。
6. 差错检测和纠正（Error Detection and Correction）：
   • 数据链路层使用差错检测技术（如CRC校验）来检测帧在传输过程中是否受到损坏。一些数据链路层协议还可以进行错误纠正，尝试修复损坏的数据。

3.1 - 组帧

数据链路层的主要功能就是组帧

帧（frame）代表数据链路层的数据发送单位，在接收到来自于网络层的报文（packet）时如何为其添加帧头和帧尾，并且以何种方式进行帧定界（接收方区别连续不同的帧）。

组帧的关键就在于帧定界，也就是对于接收方来说，它能够以某种方式区分连续收到的不同帧。 从这个角度出发，组帧方式可以被分为以下几种：

字符计数法

字符计数法在帧首部使用计数字段来表明帧内字符数量。

当接收方读取帧时，根据读取帧开头的一部分内容，即可得知当前帧的长度是多少，这样就

首位定界字符法

首位定界字符法即 使用特殊控制字符标志帧的开始和结束。

但是使用这种方式可能出现如下问题：就是 首位定界字符 可能会在帧内部出现，这个时候就会造成歧义。

所以当特殊字符出现在帧的数据部分时，需要用转义字符ESC来对特殊字符进行转义，同样，ESC出现在数据部分同样需要转义。

以上图为例，假设我们使用 FLAG 作为首位定界字符的话（注意这里 FLAG 只是字符名称，不是表示字符是 FLAG），那么当 FLAG 出现在数据部分时，我们需要对 FLAG 进行转义，需要注意的是，因为我们使用 ESC 作为转义字符，所以当数据中出现 ESC 时，我们也需要对转义字符自己进行转义。

零比特填充法

零比特填充法（Bit Stuffing）与首位定界字符法思路类似。

用 01111110 作为一个新的数据帧的开头，这里的关键在于要对数据帧内容中与 01111110 相同的部分进行转义，转义的方式是如果碰到11111，就在后边添加一个0，接收方在处理接收到的数据时，需要进行反向处理，如果在数据部分碰到111110时，就要删除这个0。

在传送的比特流中可以传送任意比特组合，而不会引起对帧边界的判断错误。零比特填充法很容易由硬件来实现，性能优于字符填充法。

对于零比特填充法，需要记住 01111110 这种开头的比特填充方式 以及 具体如何进行转义。

违规编码法

违规编码法（Physcial Layer Coding Violations）使用特殊电平进行定界。比如，曼彻斯特编码将数据比特“1”编码为“高-低”电平，将比特“0”编码为“低-高”电平对，而“高-高”电平对和“低-低”电平对是没有被使用的，所以可以用这两个电平进行帧定界。

编码方式详见 编码和调制。

3.2 - 差错控制

分类

• 检错编码：奇偶校验码、循环冗余码
• 纠错编码：海明码

奇偶校验码

奇偶校验码（Parity Check Code）是一种错误检测机制，通常用于数据传输中，以检测传输过程中的单比特错误。奇偶校验码通过在数据中添加一个额外的比特（校验比特）来实现。这个校验比特的值被设置为确保数据中的所有比特（包括校验比特）的总数是奇数或偶数，具体取决于所选择的奇偶性规则。

奇偶校验码有两种常见的类型：奇校验和偶校验。

1. 奇校验（Odd Parity）：在奇校验中，校验比特被设置为确保数据中的所有比特的总数（包括校验比特）为奇数。如果在传输过程中某个比特发生了错误，导致总比特数变为偶数，接收端将检测到错误。
2. 偶校验（Even Parity）：在偶校验中，校验比特被设置为确保数据中的所有比特的总数（包括校验比特）为偶数。如果在传输过程中某个比特发生了错误，导致总比特数变为奇数，接收端将检测到错误。

奇偶校验的工作原理是发送端计算数据中所有比特的总数，并根据所选的奇偶性规则设置校验比特的值。接收端在接收数据后再次计算所有比特的总数，包括校验比特，然后检查总数是否满足所选的奇偶性规则。如果总数不符合规则，接收端将检测到错误。

循环冗余码

循环冗余校验（CRC）是一种常用的数据完整性校验方法，主要用于数据传输的错误检测。CRC 的核心思想是将数据看作多项式的系数，并用特定的生成多项式进行除法操作，得到的余数即为 CRC 值。

CRC 校验大致流程：

• 生成多项式：CRC 的核心是一个生成多项式，通常用二进制表示。这个多项式是事先定义好的，并且在发送端和接收端都必须知道。
• 帧校验码计算：为了计算 CRC 校验码，发送端将数据帧和生成多项式进行除法运算，得到余数，然后将余数附加到数据帧的末尾。如果生成多项式是 n 位长，那么 CRC 校验码将是 n-1 位长。
• 传输：将 CRC 校验码附加到数据帧的尾部，发送至接收端。
• 接收端校验：接收端接收到数据帧后，也执行相同的 CRC 校验操作。它将接收到的数据帧与生成多项式进行除法运算，得到一个余数。如果余数为零，表示数据帧没有错误。如果余数不为零，表示数据帧存在错误。

以一个实际例子说明 CRC 校验过程：

假设我们要发送的数据是：1010001101

我们选择的生成多项式是：110101，对应的是 $x^5 + x^4 + x^2 + 1$

发送方操作：

1. 为了进行校验码计算，首先在原始数据的尾部添加 k−1 个零（其中 k 是生成多项式的位数，这里是 4），所以数据变成了：1010001101 00000
2. 使用生成多项式除以这个新的数据。实际上，我们使用二进制的异或操作来进行模 2 除法。
3. 计算得到的余数就是 CRC。

              110101011
       ------------------
110101 | 101000110100000
         110101
         ------
          111011
          110101
          ------
            111010
            110101
            ------
              111110
              110101
              ------
                101100
                110101
                ------
                 110010
                 110101
                 ------
                   01110

将计算得到 CRC 01110 添加到数据后面一起发送，接收方接收到的数据为 101000110101110

接收方接收到数据后进行校验，计算过程如下：

              110101011
       --------------------------------------
110101 | 101000110101110
         110101
         ------
          111011
          110101
          ------
            111010
            110101
            ------
              111110
              110101
              ------
                101111
                110101
                ------
                 110101
                 110101
                 ------
                      0

计算得到余数为零，表示数据帧没有错误。

海明码

海明码（Hamming Code）是一种用于错误检测和纠正的编码方案，通常用于数据传输和存储系统中。它的主要目标是检测和纠正数据中的单比特错误。

海明码的核心思想是在数据位之间插入一定数量的校验位（也称为奇偶校验位），使得每个校验位都负责检查一组特定的位。校验位的数量取决于数据位的数量，并且它们的位置通常是2的幂次（即第1位、第2位、第4位……）。

以一个 实例 说明海明码的 生成和纠正 过程：

步骤 1：确定校验位数量

假如我们的数据是 $1011$ ，也就是 $4$ 位。根据海明码的原则，我们需要确定足够的校验位 $r$ 来满足以下条件：

$2^r \ge k + r + 1$

对于 $k = 4$ （数据位），我们找到最小的 $r$ 为 $3$

步骤 2：放置数据位

首先放置数据位 $d$ ：

• 第 $3$ 位（$2^0+2^1$）: 数据位 $d_1$
• 第 $5$ 位（$2^0+2^2$）: 数据位 $d_2$
• 第 $6$ 位（$2^1+2^2$）: 数据位 $d_3$
• 第 $7$ 位（$2^0+2^1+2^2$）: 数据位 $d_4$

将校验位（ $p$ ）插入到数据位中的适当位置。校验位位置通常是 $2$ 的幂（ $1, 2, 4, 8, …$ ）。

步骤 3：计算校验位

• $p_1 $ 检查位置 $1$ 、 $3$ 、 $5$ 、 $7$ 的位，因为它们的二进制表示中，最右边的位是 $1$ 。所以 $p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0$ ，所以 $p_1 = 0$ 。
• $p_2 $ 检查位置 $2$ 、 $3$ 、 $6$ 、 $7$ 的位，因为它们的倒数第二位是 $1$ 。这些位的异或值为 $p_2 = d_1 \oplus d_3 \oplus d_4 = 1 \oplus 1 \oplus 1 = 1$，所以 $p_2 = 1$ 。
• $p_3 $ 检查位置 $4$ 、 $5$ 、 $6$ 、 $7$ 的位，因为它们的倒数第三位是 $1$ 。这些位的异或值为 $p_3 = d_2 \oplus d_3 \oplus d_4 = 0 \oplus 1 \oplus 1 = 0$，所以 $p_3 = 0$ 。

步骤 4：生成海明码

所以， $1011$ 的 $(7,4)$ 海明码是 $0110011$ 。任何一位的单一错误都可以通过分析校验位来检测并纠正。

步骤 5：检测和纠正错误

假设在传输过程中第二位出现了错误，接收的码变为 $0010011$ 。接收者现在要检查每个校验位：

• $p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0$ (没有变化)
• $p_2 = d_1 \oplus d_3 \oplus d_4 = 1 \oplus 1 \oplus 1 = 1$ (错误)
• $p_3 = d_2 \oplus d_3 \oplus d_4 = 0 \oplus 1 \oplus 1 = 0$ (没有变化)

校验位 $p$ _ $2$ 错误，这告诉我们位模式 $ 2, 3, 6, 7 $ 中的某个位出错。因为只有 $p_2$ 指示出错误，我们可以断定是第 $2$ 位出错了。

要纠正这个错误，只需要改变第二位：

从：0 1 1 0 0 1 1
到：0 0 1 0 0 1 1

现在，海明码回到了正确的 $0010011$ 状态。

3.3 - 流量控制

Stop Wait

停等 (Stop-and-Wait) 是一种基础的自动重传请求 (ARQ) 协议。其基本思想是在发送每个数据帧后都停下来，等待接收方的确认。只有在收到确认后，发送方才会继续发送下一个帧。由于这种方法在任何时刻只允许一个帧在传输中，因此它被称为“停等”。

过程关键：

1. 发送数据：发送方发送一个数据帧到接收方，并启动一个计时器等待确认。
2. 等待确认：发送方在发送数据帧后处于等待状态，直到接收到确认或计时器到期。
3. 确认的接收：接收方在收到数据帧后，检查其完整性（例如通过校验和）。如果数据帧正确，接收方会发送一个确认帧回到发送方。
4. 计时器到期：如果发送方的计时器在收到确认之前到期，发送方会假设数据帧丢失或确认丢失，并重新发送数据帧。然后再次启动计时器。

GBN

在 回退N帧（GBN, Go Back N）协议中，发送方可以连续发送多个帧，而不需要等待每个帧的确认。但是，发送方需要为每个帧维护一个计时器。如果一个帧的计时器到期而没有收到确认，发送方会重新发送该帧及其之后发送的所有帧。

过程关键：

1. 窗口大小：在GBN中，若帧序号的比特数为 $n$，则发送窗口的最大值为 $2^n - 1$，接受窗口的大小为 $1$。
2. 发送过程：发送方连续发送窗口内的帧，每发送一个帧，都会为其启动一个计时器。
3. 接收过程：接收方只接收期望的帧序号。如果接收到的帧是期望的，它会发送一个确认。如果接收到的帧不是期望的（可能是由于前面的帧丢失），它会丢弃该帧并重新发送对上一个正确接收的帧的确认。
4. 超时和重传： 发送方通常只为 最早发送但未确认的帧（窗口内的第一个未确认帧）设置一个单一的超时定时器。 如果计时器到期，该帧及其之后发送的所有帧都会被重传。重传的原因是，如果一个帧丢失，后续的帧虽然可能已经到达接收方，但由于接收方的窗口大小为1，它们会被丢弃。
5. 滑动窗口：当发送方收到一个帧的确认，它知道该帧及其之前的所有帧都已正确接收。于是，它会将窗口向前滑动，从而可以发送新的帧。

通过GBN, SR交互演示你可以更好理解GBN、SR的过程。

SR

选择性重传(SR，Selective Repeat）是另一种自动重传请求 (ARQ) 协议，它旨在解决 Go-Back-N 协议在高误码率环境下的效率问题。与 Go-Back-N 不同，Selective Repeat 只重传那些确实丢失的帧，而不是所有之后的帧。这使得 SR 在高误码率环境下比 GBN 更为高效。

过程关键：

1. 窗口大小：在SR中，一般发送窗口和接受窗口大小一致，若帧序号的比特数为 $n$，则窗口大小最大为 $2^{n-1}$。
2. 发送过程：发送方连续发送窗口内的帧，并为每个发送的帧启动一个计时器。
3. 接收过程：接收方接收所有在其窗口范围内的帧，并为正确接收的每个帧发送确认。接收到的帧可能是乱序的，但接收方可以缓存这些乱序的帧，直到可以按正确的顺序将其传递给上层。
4. 超时和重传：如果发送方的某个帧的计时器到期，只有这个特定的帧会被重传，而不是所有的帧。这是 SR 与 GBN 的主要区别。
5. 滑动窗口：发送方和接收方的窗口都是动态移动的。当发送方收到一个帧的确认时，它会尝试滑动其窗口以发送新的帧。同时，接收方在将帧按正确顺序传递给上层后，也会滑动其窗口。
6. 处理冲突的确认：考虑到网络的延迟，发送方可能在超时并重传一个帧后才收到其早期版本的确认。为了处理这种情况，SR 协议需要具有识别和丢弃重复确认的机制。

对比

停等协议（Stop-and-Wait）、GBN（Go-Back-N）、SR（Selective Repeat）是计算机网络中用于可靠数据传输的三种流量控制和错误处理协议。它们的主要目标是确保在不可靠的通信信道上的数据传输的可靠性。

重点注意接收方和发送方的窗口大小范围。

窗口大小限制

$$\text{发送窗口大小} + \text{接受窗口大小} \le 2^n$$

滑动窗口协议是计算机网络中用于控制传输层数据流的一种机制。在这种协议下，发送窗口和接收窗口的大小有一个重要的限制，即它们的和不能超过序列号空间的大小。序列号空间是由能够用于标识帧的序列号的总数确定的，这通常是由序列号的位数决定的。

对于一个使用了 $n$ 位序列号的协议，序列号的范围是从 $0$ 到 $2^n-1$ 。因此，整个序列号空间的大小是 $2^n$ ，这意味着理论上最多可以有 $2^n$ 个不同的帧在传输中被唯一区分。

这个限制的主要原因是防止所谓的“序列号回绕”（Sequence Number Wraparound）。如果发送窗口和接收窗口的大小之和大于序列号空间的大小，那么就可能发生一个新的帧使用了一个老的、已经被使用的序列号，但是该帧可能还在网络中传输或者被延迟。接收方将无法区分这是一个新的帧还是重复的帧。

链路利用率计算

假设信号传播时间为 $T_p$，一个数据帧的传输时间为 $T_f$，确认帧一般不考虑传输时间因为比较小，则 $RTT = 2 \cdot T_p$。

对于停等协议，信道利用率：

$$ratio = \frac{T_f}{RTT + T_f}$$

对于使用了滑动窗口的协议，一次性可以传输 $N$ 个数据帧，则信道利用率：

$$ratio = \frac{N \cdot T_f}{RTT + T_f}$$

视频讲解

3.4 - 介质访问控制

共享介质

在介绍 MAC 概念之前，必须要说明一下共享介质的概念。

在一个网络环境中，多个设备可能需要同时访问同一个物理介质来发送数据，这个介质可以是电缆、光纤或者无线信道。

当设备发送数据时，数据包会在整个介质上传播，所有连接到该介质的设备都可以接收到数据包。如果多个设备同时发送数据，介质上的数据信号就会相互冲突进而导致错误。

所以 MAC 协议确保了 共享介质上的 有效、公正且有序的数据传输。

MAC方式总结

介质访问控制（MAC，Media Access Control）可以分为 信道划分 以及 随机访问 两种大方向。

信道划分 介质访问控制：也叫做多路复用，在一条传输介质上同时传输多个不同种类的信号（种类可以根据不同的参数进行划分），这样不同的设备可以发送特定类型的信号，并且不同信号之间相互不干扰，信道划分 访问控制可以分为以下几种：

• FDM：频分多路复用
• TDM：时分多路复用
• WDM：波分多路复用
• CDM：码分多路复用

随机访问 介质访问控制是指多台设备共享同一个通信介质时，它们可以随机地尝试发送数据，而不需要事先协调，当发生冲突后再做后续的协调，以保证不会接收到错误的数据。

• ALOHA
• CSMA
• CSMA/CD
• CSMA/CA

多路复用

1. 频分多路复用（Frequency Division Multiplexing，FDM）：
   • FDM是一种通过将频谱划分成不同的频率带宽块，使多个信号能够同时传输的方法。每个信号占用不同的频带宽度，以避免干扰。
   • 电视和广播广播中的不同频道，以及有线通信中的多频道宽带互联网，都使用了FDM。
2. 时分多路复用（Time Division Multiplexing，TDM）：
   • TDM是一种通过在时间轴上分割信号的方式，使多个信号能够依次传输的技术。每个信号在不同的时间段内传输，时间段通常非常短，以实现快速切换。
   • 电话网络中的T1和E1传输系统以及数字电视信号的传输都采用了TDM。
3. 波分多路复用（Wavelength Division Multiplexing，WDM）：
   • WDM是一种在光纤通信中使用的多路复用技术，它通过在光波的波长维度上分隔信号来允许多个信号共享同一光纤。
   • 长距离光纤通信网络中使用WDM来实现高容量数据传输。
4. 码分多路复用（Code Division Multiplexing，CDM）：
   • CDM是一种通过在传输中使用不同的编码序列来区分不同的信号的方式。每个信号都与一个唯一的编码序列相关联，以使接收器能够区分它们。
   • 无线通信中的CDMA（Code Division Multiple Access）是一种使用CDM的技术。

CDMA原理

在CDMA中，每一个比特时间划分为 m 个短的间隔，称为码片(chip)，每个站被指派一个惟一的 m bit 码片序列(chip sequence) 。

每个站被指派一个惟一的 m bit 码片序列(chip sequence) 。

• 如发送比特 1，则发送自己的 m bit 码片序列。
• 如发送比特 0，则发送该码片序列的二进制反码。

令向量 $S$ 表示站 S 的码片向量，令 $T$ 表示其他任何站的码片向量。两个不同站的码片序列正交，就是向量 $S$ 和 $T$ 的规格化内积(inner product)都是0：

$$S \cdot T = \frac{1}{m} \sum_{i=1}^{m}{S_i T_i} = 0$$

任何一个码片向量和该码片向量自己的规格化内积都是1：

$$S \cdot S = \frac{1}{m} \sum_{i=1}^{m}{S_i^2} = 0$$

ALOHA协议

1. 纯ALOHA (Pure ALOHA)

工作原理：

• 当一个站点有数据要发送时，它会直接发送数据。
• 发送完成后，该站点会等待一个预定的时间间隔，以便接收来自接收方的确认。
• 如果在此时间段内未接收到确认，站点会假定数据已冲突并被损坏，因此它会在随机的后续时间重新发送数据。

2. 时隙ALOHA (Slotted ALOHA)

工作原理：

• 与纯ALOHA不同，时隙ALOHA将时间分为固定的时隙或间隔。
• 站点只在时隙的开始时发送数据，这减少了两个数据包可能在同一时间内发送的机会，因为它们必须在时隙边界上对齐。
• 如果数据冲突（多个站点在同一时隙发送数据），发送站点会在随机的后续时隙重试。

CSMA协议

CSMA（Carrier Sense Multiple Access）的中文叫做 载波监听多路访问，理解 CSMA 的关键在于理解它的名称中的两个部分：载波监听 以及 多路访问：

• 载波监听（Carrier Sense）：因为 CSMA 是随机访问介质控制的一种方式，所以在发送数据前，必须确定当前通信介质中没有其他设备正在发送数据。所以载波监听可以被理解为以太网口内部芯片自带的一种功能，具体而言就是一种可以监听 信道在当前位置是否有数据传输的 的一种功能。
• 多路访问（Multiple Access）：多个设备可以访问同一个通信介质。这意味着在任何给定时间，任何设备都可以尝试发送数据。

所以 CSMA 可以理解为 通过 载波监听 避免冲突，进而实现共享介质上的 多路访问。

以下图为例，A、B、C、D 分为是连接到同一共享介质上的不同设备，当 A 开始发送数据时，B、C、D 分别会在不同的时刻监测到信号，具体的时刻为 设备与A之间的距离 / 信号传播速度。

CSMA 的问题在于它无法处理碰撞，当一个设备监听到当前介质中无信号时，它就可以发送数据，但监听得到的结果可能是 “假结果”。因为有可能其他设备已经发送信号了，只是信号由于传播时延还没有到达当前设备。

所以假设当前设备监听得到了 “假结果”，那么此时发送数据后介质上就会发生冲突。

CSMA 也 根据其在信道空闲时的行为分为三种类型，如下所示，了解即可。

CSMA/CD协议

CSMA/CD （CSMA with Collision Detection，载波监听多路访问/碰撞检测） 是 CSMA 的一种拓展，在了解这个知识之前，请确保你已经明晰了什么是 CSMA 中的 CS（Carrier Sense 即 载波监听），以及什么是 CSMA 中的 MA（Multiple Access 即 多路访问）。

CSMA/CD 比 CSMA 多出一个 CD（Collision Detection 即 碰撞检测）的功能。 在上文中我们提到，CSMA 中监听到信道空闲可能是 “虚假的”，所以在 CSMA 发送数据后介质中也许会发生冲突，但 CSMA 只能依靠非常原始的方案处理冲突。

CSMA/CD 就高级一些，在发送数据期间，我们刚刚提到的 监测器件（Carrier，就是 CSMA 中 C 的简称）会一直监听有没有冲突发生， 如果有冲突的话，就等待一段随机的时间，然后重试以上过程，并且发送一个特殊信号告诉其他设备发生了冲突。

上图说明了 碰撞检测的功能，这里需要内化 传播时延和传输时间 这两个概念：

• 传输时延 = 距离 / 信号传播速度
• 传输时间 = 数据大小 / 数据传输速率

碰撞发生的时间和检测到碰撞的时间是不一样的，在上图中竖线表示时间轴，通过时间轴我们可以得知某个事件发生的时间。

这里再总结一下 CSMA/CD 的流程：

1. 监听信道（Carrier Sense）：设备在尝试发送数据之前首先监听物理信道，检查是否有其他设备正在传输数据。如果信道忙，则设备等待，直到信道变为空闲。
2. 等待随机时间（Backoff）：如果信道忙，设备会随机选择一个退避时间（Backoff time），然后等待该时间段，以便稍后重新尝试发送数据。这个随机等待时间有助于减少碰撞的概率，因为不同设备的退避时间可能不同。
3. 发送数据：当设备检测到信道为空闲时，它可以开始发送数据帧。设备发送数据时会继续监听信道，以检测是否发生碰撞。
4. 碰撞检测（Collision Detection）：如果两个或多个设备同时发送数据并发生碰撞，它们会检测到碰撞并立即停止发送。这是通过在发送过程中持续监听信道来实现的。如果设备在发送数据时检测到信道上的信号强度增加（即碰撞），它会立即停止发送，以避免数据损坏。
5. 碰撞处理：一旦设备检测到碰撞，它会发送一个特殊的信号（碰撞信号）通知其他设备发生了碰撞。所有参与碰撞的设备将等待一段随机的时间，然后重新尝试发送数据。
6. 重传数据：设备在等待随机时间后，会重新尝试发送数据。如果再次发生碰撞，设备将重复上述碰撞处理步骤，直到成功发送数据或达到最大重传次数（通常是16次）为止。
7. 成功发送或放弃：如果设备成功发送数据（即没有发生碰撞），接收设备将确认数据的接收。如果设备多次尝试发送数据但仍然无法成功，它最终会放弃发送，以避免网络过度拥塞。

CSMA/CA协议

CSMA/CA（Carrier Sense Multiple Access with Collision Avoidance）是一种用于无线局域网（如Wi-Fi）中的协议，用于协调多台无线设备共享通信媒体的访问。与CSMA/CD不同，CSMA/CA采用碰撞避免而非碰撞检测的方式来管理共享媒体。以下是CSMA/CA的主要过程：

1. 侦听信道（Carrier Sense）：当一个设备想要传输数据时，它首先侦听信道，检查信道是否忙碌。如果信道被其他设备使用，当前设备会等待一段随机的时间再次检测信道是否空闲。这是为了避免同时尝试发送数据而导致碰撞。
2. 发送请求（Request to Send，RTS）：如果信道在一段时间内保持空闲，设备可以选择发送一个RTS帧，该帧包含了将要传输的数据的信息。这个RTS帧通知其他设备，该设备打算发送数据，以防止其他设备在此期间发送数据。
3. 清除发送请求（Clear to Send，CTS）：如果其他设备接收到RTS帧并且信道仍然空闲，它会发送CTS帧作为响应。CTS帧确认了该设备的数据传输请求，并告诉发送设备可以开始传输数据。
4. 数据传输：一旦设备收到CTS帧，它可以开始传输实际的数据帧。其他设备会侦听传输，以确保不会干扰正在传输的设备。
5. ACK帧（Acknowledgment）：接收设备在成功接收到数据后发送一个ACK帧，以通知发送设备数据已被成功接收。如果发送设备没有收到ACK帧，它会假定数据包已丢失，然后根据需要重新传输数据。

视频讲解

3.5 - 局域网和广域网

局域网

以太网

传输介质

• 注意字母 T 是 twisted pair 的首字母，含义是双绞线。
• FL 是 Fiber optic 的缩写，含义是光纤。

帧格式

如上图所示，以太网帧格式从逻辑上可以分为物理层控制字段、帧首部、数据负载、差错校验字段这四个部分，每个字段的具体说明如下所示：

• 物理层控制字段
  • 前导码（Preamble）：7B
    • 由7字节的交替的1和0位组成，用于同步接收方的时钟。
  • 帧开始分隔符（Start of Frame Delimiter, SFD）：1B
    • 通常为10101011，标志帧的开始。
• 帧首部： 固定为14B
  1. 目的地址（Destination MAC Address）：6B
     • 指定帧的接收者的物理MAC地址。
  2. 源地址（Source MAC Address）：6B
     • 指定帧发送者的物理MAC地址。
  3. 类型/长度字段（Type/Length）：2B
     • 如果值大于或等于0x0600（1536），则表示帧携带的数据的类型（例如IPv4、IPv6、ARP等）。
     • 如果值小于或等于0x05DC（1500），则表示数据字段的长度。
• 负载
  • 数据和填充（Data and Padding）： 范围为46-1500B
    • 携带帧的有效载荷，即要传输的数据。
    • 如果数据少于46字节，则需要填充，确保数据字段的最小长度为46字节。
• 差错校验字段
  • 帧校验序列（Frame Check Sequence, FCS）：4字节：
    • 一个循环冗余校验（CRC）值，用于错误检测。接收方计算帧的CRC，并与这个字段进行比较，以确定帧是否在传输过程中被损坏。

无线局域网

• To DS（To Distribution System）：表示帧是从一个设备（通常是一个Wi-Fi客户端）发送到分布系统（Distribution System），也就是Wi-Fi接入点（AP）或Wi-Fi路由器。这是常用的值，用于表示数据流从Wi-Fi客户端发送到AP或路由器。
• From DS（From Distribution System）：表示帧是从分布系统（通常是AP或路由器）发送到一个设备（Wi-Fi客户端）。这个方向的帧通常用于将数据从AP或路由器传输到Wi-Fi客户端。
• address1: RA(receiver address)，接收方地址
• address2: SA(source address)，发送方地址
• address3: DA(destination address)，目的地地址

广域网

PPP协议

PPP（Point-to-Point Protocol）是一种数据链路层协议，用于在两个点对点连接的网络之间传输数据。PPP最初是为拨号连接设计的，但它后来被广泛用于建立各种类型的点对点连接，包括DSL（数字用户线路）、ISDN（综合业务数字网）和串口连接等。

3.6 - 数据链路层设备

网桥

• 工作原理：网桥根据目的MAC地址来决定是否将数据帧从一个接口转发到另一个接口。当一个数据帧进入网桥时，它会检查数据帧的目的MAC地址，然后将其转发到适当的接口，以便数据帧到达目标设备。网桥还可以学习MAC地址，并维护一个MAC地址表，以便更智能地转发数据帧。
• 功能：网桥主要用于连接两个或多个局域网段，使它们能够在同一网络中通信。网桥帮助减少了网络中的碰撞域（collision domain），提高了网络性能。

在过去，网桥是用来连接不同的物理媒体类型，例如以太网和令牌环。然而，现代交换机已经取代了许多网桥的功能，因为交换机通常更智能、更高效。

交换机

• 工作原理：交换机使用MAC地址表来确定将数据帧从哪个接口转发到哪个接口。当数据帧到达交换机时，交换机会查找MAC地址表以查找目标设备的位置，并将数据帧仅发送到目标设备所连接的接口，而不是广播到整个网络。
• 功能：交换机提供了更快的数据帧传输速度和更低的碰撞域，因为它只将数据帧传输到需要的接口，而不是广播到整个网络。这提高了网络性能和带宽利用率。