漫游计算机网络之技术篇

其实完全可以放在《协议篇》里，确信。不过为方便对比分析，所以单开一篇 来水 了。

Retransmission 重传机制

1. 概述

1. 哪些层需要进行重传？

即答：数据链路层 and 传输层；

2. 数据链路层的重传

ARQ 技术，即 Automatic Repeat Request ，自动重传请求。当物理层出现传输误码时，数据链路层需要对错误进行恢复。由于一般采用检错码，所以需要发送方对出错的数据进行重传，并且重传是发送方自主完成的。

3. 传输层的重传

本质上也用到了 ARQ ，但使用了一些机制用于优化重传。

3.1 超时重传

就是普通的重传，重传计时器 RTO 超时，重传对应的数据包。

3.2 快速重传

优化前者，当发送方连续收到 3 个重复的 ACK ，它就知道该包可能丢了，于是无需等待该包的 RTO 超时就直接进行重传。

3.3 SACK 选择确认

接收方在 TCP Header 的选项字段添加 SACK ，告诉发送方自己已经接收到哪些数据，这样发送方就只需重传特定的数据。

3.4 Duplicate SACK

简单来说，就是让发送方知道自己是否发送了重复的数据包。

Timer 定时器管理

1. 概述

1. 哪些层有定时器

事实上，除了物理层之外，其上每一层都有定时器，只不过有些并不明确把它当作一个定时器，但是事实上也发挥了定时器的功能。

2. 数据链路层的定时器

1. Frame Timer 帧计时器：每一个帧在发送时启动一个对应的重传计时器，若超时还没收到 ACK 则重传该帧；
2. ACK Timer ACK 计时器：在收到帧后不直接回送 ACK ，如果在 ACK_Timer 超时前有数据需要发送，则捎带 ACK ，若超时，则单独发送一个 ACK 帧；用于延时确认，减少了单独的 ACK 帧数量，提高了网络效率

无线通信中，虚拟载波监听技术还有 NAV 网络分配向量 ，站点维护一个 NAV ，表示需要退避的时间。

3. 网络层的计时器

比如 IPV4 包的 TTL 字段， ICMP 报文的超时反馈也涉及 TTL ，部分路由协议中的周期性广播等。

4. 传输层（TCP 协议）的计时器

传输层的计时器以 TCP 协议为主，TCP 协议也是计时器最复杂的协议之一。

• Retransmission Timer 重传计时器：即 RTO ，超时重传计时；
• Persistence Timer 持续计时器：用于周期性地进行窗口探测，防止窗口为 0 的死锁；
• Keepalive Timer 保活计时器：当另一方始终静默时，发送一个包试探其是否还处于通信状态，防止半开连接；
• Time-Waited Timer 等待时间计时器：
  • Time-waited State：当主动关闭连接的一方（即先发 FIN 的那一方）在完成 TCP 四次挥手后，会进入一个叫做 TIME_WAIT 的状态；
  • 该状态通常会持续一段时间，其值一般为 TIME_WAIT = 2 × MSL（Maximum Segment Lifetime），即最大报文生存时间的 2 倍；
  • 作用一是确保对方正确收到了 ACK ，双方都正确关闭连接（为自己第一次发送的 ACK 丢失，对方重发 FIN ，自己重新回 ACK 预留时间）；
  • 作用二是防止混入新的连接，确保连接已经完全关闭；

4.1 RTO 计时器的设置

由于网络情况顺序万变，RTO 本来略大于 RTT 即可，但是 RTT 动态变化，所以 RTO 也需要进行相应调整。

SRTT 平滑 RTT 计算

SRTT = $\alpha$ $\times$ SRTT $+$ $(1 - \alpha)$ $\times$ New_Sample ，一般取 $\alpha = \frac{7}{8}$ ；

RTTVAR RTT 偏差计算

RTTVAR = $\beta$ $\times$ RTTVAR + $(1-\beta)$ $\times$ |SRTT - Sample| ，一般取 $\beta = \frac{3}{4}$ ；

RTO 计算

RTO = SRTT + 4 $\times$ RTTVAR ；

信道共享算法

我们仅看时分复用的部分：

