计算机网络¶

Chapter 1: Introduction¶

网络提供的最基本服务是：信息传递

最早的信息传递

不同网络用所提供的服务区分

服务用功能、延迟、带宽、丢失率等区分

网络分类： - 个域网 PAN (personal area network) - 局域网 LAN (local ~) - 城域网 MAN (metropolitan ~) - 广域网 WAN (wide ~)

Internet (互联网) vs internet(互连网)

网络的网络具体实例泛指这种类型

TCP/IP 可以用其他协议

互联网层级结构

树形

根：Tier One ISP

接入网：将主机连接到边缘路由器（端系统 Host 去往任何其他远程端系统的路径上的第一台路由器）上

接入网：光纤到户 FTTH

无源光纤网络 PON

数字用户线 DSL

如何创建一个网络应用——编写分布式程序，运行在不同的（多个）端系统（主机）上，通过网络通信

进程如何标识自己？（以便其他进程能够找到他）

不能直接用主机的地址，因为可能有多个进程同时运行在一个主机上

端口号：用于区分同一主机上的进程

IP 提供主机的标识，TCP 提供进程标识——对应 IP 地址 + 端口号

通信必然需要用到标识

网络分层之间通过服务的形式操作（接口，函数调用）

常用：Socket API 标准的互联网程序的接口，使上层可以调用下层 C/S 模式（客户端——服务器）

Socket API 提供的两种服务： TCP 服务——面向连接（字节流服务），更为可靠，不会出现乱序、丢包 UDP 服务——无连接（数据报服务），只关注路由

一个例子：回音服务（ECHO）

套接字地址：IPv4

创建套接字：socket()

在套接字描述符上的发送、接收数据的行为都可以用文件写读完成（read/write）

绑定套接字地址：bind()

关闭套接字：close()

UDP 套接字实现回音：

只需要发送 sendto() 和接收 recvfrom()

TCP 套接字实现回音：

类比封闭管道

按顺序送入管道，按顺序从管道读出

TCP 实现一个服务器——多个套接字服务客户

服务器多进程，每收到一个 TCP 的请求则创建新的进程

建立监听进程（绑定监听套接字）

客户进程发送请求，服务器接收后，在本地建立临时套接字（或连接套接字）和一个新的服务器进程

服务器监听进程继续监听、等待

这样就实现了一对多

CN 度量单位

bit rate - b/s

带宽：数据传输能力 i.e. 单位时间能够通过最高的数据率 - b/s

包转发率 PPS：package per second

线速转发：交换机端口在满负载的情况下，对帧进行转发时能够达到该端口线路的最高速度

时延（Delay）

指数据从网络的一端传送到另一端所需的时间

传输时延：从结点进入到传输媒体所需时间传播时延：电磁波在信道中需要传播一定距离处理时延排队时延

往返时延（round-trip time）判断通断性、测试网络时延、计算丢包率

ping 命令获取往返时延

时延带宽积

传播时延 $\times$ 带宽

在代表链路的管道充满比特时，才充分利用

吞吐量 throughput b/s

有效吞吐量

利用率：被利用的时间占总时间的比例网络利用率：全网络的信道利用率的加权平均

丢包率

时延抖动 jitter 起源于网络中的队列或缓冲

抖动难以精确预测

延迟丢包时间过长

网络安全

国际标准组织

国际标准化组织：ISO international organization for standardization

国际电信联盟：ITU international telecommunications Union

国际电气和电子工程师协会：IEEE

WIFI 联盟：WFA

万维网联盟：W3C

IETF 互联网工程任务组 RFC

Chapter 2: The Physical Layer¶

Section 2.1:¶

物理层功能：网络体系结构中的最底层不连接计算机物理设备不是负责信号传输的具体物理媒体（是一个整体的概念）

功能：如何在连接各计算机的传输媒体上传输数据比特流

尽可能屏蔽不同传输媒体和通信手段的差异为数据链入层提供一个统一的数据传输服务

物理层接口特性

数据终端特性 DTE

数据电路终结设备 DCE

电气特性：多条信号线的电气连接及有关电路特性

点对点

物理层标准 EIA RS-232-C 等

广播通信线路：一条公共通信线路连接多个结点

Section 2.2: 数据通信基础¶

傅里叶分析

传输方式

同步 & 异步

基带传输 & 频带传输

传输的数据就认为是基带（就传010101.....），即高低电平

基带的限制：比如传全1，由于信号衰减，可能会衰减到 0，产生干扰（

频带传输：做一个调制的动作，将基带信号搬移到信号频谱

适应信道的频率特性

数据编码技术

编码 coding 和调制

解码 decoding 和解调

编码：在基带上进行变换

不归零编码：高低电平代表 1 0

逢 1 跳变和逢 0 跳变（跳变指取反）

曼彻斯特编码（相位编码）

每一位中都有跳变，从低跳变到高表示 0，反之表示 1（解决长0/长1过程中的传输错误问题）

曼彻斯特效率更低，但是可以有效规避错误，做同步更加容易

差分曼彻斯特：每一位开始时跳变代表 0，不跳变代表 1，但是中间仍然需要跳变

曼彻斯特

Clock Recovery

4B /5B

4B：16 种编码 5B：32 种编码

在 5B 中选取 16 个与 4B 对应（选取的原则是，连续的 0 不能超过 3 个，以解决前面说的长 0/长1 的问题）

编码效率？？如何计算

\[ \text{波特率} = \frac{\text{数据传输率}}{\text{编码效率}} \]

频带传输

在一定频率范围内的线路上，进行载波传输

调制（modulation）：用基带脉冲对载波信号的某些参量进行控制，使之变化为适合于线路传输的信号

解调（demodulation）

调制解调器 MODEM

三种调制技术：调幅、调频、调相，即调 x 键控法（x SK）

信号表示：星座图

IQ 平面（类似于极坐标）

BPSK & QPSK 二进制 & 四进制相移键控

QAM 正交幅度调制（正交调幅和复合相移）

性能度量

传输速率：调制速率（波特率，码元速率）、数据信号速率（传信率，比特率）

带宽（两个含义）：频带宽度（模拟传输）/数据速率（数字传输）

模拟信道的度量

香农定理

$$ C = B \log(1+\frac{S}{N}) $$ 得出：提升模拟信道容量方式：增加系统带宽、提升源端信号发射功率、降低噪声（提高信噪比）

数字信道的容量

奈奎斯特公式：

\[ C = 2 B \log M \]

频带利用率

信噪比 SNR：描述信号在传输过程中受到噪声影响的度量。

\[ SNR = 10 \log_{10}\frac{P_s}{P_N} \text{(dB)} \]

Section 2.3: 传输介质¶

传输介质分类

导引型介质 & 非导引型介质

一般导引型就是摸得着的

导引型

双绞线

同轴电缆

基带同轴电缆和宽带同轴电缆

光纤（原理：光的全反射）

多模：多种不同频率的光在其中传输

多模突变光纤、多模渐变光纤、单模光纤

光源：发光二极管，接受：光敏二极管

光通断的特性天然代表 0/1，故多用光脉冲

固有损耗、非固有损耗

Chapter 3: 数据链路层 The Data Link Layer¶

Section 3.1: Data Link Layer Design Issue¶

向下：利用物理层提供的 bitstream 服务向上：为网络层提供接口

功能： - 成帧（Framing）—— 将 bitstream 划分为帧 - 差错控制（Error Control）—— 处理传输中出现的错误 - 流量控制（Flow Control）—— 确保发送方的发送速率不大于接收方的接收速率

提供服务： - 无确认无连接服务 Unacknowledge Connectionless - 有确认无连接服务 Acknowledge Connectionless - 有确认有连接服务 Acknowledge Connection-oriented

成帧（Framing）

分组（Packet）与帧（Frame）

发送方网络层丢下来一个 packet 作为有效载荷，数据链路层加上头标、尾标后形成 frame；接收方从中提取 packet.

标识一个帧的开始：帧同步、帧定界、定界符

成帧方式（定义定界符） - 字节计数法 - 带字节填充/带比特填充的定界法 - 物理层编码违例

字节计数法要求数据严格不能出错，否破坏了帧的边界，导致一连串的错误

带字节填充：用一个特殊的 byte 作为边界（0x7E）问题：有效载荷中出现了与该字节相同的 byte，则在前面加一个转义字符 ESC，然后在其他位置的转义字符前面再加一个转义字符（否则转义字符会转义其他有效数据）

带比特填充：2 个 0 之间，连续 6 个 1 有效载荷中如果出现连续 5 个 1，立刻插入一个 0，接收方只需在连续 5 个 1 出现时注意一下下一位是什么，如果是 0 直接丢弃，是 1 则构成定界符即可。

物理层编码违例：定界符不会在数据部分出现

4B/5B：将没有参与映射的编码当作定界符

前导码：很长的前导码 preamble 可用作定界符

曼彻斯特编码：正常信号在中间会有跳变，那么不会在数据中出现的连续的高/低电平可用作定界符

Section 3.2: Error Dectection and Correction¶

信道噪声导致数据传输问题

差错
丢失：接收方未收到
乱序：先发后到，后发先到
重复：一次发送，多次接收

解决方案：检错、纠错，确认重传

确认：校验数据（差错校验）
定时器：防止丢失
顺序号：防止乱序、重复

