计算机网络进阶

1. TCP 拥塞控制

1.1 拥塞控制原理

发送方维护拥塞窗口（cwnd），实际发送窗口：

$\text{发送窗口}=\min (\text{cwnd},\text{rwnd})$

1.2 慢启动

• 初始 cwnd = 1 MSS（最大段大小）
• 每收到一个 ACK，cwnd 增加 1 MSS
• 指数增长：cwnd 经过 $n$ 个 RTT 后为 $2^n$ MSS
• 到达慢启动阈值（ssthresh）后转为拥塞避免

1.3 拥塞避免

• 每个 RTT，cwnd 增加 1 MSS
• 线性增长：cwnd 每经过一个 RTT 加 1

${\text{cwnd}}_{new}=\text{cwnd}+\frac{{\text{MSS}}^2}{\text{cwnd}}$

1.4 快速重传与快速恢复

快速重传：收到 3 个重复 ACK，立即重传丢失段。

快速恢复：

1. ssthresh = cwnd / 2
2. cwnd = ssthresh + 3 MSS
3. 每收到重复 ACK，cwnd 增加 1 MSS
4. 收到新 ACK，cwnd = ssthresh，进入拥塞避免

1.5 TCP 拥塞控制状态机

慢启动 → ssthresh → 拥塞避免
  ↑                     │
  │    超时：ssthresh=cwnd/2, cwnd=1
  │                     │
  └─────────────────────┘

拥塞避免 → 3重复ACK → 快速恢复 → 新ACK → 拥塞避免

1.6 BBR 算法

Google 提出的基于模型的拥塞控制：

$\text{BDP}=\text{带宽}\times \text{RTT}$

BBR 目标：将 cwnd 设为 BDP，而非基于丢包调整。

2. 路由算法

2.1 距离向量算法（DV）

Bellman-Ford 方程：

$D(x,y)={\min }_v\{c(x,v)+D(v,y)\}$

RIP 协议：

• 使用跳数作为度量
• 最大跳数 15（16 视为不可达）
• 每 30 秒广播路由表
• 问题：计数到无穷

毒性逆转：向邻居通告到其自身的距离为无穷大。

2.2 链路状态算法（LS）

Dijkstra 算法：

1. 每个节点构建完整的网络拓扑图
2. 从源节点运行 Dijkstra 最短路径算法
3. 时间复杂度：$O(n^2)$ 或 $O((n+m)\log n)$（优先队列）

OSPF 协议：

• 使用链路状态算法
• 支持区域划分
• 支持等价多路径（ECMP）

2.3 路径向量算法

BGP 协议：

• 自治系统间的路由协议
• 通告完整路径（AS 序列）
• 基于策略的路由选择

BGP 选路优先级：

1. 最高本地优先级
2. 最短 AS 路径
3. 最低起源类型
4. 最低 MED
5. eBGP > iBGP
6. 最低 IGP 度量

3. 软件定义网络（SDN）

3.1 SDN 架构

应用层（网络应用）
    ↕ 北向 API
控制层（SDN 控制器）
    ↕ 南向 API（OpenFlow）
基础设施层（交换机/路由器）

3.2 OpenFlow 协议

流表结构：

3.3 SDN 优势

• 集中控制：全局视图优化
• 可编程：灵活部署网络服务
• 开放接口：设备解耦

4. 服务质量（QoS）

4.1 QoS 参数

4.2 QoS 机制

流量整形：

• 令牌桶：以速率 $r$ 生成令牌，桶容量 $b$
  • 允许突发：最多发送 $b$ 个包
  • 长期平均速率不超过 $r$

$\text{合规条件}：\text{任意时间 }t\text{ 内发送量}\le b+r\times t$

• 漏桶：恒定速率输出，平滑突发

分类与标记：

• DSCP（DiffServ Code Point）：IP 头中的 QoS 标记
• 802.1p：VLAN 标签中的优先级

队列调度：

4.3 DiffServ 模型

• 边界路由器：分类、标记、整形
• 核心路由器：基于 DSCP 转发

每跳行为（PHB）：

5. 网络性能分析

5.1 排队论基础

M/M/1 队列：

• 到达率 $\lambda$，服务率 $\mu$
• 利用率 $\rho =\lambda /\mu$
• 平均队列长度：$L=\frac{\rho }{1-\rho }$
• 平均等待时间：$W=\frac{1}{\mu -\lambda }$

Little 定律：

$L=\lambda \times W$

5.2 网络延迟分析

$\text{总延迟}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$

5.3 吞吐量分析

$\text{端到端吞吐量}=\min (R_1,R_2,...,R_n)$

瓶颈链路决定端到端吞吐量。

5.4 网络可靠性

$\text{可用性}=\frac{\text{MTTF}}{\text{MTTF}+\text{MTTR}}$

$\text{年停机时间}=(1-\text{可用性})\times 8760\text{ 小时}$