• 静态信道分配算法（同步时分复用）：将信道划分为多个子信道使用，e.g. PCM；
• 动态信道分配算法（异步时分复用）：
  • 受控多路访问控制：
    • 轮询 Polling（中心式控制）；
    • 令牌 Token（分布式控制）；
  • 随机多路访问控制：
    • ALOHA ；
    • CSMA ；
    • CSMA/CD ；
    • CSMA/CA ；

1. 评价信道共享算法的指标

低负载情况下的时延和高负载下的吞吐量（或信道利用率）；

注：低负载下适合用竞争的方法（即 1-persistent CSMA）；而 p 越小，负载高时，发送帧的随机化越好，冲突越小，吞吐量越高；

2. ALOHA

2.1 Pure ALOHA

• 任何时刻想发就发；
• 没收到 ACK ，则随机等待一段时间，再进行重传；
• 脆弱期 = $2t_{trans}$ ；

2.2 Slotted ALOHA 时隙 ALOHA

• 只能在每个时隙的开始时刻发送数据；
• 需要统一的时钟管理；
• 脆弱期 = $t_{trans}$ ；

3. CSMA 载波监听多路访问

• 发前先听：
  • 若信道空闲则以一定概率发送；
  • 发信道正忙则等待直至空闲；
  • 发出一段时间后没收到 ACK ，则重传；
• 脆弱期 = $t_{prop}$ ；

3.1 常见类型

• Nonpersistant CSMA 如果监听到信道正忙，那它会等待一个随机时间后在进行监听；
  • 高负载时，有较高的吞吐量；
• Persistant CSMA 如果监听到信道正忙，会持续监听到信道上没有信号，然后以一定的概率 $p$ 发送；
  • 1 - Persistant CSMA：$p = 1$，即监听到信道上没有信号就发送；
    • 低负载时，能有较低的时延和较高的吞吐量；
    • 高负载时，吞吐量较低；
  • p - Persistant CSMA：以一定的概率 $p$ 发送；

简单来说，当 $p$ 较小时，高负载情况下，有较好的随机化，冲突概率小，表现更好。

4. CSMA/CD 带冲突检测的 CSMA

4.1 特点

• 半双工 Half Duplex ：即同一个站点同一时刻只能作为发送方或接收方；
• 经典以太网使用；

4.2 基本步骤

1. 载波监听；
2. 发送方检测冲突；
3. 冲突检测：当发送方检测到冲突时，停止传输，并发送一个 Jam Signal(强化信号)；
4. backoff 退避：当发送方接收到 Jam 强化信号后，等待一个随机时间在恢复发送；（目的是避免两个发送方同时检测到冲突并进行退避后，监听到信道空闲又发送导致再一次冲突）

4.3 一些注意点

• 发送方来检测冲突；
• 如何检测？
  • 通过一条收线，从总线上读取数据，比较是否与自己发送出去的数据相同；
  • 不适用于无线通信，原因：
    • 无线通信收到的信号可能比原信号弱很多；
    • 无线通信的信号分为不同的频段，站点并不一定能收到全部的频段；
    • 隐藏终端和暴露终端问题；
• 发现冲突的时间 = $2t_{prop}$ ；
• 采用随机指数退避；
  • 一般最多尝试 16 次，超过则认为失败；
  • 指数达到 10 后不再增加；
  • 基础退避时间 = 51.2 us ；

5. CSMA/CA

5.1 无线通信中的问题

5.1.1 Hidden Terminal 隐藏终端

隐藏终端问题是与正在通信的工作站距离较远时无法判断其正在通信，此时发数据会在接收站产生干扰，如下图：

5.1.2 Exposed Terminal 暴露终端

暴露终端问题是与正在通信的工作站距离较近但与接收站点距离较远，此时发数据不会产生干扰，但是暴露终端会错误的认为存在干扰。

5.1.3 解决方法 —— MACA

MACA ，即 Multiple Access Collision Avoidance ，冲突避免多路访问。通过 RTS 和 CTS 帧来预约信道，也可以理解为是一个握手的过程。

简单来说，暴露终端只会收到 RTS ，隐藏终端只会收到 CTS ，都会保持沉默。一种特殊情况是两个站点同时向同一个站点发送 RTS ，此时目的站点先回复先收到的 RTS ，另一个发送站点发现一定时间未收到 CTS ，则采用指数退避。