链路层存在的另一个问题：接收方的处理速率

基于反馈
基于速率（发送方内建机制）

解决信道传输差错问题：通常采用增加冗余信息（或校验信息）的策略降低效率提高可靠性

如何减少冗余信息？

检错码

包含的冗余信息只能供接收方判断有没有出错，进而判断是否请求重发用于高可靠、误码率低的信道，可用重传解决

纠错码

加入足够的冗余信息，接收方能够判断接收到的数据是否有错，并能够纠正错误用于错误发生较为频繁的信道，常用于物理层和更高层称为前向纠错

一些概念：

码字 code word —— 共 n 位，其中数据 m 位，校验位 r 位，$n = m+r$
码率 code rate —— m 所占比例
Haming Distance —— 两个码字的不同比特数目

为了检测出 d 位的错误，则使用 Haming distance 为 $d+1$ 的编码（编码的 Haming distance 指 inf）为了纠正出 d 位的错误，则使用 Haming distance 为 $2d+1$ 的编码

典型检错码：

奇偶校验

偶校验：增加一位校验位，保证 1 的个数是偶数（可以检测奇数位错误）

校验和

发送方进行 16 位二进制补码求和运算，计算结果取反，随数据一并发送，接收方进行 16 位二进制补码运算

循环冗余校验

原始数据 $D$ 位，要产生 $n$ 位 CRC 校验码，需要生成一个 $n+1$ 位的 $G$，根据各位表示成系数为 0/1 $的n$ 次多项式（由双方事先确定）。然后将 $D$ 左移 $n$ 位，除 $G$ 得余数 $R$，加在 $D$ 的后半。

设计纠正码

典型纠错码：Haming Code

单位纠错

以 (15, 11) Haming Code 为例，将码字按位放在 4x4 的方格中，校验码放在第 1,2,4,8 格。

第一位填入本列和无校验码的一列的偶校验，第二位同样，第四、第八则改列为行

这样，根据几个校验码，可以定位错误的位的行和列，进而锁定错误的位具体是什么。

典型纠错码：RS 码

将流数据当作 symbol

Section 3.3: Elementary Data Link Protocols¶

关键假设：

网络层、数据链路层、物理层为独立进程
提供可靠、面向连接的服务
仅处理通信错误

乌托邦式单工协议¶

数据单向传输
完美信道、始终就绪、瞬间完成

完美但不现实，不处理任何流量控制或纠错，接近无确认无连接，但依赖更高层解决

无错信道上的停-等式协议¶

传输、接收、处理需要时间（不再是无限制），发送帧的速度过高会导致接收方 overwhelming，传输链路为双向，其他假设仍然保持。

stop and wait：接收方收到后发送一个哑帧向发送方确认，然后发送方才能发送下一个帧。

有错信道上的停-等式协议¶

信道不再可靠，可能出现丢帧（数据帧或者哑帧）

哑帧丢失，导致重发的帧被接收方识别为新的帧

另外，也可能出现重复的情况。

解决办法是给每一帧加上序列号（SEQ），注意接收方收到重复帧后仍然会回复哑帧。

有错信道上的单工停-等式协议¶

总延时中传播时延需要 double

对于长肥管道，这样的方式效率极低。

一种方法：管道协议，即在收到确认之前连续不断发出帧

Section 3.4: Sliding Window Protocols¶

发送方和接收方都有一定容量的缓冲区（窗口），发送方在收到确认之前可以发送多个帧。

协议： - 以连续发送的最多帧数为限制 - 循环使用有限的序列号（序列号复用） - 累计确认：不必对每一帧逐个确认，而是对按序到达的最后一个帧回复确认（$ACK_k$ 表示对前 $k-1$ 个帧的确认）

对于每一帧，发出后将窗口下限滑动一格；如果收到其 ACK，将窗口上限滑动一格

接收方收到一帧，滑动下限；发出一个确认，滑动上限

如何处理序列号相同的老帧和新帧同时到达的情况？

捎带确认 Piggybacking¶

接收方允许发送 Receive Not Ready （RNR）报文来切断发送方帧流，并且需要确认帧重启滑动窗口

双向链路：如果发送数据，捎带 ACK

链路利用率

见 Slides

回退 N 协议¶

出错全部重发（无论是中间出错还是超时），客体为所有未被确认的帧

主要目的是强化发送方的滑动窗口的优势

一般用于接收方窗口大小为 1 的情况。

Example

发送 0-4 五个帧，其中 2 丢失；那么 $ACK_3$, $ACK_4$ 被发送方收到时自动变为 $ACK_1$（因为没有 $ACK_2$）；之后重传 2，3，4，只需收到 $ACK_4$ 即可（因为存在累计确认的机制）

选择重传 Selective Repeat¶

接收窗口大于 1，通常等于发送方的窗口大小

接收方可以回复否认帧（NAK）

收到出错帧时，接收方暂存序列号在其后的所有帧，发送方只需重传出错帧即可

避免重传已经接收的正确帧

每一个帧设一个 timer，超时则认为出错（丢失或被破坏）

如果在窗口内的帧从未被接收，那么将其存储，等序列号小于之的所有帧都被正确接收后，按序交付给网络层。

重传次数超过一个 Threshold，则认为协议失败，上报

发送窗口的尺寸应当小于序列号空间的一半：$W_T \le 2^{n-1}$

为什么呢

Section 3.5: Protocol Verification¶

点到点协议 Point to Point Protocol

png

PPP 的状态转移图见教材中文版

PPPoE: Point to Point Protocol over Ethernet

PPP 自带的身份认证解决了以太网的安全问题

Chapter 4: The Medium Access Control Sublayer¶

数据链路层内部分为两个子层： - LLC（弱层，承上启下） - MAC（介质访问）

Section 4.1: The Channel Allocation Problem¶

在计算机网络中，信道是共享的（回顾 Bus 的结构）

多点访问信道：多用户共享一条信道

拓扑结构： - 总线型 - 星形 - 环形

结点：hub 集线器

如何处理同时的信道占用请求？

介质的多路访问控制

静态分配
动态分配

静态分配¶

排队论

动态分配¶

Section 4.2: Multi Access Protocol¶

随机访问协议：ALOHA¶

Pure ALOHA

想发就发

冲突可能随时发生在两个及以上的帧

冲突的帧被完全破坏，需要重传

效率极低

帧时：发送一个标准长的帧所需的时间

一个帧时内，用户产生的新帧和信道中产生的帧服从泊松分布（均值分别为 $N$, $G$）

用 Throughput ($S$)接近于 1 的程度衡量信道利用率

运载负载 $G$：T 内所有发送成功的帧数

传输成功概率：$P_0$

$$ S = G \times P_0 $$ 冲突危险的时间：$2t_{prop}$

故 $P_0 = e^{-2G}$

\[ S = Ge^{-2G} \le S_\max = \frac{1}{2e} \approx 0.184 \]

分隙 ALOHA （slotted ALOHA）

将时间分成时隙，长度对应帧的 $t_{prop}$；发送只能在时隙的起点

此时冲突只发生在时隙的起点

冲突危险期变为 $t_{prop}$

\[ S = Ge^{-G} \le \frac{1}{e} \approx 0.368 \]

载波监听多路访问协议（CSMA）¶

Carrier Sense Multiple Access Protocols

非持续性 (nonpersistent) CSMA
经侦听，如果信道空闲，立刻开始发送；
反之，等待一个随机分布的时间，然后重复 1。
1-持续性 (persistent) CSMA

先听后发，边发边听

介质空闲直接发送；
介质忙，持续侦听，一旦空闲重复 1；
若冲突，随机等待在重复 1

如果有两个及以上在等待，一定冲突

$p$-持续性 CSMA

适用于时间分槽的信道（time slotted）

介质空闲，以概率 $p$ 发送，以 $(1-p)$ 的概率延迟一个时间单元发送；
介质忙，持续侦听，一旦空闲重复 1；
发送已延迟一个时间单元，随机等待在重复 1

这样一定程度上缓解了 1-持续性的冲突

然而，冲突仍然发生：

同时发送
传播时延

Propagation Time 对冲突的影响（摘自课本）

这里存在一个时机，在某个站开始发送后，另一个站也刚好做好发送的准备并使听信道。如果第一个站的信号没能到达第二个站，后者侦听到信道是空闲的，因而也开始发送,由此导致双方的冲突。

带冲突检测的 CSMA (CSMA/CD, CSMA with Collision Detection)

一般是 1-persistant 的 CSMA + CD（吞吐量和冲突比 ALOHA 少，延迟比 p-persistant 低）

冲突窗口：发出帧后能检测到冲突的最长时间

一旦发生冲突，发送强化信号（Jam），强到足以告知其他方冲突已经发生

实现的要点：

如何实现冲突的感知
如何实现“随机分布的等待”

冲突的侦听：发出信号分叉，接受两路信号，若不同则说明发生了冲突

（Slides 中图）

这就要求发送帧的时间不能太短，且一个冲突窗口时间：$2t_{prop}$

受控访问协议（无冲突协议）¶

统一的思想：在一开始就对资源进行分配，实现方式和思路可以不同

位图协议（预留协议，reservation protocol）

时分的

大体上将时间片分为两类： 1. 决定发送的帧和次序（竞争期） 2. 按序发送（传输期）