注：MACA 只是早期提出的一种理论，基于 RTS / CTS 来避免碰撞，并非标准。

5.2 CSMA/CA 的工作流程

对于发送方：

1. 通过载波监听等待直到信道空闲，并在等待 DIFS 的时间（即在 DIFS 时间内信道空闲，才认为信道空闲，能发送数据）；
2. 随机退避（0 ～ 15 个时间槽），如果在退避时间内信道变为忙碌，设备会停止退避并持续监听，等到信道再次空闲并经过 DIFS 时间后，重新启动退避计时器，直到退避时间结束且信道空闲才发送数据；
3. 如果没有收到 ACK ，那么采用指数退避，加倍退避时间；

对于接收方：

4. 如果正确接收到帧，则等待 SIFS 的时间后回复ACK；

注：$t_{SIFS} < t_{DIFS}$，这能保证 ACK 的优先级更高；事实上，可以通过为不同类型的帧设置不同长度的 IFS 帧间隔，来实现优先级服务；

Error Control 差错控制

1. 哪些层需要差错控制？

数据链路层 and 传输层；

注：网络层中，IPv4 Header 虽然也有 Checksum 字段，但它只对头部做校验，确保路由器转发正确，并不校验数据部分，也不进行重传，只是尽力而为，所以没有差错控制。到 IPv6 直接把该字段舍去了。

2. 数据链路层的差错控制

2.1 Error Detection 检错码

仅加上有限的冗余位，用于接收方判断是否出错，但没有纠错能力。

• 奇偶校验码（Parity check）；
• 校验和（Checksum）；
• 循环冗余校验码（CRC）；

会计算 CRC ：

• 看给出的多项式$G(x)$的最高位$r$，则在数据位后添加$r$个$0$后再进行除法；
• 这里的除法不同于常规的多项式除法，是模2除法，即按位异或；

2.2 Error Correction 纠错码

纠错码是指在发送端在发送的信息中采用相关算法加上足够多的冗余信息，使接收端不 仅可以判断接收的信息有误码，还可纠正出现的错误。

2.2.1 纠正单比特错误的汉明编码

1. 首先计算需要的校验位位数：

• $m$：原始信息长度；
• $r$：check bits，即需要增加的校验位长度；
• $n$：码字长度，即$n = m + r$；

根据原始信息长度，可推出存在 $2^m$ 合法信息，每一个合法性信息按照码字传输，会产生单比特错误的信息 $n$ 个，所以共存在 $(n + 1)2^m$ 个码字。

为确保能纠正单比特错误，需要保证 $(n+1)2^m\le2^n \Rightarrow m + r + 1\le 2^r$ ，即合法的码字和不合法的码字不重叠；

2. 计算校验位（偶检验 or 奇检验）并在 2 的幂次位置插入校验位；

2.3 检错和纠错能力

检错和纠错能力与汉明距离有关。

• 汉明距离 = $d + 1$ $\Rightarrow$ 可以检查出 $d$ 比特错误；
• 汉明距离 = $2d + 1$ $\Rightarrow$ 可以纠正 $d$ 比特错误；

3. 传输层的差错控制

主要就是 TCP 和 UDP 报头中的 Checksum 字段。

Flow Control 流量控制

1. 概述

1. 哪些层需要流量控制？

即答：数据链路层 and 传输层；

2. 流量控制的作用？

即答：对于数据链路层，防止链路发送方淹没接收方；
对于传输层，防止发送主机淹没接收主机；

3. 传输层和数据链路层的流量控制有什么区别？

比较项	数据链路层流量控制	传输层流量控制
作用范围	相邻两个节点（点到点）	端到端（主机到主机）
主要对象	控制链路发送方别淹没接收方	控制发送主机别淹没接收主机
典型协议/机制	HDLC 和 PPP 协议的滑动窗口机制、Gbit 以太网Pause帧	TCP 滑动窗口
依赖的上下文	链路速度、网卡缓存	应用层速率、操作系统缓存
是否感知整体路径	只感知本地链路	感知整条路径的接收端
是否跨路由器	不跨路由器	会跨多跳路由器
可靠性机制	有时包含确认和重传	包含确认、重传、窗口管理

2. 数据链路层的流量控制

2.1 滑动窗口机制

主要包括基本的停等协议，GBN 协议和 SR 协议。考点的话一般包括滑动窗口大小的计算、序列号所需比特数的计算以及对应协议效率的计算。

机制	停等协议	1-bit 滑动窗口	GBN 协议	SR 协议
通信模式	Simplex	Duplex	Duplex	Duplex
Seq Bit	1	1	n	n
$W_T$	1	1	>1	一般默认 = $2^{n-1}$
$W_R$	1	1	=$2^n-1$	= $2^{n-1}$

注：需要满足 $W_T + W_R \le 2^n$ ；

2.2 协议效率计算

• 发送时间，或称传输实验，即数据装载到信道上的时间为 $t_{trans}$ ；
• 传播时延为 $t_{prop}$ ；
• 令 $\alpha = \frac{t_{prop}}{t_{trans}}$ ；
• 单个帧的有效传输时间即为 $t_{trans}$ ，采用 ACK 确认需要花费的总时延为 $t_{trans} + 2t_{prop}$ ，即单独的 ACK 帧较小，传输时间可以忽略；
• 当采用 Piggybacking 机制时，由于 ACK 帧和数据一起发送，传输时间并不能忽略；

1. 仅采用 ACK 确认：$U = min\{100\%, \frac{W_T}{1 + 2\alpha}\}$ ；
2. 采用捎带确认时，$U = min\{100\%, \frac{W_T}{2 + 2\alpha}\}$ ；
3. 以上均未考虑有错信道；

2.3 G 比特以太网中的流量控制

进化到 G 比特以太网（全双工通信时）后，由于传输速率过快，接收方极短的 CPU 忙碌就会造成大量帧的堆积，占满缓冲区，接收方此时会向发送方发送一个 Pause 帧，发送方收到后，暂停数据发送。

3. TCP 的流量控制

TCP 的滑动窗口大小并不是帧的数量，而是面向字节的，以字节数为单位，题目中一般认为窗口大小 = n $\times$ MSS Bytes ；同时 TCP 的窗口大小是动态变化的，适用于多样和复杂的网络环境。

问题：流量控制和拥塞控制有何区别？

首先，流量控制仅发生在发送方和接收方之间，流量控制是确保让发送方发送的数据不至于淹没接收方，能根据接收方的实际接收能力发送数据。

拥塞控制考虑整个网络的拥塞情况，网络拥堵，TCP 包无法到达，进行重传，进一步加重拥堵，所以在网络拥塞时，同样需要发送方调整发送速率，避免发送方的发送的数据填满整个网络，加重网络负担。

3.1 工作机制

窗口滑动的操作与数据链路层是类似的。关于动态调整窗口大小的过程，简单来说，当接收方收到 TCP 报文后，存入操作系统缓冲区，不过受限于上层的处理能力，并不一定一次性读取所有数据并前移接受窗口，如果当前接受窗口减小了，会在回复的 ACK 包中的 Window Size 字段指明接收方的处理能力，发送方在收到 ACK 包后，根据接受窗口的大小调整发送速率。

3.2 隐患一、窗口关闭的死锁

3.2.1 病症

试想如果接收方的应用层处理能力太逊了，窗口大小减着减着减到 0 了，此时接收方通知发送方窗口为 0 关闭，此时发送方不能再发送数据。

当然，当接收方窗口恢复时，它会发送 Window Update 包通知发送方可以继续发送数据，但是这个包并不需要发送方确认，如果丢了，发送方认为接收方窗口仍关闭，接收方认为发送方确实没数据要发，两边就死锁了。

3.2.2 解决方案：窗口探测包

一句话：Window Probe 包 + Persistence Timer 持续计时器！

在接收方窗口关闭之后，发送方会周期性（即 Persistence Timer 的时限）地向接收方发送一个 Window Probe 包，试探接收方是否在线，直到收到接收方的回复。

3.3 隐患二、糊涂窗口综合症

3.3.1 病症

1. 和上述情形类似，接收方应用层的处理能力有限，导致接收窗口不断减小，并不断通知发送方，使得发送方不断发送小包，浪费带宽。
2. 也有可能发送方的应用层需要发送的数据就是小包。