竞争期在自己的 slot 内发送竞争比特（举手示意，预留资源），这样在传输器每一个阶段就有明确的使用权，从而避免了冲突

png

缺点：无法考虑优先级

令牌传递

在循环队列上安排站点

站点想要发送信息，必须持有令牌（持有的时间有限制，持有一段时间必须交出）

令牌有站点抓取，获得发送权（可以发送也可以不发送）

发送的帧需要由目的站将其从信道上去除（防止无限循环），或者由发送站去除（广播的形式）。

缺点：令牌的维护、分配问题

二进制倒数协议

可以看作位图协议的扩展

给所有站点编一个等长序号，然后按二进制从高到低排序，高者得到发送权，低者侦听得到发送权的序号自动放弃发送（从高位开始感知，判断大小）

这样，高序号站点优先

有限竞争协议¶

竞争 vs 非竞争 - 低负载：考察时延（竞争协议更小） - 高负载：考察信道利用率（非竞争协议更大）

之前提到的协议都是对称的（每个站点获得信道的概率相同），若有 $k$ 个站点，$p$ 最优值为 $1/k$

站点数少时，成功占用信道的概率很高；但一旦站的数量达到 5 个后，概率很快下降，接近 $1/e$

结合竞争和非竞争的优势：有限竞争协议

自适应树遍历协议

类比：病毒检测

没懂

Section 4.3: Ethernet¶

以太网

经典以太网¶

物理层：10 Mbps + 曼彻斯特编码 + 同轴电缆和中继器

thick Ethernet -> thin Ethernet

5-4-3-2-1 原则

MAC 子层：CSMA/CD 协议 + 帧格式（DIX/IEEE 802.3）

png png 前导码（8 bytes）：10101010 比特模式（曼彻斯特编码下产生方波） + 帧起始定界符（SOF）

目的地址、源地址：MAC 地址（硬件地址，物理地址）

特殊 MAC 地址举例：

广播：FF-FF-FF-FF-FF-FF
组播：往一组地址发送，组中所有站都要接受

源地址有全球唯一性，由 IEEE 统一分配，地址字段的前三个 bytes 用作该站所在的组织唯一标识符（OUI, Organization Unique Identifier）

类型/Length：DIX 将其视为上一层的==协议类型==；802.3 将其视为==数据长度==，用数据包前端的一部分来存放协议类型

数据：最多 1500 bytes

因此，最大有效帧长为 $1500+6+6+2+4=1518$。为了确保有效帧至少为 64 bytes，需要确保数据部分至少有 46 bytes。当不足 46 bytes 时，进行填充（Padding）。

限制最小有效帧长的原因（完整见课本 4.3.2）

冲突窗口时间 $\ge 2 t_{prop}$

CSMA/CA：二进制指数后退的 CSMA/CD

前文提到“等待的随机分布问题”，在这里解决。

重传次数（冲突次数）：$k$，最大不超过 10

从 $\{2^i\}_{i=0}^k$ 中随机选取，作为等待的 time slot 个数

以太网性能¶

见课本 4.3.3

交换式以太网¶

使用集线器（hub）组建、扩展以太网

集线器无法增加网络容量，有集线器组成的局域网在同一个冲突域中

核心：交换机（Switch）

工作在数据链路层，检查 MAC 帧的目的地址转发收到的帧

交换机中，每个端口都有独立的冲突域，实现了网络分割的效果

png

快速以太网、千兆/万兆以太网¶

Fast Ethernet

带宽提高到 100Mbps，电缆最大长度降低到十分之一，比特时间降为 10ns

保留基本工作方式

Gigabit Ethernet

提高带宽到 1Gbps/1000Mbps

最大长度 100m，最小帧长 64 bytes，

两种操作模式：全双工（正常情况），半双工（向下兼容）

特性：载波扩充，竞争周期增大到 512 bytes（原因是让硬件在帧后增加填充位，到 512 bytes）

特性：帧突发，允许多个待发送的帧连在一起发送

10 Gigabit Ethernet

Section 4.8: Data Link Layer Switching¶

原理¶

冲突域：同一时间内只能有一个站点发送数据的网络区域

物理层设备扩充网络（如 Hub）：扩大冲突域

数据链路层设备（网桥/交换机）扩充网络：分隔冲突域

理想的网桥是透明的，即插即用，且不需要被其他设备感知。

学习网桥¶

构建 MAC 地址表——逆向学习源地址

网桥在收到数据帧时，根据帧的源地址在 MAC 地址表中查找，若不存在，则将该地址和接收端口记录在表中；若存在，则更新对应的端口号，重置老化时间。

添加、删除、更新

网桥如何利用 MAC 地址表进行数据帧的转发?（勾连两个不同的冲突域）

Forwarding, Filtering, Flooding

Forwaring

当网桥收到一个帧时，查找 MAC 地址表，如果目的地址在表中，且对应的端口不同于接收端口，则将该帧转发到对应端口。

Filtering

交换机在查找自己的 MAC 地址表时，发现目的地址和源地址在同一个冲突域内，则丢弃该帧，不进行转发。

Flooding（泛洪）

与 MAC 地址表的构建相关，一般发生在交换机的初始化的情形下。

MAC 表不完整，即目的地址不在表中，则将该帧发送到除发送端口以外的所有端口。

附带的后果是，一个网段的数据被发送到无关网段。

链路层交换机¶

过去，主机通过集线器（Hub）连接到交换机；现代交换机直连PC

交换方式：对称/非对称（取决于出入端口带宽是否相等）
交换模式（从转发时机的角度）
- Store and Forward
- Cut-through
- ？？
Store and Forward

转发前必须接收整个帧，执行 CRC 校验，这样带来很大的时延，但是保证了出口帧的正确性。另外，支持非对称交换。

直通交换

接收到帧的目的地址就开始转发。可能转发错误帧，但是优点在时延极小

无碎片交换

接收到帧的前 64 bytes 后开始转发，虽然仍然可能转发错误帧，但比 Store and Forward 能大幅降低时延，同时过滤了冲突碎片

生成树协议¶

多个交换机连接同两个网段（冗余拓扑），则在物理上存在环路。如果传输的是需要广播的帧，会引发广播风暴的问题，即无休止地 Flooding，迅速消耗资源。

另外，当跨网段发送单播帧，且交换机没有目的地址对应的 MAC，需要需要进行广播，可能回到原网段，造成重复帧

一个帧的多个副本到达不同端口时（且交换机没有目的地址对应的 MAC），交换机会不断修改另一个交换机中同一个 MAC 地址对应的端口，这样 MAC 地址表非常不稳定。

生成树协议就是为了解决这些问题。

环路由多个交换机产生，需要在交换机中打破这些环。一个自然的想法是将交换机作为树的节点。因此，给定一系列交换机，只需要给出其 Spanning Tree 即可。

选举
- 根桥
- 非根桥选举根端口（连接到根桥的端口）
- 每一个网段确定一个指定端口（通往根桥的最短路径）
根桥选举：桥 ID 最小（首先优先级最小，然后MAC 地址最小）的交换机

根桥所有端口都处在转发状态。

非根桥选举根端口：到根桥的根路径开销（到根桥的路径上所有链路的开销之和）最小的端口，开销相同则选择端口 ID 最小的端口。

开销由 IEEE 规定，也可通过手工配置改变，一般来说速率越大开销越小。

根端口处于转发状态。

每一个网段确定一个指定端口：对于每一个网段，在所有连接到它的交换机的端口中进行选择，选出到根桥路径开销最小的端口作为指定端口，若相同则选择桥 ID 最小的端口

指定端口处于转发状态。对于不是指定端口也不是根端口的端口，则阻塞。

网络拓扑改变时，需要重新构造生成树。如某处出现故障，其指定端口的交换机需要通过合适的端口（如果根端口能用则用根端口，不能使用则使用其他端口，包括阻塞的端口）向根桥及其路径上的所有交换机发送 BPDU（Bridge Protocol Data Unit）报文，通知根桥网络拓扑改变，根桥再通知其他交换机重新选举根端口和指定端口。

虚拟局域网¶

广播域（Broadcasting Domain）

广播域是广播帧能到达的范围。交换机所有端口同属于一个广播域，因此交换机无法隔离广播域。这样会导致很多的资源浪费和安全隐患。

要解决这个问题，可以使用支持 VLAN（Virtual LAN，虚拟局域网）的交换机。

VLAN 将物理网络根据用途进行逻辑上的划分，从而与用户的物理位置无关。

不同 VLAN 的用户无法进行数据链路层（二层）的通信，需要通过路由器或者三层交换机通信

划分 VLAN：基于端口（最常见）、基于 MAC 地址、基于协议、基于子网
基于端口的 VLAN

在交换机上创建 VLAN，然后指定成员端口，并给分配 VLAN ID，相关信息存储在交换机的 VLAN 表中。相同 VLAN ID 的端口同属一个 VLAN

基于 MAC 地址

直接使用 MAC 地址决定成员身份。VLAN Table 中的 entry 形式为：$(VLAN\_ID, MAC\_Addr)$

难点在于收集 MAC

基于协议

相同协议的属于同一个 VLAN

需要上层参与

基于子网

借助 IP 地址，一个子网就是一个 VLAN

如何区分不同 VLAN 的数据帧？

在数据帧中携带 VLAN 标记，由交换机添加/剥除，对终端站点透明

Trunk 链路类型端口和 Trunk 链路

Section 4.4: Wireless LANs¶

无线局域网：指以无线信道作为传输介质的计算机局域网。

基础架构：
- 分布式系统（DS）
- 访问点（AP）
- 站点（STA）
- 基本服务集（BSS）
- 扩展服务集（ESS）
- 站点之间通信通过 AP 转发
自组织模式（Ad hoc）
- 。。。。

WLAN 体系结构¶

物理介质相关子层（PMD Layer）：调制解调
物理层汇聚协议（PLCP Layer）提供独立于传输技术的访问点
？
？

需要解决的问题：有限的无线频谱带宽资源、共享无线信道

IEEE 802.11 物理层¶

IEEE 802.11 MAC¶

隐藏终端问题
暴露终端问题

由于侦听到其他站点的发送而误以为信道忙导致不能发送。暴露站点能侦听到发送端但不会干扰接收端。

CSMA/CA

![[temp1.png]]

建立信道繁忙程度和随机后退时间分布的关系：

用信道上的重传次数 $m$ 来表示信道繁忙程度，则后退时间的取值范围为 $[0, 2^m]$ 个 time slot

差错检测

32 位 CRC 校验（与 Ethernet 相同）

确认重传

停等机制。如果达到最大重传次数，报错上报，并丢弃帧。

为什么不用滑动窗口协议？

WLAN 是长肥管道吗？实现的复杂程度？

用不同帧间隙（IFS）控制优先级
- SIFS（Short IFS）：最高优先级，ACK、CTS、轮询响应
- PIFS（PCF IFS）：次高优先级（SIFS+1 槽口时间），轮询服务
- DIFS（DCF IFS）：最低优先级（SIFS+2 槽口时间），异步数据服务
RTS-CTS 机制

在 CSMA/CA 中是可选的，目的是通过信道预约避免长帧冲突

发送方发送 RTS（Request to Send）帧，请求发送数据；接收方收到 RTS 后，若信道空闲，则回复 CTS（Clear to Send）帧，允许发送方发送数据。在 RTS 和 CTS 持续时间中必须指明传输所需时间（数据+控制）。

其他站点收到 RTS 或 CTS 后，维护一个网络分配向量（NAV, Network Allocation Vector），表示信道被占用的时间（包括 RTS, CTS, Data），同时在这段时间中自身保持静默，从而避免冲突。

无线链路出错率较高，传输长帧时冲突概率较大，解决方法是采用较小的帧。另外，同一源可以在先后发送的两个帧中的前一个携带后一个帧的传输时间，从而避免在两帧中间出现的冲突。

EDCA（Enhanced Distributed Channel Access，增强型分布式信道访问）

目标是针对不同的应用提供不同优先级，保证 QoS（Quality of Service）

单发送队列->多发送队列

四个竞争参数： - AIFS（Arbitration IFS）：不同优先级使用不同的 AIFS，优先级高的 AIFS 短 - CWmin：最小竞争窗口大小 - CWmax：最大竞争窗口大小 - TXOP（Transmission Opportunity）：允许连续发送的时间片长度

IEEE 802.11 帧结构¶

运行在 MAC 子层。

有四个 6 字节的地址字段（与 802.3 不同），分别表示不同的含义.

地址 1（DA, Destination Address）：物理接收者
地址 2（SA, Source Address）：物理发送者
地址 3（IBSSID, Intermediate Basic Service Set Identifier）：逻辑发送者
地址 4：逻辑接收者

WLAN 的构建与管理¶

通过 AP 连接到有线网络

BSSID：AP 的 MAC 地址，标识 AP 管理的基本服务集（BSS）

SSIDID：服务集标识符，标识一个扩展服务集（ESS）

没记完

扫描（Scanning）

被动扫描：AP 周期性发送 Beacon 帧，站点在每个可用的通道上扫描 Beacon 帧

主动扫描：站点依次在每个可用的通道上发出包含 SSID 的 Probe Request 帧，AP 收到后回复 Probe Response 帧

认证过程

站点寻找与其 SSID 匹配的 AP，在其中选择 AP 信号强度最强的进入认证阶段。

认证方式： - 开放系统认证（Open System Authentication）：无认证 - 共享密钥认证（Shared Key Authentication）：使用 WEP 加密技术进行认证 - WPA PSK 认证（Wi-Fi Protected Access Pre-Shared Key Authentication）：使用预共享密钥进行认证 - 802.1X EAP 认证（IEEE 802.1X Extensible Authentication Protocol Authentication）：基于端口的网络访问控制协议，使用 RADIUS 服务器进行集中认证

AP 中保留 AID （Association ID）表，记录已认证站点的信息。每个 AID 与对应站点的 MAC 地址绑定。

AID 范围为 1-2007，0 保留给广播/组播。

自组织模式

站点先寻找具有指定 SSID 的 IBSS，如果存在则加入；如果找不到则创建一个新的 IBSS 并发送 Beacon，等待其他站加入。

IBSS 中所有站点参与 Beacon 发送，每个站点随机选择一个时间间隔（$k$ 个 time slots）发送 Beacon，从而避免冲突。

站点漫游

当前 AP 通道质量下降，站点漫游到不同的 AP

通过扫描发现更好的 AP（主动/被动）

发现后，向新 AP 发送重关联请求（Reassociation Request）帧，旧 AP 发送重关联响应（Reassociation Response）帧，新 AP 更新 AID 表，完成漫游。

站点睡眠管理

目的是延长电池续航。无线网卡在空闲时关闭；关联的 AP 允许空闲站（周期性）睡眠，但跟踪睡眠站，并为之缓存数据，保证数据不丢，保持会话持续性

定期唤醒

Wi-Fi 6 核心技术概览¶

MU-MIMO
OFDMA
1024-QAM
BSS 着色

Chapter 5: The Network Layer¶

也叫 IP 层

没记完

面向连接的虚电路¶

无连接的数据报¶

允许数据包走不同的路

Router 仍然维护转发表，标签改为目的地址

虚电路 vs. 数据报

性能：虚电路在多用户需求量小的时候，带宽不浪费；但多用户峰值需求大时，可能无法提供可靠服务。
效率：虚电路需要经历连接、建立等阶段，总时延较大；数据报则无连接，时延较小。

Section 5.6: The Network Layer in the Internet¶

IPv4¶

网际协议版本 4：一种无连接协议

基本功能：寻址（addressing）和分片（fragmentation）

分片指的是当数据报大于网络层所允许的最大传输单元（MTU, Maximum Transmission Unit）时，将数据报分割成多个片段进行传输，目的地再将其重组。

数据报格式：

png

生存时间（TTL, Time to Live）：防止数据报在网络中无限循环，每经过一个路由器，TTL 减 1，若 TTL 减到 0，则丢弃该数据报。

协议：标识上层（传输层）协议类型，如 TCP、UDP 等。

首部校验和：对 IP 首部进行差错检测（注意，仅对首部进行检测，不包括数据部分）。

源/目的地址：32 bits = 4 bytes，所以会写为 xx.xx.xx.xx 的形式

数据报分片

MTU (Maximum Transmission Unit)：最大传输单元

将最差的链路的 MTU 作为整个路径的 MTU

分片策略：允许图中分片，即根据下一跳链路的 MTU 分片；或不允许~，发出数据报长度严格小于路径 MTU

重组策略：途中重组；目的端重组（广泛使用）

每一个切片大概是 1400 bytes，偏移需要以 8 bytes 为单位

原始数据报和分片有相同的 IP 标识符

IP 地址¶

每一台主机的每一个接口分配到的全球唯一的 32 位标识符

这 32 位由两部分组成：

网络号（Network Number）：标识主机所在的网络
主机号（Host Number）：标识主机本身

IP 地址分类：A、B、C、D、E 类地址。

其中 ABC 为单播地址，对于指定的 IP 地址，对应唯一的主机。三者的区别仅在于网络前缀（网络号）不同，即网络号和主机号的划分不同，A 类网络号占 8 bits，B 类占 16 bits，C 类占 24 bits。

Info

原先 IPv4 采用 32 位，现有地址资源紧张，IETF 提出 IPv6，采用 128 位地址。

D 类地址用于多播（指一对多，包括广播、组播等特殊形式）

E 类地址保留作未来使用。

IP 的书写采用点分十进制，将其分为 4 段，每一段范围为 0-255。

这几类地址的区分由头部决定，A 类为 0 开头，B 类为 10 开头，C 类为 110 开头，D 类为 1110 开头，E 类为 1111 开头。

IP 特殊地址

全 0 网络地址：仅在系统启动时使用，用于启动时临时通信，又叫主机地址

127.0.0.1 - 127.255.255.255：本地节点，用于测试网卡、TCP/IP 协议栈，或称回环地址（loopback address）

全 0 主机地址：指定网络本身

全 1 主机地址：用于广播

0.0.0.0：任意地址

255.255.255.255：用于本地广播

子网划分（subnetting）

在网络内部将一个网络划分为多个子网，对外仍是一个网络。

将网络号划分为网络号和子网号。

子网掩码（subnet mask）：32 位，用来区分 IP 地址中的网络号和主机号，与 IP 地址按位与运算，得到网络号。（这就是为什么很多子网掩码都是以 255 开头，并且长得像 IP 地址的原因）