3.3.2 解决方案：Nagle && Clark 算法

1. 发送方：Nagle 算法，即延迟发送小包
   • 当满足以下条件才发送窗口数据：
     • 收到之前发出的包的 ACK 帧；
     • 缓存的小包大小达到发送窗口大小的一半；
     • 缓存的小包大小超过 MSS ；
   • 需要接收方配合，不回复小包的 ACK ；
2. 接收方：Clark 算法，即延迟通知窗口更新
   • 当满足以下条件才通知窗口更新：
     • 接受窗口的大小超过 MSS 长度；
     • 接受窗口的大小超过一半，即一半空闲了；

Congestion Control 拥塞控制

1. 概述

1. 哪些层需要拥塞控制？

即答：网络层 and 传输层；

2. 拥塞控制的作用？

即答：都是为了减轻网络的拥塞状态；

3. 网络层和传输层的拥塞控制有何区别？

比较项	网络层	传输层
控制位置	路由器	通信两端
控制对象	链路拥塞、队列	数据发送速率
控制手段	丢包、标记、负载均衡	慢启动、窗口调整等
控制范围	局部链路	整体连接
是否需要路由器支持	是	否（也不能否定吧，路由器标记 ECN 也是间接来通知两端的传输层）

虽说控制范围不同，但本质上都作用于整个网络，防止整个网络过于拥塞而“雪崩”。

2. 网络层的拥塞控制

2.1 概述

网络层事实上的主要作用是 “感知和通知” 拥塞，不过也有控制手段，主要防止网络层中的链路或节点（主要是路由器）被数据淹没，手段要么及其简单粗暴（粗粒度的），要么就是间接调控。主要分为以下 5 种；

1. 网络供给 Networking Provision；
2. 业务感知路由 Traffic aware-routing；
3. 准入控制 Admission control；
4. 流量限制 Traffic throttling；
5. 负载掉落 Load shedding；

• 前 2 种属于增加资源的操作，后 3 种属于减少负载的操作；
• 前 3 种属于预防性措施，后 2 种属于反应性措施；

2.2 流量限制/业务量调节 Traffic throttling

1. 检测拥塞：通过链路利用率、队列长度、丢包数量或估计队列延时；
2. 通知拥塞：
   1. 路由器直接向发送方发送 Choke Packet 抑制分组；
   2. 显示拥塞通知：IP 协议来操作！将 IP 包中的 ECN 字段置位，会间接通知传输层；
   3. 隐式拥塞通知：详见 TCP 协议，通过超时 Timeout 来判断；
3. 响应拥塞：发送方通过调整发送窗口调整发送速率；

2.3 负载掉落 Load shedding

2.3.1 RED 随机早期检测

RED ，即 Random Early Detection ，顾名思义，就是路由器在完全失效前，就开始随机丢弃队列中的一部分分组。

3. 传输层的拥塞控制

3.1 概述

相较于前者，传输层的拥塞控制就比较细致了，并且它事实上也使用到了 IP 协议的部分功能，以下是几种典型机制。

3.2 一些泛用的机制

3.2.1 最大最小公平性

1. 有什么用？

用于拥塞控制中的资源分配问题。在数据流共享链路的情况下，不让“独占”或“饿死”的情况发生，最大可能的实现公平。

2. 基本思想？

如果不能再增加某个流的带宽，除非减少另一个带宽小于或等于它的流的带宽，那就是最大最小公平。

3.2.2 AIMD 加法增乘法减

1. 基本思想？

网络进入拥塞是很容易的，但是从中恢复却很难，所以递增过程应该平缓，递减过程应该激进。

2. 怎么做？

评价是理解下图即可：

3.3 TCP 和 IP 层的联动

我在前面提到了路由器检测到拥塞后会将 IP 包中的 ECN 字段置位，接受端收到该 IP 包后，发现 ECN = 11 ，会将回送给发送端的 TCP 报文头的 ECE(ECN Echo 回声) 设置为有效，发送端收到后，会将发送给接收端的 TCP 报文头的 CWR(Congestion Window Reduce 拥塞窗口减小标志) 设置为有效，告诉接收方我已经响应拥塞了，并减小窗口。