子网划分减少了 IP 地址的浪费，使得网络的组织更加灵活，便于维护管理。

如果主机号全 0，说明不对应任何一个主机，而是表示子网本身。另外全 1 表示广播，所以实际可用主机号为 $2^h-2$，其中 $h$ 为主机号的位数。

CIDR（Classless Inter-Domain Routing，无类域间路由）

更加自然的是，将子网掩码的 1 个数直接记录来表示网络号的范围，添加在 IP 地址的后面，用斜杠分隔开来。

一个 CIDR 块可以表示很多地址，与路由聚合密切相关。

聚合技术在网络中大量使用，允许前缀重叠，数据报按照具体路由的方向发送，即具有最少 IP 地址的最长前缀匹配。

最长前缀匹配（Longest Prefix Matching）

IP 地址与 IP 前缀匹配时，总是选取前缀长度最长的那个进行匹配，从而决定数据报的下一跳路由。

如果都匹配不上，则使用主机地址，即全 0 网络地址。

IP 包转发
直接交付：目的地址在同一 IP 子网内（网络号相同），通过交换机直接发送给目的主机。

此时发送方与接收方互相知道 IP 地址，但是可能不知道 MAC 地址，因此需要使用 ARP 协议将 IP 地址映射为 MAC 地址。

间接交付：目的地址不在同一 IP 子网内（网络号不同），发送给默认网关（路由器）。

同样地，路由器上也有多个接口，每个接口有一个 MAC 地址，路由器维护一个转发表（暂时认为已经有了）。

发送方知道接收方的 IP 地址，想要将数据报发送，则在帧头写入源 IP 和目的 IP 地址，同时将目的 MAC 地址写为路由器对应端口的 MAC 地址，由路由器转发。

路由器收到待转发的包时，执行前述最长前缀匹配，找到下一跳路由，然后将数据报封装在新的帧中发送出去。

另外，每个主机都绑定一个网关地址，即路由器上对应接口的 IP 地址。

DHCP¶

IPv4 地址的获取：

静态设置：申请
动态获取：DHCP（Dynamic Host Configuration Protocol），基于 UDP 工作，采用 client/server 模式，服务器时刻监听客户端的请求。

具体来说，一个客户机将 0.0.0.0/68 作为源地址，255.255.255.255/67 作为目的地址发送（广播）发现报文（DHCPDISCOVER），因为客户机还没有 IP 地址，且不知道DHCP 服务器的地址。DHCP 服务器收到请求后，通过源和目的地址告诉客户机自己的地址，并分配一个 IP 地址（具有 lifetime）给客户机（DHCPOFFER）。然后客户机发送（广播）一个正式的 DHCPREQUEST，服务器回复一个 DHCPACK，完成地址分配。

其中正式 request 的目的是，可能有多个服务器响应客户机的初始请求，客户机需要向其中一个服务器发送 request，告诉它接受哪个 IP 地址，其他服务器则收回原先分配但未被选择的地址。

后续交互基本上是完成续租之类的服务。

ARP 地址解析协议¶

A 已知 B 的 IP 地址，想要知道 B 的 MAC 地址。

如果 A 的 ARP 表中有 B 的 MAC 地址，则直接使用。

否则，A 发送一个 ARP 请求广播帧（包含 A 的 MAC 和 IP 地址，B 的 IP 地址），请求 B 回复自己的 MAC 地址。

B 收到请求后，发送一个 ARP 回复帧，告诉 A 自己的 MAC 地址。

A 在 ARP 表中记录 B 的 MAC 地址，以备下次使用。若超时未使用，则删除该记录。

思考：如何对 ARP 表进行优化？

如果需要路由到另一个局域网，则发送给路由器的 MAC 地址，而不是目的主机的 MAC 地址。

网络地址转换¶

使用网络地址转换（NAT）解决 IPv4 地址不足的问题。

NAT：将私有（保留）地址转化为公有 IP 地址的转换技术

私有地址通常由一个固定的范围。

对于使用同一公网 IP 的主机，各自有不同的私网地址，使用源端口号（传输层）进行主机之间的区分。这些主机都与一个 NAT 路由器相连，路由器维护一个 NAT 表，记录私有地址与公网地址的映射关系。相当于 NAT 路由器充当了一个代理服务器的角色，收到待发送数据报时，将源地址改为自己的公网 IP，将端口号改为自己的某个端口号。

传输层 TCP/UDP 拥有 16 bits 端口号字段。

NAT 的优势在于，节省合法地址，减少冲突，灵活连接 Internet，保护局域网私密性。

其缺点是违反了 IP 的结构模型和端到端原则，由路由器处理传输层协议，违反协议分层模型。并且，不能处理 IP 报头加密。

新型网络应用设计者必须考虑 NAT 场景。

一个使用 P2P 的 solution：relaying

使用一个中继服务器，所有 P2P 通信都通过该服务器转发，从而避免 NAT 带来的问题。

Internet 控制报文协议¶

ICMP 协议：一个传输层协议，用于向源主机报告路由器在处理数据包时发生的意外；还可以用于测试网络连接状况。

分为差错报文和询问报文

差错报文

终点不可达

询问报文

回送请求，回答（ping）

报文：在 IP 数据包中的数据部分

这里缺少差错报文和询问报文的结构和类型

ping 和 ICMP

ping 命令用于测试两个主机之间的网络连通性。

ping 使用 ICMP 回送请求和回送回答报文。

输出的信息中，TTL 指的是数据包在网络中经过的路由器数目（跳数）加 1。

traceroute 和 ICMP

traceroute 命令用于确定从源主机到目的主机经过的路由。

其思路是，通过发送一系列的 ICMP 回送请求报文来实现，每个报文经过的跳数依次多 1，具体用 TTL 控制。对于某个路由器，如果收到数据报的 TTL 恰好减为 0，则返回一个差错报文，而不会将其继续转发至下一跳。

traceroute 的停止条件是，UDP 报文到达目的主机，或者目的主机返回一个 ICMP 端口不可达的差错报文并被接收。

Section 5.3: Routing Algorithms¶

需满足的特性：正确、简单、鲁棒、稳定、公平、有效

路由算法分为静态路由选择（非自适应）和动态路由（自适应）

一个简单的算法：Flooding

扩散法

先向所有邻接的路由器发送数据包，然后这些路由器再向它们的邻接路由器发送，以此类推，直到到达目的地。

所有接收数据报的节点逆着回来，就是一条路径。

Selective Flooding

减少纯 Flooding 带来的冗余传输

优化原则¶

汇集树（Sink Tree）

所有源节点到某一个目标节点的最优路径的集合构成以目标节点为根的树，称为汇集树。

这样，每个其他节点到目标节点的路径就是唯一的最短路径。

最短路径算法¶

Dijkstra 算法

这里关于 Dijkstra 算法的内容省略，回忆《数据结构》

距离向量路由算法¶

Bellman-Ford 算法

每一个节点仅与其直接相连的邻居节点交换信息，而不是像 Dijkstra 算法那样要求每一个节点知道整个网络的拓扑结构。

每个节点到目标节点的最短路径为所有邻居节点到目标节点的路径加上到该邻居节点的距离中最短的一条。

Bellman-Ford 算法无需全局信息，只需要邻居节点的信息，但是是迭代的、分布式的（像动态规划）。

当某个节点的信息变化时，需要更新其邻居节点的信息，从而引发连锁反应，最终收敛。

在网络中，由路由器逐级向上汇报最短的下一跳，在路由表中储存相应信息。

距离向量路由的问题是，由于每一个节点无法获知全局的信息，导致计数到无穷（count-to-infinity）的现象。

简单来说，好消息传播快，坏消息传播慢。

链路状态路由¶

Link State Route 分为五个部分：

发现邻居路由器（节点），了解其网络地址
设置到每个邻居的成本度量
构造一个分组，分组中包含刚收到的所有信息
将分组发送给其他节点（广播），注意这里不局限于邻居节点，因为每个节点都需要知道全局的信息
计算到其他节点最短路径

第一步中，“发现”以问候的形式扩散开来。

第二步中，度量可以用带宽（反比，较常用）、延迟等指标来表示。

第三步中，分组叫 Link State Packet，包含节点 ID（发送方标识）、序列号（递增）、邻居列表等信息。

第四步中，路由器收到某一个 LSP 后，记录 ( 源，序列号 )。如果是新的分组，则泛洪；如果是重复的分组，则丢弃；如果是超时的分组，则丢弃。

第五步中，使用 Dijkstra 算法计算最短路径。

对于网络状态信息，链路状态路由的信息更可靠，因为是自己测量的，而不是从邻居节点获取的。另外，链路状态路由的鲁棒性相较于距离向量路由更好，且收敛更快。

距离向量和链路状态形成不同的协议。

层次路由¶

Hierarchical Routing

网络规模很大，拓扑结构非常复杂时，单个路由器需要维护的路由表非常大，且路由查找、计算开销也很大。

一种解决的思路是，将路由表中的转发关系分组，通过地址聚合进一步缩短路由条目，这就是层次路由的由来。

聚合的方式：CIDR，最长前缀匹配。

现实中，地址分配往往随机，难以高效聚合

自治系统（AS, Autonomous System）

互联网由大量不同的网络互连，每个管理机构控制的网络是自治的。

AS 内部使用相同的路由算法/协议（内部网关路由协议/ IGP，包括 OSPF、RIP 等），使用统一的路由度量。AS 之间使用外部网关路由协议（EGP，如 BGP）

AS-ID：每个自治系统有一个唯一的 AS 号。

AS 内部可以进一步划分。

使用 AS 实现类似地址聚合的效果，将 AS 内部的路由器聚合为一。对跨 AS 的转发，将 dest 设置为 AS 本身，而不是某个特定的路由器。

广播路由¶

Broadcast Routing

考虑一种特殊的情形，需要将数据从一个源节点发送到网络中的所有节点。

一种最简单的方法是给每一个主机单独发送一份数据。

另一种方法是在需要转发的路由器线路对数据报进行一次复制。

Flooding

解决上面两种方法的问题。

对于每个收到数据报的路由，将其转发到所有邻居节点（除了收到数据报的那个节点）。

其鲁棒性、简单性、有效性较好。

问题在于，网络拓扑中可能有环路存在，Flooding 引发广播风暴（Broadcast Storm）。解决方法是跟踪已经收到的数据报，或者限制数据报的跳数。即便这样，还是无法完全消除 Broadcast Storm 的影响。

进一步解决：Selective Flooding

序列号控制泛洪

每个数据报携带一个唯一的序列号，路由器记录已经收到的序列号及其源，避免重复转发。

逆向路径转发

路由器中维护一张表，记录到各个网络的最优路径。收到数据报时，检查数据报的源地址是否与最优路径一致，若一致则转发，否则丢弃。

Spanning Tree

对于所有需要接收数据报的主机所在的网络连接的路由，构造一棵生成树，令数据报沿着生成树转发，避免环路。

组播路由¶

给部分网络中一部分目标发送数据报。

为每个组建立多播转发树。

IGMP 协议

实现步骤：

确定组成员
建立生成树

在建立生成树时，需要区分组成员在网络中的密集分布和稀疏分布两种情形。

密集分布：基于源点树

链路状态：对于每一个需要组播的源，构造一棵独立的、以该源为根的生成树。

距离向量：逆向路径转发，修建没有组成员的分支

稀疏分布：基于核心树

多个组播共享一棵树，不属于共享树的节点不需要做任何事。

一种思想：在树所有节点中确定一个 RP（Rendezvous Point，组播流量汇聚点），所有源节点都将数据以最短路径发送给 RP，由 RP 向组成员转发。

使用核心树存在的问题是，可能导致路径次优。

Internet 组播

主干（MBone）：可以转发多播流量的路由器和主机组成的网络

隧道（tunneling）：将组播数据报封装在普通的单播数据报中进行传输，从而穿越不支持组播的网络。

选播路由¶

Anycast Routing

将数据报发送给一组节点中的任意一个，而不是所有节点。

选播的目的是当存在多个服务器时，用户希望快速获得信息，而不在乎信息从哪个服务器获得。

选播的典型应用：DNS

Section 5.4: Internet Routing Protocols¶

OSPF 协议¶

开放最短路径优先协议（OSPF, Open Shortest Path First）：一种链路状态路由协议。

各路由器之间频繁交换信息，最终所有路由器都能建立一个链路状态数据库 LSDB。这个 DB 实际上就是区域内的拓扑结构图，在区域内是一致的（同步）。

每个路由器根据 LSDB 使用 Dijkstra 算法计算最短路径，建立路由表。

OSPF 的五种报文：

Hello
Database Description
LSA Requeset
LSA Update
LS Acknowledgment

每一个路由器需要周期性地泛洪 LSA Update，向邻居路由器发送自己的链路状态信息。

OSPF 是网络层协议

OSPF 区域

层次划分：主干和非主干

OSPF 报文

是一个 IP 报文

RIP 协议¶

路由信息协议（RIP, Routing Information Protocol）：一种距离向量路由协议。

使用跳数衡量到达目的网络的距离，认为好的路由就是跳数少的路由。一条路径最多包含 15 跳，超过则认为不可达。

基本思想：仅和相邻路由器交换信息，交换的内容是自己的路由表。周期性更新。

全网信息的稳定性取决于收敛的速度。

在更新的过程中，不管距离是否变大，都选择最新的。

RIP 报文

RIP 运行在传输层，报文封装在 UDP 报文中，UDP 端口号为 520。

V2 版本相较于 V1 版本，多了子网路由、身份认证、多播等功能。

RIP 特点是简单、易实现，但收敛慢，适合中小型网络。另外，需要增加防环路机制。

BGP 协议¶

边界网关协议（BGP, Border Gateway Protocol）：用于不同 AS 之间的路由算法

功能：

eBGP：跨 AS 获得网络可达信息
iBGP：在 AS 内部传播路由信息

BGP 会话：两个 BGP 路由器通过 TCP 连接交换 BGP 报文

BGP 路由器可能会学到多条到目的网络的路径，选择的策略由人为确定。

最后，根据可达信息和策略决定路由。

BGP 报文

BGP 报文封装在 TCP 报文中，使用端口号 179。

前缀信息包含 BGP 属性：AS 路径、下一跳

BGP 最佳路由的选择规则：

缺

标签交换和 MPLS¶

多协议标签交换（MPLS, Multiprotocol Label Switching）

标签交换路由器（LSR, Label Switching Router）：支持 MPLS，具备标签交换、路由选择的功能

加标签、标签交换、去标签
MPLS 报文格式

注意，MPLS 报文封装在 IP 头的前面，通常认为是数据链路层和网络层中间的一层。

Section 5.5: How Routers Work¶

路由器控制层

不同类型的路由具有不同的优先级（数值最小，优先级最高）

优先级：直连 > 静态 > eBGP> OSPF > RIP > iBGP

路由器数据层

链路层解封装，IP 头部校验，获取 dest IP，基于最长前缀匹配查找路由表。如果查询成功，获取发出接口和下一跳 IP，TTL 减 1，重新计算校验和，重新封装链路层帧，发送。

交换结构：共享内存、共享总线、纵横式 Crossbar

注意家用路由器和经典网络路由器差异较大。

Section 5.6: Congestion Control Algorithms¶

拥塞指网络数据包过多，导致传输延迟或丢失，从而使网络 throughput 下降。

拥塞控制需要确保子网能够承载用户提交的数据量，是全局性问题。

产生拥塞的原因：

数据包过多
缓冲区溢出（突发流量过多）
系统部分之间的速率不匹配

congestion control 和 flow control 的区别：

Congestion Control：Subnet, global
Flow Control：End-to-end traffic, local

基本策略：

开环控制——事先对通信流参数进行协商
闭环控制——反馈机制（显式/隐式）和控制机制，动态监测网络状态，调整发送速率

拥塞控制的途径¶

Network Provisioning: 增加网络供给
Traffic-aware Routing: 流量感知路由
Admission Control: 准入控制
Traffic Throttling: 流量节流
Load Shedding: 负载丢弃
Network Provisioning

增加网络供给，提升网络容量，减少拥塞发生的概率。

类比：修路

缺点：时效性最差（months）

Traffic-aware Routing¶

绕开热门的区域，疏散流量。

通过根据信息调整路径权重。

但路由表可能会出现反复变化，导致不稳定的路由，同时时效性较差（hours）

Admission Control¶

直接去掉发生拥塞的节点

这里的笔记不是很完整，上面的做法不一定对

Traffic Throttling¶

路由器判断拥塞什么时候发生（在拥塞发生前），通过反馈通知发送方降低发送速率。

感知

通过检测某时刻的带宽利用率实现对拥塞状态的最基本的监视。但是这种方法检测的是某一个瞬时值，但拥塞是动态变化的、连续的过程。

另一个方法是设定阈值，当带宽利用率超过该阈值时，认为发生拥塞。但是阈值的设定比较困难，且容易引发振荡。

一段时间采样，求平均值也是不可取的，无法反映动态变化。

Exponetially Weighted Moving Average (EWMA)

使用指数加权移动平均，考虑历史数据和当前数据的加权和。

\[ u(t+1) = \alpha \cdot u(t) + (1-\alpha) \cdot f(t+1) \]

其中 $f$ 指当前观测值，$\alpha$ 可以看作对历史数据的重视程度（遗忘度，越大越不容易忘）

反馈（控制）
Warning Bits: 警告位
Choke packets: 抑制包
Hop-by-hop Choke Packets: 单跳抑制包
Choke Packets

当路由器检测到拥塞时，选择一个被拥塞的数据包，向其源主机发送一个抑制包，通知其减少流量。

类型: 温和 mild, 严格 stern, 强制 ultimatum

显式拥塞通告（Explicit Congestion Notification, ECN）

在 IP Head 中记录数据包是否经历拥塞（ECN 位，11 表示路由器正在经历拥塞），路由器可以在包头中标记为经历拥塞，然后接收方在下一个应答数据包中回显该标记作为显式拥塞信号。

只有应答数据包返回发送方，ECN 才完成，减少流量；但若其间路径过长，效率较低。

Hop-by-hop Choke Packets

当 Choke Packet 返回源主机时，沿途的每一个路由器都可以检查该包，并减少该条路径上的流量。区别在于，Choke Packet 的流量控制只由源主机完成，而 Hop-by-hop Choke Packets 则由沿途的每一个路由器完成。