一句话，接收方设置 ECE ，发送方设置 CWR 。

3.4 TCP 的拥塞控制算法

TCP 通信中，在发送窗口 swnd 和 接收窗口 rwnd 的基础上，又新增了一个拥塞窗口 cwnd ，由发送方维护。

$$swnd = min\{rwnd,cwnd\}$$

注：看清题目问的是发送窗口还是拥塞窗口怎么变。

需要注意以下提到的各种算法一般是结合使用的，即 TCP Reno 。

3.4.1 慢启动 Slow Start

1. 初始化 $cwnd = 1$ ；
2. 指数增加，第 $i$ 个 RTT 时，$cwnd = 2^i$ ；
3. 当 $cwnd \ge ssthresh$ ，即超过慢启动门限时，转 3.3.2 拥塞避免算法，或者直接称其为 AI(Additive Increase 线性增长)；

3.4.2 拥塞避免算法 —— AI

1. cwnd 达到慢启动门限时，每个 RTT 时间，线性增长，即 $cwnd+=1$ ；
2. 也可以这么理解，达到阈值后，每收到 1 个 ACK ，$cwnd += \frac{1}{cwnd}$ ；

无论有无达到门限，在发生严重拥塞，即重传计时器超时时，都转入 3.3.2 ；

3.4.3 拥塞发生 —— MD

MD ，即 Multiplicative Decrease ，乘法减少，在拥塞发生时，需要迅速减小发送速率。

1. 重传计时器超时，$cwnd = 1,ssthresh = \frac{1}{2}cwnd$ ；
2. 重新进入慢启动状态；

3.4.4 快速恢复

快速恢复事实上是与快速重传配合使用的，首先回顾一下快速重传的概念：

快速重传：当发送方连续收到 3 个重复的 ACK ，它就知道该包可能丢了，于是无需等待该包的 RTO 超时就直接进行重传。

TCP 认为连续收到 3 个重复的 ACK 时，可能只是中间的某个数据包丢了，所以并不太严重，于是执行以下操作：

1. $cwnd = \frac{1}{2}cwnd,ssthresh = cwnd$ ；
2. 执行恢复过程，似乎并不要求；

下图还是相当直观的，展示了上述 4 个算法是如何配合工作的：

路由技术

网络层的功能。由路由器进行，路由表的构建需要路由算法 + 路由协议，这里将一些基本的路由算法，或者也可以说路由技术。

1. 最优化原则

一句话，最优路径上的任意两点间的路径也是最优的。

2. 泛洪 Flooding 路由算法

每一个入境分组将被路由器转发到除了它进来的那条路线之外的每一条输出线路上，但是由于扩散算法会产生大量的重复分组，需要改进扩散算法，避免重复的分组。

• 优点是简单，无需路由表，并且所有路径都会尝试，具有鲁棒性；
• 缺点是产生大量重复的包；

解决无限制扩散的方法有增设跳计数器和序列号；

3. 距离矢量选路 DVR

路由器周期性地向邻接路由器广播自己的路由表（包括与其他路由器的最短距离和下一跳使用的接口信息）。

存在无穷计数问题，即好消息迅速传遍整个网络，但对坏消息反应慢，只知道距离，不知道路径！

采用 DVR 的协议？ —— RIP 协议

4. 链路状态选路 LSR

路由器在网络拓扑结构变化时，向网络内的所有路由器广播自己的链路状态信息，或称自己学习到的网络拓扑结构。

4.1 与 DVR 的区别？

• DVR 周期性广播，LSR 在网络拓扑结构改变时广播；
• DVR 只向邻居广播，LSR 向整个网络内其他的路由器广播；

4.2 基本步骤

1. 发现邻居节点：
   1. 路由器向邻居路由器广播一个 Hello 包；
   2. 邻居收到 Hello 包后，回复 1 个包含自己网络地址（Route ID ，全网唯一）的包给路由器；
2. 测量线路开销：通过 Echo Packet 包测量 RTT ；
3. 创建链路状态分组 LSP(Link-State Packet)：分组中包含所有它刚刚知道的链路状态信息，具体可见下图；
4. 泛洪链路状态分组：采用刚刚提到的 Flooding 算法发送 LSP ；
5. 计算最短路径：路由器根据网络拓扑采用 Dijkstra 算法计算出到每一个其他路由器的最短路径树；