时效性：seconds

Load Shedding¶

前述是无损的拥塞控制，而 Load Shedding 是有损的拥塞控制。

当路由器检测到拥塞时，直接丢弃一些数据包，从而减轻拥塞。

问题是：丢谁？

随机丢弃

对随机丢弃，有进一步的问题：什么时候丢？然后再考虑丢谁。

所以路由器采取的措施是 RED（Random Early Detection，随机早期检测），尽早探测拥塞，尽早丢包（随机）。

每有数据包到达，计算平均队列长度 $L_{AV}$，若长度小于最小门限 $TH_{\min}$，正常发送；大于最大门限 $TH_{\max}$，直接丢；在最大最小之间，以一定概率 $p$ 随机丢弃。

可以将概率 $p$ 以分段线性函数的形式衡量其与 $L_{AV}$ 的关系。

Section 5.7: Quality of Service¶

网络服务质量概述¶

QoS 度量指标：

带宽
时延
抖动
丢包率

确保服务质量需要解决 4 个问题：

应用程序需要网络提供什么质量
如何规范进入网络的流量
为了保障性能，如何在路由器预留资源
网络能否安全地接收更多流量

流量整形¶

流量整形（Traffic Shaping）：限制流出某一网络的某一连接的流量和突发，使发出速度均匀

算法：漏桶算法（Leaky Bucket）、令牌桶算法（Token Bucket）

漏桶算法

漏桶算法将“水龙头流出的”数据包放入一个固定容量的桶（底部有漏孔）中，以恒定速率流出。如果桶满了，则新到的数据包被丢弃。

这样，漏桶漏出的流量是较为平滑的。

令牌桶算法

以恒定速率向桶中放入令牌，输入数据包必须从桶中获取一个令牌才能发送出去。如果桶中没有令牌，则数据包被丢弃。令牌桶满了，则新到的令牌被丢弃。

通常大包比小包消耗的令牌更多。

令牌桶与漏桶的区别在于，令牌桶允许突发流量（一小段时间），因为可以事先屯一些令牌，用于应对突发流量。

数据包调度¶

在同一流的数据包之间以及在竞争流之间分配路由器资源的算法，负责确定缓冲区中哪些数据包先发送到输出链路上。

先入先出（FIFO, First In First Out）
公平队列（Fair Queuing, FQ）——不同队列轮流
加权公平队列（Weighted Fair Queuing, WFQ）
优先级队列（Priority Queuing, PQ）

对于所有调度算法，都需要预留一些资源（Resource Reservation），以确保服务质量。

FCFS

略

FQ

or Round-Robin

WFQ

权重越大的队列，发送的数据量越多

\[ F_i = max \{ A_i, F_{i-1} \} + \frac{L_i}{W_j} \]

其中 $F_i$ 为（当前队列中）第 $i$ 个数据包的完成时间，$A_i$ 为到达时间，$L_i$ 为数据包长度，$W_j$ 为第 $j$ 个队列的权重。

根据上式计算的完成时间，每次选择最小的进行发送（output order）。

准入控制¶

对于每一个队列内部，可以使用前述令牌桶算法进行流量整形。

综合服务¶

总的来说就是资源预留的思路

资源预留协议（Resource Reservation Protocol, RSVP）

区分服务¶

DiffServ

在 IP 网络下分类和管理网络流量和提供不同级别的服务质量。

Assured Forwarding (AF)

规定四个优先级，对数据包进行相应的置位。

在路由器中使用加权公平队列进行调度。

Section 5.8: Layer 3 Switching¶

三层交换

二层交换中的广播限制了网络规模的发展，对于目标地址无法匹配的数据帧，需要进行广播转发，大量消耗网络资源。

之前我们使用虚拟局域网划分广播域来减少广播的开销，但是仍然无法避免跨 VLAN 通信时的广播。

单臂路由器通过在一个物理接口上配置多个逻辑子接口来实现不同 VLAN 之间的通信，但是这种方式虽然简化了物理拓扑，但不能应对流量瓶颈。

ARP 报文消耗大量网络资源的现象仍然存在。

三层交换机通过内置的二层交换引擎和与三层交换引擎之间的高速背板，将 ARP 过程隐藏在设备内部。

Chapter 6: The Transport Layer¶

传输层

Section 6.1: Introduction and Transport-Layer Services¶

进程对应端口。

如前述，进程间的通信是基于套接字（Socket）的。

传输层依赖于网络层提供的通路（不可靠）的服务，而其可靠性只能靠传输层自己实现。

具体来说，网络层是“尽力而为”，不保证交付、按序、无差错、延迟、带宽等，而传输层可以通过差错恢复、重排序等手段提供可靠、按序的交付服务。

但传输层无法提供延迟保证、带宽保证等服务。

Internet 传输层提供的服务：

最低限度传输：
- 进程-进程的数据交付
- 报文检错
增强服务
- 可靠数据传输
- 流量控制
- 拥塞控制

UDP 提供不可靠的数据报服务，TCP 提供可靠的字节流服务。

Section 6.2: Socket Prorogramming¶

略

Section 6.3: Multiplexing and Demultiplexing on the Transport Layer¶

复用（Multiplexing）
分用（Demultiplexing）

发送端的复用是指，传输层从多个套接字接收数据，将其封装在传输层报文段中，并交给网络层发送。对应的是接收端的分用，即传输层从网络层接收报文段，检查报文段头部信息，将数据交给相应的套接字。

传输层协议的寻址通过端口号实现，向下对应网络层的 IP 地址。

端口号是套接字标识的一部分，一共 16 bits，分为三类：

熟知端口（Well-Known Ports）：0-1023
注册端口（Registered Ports）：1024-49151
动态/私有端口（Dynamic/Private Ports）：49152-65535

端口号的分配有自动分配、？？等方式

UDP 的分用¶

UDP 套接字使用 $\langle IP, port\rangle$ 进行标识。

接收方传输层收到 UDP 报文后，检查端口号，将报文段交付到具有该端口号的套接字。

TCP 服务器使用的套接字¶

TCP 服务器通常使用两个套接字：

监听套接字（Listening Socket）：用于监听客户端连接请求，具有总所周知的端口号
连接套接字（Connected Socket）：用于与某个客户端通信，服务器有多个这样的套接字，从而与多个客户端通信

连接套接字需要使用四元组 $\langle src\ IP,\ src\ port,\ dest\ IP,\ dest\ port \rangle$ 进行标识。

Section 6.4: Connectionless Transport -- UDP¶

用户数据报协议（UDP, User Datagram Protocol）

提供服务：

进程-进程的数据交付
报文检错

需要实现：

复用和分用
差错检测

UDP 报文段结构¶

头：src port, dest port, length (bytes), checksum
payload（需要 padding，以便校验和的计算）

其中，校验和的作用是对传输的报文段进行检错，实现“兜底”的功能。

事实上，UDP 还有一个伪头部（pseudo header），加入校验和的计算中，避免由于 IP 地址错误等造成的误投递。

Pseudo Header 取自 IP 头部中的一些字段，包括源 IP 地址、目的 IP 地址、UDP 协议号（17）和 UDP 长度。

UDP 校验和的使用是可选的，若不使用则填入 0。

Section 6.5: Connection-Oriented Transport -- TCP¶

传输控制协议（TCP, Transmission Control Protocol）

将其建模为一个在一对进程之间的理想的字节流管道，是 point2point 通信，且保证可靠、有序。

需要的机制：

建立连接
可靠数据传输（包括检错、丢失重传等）
流量控制

TCP 报文段结构¶

头部

src port, dest port, seq num, ack num, head len, not used, flags(URG, ACK, PSH, RST, SYN, FIN), recv win, checksum, urg ptr, options(variable length)

seq num & ack num：字节流中的字节编号，而不是报文段的序号

MSS：TCP 中可以携带的最大数据字节数

window scale：窗口比例因子，实际接收窗口大小 $= win\ size * 2^{window\ scale}$

SACK：选择确认，允许接收端指出缺失的数据段

中间内容缺失！！！

TCP 确认的二义性问题

主要是重传和 ACK 的问题。

Karn 算法

发生重传，则将 RTO 加倍，并且不更新 RTT 估计值。

推迟确认

接收方收到数据段后，并不立即发送 ACK，而是等待一段时间。

这人为地影响了 RTO。

解决方法是接收方至少每隔一个报文段使用正常方式进行确认。

推迟确认的时间最多是 500 ms。

快速重传¶

仅靠超时重传来解决丢包问题，效率较低，恢复太慢。

TCP 中鲜明的特点是，接收方如果接收到乱序的数据段，会反复发送 ACK。这样，发送方可以利用重复的 ACK 检测报文段丢失。收到 3 个重复的 ACK 时，即使没有 time out，也立即重传。

注意发送方总共收到了四个相同的 ACK，其中第一个是正常的确认的 ACK 的 sequence number。

之所以是 “3” 个，是因为对于 $N-1$ 到 $N+2$ 四个包，考虑仅失序和丢包且可能失序两种情形，如果丢包，则一定会收到 3 次重复的 ACK($N$)。（具体情况排布见 Slides）

流量控制¶

TCP 接收方的缓存空间是有限的，因此可能出现因缓存溢出，从而丢包的情形。

解决思路是发送方调节流量速率。

GBN/SR 不需要流量控制的原因是，发送方根据 ACK 可以知道哪些窗口空出，从而控制发送流量。

UDP 的原因：？？？

定义接收缓存中可用空间为接收窗口 RevWindow，将 RevWindow 放在报头中报告给发送方。

发送方限制未确认字节数不超过接收窗口的大小。当接收方通告的窗口为 0 时，发送方必须立刻停止发送。接收缓存中，部分数据按序交付给上层后，窗口变为非 0，应当通告发送方，允许其继续数据发送。

触发 TCP 传输的条件：

应用程序调用
超时
收到数据/确认

对于接收方来说，能用到的触发 TCP 的条件只有第三个“收到数据/确认”。问题就在于，接收方接收窗口变为非 0 时，触发不了第三条件，从而无法发送非零窗口通告。

因此这里设计者做了一个补丁，发送方收到零窗口通告时，可以过一段时间后，发送零窗口探测的报文（序号为上一个段中最后一个字节的序号），从而接收方有机会发送非零窗口通告。

这里“过一段时间”就需要计时器来实现，称为“坚持计时器”（persistence timer）。如果恢复零窗口通告，则重新启动坚持计时器。

上面简单的实现有一个问题，当发送速率很大，而接收数据交付的速率很小，接收方不断发送微小窗口通告，发送方不断发送很小的数据分组，大量带宽被浪费。（糊涂窗口综合征）

解决方式是接收方启发式策略和发送方启发式策略。

接收方启发式策略

仅当窗口大小显著增加之后才发送更新的窗口通告。显著增加指的是达到缓冲区的一半或者一个 MSS（最大报文段长度），取两者较小的值。

TCP 执行该策略的方式是，窗口大小不满足时，接收端推迟发送确认（如前述），寄希望于推迟间隔内更多数据被消耗。

发送方启发式策略

发送方应当积聚足够多的数据，再发送。问题是发送方应该等待多长时间？更重要的是，TCP 不知道应用程序会不会在将来生成更多的数据。

对新建立的连接，当应用数据到来时，组成 TCP 段发送，哪怕只有一个字节。

在收到确认之前，后续到来的数据放在发送缓存中。

当积累的数据达到一个 MSS，或者上一次传输的确认到来（取两者较小的时间），用一个 TCP 段将缓存的字节全部发走。

上面的解决方案不适用于即时性要求很高的应用程序。

连接管理¶

在不可靠的网络中，两次握手是不可靠的，可能存在重传、乱序等意外。（Slides 上“半开连接”的例子）

因此，TCP 使用三次握手建立连接。

连接的初始序号不能从 0 开始，这样旧连接上重传的报文段可能被误认为新连接上的报文段。

随机选取初始序列号似乎还行，但是当两个连接的初始序列号相差不大时，仍可能重叠。

总之，我们在想办法避免这种重叠。

一种思路是，使用一次性的传输地址，如果序列号在此前出现过，将包丢弃。这对系统来说负担很大。

另一种思路是维护一个 log，记录历史信息。这也付出很大的存储代价。

现在考虑区分同一连接中重复的包和新连接的同序号包的方法：将 Sequence Number 空间设计的很大（32 bits 长）。这样，可以通过衡量时间来给出判断。

对重传的包，用其生命周期的倍数 $T = n * pkt\ lifetime$ 作为其时间的上界估计，即认为一个包在发出后的 $T$ 时间后不可能继续存活，进而不可能被接收。

通过定义 forbidden region 来限制序列号的使用。（Slides）

使用系统时钟的时间戳加上随机数来构建 ISN，使得新连接的 SeqN 远大于旧连接，从而实现“$T$ 秒禁止重复”。

具体来说，每个主机使用一个时钟（二进制计数器），每隔 $\Delta T$ 计数器加一。新建连接时，以本地计数器值的低 32 位作为起始序号，确保连接的 ISN 对时间单调增加。

这里 $\Delta T$ 应当取较小的值（$4\mu s$），确保发送 SeqN 的增长慢于 ISN 增长。另外还需要使用较长的字节序号（32 位），确保序号回绕的时间远大于分组在网络中的最长寿命。

为了避免进入 forbidden region，传数据的速率应当是 1segment/ clock tick；？？？

\[ \frac{S}{C}>T \]

forbidden region 的斜率就是时钟脉冲周期的倒数，增长到时钟周期（与时钟的 bits 相关）停止。

如上机制就保证了三次握手是足够可靠的，解决两次握手带来的半开连接的问题。

四次挥手释放连接。

故障恢复¶

TCP 连接可能因为各种原因中断，如网络故障、主机崩溃等。

对于面向连接（TCP）来说，实现故障恢复是比较困难的。

Server Behavior：先 ACK 后 Write，或者先 Write 后 ACK
Client Behavior：仅当在 S1 状态时 retrainsmission

Crash 可能发生在 A，W 前后或中间的任意位置。

![[fig-6-5-a.png]]

无法保证仅在传输层实现无差错无冗余的故障恢复（上表中全部都是 OK），需要应用层来兜底。

差错控制和流控制¶

流控制是为了防止接收方缓存溢出，而差错控制是为了防止数据出错、丢失等。

数据链路层的差错控制只关注本层，无法保证传输层的正确。

Section 6.6: Understanding Network Congestion¶

原因：大量分组短时间进入网络，超出处理能力
措施：减少进入网络的分组

与流量控制的区别：流量控制是端到端的（关注接收端能不能收），拥塞控制是网络范围的（关注网络能不能装）

网络拥塞造成丢包、分组延迟增大，此时大量网络资源用于重传丢失的或延迟过大（这是原本是不必要的）分组，伴随着转发最终被丢弃的分组，最后网络 load 很大，但是 throughput 很小。

拥塞控制方法¶

网络辅助的方法：

路由器向端系统提供显式反馈

端到端方法：

网络层不向端系统提供反馈
端系统观察丢包和延迟，自行推断拥塞发生
这是 TCP 采用的方法

TCP: Congestion Control¶

AIMD

加性增，乘性减

ACK 时延反映了 bottleneck 的路径的情况，因此可以作为主要的观察 Congestion 的指标。

而 ACK 时延可以用 RTT 衡量。

Section 6.7: TCP: Congestion Control¶

三个问题：

发送方如何感知拥塞
发送方如何限制发送速率
发送方感知到网络拥塞后，采取什么策略调节发送速率？

发送方利用丢包事件（重传定时器超时，或者收到 3 个重复的 ACK，即快速重传）感知拥塞。

发送方采用拥塞窗口 cwnd 限制已发未确认的数据量。

\[ \text{rate}=\frac{\text{cwnd}}{\text{RTT}} \text{ Bytes/sec} \]

cwnd 随发送方感知的网络拥塞程度而变化。

拥塞窗口调节策略：AIMD¶

Multiplicative Decrease

检测到丢包，cwnd 直接减半（不能小于一个 MSS）

Additive Increase

若无丢包，每经过一个 RTT，将 cwnd 增大一个 MSS

AIMD 对于新建立的连接增长非常慢（加性增）

慢启动

慢启动是为了解决上面提到的新连接增长慢的问题。在新建连接上指数增大 cwnd，直至检测到丢包。

策略是，每经过一个 RTT，将 cwnd 加倍。具体来说，每收到一个 ACK，cwnd 增加一个 MSS，只要发送窗口允许，发送端可以立刻发送下一个报文段。

发生超时重传时，cwnd=1 MSS

区分丢包的原因

超时和连续 3 个重复 ACK 反映出的拥塞程度不同。超时说明交付能力极差，连续 3 个 ACK 说明网络还有一定的交付能力。

3 ACK：将 cwnd 减半，并使用 AIMD 继续调节；
超时：设置 threshold = cwnd/2，然后令 cwnd = 1MSS。使用慢启动增加至 threshold，此后使用 AIMD

发送方维护一个 ssthresh，发生丢包时，ssthresh = cwnd/2。

cwnd 低于门限时，慢启动；反之，执行拥塞避免。（如果慢启动超过阈值，取与阈值最接近的一个窗口大小）

超过阈值后，拥塞避免（线性增）：每当收到 ACK，$cwnd=cwnd+MSS*(MSS/cwnd)$

快速恢复（检测到 3 ACK）：

TCP Reno 实现：$cwnd = ssthresh +3$
TCP Tahoe 实现：丢包 $cwnd=1 MSS$，慢启动，超过阈值线性增

注意：收到 1 个重复 ACK，只是将重复的次数记录。

注意：慢启动到线性增的转变是以 ACK 为单位的，而不是 RTT 为单位的。例如某一轮预期收到 8 个 ACK，但是在收到第一个后 cwnd 就达到了 ssthresh，那么本轮后续的 ACK 都会以线性增的方式处理（加上 $7\times \frac{MSS}{cwnd}$）。

TCP 公平性¶

一条带宽为 R 的链路，同时是 K 条链路的瓶颈，公平分配 $R/K$

若相互竞争的TCP连接具有不同的参数（RTT、MSS等），不能保证公平性。

若应用（如web）可以建立多条并行TCP连接，不能保证带宽在应用之间公平分配，比如：

一条速率为R的链路上有9条连接
若新应用建立一条TCP连接，获得速率 R/10
若新应用建立11条TCP，可以获得速率 R/2 !