注：其中 Seq 和 Age 字段就是用来解决 Flooding 算法无限泛滥的问题的。

4.3 应用

• IS-IS 协议；
• OSPF 协议；

5. 层次路由 Hierarchical Routing

大型网络中使用，将网络划分为不同层次的区域，从域内选路到路由器，再从域间选路到域，有效减小了路由表的规模。不过存在次优路由问题。

层次等级：regions 区域 $\rightarrow$ clusters 簇 $\rightarrow$ zones 区 $\rightarrow$ groups 群；

QoS(Quality of Service 网络服务质量)

1. QoS 参数

• Reliability：可靠性，包括错误率和丢包率；
• Delay；
• Jitter；
• Bandwidth；

一些例子：

• 电子邮件系统：要求高可靠性，别的无所谓；
• 电话：抖动和时延，这种语音或者视频流错一点东西看不出来；
• 视频会议：抖动 + 时延 + 带宽，需要音视频流的实时传输；

2. 哪些层有 QoS ？

课内讲到的主要涉及数据链路层 and 网络层。

3. 网络层的 QoS

3.1 流量整形 Traffic Shaping

目的：减少网络中的突发流量。

3.1.1 漏桶 Leaky Bucket

桶中保存的是数据，恒定输出速率，当桶满时会丢弃一些数据分组。

3.1.2 令牌桶 Token Bucket

• 路由器匀速产生令牌，如果令牌桶满则丢弃多余的令牌；
• 数据包到达路由器的队列后，需要消耗令牌进行发送，一个 Token 对应 一个 Packet；
• 令牌桶并没有数据队列的缓存限制，不会丢弃数据帧；
• 令牌桶能接受一定的突发流量，比如突发流量到达，可以一次性消耗所有令牌（跟令牌桶的大小有关）；

突发流量持续时间计算

令：

• 突发数据的持续时间为 $S$ sec；
• 令牌桶的容量为 $B$ Bytes；
• 令牌的产生速率为 $R$ Bytes/s；
• 最大的输出速率为 $M$ Bytes/s；

则有：

$$M\times S = B + R\times S$$

即：

$$S = \frac{B}{M-R}$$

3.2 分组调度 Packet Scheduling

3.2.1 公平队列

3.2.2 公平加权队列

4. IEEE 802.11 的 QoS

4.1 帧间隔

简单来说，就是设置不同的帧间隔，来实现优先级服务！

4.2 TXOP 机会传输

默认情况下，站点竞争到信道 1 次，发送 1 个帧。但是这对发送速率快的站点并不公平。假设站点的带宽分别为 $c_1,c_2$，则平均数据率为：

$$\frac{1}{c_{ave}} = \frac{1}{c_1} + \frac{1}{c_2} \Rightarrow c_{ave} = \frac{1}{\frac{1}{c_1} + \frac{1}{c_2}}$$

而 TXOP 给予两个站点相同的发送机会，即竞争一次，获得一段传输时间，即

$$c = c_i / n$$

比如对于 6Mbps 和 54Mbps 的两个站点，采用TXOP后，按照 3Mbps 和 27Mbps 发送帧；

Internetworking 网络互联

1. 互联网络的分组转发；
2. 隧道（Tunneling）计数：当源和目标主机位于相同类型的网络中，中间的网络属于不同类型时使用隧道方案，用中间网络的协议封装源主机发送的数据报；
3. 互联网络路由；
4. 分段与重组：不同网络有不同的 MTU ；
   1. 发送主机或路由器进行分片；
   2. 目的主机进行重组；

互联的网络中，路由的架构如下：

• 首先，整个网络被分为无数个自治系统（AS, Autonomous System），可以理解为单一技术下管理的多个路由器，一个 AS 内部需要一种路由协议，不同 AS 之间也需要一种路由协议；
• AS 内部路由协议 —— 内部网关协议 IGP（Interior Gateway Protocol）；
  • IS-IS 协议；
  • RIP 协议；
  • OSPF 协议；
• AS 间的路由协议 —— 外部网关协议 EGP（External Gateway Protocol）；
  • BGP 协议；