计算机网络自顶向下方法第九版学习:第4章复习题与习题详解

虾球xz

467人浏览 · 2026-05-02 18:59:17

虾球xz · 2026-05-02 18:59:17 发布

网络层数据平面：路由器内部结构、IP协议、广义转发、SDN

一、复习题解答

Section 4.1

R1. 网络层数据包叫什么？路由器和链路层交换机的本质区别是什么？

网络层数据包叫做数据报（datagram）
- 传输层叫：报文段（segment）
- 链路层叫：帧（frame）
路由器 vs 链路层交换机：

对比维度	路由器（Router）	链路层交换机（L2 Switch）
工作层次	网络层（第3层）	链路层（第2层）
转发依据	IP地址	MAC地址
转发表	路由/转发表（按IP前缀）	MAC地址表（按MAC地址）
能否跨网段通信	能	不能（只在同一网段内）

R2. 数据平面和控制平面的主要功能分别是什么？

平面	主要功能	实现方式
数据平面（Data Plane）	每个路由器内部：决定从哪个输入端口到来的包从哪个输出端口转发出去——即"转发"	硬件实现（纳秒级）
控制平面（Control Plane）	网络范围：决定数据包从源到目的经过哪条路径——即"路由"	软件实现（毫秒级）

简单记忆：数据平面管"怎么走这一步"，控制平面管"走哪条路"。
R3. 转发（Forwarding）和路由（Routing）的关键区别？

转发（Forwarding）：
  - 局部操作，发生在单个路由器内部
  - 查转发表，决定从哪个输出端口发出
  - 时间尺度：纳秒级（硬件完成）
  - 类比：在十字路口看路牌决定往哪个方向走
路由（Routing）：
  - 全局操作，涉及整条路径的规划
  - 运行路由算法（如OSPF、BGP），生成转发表
  - 时间尺度：秒级（软件计算）
  - 类比：出发前规划从北京到上海走哪条高速

R4. 转发表在路由器中的作用？
转发表是路由器进行目的地转发的核心数据结构：

存储"目的IP前缀 → 输出端口"的映射关系
路由器收到数据包后，用目的IP地址查转发表，找到对应输出端口，将包送入交换结构
使用最长前缀匹配规则：当多条前缀都匹配时，选最长（最具体）的那条
R5. 互联网网络层的服务模型是什么？提供什么保证？
互联网网络层采用**尽力而为（Best-Effort）**服务模型：
不保证数据包的按序到达
不保证数据包不丢失
不保证端到端时延的上界
不保证最小带宽
换句话说：互联网网络层什么都不保证，可靠性全部交给上层（TCP）来处理。

Section 4.2

R6. 路由器各组件哪些用硬件实现，哪些用软件实现？

组件	实现方式	原因
输入端口（Input Port）	硬件	需要在纳秒级完成查表和转发决策，只有硬件才够快
输出端口（Output Port）	硬件	同上，高速排队和发送需要硬件
交换结构（Switching Fabric）	硬件	要在极短时间内将包从输入搬到输出
路由处理器（Routing Processor）	软件	运行路由协议、管理转发表，对速度要求相对低

对应到数据平面/控制平面：

数据平面（转发）→ 硬件
控制平面（路由计算）→ 软件
R7. 为什么高速路由器的每个输入端口都存一份转发表的副本（影子拷贝）？
目的：避免每次查表都访问中央路由处理器，消除瓶颈。

不用影子拷贝的情况：
  输入端口1 ──查表──→ 中央路由处理器 ──→ 结果
  输入端口2 ──查表──→ 中央路由处理器 ──→ 结果  （串行，慢！）
  输入端口N ──查表──→ 中央路由处理器 ──→ 结果
用影子拷贝的情况：
  输入端口1 ──查本地表──→ 结果（无需访问中央处理器）
  输入端口2 ──查本地表──→ 结果（并行，快！）
  输入端口N ──查本地表──→ 结果

每个输入端口保存一份完整转发表的副本，可以并行、独立地完成转发决策，大幅提升吞吐量。
R8. 什么是目的地转发？它与广义转发有何不同？SDN采用哪种？

对比维度	目的地转发	广义转发
匹配字段	只看目的IP地址	可以匹配多个字段（源IP、目的IP、端口号、MAC、入端口……）
动作	只能转发到某个端口	可以转发、丢弃、修改字段、发给控制器等
灵活性	低	高
实现复杂度	低	高

SDN 采用广义转发（OpenFlow 流表）。

R9. 数据包匹配到多条转发表规则时，用什么规则决定？
传统目的地转发：使用最长前缀匹配（Longest Prefix Match）。

选择前缀位数最多（最具体）的那条规则
例：目的IP 200.23.18.5 同时匹配 /20 和 /23，选 /23

R10. 三种交换结构及其并行能力？

只有**交叉开关（Crossbar）**可以在同一时刻并行传输多个不冲突的数据包。
R11. 输入端口如何发生丢包？如何消除？
发生原因： 输入端口队列满，新到达的包无处存放，被丢弃。
更隐蔽的原因——HOL（队头阻塞）：

输入端口1队列：[包A→输出3][包B→输出2][包C→输出1]
                    ↑
         包A要去输出3，但输出3被占用
         包B虽然输出2空闲，但被包A挡住，无法发送
         → 包B、C白白等待 = HOL阻塞

消除方法（不用无限缓冲）：
使用交叉开关并配合合理的调度策略（如输入排队调度），可以让每个输入端口的包独立向不同输出端口发送，大幅减少甚至消除 HOL 阻塞。
R12. 输出端口如何发生丢包？提升交换结构速度能否防止？
发生原因： 当多个输入端口同时向同一个输出端口发包时，短时间内到达的包超过了输出链路的发送能力，缓冲区溢出。
提升交换结构速度能防止吗？
不能。 交换结构再快，也无法改变输出链路的带宽上限——如果5个输入端口同时各自发来一个满速包，它们都想从同一个输出端口出去，输出端口每次只能发一个，剩下的必须排队，缓冲区终究会满。
R13. HOL阻塞是什么？发生在输入端口还是输出端口？
HOL（Head-of-Line Blocking，队头阻塞） 发生在输入端口：

队列头部的包因目标输出端口被占用而无法前进
它身后的包即使目标输出端口空闲，也被挡住无法发送
导致输入端口带宽利用率严重下降（理论上最坏只有 $\approx 58\%$ ）
R14. 哪种调度能保证包按到达顺序离开？
只有 FIFO（先进先出） 保证包严格按到达顺序离开。
优先级队列、轮询（RR）、WFQ 都可能改变离开顺序。
R15. 举例说明为什么需要给某类包更高优先级？
例：企业网络中同时运行视频会议和文件备份：
视频会议是实时流量，延迟超过 150ms 就会出现卡顿，严重影响体验
文件备份是弹性流量，传得慢一点完全可以接受
若不区分优先级，大量文件备份流量可能将视频包堵在队列里，导致视频通话质量急剧下降。
设置优先级后，视频包优先发送，保证实时性；文件备份包在空闲时再传，两全其美。
R16. RR和WFQ的本质区别是什么？何时行为相同？

对比	轮询（RR）	加权公平队列（WFQ）
服务顺序	各类别轮流各发一个包	各类别按权重比例分配带宽
灵活性	每个类别得到等量服务	权重高的类别得到更多带宽

何时行为完全相同： 当所有类别的 WFQ 权重相等时（如都为1），WFQ 退化为 RR，行为完全一致。

Section 4.3

R17. Host B 如何知道把 IP 载荷交给 TCP 而不是 UDP？
靠 IPv4 数据报头部的协议号（Protocol）字段：

值为 6 → 交给 TCP
值为 17 → 交给 UDP
值为 1 → 交给 ICMP
这个字段就是网络层和传输层之间的"胶水"。
R18. IP头部哪个字段可以限制包最多经过N个路由器？
TTL（Time-to-Live，存活时间）字段：
发送方设置 TTL = N
每经过一个路由器，TTL 减 1
TTL 减到 0 时，路由器丢弃该包并返回 ICMP 错误消息
这样包最多经过 N 个路由器
R19. 传输层校验和和IP层校验和是否覆盖相同的字节？
不覆盖相同的字节：
IP 头部校验和：只校验 IP 头部（20字节），不包含数据载荷
TCP/UDP 校验和：校验 整个 TCP/UDP 报文段（头部+数据），外加一个伪头部（包含源/目的IP地址等）
两者唯一的"公共部分"是伪头部中的IP地址字段，但伪头部本身不是IP数据报的一部分，只是计算校验和时临时使用的。
因此两个校验和几乎不覆盖完全相同的字节。
R20. 大数据报分片后，在哪里重组？
在目的主机处重组，不在中间路由器处重组。
IPv4 允许中间路由器分片，但重组只在目的端进行
IPv6 根本不允许中间路由器分片（源端如果发现包太大，必须自己分；路由器直接丢包并返回"Packet Too Big"）
R21. 路由器有IP地址吗？有几个？
有。路由器每个接口（interface）都有一个IP地址。
一台有 N 个接口的路由器就有 N 个 IP 地址。（IP地址与接口绑定，不与设备绑定。）
R22. 223.1.3.27 的32位二进制是什么？

223  = 11011111
  1  = 00000001
  3  = 00000011
 27  = 00011011
结果：11011111 00000001 00000011 00011011

R23. DHCP 获取信息（概念说明）
DHCP 客户端通常可以获取并查看以下信息（以 Linux 为例用 `ip addr` 和 `ip route` 命令查看）：

信息项	示例值
IP 地址	192.168.1.105
子网掩码	255.255.255.0 (/24)
默认网关（第一跳路由器）	192.168.1.1
本地 DNS 服务器地址	192.168.1.1（或运营商DNS如 8.8.8.8）

R24. 经过3个路由器，包经过多少个接口和转发表？

源主机 → 路由器1 → 路由器2 → 路由器3 → 目的主机
接口（interfaces）：
  源主机出口 = 1
  路由器1入口 + 出口 = 2
  路由器2入口 + 出口 = 2
  路由器3入口 + 出口 = 2
  目的主机入口 = 1
  总计：1 + 2 + 2 + 2 + 1 = 8 个接口
转发表查询次数：
  每个路由器查一次 → 3 次（源主机和目的主机不查转发表）

R25. 数据报中头部开销占比是多少？
应用数据：40 字节
IP头部：20 字节，TCP头部：20 字节，总头部：40 字节
$\text{总数据报大小} = 40 + 40 = 80 \text{ 字节}$
$\text{头部占比} = \frac{40}{80} = 50\%$
$\text{应用数据占比} = \frac{40}{80} = 50\%$
R26. 无线路由器后面5台电脑的IP如何分配？用NAT吗？

ISP 给无线路由器分配一个公网IP（通过DHCP）
无线路由器内置DHCP服务器，给5台电脑各分配一个私有IP（如 192.168.1.x）
无线路由器使用NAT：5台电脑共享那一个公网IP与外网通信
使用 NAT 的原因：ISP 只给了一个公网IP，但5台设备都需要访问互联网，NAT 用端口号区分各设备的连接。
R27. 路由聚合（Route Aggregation）是什么？为什么有用？
路由聚合（也叫地址聚合/路由汇总）： 将多个连续的小地址块合并成一个大地址块来宣告。

不聚合时（8条路由）：
  200.23.16.0/23
  200.23.18.0/23
  200.23.20.0/23
  ...（共8条）
聚合后（1条路由）：
  200.23.16.0/20 → 涵盖上述所有8个/23块

好处：

减少互联网骨干路由器的路由表条目数量（路由表爆炸是互联网扩展性的重大挑战）
加快路由查找速度
减少路由更新消息的传播
R28. 什么是"即插即用"或"零配置"协议？
即插即用（Plug-and-Play）/ 零配置（Zeroconf）协议 = 设备接入网络后不需要人工配置，自动完成所有网络参数的获取。
DHCP 是典型代表：设备插上网线（或连接WiFi），自动获取IP地址、子网掩码、默认网关、DNS服务器，无需管理员手动配置。
R29. 什么是私有网络地址？私有地址应该出现在公共互联网上吗？
私有地址： 仅在内部网络（如家庭网、企业网）内有意义的IP地址，全球有无数网络使用相同的私有地址段：

私有地址块	用途
`10.0.0.0/8`	大型企业内网
`172.16.0.0/12`	中型网络
`192.168.0.0/16`	家庭/小型网络

不应该出现在公共互联网上。 因为：

全球有无数网络都在用 192.168.1.x，路由器无法区分哪个是哪个网络的 192.168.1.1
私有地址在互联网上不可路由，含私有地址的包会被丢弃
NAT 的职责就是在包进出边界时替换私有地址和公网地址。
R30. IPv4 和 IPv6 头部字段对比

字段	IPv4	IPv6	备注
版本号	4位，值=4	4位，值=6	相同位置，不同值
服务类型/流量类别	TOS（8位）	Traffic Class（8位）	功能类似
TTL / 跳数限制	TTL（8位）	Hop Limit（8位）	功能相同，名字不同
协议号 / 下一头部	Protocol（8位）	Next Header（8位）	功能相同
源/目的地址	各32位	各128位	IPv6大幅扩展
头部长度	有（4位）	无（固定40字节）	IPv6固定头部，不需要
总长度	有（16位，含头部）	负载长度（16位，不含头部）	计算方式不同
校验和	有	无	IPv6删除，提升速度
分片字段	有	无（端系统分片）	IPv6删除，提升速度
可选项	有（可变长）	无（改用Next Header链）	IPv6固定头部
流标签	无	有（20位）	IPv6新增

R31. IPv6 通过IPv4隧道传输时，是否把IPv4当作链路层协议？
同意这个说法。
原因类比：

在正常协议栈中，链路层为网络层提供传输服务（如以太网帧承载IP包）
在IPv6隧道中，IPv4为IPv6提供传输服务：IPv6整个数据报被封装在IPv4的数据字段里

正常情况：
  [以太网帧头] + [IPv4数据报] = 链路层承载网络层
隧道情况：
  [IPv4头部] + [IPv6数据报] = IPv4承载IPv6
                                ↑
                          相当于IPv4在这里扮演了"链路层"的角色

IPv6 节点看到的是：把 IPv4 当作一条"虚拟链路"，对端是隧道出口的 IPv6 节点。

Section 4.4

R32. 广义转发与目的地转发的区别？
见 R8，简要重述：

目的地转发：只匹配目的IP，只能转发
广义转发：匹配多个字段（跨多个协议层），可以执行丰富的动作（转发、丢弃、修改字段……）
R33. 传统转发表与 OpenFlow 流表的区别？

对比	传统转发表	OpenFlow 流表
匹配字段	只有目的IP前缀	12个字段（IP、MAC、端口号……）
动作	只有"转发到端口X"	转发、丢弃、修改字段、发给控制器
计数器	通常没有	每条规则有匹配计数和时间戳
来源	路由算法在本地计算	远程控制器集中计算并下发
灵活性	低	高（可实现路由、防火墙、NAT、负载均衡…）

R34. 匹配+动作操作是什么？目的地转发中匹配什么、动作是什么？SDN中呢？
匹配+动作（Match-Plus-Action）： 对数据包头部字段进行匹配，根据匹配结果执行对应动作。
目的地转发：

匹配：目的IP地址（最长前缀匹配）
动作：转发到指定输出端口
SDN（OpenFlow）可匹配的三个字段举例：
源IP地址
目的IP地址
入端口（Ingress Port）
SDN 可执行的三个动作举例：
转发到指定端口
丢弃数据包
修改头部字段（如改写目的IP，用于NAT）
R35. OpenFlow 1.0 中可以匹配和不可以匹配的IP头部字段各举3个？
可以匹配（3个）：

源IP地址（IP Src）
目的IP地址（IP Dst）
IP协议号（IP Protocol）
不可以匹配（3个）：
TTL（存活时间）
数据报总长度（Datagram Length）
头部校验和（Header Checksum）

二、习题详解

P1. 路由器A的转发表

题意： 有一个网络拓扑，需要设计路由器A的转发表。
a. 所有去往H3的流量走接口3：

转发表（简化）：
┌────────────────────┬──────────┐
│  目的地址/前缀      │  出接口   │
├────────────────────┼──────────┤
│  H3的IP前缀        │   3      │
│  （其他）           │  默认接口 │
└────────────────────┴──────────┘

b. H1→H3走接口3，H2→H3走接口4——能做到吗？
不能！这是陷阱题。
传统目的地转发只看目的IP地址（H3的IP），不看源地址，因此无法区分"来自H1"还是"来自H2"——相同目的地只能对应一个出接口。
要实现这个需求，必须用广义转发（OpenFlow），同时匹配源IP和目的IP。

P2. 交换结构并行传输分析

场景： 两个包同时到达不同输入端口。
a. 共享总线（Shared Bus），目的是不同输出端口——能并行？
不能。 共享总线同一时刻只能被一个包使用，两个包必须串行通过总线。
b. 经内存交换（Switching via Memory），目的是不同输出端口——能并行？
不能。 经内存交换需要 CPU 将包从输入端口读入内存，再写到输出端口，内存总线是瓶颈，同样是串行操作。
c. 交叉开关（Crossbar），目的是相同输出端口——能并行？
不能。 即使是交叉开关，同一个输出端口在同一时刻只能接收一个输入，两个包都要去同一出口，产生竞争，只能串行。（如果是不同输出端口，交叉开关才能并行。）

P3. 不同交换结构的最大输入排队延迟

条件： 交换速率 $R_{switch} = R_{line}$ （即交换结构速度等于线路速度），所有包目的是不同输出端口，包传输时间为 $D$ 。
a. 经内存交换（Memory）：
内存总线是瓶颈，同一时刻只能处理一个包。N个输入端口中最坏情况是所有包排队等待前面的包处理完，最大排队延迟：
$D_{max} = (N-1) \cdot D$
b. 共享总线（Bus）：
与内存类似，总线同一时刻只能传一个包：
$D_{max} = (N-1) \cdot D$
c. 交叉开关（Crossbar）：
当所有包目的是不同输出端口时，交叉开关可以并行处理，不需要等待：
$D_{max} = 0$
（无排队延迟）

P4. 时隙调度（HOL vs 最优）

题意： 交叉开关，同步时隙，每时隙传一个包，求最少和最多时隙数。
通用分析框架（以常见教材例题为例）：

假设输入端口和目标输出端口的映射如下（教材给出具体图）：
最优调度（无HOL约束，自由选择）：
  - 每个时隙，选择不冲突的包集合（每个输出端口至多被一个包选中）同时传输
  - 利用匈牙利算法或贪心方法求最小时隙数
最差调度（故意制造最多等待）：
  - 每个时隙只传一个包，其余全部等待
  - 最多时隙数 = 包的总数

最少时隙数的计算原则： 每个时隙选出尽量多的不冲突包（每个输出端口最多一个）同时传输，直到所有包传完。

P5. WFQ 权重 0.5、0.25、0.25 的服务顺序

a. 三个类别都有大量包时，WFQ的服务顺序？
权重比为 $0.5 : 0.25 : 0.25 = 2 : 1 : 1$ ，即类别1获得 $50\%$ 带宽，类别2和3各获得 $25\%$ 。
可能的服务序列：1 2 1 3 1 2 1 3 …（类别1每2个时隙服务一次，类别2和3各每4个时隙服务一次）
或更精确地：1 1 2 3 1 1 2 3 … 等价序列，只要长期比例满足 $2 : 1 : 1$ 即可。
b. 只有类别1和2有包（类别3队列空），服务顺序？
权重按有包的类别重新归一化： $w_1 = 0.5, w_2 = 0.25$ ，比值 $= 2 : 1$ 。
服务序列：1 2 1 1 2 1 1 2 … 或等价地 1 1 2 1 1 2 …
类别3的份额被"回收"，当类别3没有包时，WFQ会立即跳过它（work-conserving原则）。

P6. 四种调度策略对比（时隙分析）

本题要求对给定的包到达时间图，分别计算FIFO、优先级、轮询、WFQ下各包的离队时间和延迟。
解题框架（适用于所有四种调度）：

已知条件（教材图）：
  - 12个包，每个包占用1个时隙传输
  - 每个包有到达时间（从图中读取）
  - 链路同一时刻只能传一个包
通用步骤：
  Step1: 列出每个包的到达时刻
  Step2: 按调度策略，逐时隙决定哪个包被发送
  Step3: 记录每个包的发送开始时刻（= 离队时刻）
  Step4: 计算延迟 = 发送开始时刻 - 到达时刻
  Step5: 求平均延迟

关键结论（e小问）：
无论采用哪种调度策略（FIFO、RR、优先级、WFQ），所有12个包的平均延迟都相同！
原因：调度策略只改变包的服务顺序，不改变"总工作量"。在单服务器模型中，总处理时间固定，平均等待时间由总负载决定，与调度顺序无关。调度策略影响的是不同类别包之间的公平性和延迟分布，不影响整体平均。

P8. 最长前缀匹配转发表（32位地址）

给定目的地址范围，需要找出匹配的CIDR前缀：
接口0： 地址范围 11100000 00000000 ... 到 11100000 00111111 ...

起始: 11100000 00000000 00000000 00000000
终止: 11100000 00111111 11111111 11111111
前18位相同：11100000 00（后面不同）
→ 前缀：11100000 00 = 224.0.0.0/10 ？
更仔细分析：
起始到终止，第3字节从00000000到00111111（即0~63），
第3字节前2位固定为00，后6位可变
→ 精确前缀：11100000 00 xxxxxx = 224.0.0.0/10
验证：
  11100000 00 = 前10位
  a.b.c.d/10 notation: 224.0.0.0/10
接口0前缀：224.0.0.0/10

接口1： 11100000 01000000 00000000 00000000 到 11100000 01000000 11111111 11111111

第1、2字节固定，第3字节 = 01000000（固定），第4字节可变
→ 前24位固定：11100000 01000000 01000000
→ 前缀：224.64.64.0/24 ? 
重新看：
  11100000 01000000 = 前16位（224.64）
  第3字节: 00000000（固定）
  → 前24位固定: 11100000 01000000 00000000
  → 接口1前缀：224.64.0.0/24

接口2： 11100000 01000001 00000000 00000000 到 11100001 01111111 11111111 11111111

这个范围跨越了224.65.x.x 到 225.127.x.x，需要多个前缀覆盖，
或使用一个较短前缀覆盖（精确分析在实际题目图中确认）。

a. 转发表（使用 a.b.c.d/x 记法）：

前缀（点分十进制/x）	接口
224.0.0.0/10	0
224.64.0.0/24	1
224.64.1.0/24	2（部分）
（其余）	3

b. 判断三个目的地址走哪个接口：

11001000 10010001 01010001 01010101 = 200.145.81.85
  → 前缀不匹配接口0、1、2 → 接口3
11100001 01000000 11000011 00111100 = 225.64.195.60
  → 前11位: 11100000 0 匹配/10 ? 
    11100001 ≠ 11100000 → 不匹配接口0
  → 检查是否匹配接口2的范围 → 属于接口2
11100001 10000000 00010001 01110111 = 225.128.17.119
  → 不匹配接口0、1、2 → 接口3

P9. 8位地址空间，最长前缀匹配

给定前缀表：

前缀	接口
00	0
010	1
011	1
10	2
11	3

各接口对应的地址范围（8位地址）：
接口0（前缀 00）：

00000000 ~ 00111111 = 0 ~ 63，共 64 个地址

接口1（前缀 010 或 011）：

010xxxxx = 64 ~ 95（32个）
011xxxxx = 96 ~ 127（32个）
共 64 个地址（64 ~ 127）

接口2（前缀 10）：

10000000 ~ 10111111 = 128 ~ 191，共 64 个地址

接口3（前缀 11）：

11000000 ~ 11111111 = 192 ~ 255，共 64 个地址

P10. 8位地址，另一组前缀表

前缀	接口
1	0
10	1
111	2
otherwise	3

分析（最长前缀匹配优先）：
接口3（otherwise，即以 0 开头的地址）：

0xxxxxxx = 0 ~ 127，共 128 个地址

接口0（前缀 1，但需排除被更长前缀覆盖的部分）：

1xxxxxxx 共 128 ~ 255
但其中 10xxxxxx 被接口1覆盖，111xxxxx 被接口2覆盖
→ 接口0只剩：100xxxxx 和 110xxxxx
  100xxxxx = 128 ~ 159（32个）
  110xxxxx = 192 ~ 223（32个）
  共 64 个地址

接口1（前缀 10）：

10xxxxxx = 128 ~ 191（排除被更长前缀覆盖的）
但 10 只有2位，接口1前缀最长，无需再排除
→ 128 ~ 191，共 64 个地址
（注意：接口0的1前缀比接口1的10短，所以10xxxxxx匹配接口1）

接口2（前缀 111）：

111xxxxx = 224 ~ 255，共 32 个地址

汇总：

接口	地址范围	数量
0	128~159, 192~223（前缀1，排除10和111）	64
1	128~191（前缀10）	64
2	224~255（前缀111）	32
3	0~127（otherwise）	128

P11. 三个子网的地址分配

前提：都使用前缀 `223.1.17.0/24`，在此基础上划分子网。
需求：子网1 ≥ 60接口，子网2 ≥ 90接口，子网3 ≥ 12接口。
`/24` 有8位主机位，共 $2^8 = 256$ 个地址。
子网2（最大需求90，需要至少7位主机位， $2^7-2=126 \geq 90$ ）：
$\quad \text{（主机位7位，可用126个地址，满足90）}$
子网1（需求60，需要至少6位， $2^6-2=62 \geq 60$ ）：
剩余地址从 `223.1.17.128` 开始：
$\quad \text{（主机位6位，可用62个地址，满足60）}$
子网3（需求12，需要至少4位， $2^4-2=14 \geq 12$ ）：
剩余地址从 `223.1.17.192` 开始：
$\quad \text{（主机位4位，可用14个地址，满足12）}$
答案汇总：

子网	地址	可用主机数
子网2	223.1.17.0/25	126 ≥ 90
子网1	223.1.17.128/26	62 ≥ 60
子网3	223.1.17.192/28	14 ≥ 12

P14. 子网划分

给定： ISP 拥有 128.119.40.64/26，要划分4个等大小子网。
/26 有6位主机位，共 $2^6 = 64$ 个地址，划分4个子网：
每个子网 $64/4 = 16$ 个地址，即 /28（4位主机位）。
$\text{子网1: } 128.119.40.64/28 \quad (64 \sim 79)$
$\text{子网2: } 128.119.40.80/28 \quad (80 \sim 95)$
$\text{子网3: } 128.119.40.96/28 \quad (96 \sim 111)$
$\text{子网4: } 128.119.40.112/28 \quad (112 \sim 127)$

P17. MP3 分片数计算

条件： 最大数据报 1500 字节，IP头 20 字节，MP3 文件 5,000,000 字节。
每个数据报最大载荷： $1500 - 20 = 1480$ 字节
$\text{需要的数据报数} = \left\lceil \frac{5{,}000{,}000}{1480} \right\rceil = \left\lceil 3378.38 \right\rceil = 3379 \text{ 个数据报}$

P18. NAT 转换表

条件：路由器公网IP `24.34.112.235`，内网 `192.168.1.0/24`，5台主机，每台2个TCP连接到 `128.119.40.86:80`。
a. 内网地址分配（示例）：

设备	内网IP
路由器内网接口	192.168.1.1
主机1	192.168.1.2
主机2	192.168.1.3
主机3	192.168.1.4
主机4	192.168.1.5
主机5	192.168.1.6

b. NAT转换表（6条，每台主机2个连接，只列3台示例）：

内网 IP:端口	公网 IP:端口
192.168.1.2:3001	24.34.112.235:5001
192.168.1.2:3002	24.34.112.235:5002
192.168.1.3:3001	24.34.112.235:5003
192.168.1.3:3002	24.34.112.235:5004
192.168.1.4:3001	24.34.112.235:5005
192.168.1.4:3002	24.34.112.235:5006

P20. OpenFlow 流表设计（s2）

需求：

接口1来自h5/h6，目的h1/h2 → 从接口2发出
接口2来自h1/h2，目的h5/h6 → 从接口1发出
接口1或2，目的h3 → 接口3
接口1或2，目的h4 → 接口4
h3和h4互通

s2 流表：
┌────────────────────────────────────────────────┬──────────────┐
│  匹配条件                                        │  动作         │
├────────────────────────────────────────────────┼──────────────┤
│  入端口=1, 源IP=10.3.*.*, 目的IP=10.1.*.*       │  转发(接口2)  │
│  入端口=2, 源IP=10.1.*.*, 目的IP=10.3.*.*       │  转发(接口1)  │
│  目的IP=10.2.0.3                                │  转发(接口3)  │
│  目的IP=10.2.0.4                                │  转发(接口4)  │
└────────────────────────────────────────────────┴──────────────┘

P23. 防火墙流表设计（四种情形）

情形1：只允许h1和h6的流量到达h3/h4，阻断h2/h5

┌──────────────────────────────────────────────┬──────────────┐
│  源IP=10.1.0.1(h1), 目的IP=10.2.0.3          │  转发(接口3)  │
│  源IP=10.1.0.1(h1), 目的IP=10.2.0.4          │  转发(接口4)  │
│  源IP=10.3.0.6(h6), 目的IP=10.2.0.3          │  转发(接口3)  │
│  源IP=10.3.0.6(h6), 目的IP=10.2.0.4          │  转发(接口4)  │
│  （其余：无规则 → 丢弃）                        │              │
└──────────────────────────────────────────────┴──────────────┘

情形2：只允许TCP流量到达h3/h4，阻断UDP

┌──────────────────────────────────────────────┬──────────────┐
│  协议=TCP, 目的IP=10.2.0.3                    │  转发(接口3)  │
│  协议=TCP, 目的IP=10.2.0.4                    │  转发(接口4)  │
│  （UDP等：无规则 → 丢弃）                       │              │
└──────────────────────────────────────────────┴──────────────┘

情形3：只允许到h3的流量，阻断到h4的所有流量

┌──────────────────────────────────────────────┬──────────────┐
│  目的IP=10.2.0.3                              │  转发(接口3)  │
│  目的IP=10.2.0.4                              │  丢弃（无动作）│
└──────────────────────────────────────────────┴──────────────┘

情形4：只允许h1发给h3的UDP流量，其他全阻断

┌──────────────────────────────────────────────┬──────────────┐
│  源IP=10.1.0.1(h1), 协议=UDP,目的IP=10.2.0.3 │  转发(接口3)  │
│  （其余：无规则 → 丢弃）                        │              │
└──────────────────────────────────────────────┴──────────────┘

P24. ICMP 是网络层协议还是传输层协议？

ICMP（Internet Control Message Protocol）的层次位置：
ICMP 应该被认为是网络层协议，理由如下：

封装位置： ICMP 消息被封装在 IP 数据报的数据字段中（协议号 = 1），和 TCP（6）、UDP（17）一样，是 IP 数据报的载荷
但与TCP/UDP不同： ICMP 不为应用程序提供服务，而是为 IP 协议本身提供差错报告和控制功能（如 TTL 过期、目的不可达、Ping 功能）
功能归属： ICMP 服务于网络层的操作和诊断，不提供进程到进程的通信

从协议栈角度看：
  [应用层]  HTTP, SMTP, FTP...
  [传输层]  TCP, UDP ← 为应用提供进程间通信
  [网络层]  IP + ICMP ← ICMP为IP服务，同属网络层
  [链路层]  以太网, WiFi...

结论： ICMP 虽然从"封装关系"看像传输层（在IP之上），但从"功能"角度看，它服务于网络层，是网络层协议的一部分。

三、附录：C++ 代码演示

WFQ 调度模拟与延迟计算（对应 P5/P6）

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <numeric>
// ─────────────────────────────────────────────────────────────────────────────
// 数据包描述
// ─────────────────────────────────────────────────────────────────────────────
struct Packet {
    int id;          // 包编号（1~12）
    int arriveSlot;  // 到达时隙
    int classId;     // 所属类别（0 或 1）
};
// ─────────────────────────────────────────────────────────────────────────────
// FIFO 调度模拟
// 返回每个包的发送开始时隙（即离队时隙）
// ─────────────────────────────────────────────────────────────────────────────
std::vector<int> simulateFIFO(const std::vector<Packet>& pkts) {
    // 按到达时间排序（FIFO：谁先到谁先走）
    std::vector<Packet> sorted = pkts;
    std::sort(sorted.begin(), sorted.end(),
              [](const Packet& a, const Packet& b) {
                  return a.arriveSlot < b.arriveSlot;
              });
    std::vector<int> departSlot(pkts.size());
    int currentSlot = 0;  // 当前链路空闲的时隙
    for (const auto& p : sorted) {
        // 如果链路空闲时间 < 包到达时间，等到包到达才开始传输
        currentSlot = std::max(currentSlot, p.arriveSlot);
        // 记录这个包在原始数组中的位置
        departSlot[p.id - 1] = currentSlot;
        currentSlot++;  // 传输一个包需要一个时隙
    }
    return departSlot;
}
// ─────────────────────────────────────────────────────────────────────────────
// 优先级队列调度模拟
// classId=0 为高优先级，classId=1 为低优先级
// ─────────────────────────────────────────────────────────────────────────────
std::vector<int> simulatePriority(const std::vector<Packet>& pkts) {
    std::vector<int> departSlot(pkts.size(), -1);
    int currentSlot = 0;
    // 找到所有包中最大到达时间，作为模拟终止条件
    int maxArrival = 0;
    for (const auto& p : pkts) maxArrival = std::max(maxArrival, p.arriveSlot);
    // 两个优先级队列（高优先级和低优先级）
    std::queue<int> highQ, lowQ;  // 存包的索引
    int pktIdx = 0;               // 下一个要检查是否到达的包
    // 按到达时间排序
    std::vector<Packet> sorted = pkts;
    std::sort(sorted.begin(), sorted.end(),
              [](const Packet& a, const Packet& b) {
                  return a.arriveSlot < b.arriveSlot;
              });
    int processed = 0;
    int slot = 0;
    while (processed < (int)pkts.size()) {
        // 将当前时隙到达的包加入对应队列
        for (auto& p : sorted) {
            if (p.arriveSlot == slot && departSlot[p.id - 1] == -1) {
                if (p.classId == 0) highQ.push(p.id);
                else                lowQ.push(p.id);
            }
        }
        // 选择最高优先级的包发送
        int toSend = -1;
        if (!highQ.empty()) {
            toSend = highQ.front(); highQ.pop();
        } else if (!lowQ.empty()) {
            toSend = lowQ.front(); lowQ.pop();
        }
        if (toSend != -1) {
            departSlot[toSend - 1] = slot;
            processed++;
        }
        slot++;
        if (slot > maxArrival + (int)pkts.size()) break;  // 安全退出
    }
    return departSlot;
}
// ─────────────────────────────────────────────────────────────────────────────
// 打印调度结果
// ─────────────────────────────────────────────────────────────────────────────
void printResult(const std::string& name,
                 const std::vector<Packet>& pkts,
                 const std::vector<int>& departSlots) {
    std::cout << "\n=== " << name << " ===\n";
    std::cout << std::setw(6) << "包ID"
              << std::setw(10) << "到达时隙"
              << std::setw(10) << "发送时隙"
              << std::setw(10) << "延迟" << "\n";
    std::cout << std::string(36, '-') << "\n";
    double totalDelay = 0;
    for (const auto& p : pkts) {
        int delay = departSlots[p.id - 1] - p.arriveSlot;
        totalDelay += delay;
        std::cout << std::setw(6) << p.id
                  << std::setw(10) << p.arriveSlot
                  << std::setw(10) << departSlots[p.id - 1]
                  << std::setw(10) << delay << "\n";
    }
    std::cout << "平均延迟 = " << std::fixed << std::setprecision(2)
              << totalDelay / pkts.size() << " 时隙\n";
}
// ─────────────────────────────────────────────────────────────────────────────
// 主函数：演示FIFO和优先级调度的延迟计算
// 使用教材P6题的典型到达时间序列
// ─────────────────────────────────────────────────────────────────────────────
int main() {
    // 教材图P6：12个包的到达时隙（根据题图读取，这里用典型示例值）
    // 包ID:     1  2  3  4  5  6  7  8  9  10  11  12
    // 到达时隙（示例，实际值从题图读取）
    std::vector<int> arrivals = {0, 0, 1, 2, 2, 3, 5, 5, 6,  8,  9,  9};
    // P6b: 奇数包为高优先级(classId=0)，偶数包为低优先级(classId=1)
    std::vector<Packet> pkts;
    for (int i = 0; i < 12; ++i) {
        pkts.push_back({i + 1, arrivals[i], (i % 2 == 0) ? 0 : 1});
    }
    std::cout << "============================================================\n";
    std::cout << "  数据包调度延迟分析（对应习题 P6）\n";
    std::cout << "============================================================\n";
    // FIFO
    auto fifoResult = simulateFIFO(pkts);
    printResult("FIFO 调度", pkts, fifoResult);
    // 优先级（奇数高优先级）
    auto prioResult = simulatePriority(pkts);
    printResult("优先级调度（奇数包高优先级）", pkts, prioResult);
    // ── WFQ 简化演示（虚拟完成时间法）────────────────────────────────────────
    std::cout << "\n=== WFQ 调度（权重 class1=2, class2=1）===\n";
    // 奇数包=类别1(权重2)，偶数包=类别2(权重1)
    std::vector<double> vt = {0.0, 0.0};       // 每个类别的当前虚拟时间
    std::vector<double> weights = {2.0, 1.0};  // 权重
    // 用 (虚拟完成时间, 包ID) 的最小堆模拟
    using PII = std::pair<double, int>;
    std::priority_queue<PII, std::vector<PII>, std::greater<PII>> pq;
    std::vector<Packet> wfqPkts = pkts;
    std::sort(wfqPkts.begin(), wfqPkts.end(),
              [](const Packet& a, const Packet& b) {
                  return a.arriveSlot < b.arriveSlot;
              });
    std::vector<int> wfqDepart(12, -1);
    int slot = 0;
    int nextPkt = 0;  // 下一个未入队的包索引
    int processed = 0;
    while (processed < 12) {
        // 将本时隙到达的包加入WFQ堆
        while (nextPkt < 12 && wfqPkts[nextPkt].arriveSlot <= slot) {
            const Packet& p = wfqPkts[nextPkt];
            int cid = p.classId;
            // 虚拟完成时间 = max(当前虚拟时间, 包到达时刻) + 1/权重
            double ft = std::max(vt[cid], (double)p.arriveSlot) + 1.0 / weights[cid];
            vt[cid] = ft;
            pq.push({ft, p.id});
            nextPkt++;
        }
        if (!pq.empty()) {
            auto [ft, pid] = pq.top();
            pq.pop();
            wfqDepart[pid - 1] = slot;
            processed++;
            std::cout << "时隙 " << slot << ": 发送包#" << pid
                      << " (虚拟完成时间=" << std::fixed << std::setprecision(2)
                      << ft << ")\n";
        }
        slot++;
        if (slot > 30) break;
    }
    double totalDelay = 0;
    for (const auto& p : pkts) {
        totalDelay += wfqDepart[p.id - 1] - p.arriveSlot;
    }
    std::cout << "WFQ 平均延迟 = " << totalDelay / 12 << " 时隙\n";
    std::cout << "\n结论：三种调度的平均延迟应非常接近（验证 P6-e 的结论）\n";
    return 0;
}

四、总结速查表

题号	核心考点
R1	数据报；路由器vs交换机工作层次
R3	转发=局部/硬件；路由=全局/软件
R8	目的地转发只看目的IP；SDN用广义转发
R11	HOL阻塞在输入端口；交叉开关缓解
R14	只有FIFO保证按到达顺序离开
P1b	陷阱题：传统路由不能按源IP区分路径
P5	WFQ权重0.5:0.25:0.25 → 服务序列2:1:1
P6e	四种调度平均延迟相同（只影响分布）
P8	最长前缀匹配找最具体前缀
P11	子网划分：从大需求开始分配
P17	$\lceil 5000000/1480 \rceil = 3379$ 个数据报
P23	防火墙：白名单+默认丢弃
P24	ICMP是网络层协议（服务于IP）

网络层：控制平面详细解析

本文对应教材第5章，用尽可能通俗的语言解释控制平面的核心知识点。

1. 控制平面概述

1.1 什么是控制平面？

网络层分为两个平面：

平面	职责	比喻
数据平面	按照表格转发数据包	快递员按地址送包裹
控制平面	计算并维护转发表	规划哪条路最快到达目的地

控制平面负责回答一个核心问题：数据包从源主机到目的主机，应该走哪条路？

1.2 两种控制方式

方式一：每个路由器单独控制（Per-router Control）

路由器A          路由器B          路由器C
+--------+      +--------+      +--------+
|路由算法|<---->|路由算法|<---->|路由算法|
|转发表  |      |转发表  |      |转发表  |
+--------+      +--------+      +--------+

每台路由器自己运行路由算法
路由器之间互相交换信息
OSPF 和 BGP 都采用这种方式

方式二：逻辑集中控制（Logically Centralized Control / SDN）

              +--------------------+
              |   中央控制器        |
              |  (SDN Controller)  |
              +--------------------+
               /        |        \
              /         |         \
        +----+      +----+      +----+
        | CA |      | CA |      | CA |   <- 控制代理（只听命令）
        +----+      +----+      +----+
        路由器A     路由器B     路由器C

一个"大脑"统一计算所有转发表
路由器上只有控制代理（CA），负责执行命令
CA 之间不直接通信，这是与 Per-router 最大的区别
SDN（软件定义网络）采用此方式，2020年已在数据中心（64%）、广域网（58%）广泛部署

2. 路由算法基础：图模型

2.1 用图来描述网络

把网络抽象成一个图 $G = (N, E)$ ：

$N$ ：节点集合，代表路由器
$E$ ：边集合，代表物理链路
每条边 $(x, y)$ 有一个代价 $c (x, y)$
代价可以表示：链路长度、带宽、经济成本等。
若两节点之间没有直接链路，则 $\infty$ 。

2.2 最小代价路径

路径代价 = 路径上所有边的代价之和：
$c(x_1, x_2) + c(x_2, x_3) + \cdots + c(x_{p-1}, x_p)$
路由目标：找到从源节点到目的节点代价最小的路径。

2.3 路由算法的三种分类

分类一：集中式 vs 分散式

类型	特点	代表算法
集中式	需要全局网络信息	链路状态（LS）
分散式	只知道相邻节点信息，迭代计算	距离向量（DV）

分类二：静态 vs 动态

类型	特点
静态路由	路径变化慢，通常需人工干预
动态路由	随网络拓扑/流量自动调整，但可能出现路由震荡

分类三：负载敏感 vs 负载无关

负载敏感：链路代价随拥塞动态变化（早期 ARPAnet 使用，问题较多）
负载无关：链路代价固定（现代 RIP、OSPF、BGP 均采用此方式）

3. 链路状态算法 LS（Dijkstra）

3.1 核心思想

LS 算法需要每个节点都知道整个网络的拓扑和所有链路代价，然后运行 Dijkstra 算法求最短路。
信息如何获取？每个节点向全网广播自己的链路状态包（包含与自己相连的所有链路及其代价）。广播结束后，每个节点都有完整的网络视图。

3.2 算法符号定义

符号	含义
$D (v)$	从源节点到节点 $v$ 的当前已知最小代价
$p (v)$	在当前最小代价路径上， $v$ 的前驱节点
$N^{'}$	已确定最小代价路径的节点集合

3.3 算法伪代码（含详细注释）

初始化阶段：
    N' = {u}                          // 只把源节点 u 放入已确定集合
    对所有节点 v：
        if v 是 u 的邻居:
            D(v) = c(u, v)            // 直接相连，代价即链路代价
        else:
            D(v) = ∞                  // 不相连，代价为无穷大
循环阶段（重复直到 N' = N）：
    从不在 N' 中的节点里，找到 D(w) 最小的节点 w
    将 w 加入 N'                      // w 的最短路径已确定
    对 w 的每个邻居 v（v 不在 N' 中）：
        D(v) = min(D(v), D(w) + c(w, v))
        // 更新 v 的代价：要么保持原来的，要么经过 w 到达 v

3.4 C++ 完整实现（Dijkstra 算法）

#include <iostream>
#include <vector>
#include <climits>
#include <string>
// 节点数量（对应教材图5.3中的 u,v,w,x,y,z 共6个节点）
const int N = 6;
// 用 INT_MAX/2 表示无穷大，防止加法溢出
const int INF = INT_MAX / 2;
// 节点名称（索引 0~5 对应 u,v,w,x,y,z）
std::string nodeName = "uvwxyz";
// 打印结果：从源节点到每个节点的最短路径和代价
void printResult(int dist[], int prev[], int src) {
    std::cout << "\n=== 从节点 " << nodeName[src] << " 出发的最短路径 ===\n";
    for (int i = 0; i < N; i++) {
        if (i == src) continue;
        std::cout << nodeName[src] << " -> " << nodeName[i]
                  << "  代价: " << dist[i] << "  路径: ";
        // 反向追踪路径
        std::vector<int> path;
        int cur = i;
        while (cur != -1) {
            path.push_back(cur);
            cur = prev[cur];
        }
        // 逆序打印（从源到目的）
        for (int j = path.size() - 1; j >= 0; j--) {
            std::cout << nodeName[path[j]];
            if (j != 0) std::cout << " -> ";
        }
        std::cout << "\n";
    }
}
// Dijkstra 算法
// graph: 邻接矩阵，graph[i][j] 表示节点 i 到 j 的链路代价
// src:   源节点编号
void dijkstra(int graph[N][N], int src) {
    int dist[N];   // dist[i] = 从 src 到 i 的当前最短代价（对应算法中的 D(v)）
    int prev[N];   // prev[i] = 最短路径上 i 的前驱节点（对应算法中的 p(v)）
    bool inSet[N]; // inSet[i] = true 表示 i 已加入 N'
    // 初始化阶段
    for (int i = 0; i < N; i++) {
        dist[i]  = graph[src][i]; // 直接相连取链路代价，否则为 INF
        prev[i]  = (graph[src][i] < INF) ? src : -1; // 前驱节点
        inSet[i] = false;
    }
    // 源节点加入已确定集合
    inSet[src] = true;
    dist[src]  = 0;
    prev[src]  = -1;
    // 打印初始化状态
    std::cout << "\n--- 初始化 ---\n";
    std::cout << "N' = {" << nodeName[src] << "}\n";
    for (int i = 0; i < N; i++) {
        if (i == src) continue;
        if (dist[i] < INF)
            std::cout << "D(" << nodeName[i] << ") = " << dist[i] << "\n";
        else
            std::cout << "D(" << nodeName[i] << ") = INF\n";
    }
    // 循环阶段：共执行 N-1 次，每次确定一个节点的最短路径
    for (int iter = 0; iter < N - 1; iter++) {
        // 第一步：从不在 N' 中的节点里找 D(w) 最小的节点 w
        int w = -1;
        for (int i = 0; i < N; i++) {
            if (!inSet[i] && (w == -1 || dist[i] < dist[w])) {
                w = i;
            }
        }
        if (dist[w] == INF) break; // 剩余节点都不可达
        // 第二步：将 w 加入 N'
        inSet[w] = true;
        std::cout << "\n--- 第 " << iter + 1 << " 次迭代，加入节点 "
                  << nodeName[w] << " (代价=" << dist[w] << ") ---\n";
        // 第三步：更新 w 的邻居节点的代价
        for (int v = 0; v < N; v++) {
            if (!inSet[v] && graph[w][v] < INF) {
                // 经过 w 到达 v 的代价 = D(w) + c(w, v)
                int newDist = dist[w] + graph[w][v];
                if (newDist < dist[v]) {
                    dist[v] = newDist; // 更新最小代价
                    prev[v] = w;       // 更新前驱节点
                    std::cout << "  更新 D(" << nodeName[v] << ") = "
                              << dist[v] << "，前驱 = " << nodeName[w] << "\n";
                }
            }
        }
    }
    // 打印最终结果
    printResult(dist, prev, src);
}
int main() {
    // 教材图5.3的邻接矩阵
    // 节点：u=0, v=1, w=2, x=3, y=4, z=5
    int graph[N][N] = {
    //   u    v    w    x    y    z
        {0,   2,   5,   1,   INF, INF}, // u
        {2,   0,   3,   2,   INF, INF}, // v
        {5,   3,   0,   3,   1,   5  }, // w
        {1,   2,   3,   0,   1,   INF}, // x
        {INF, INF, 1,   1,   0,   2  }, // y
        {INF, INF, 5,   INF, 2,   0  }  // z
    };
    std::cout << "教材图5.3 链路状态（LS/Dijkstra）算法演示\n";
    std::cout << "节点：u=0, v=1, w=2, x=3, y=4, z=5\n";
    // 从源节点 u（编号0）运行 Dijkstra
    dijkstra(graph, 0);
    return 0;
}

编译运行：

g++ -o ls_dijkstra ls_dijkstra.cpp && ./ls_dijkstra

3.5 图5.3 网络拓扑示意

        u
       /|\
    2 / | \ 5
     /  |1  \
    v   x    w
     \  |\ /|
    3 \ |1\ |3
       \|  \|
        y---z
         2
(括号内数字为链路代价)

3.6 算法执行过程（Table 5.1 可视化）

步骤  N'          D(v)  D(w)  D(x)  D(y)  D(z)
 0    {u}          2,u   5,u   1,u   INF   INF
 1    {u,x}        2,u   4,x   --    2,x   INF
 2    {u,x,y}      2,u   3,y   --    --    4,y
 3    {u,x,y,v}    --    3,y   --    --    4,y
 4    {u,x,y,v,w}  --    --    --    --    4,y
 5    {u,...,z}    --    --    --    --    --

最终最短路径：

$\to v$ ：代价 2，路径 $\to v$
$\to w$ ：代价 3，路径 $\to x \to y \to w$
$\to x$ ：代价 1，路径 $\to x$
$\to y$ ：代价 2，路径 $\to x \to y$
$\to z$ ：代价 4，路径 $\to x \to y \to z$

3.7 算法复杂度

在最朴素的实现中，每次迭代都要扫描所有未确定节点：
$\text{总比较次数} = n + (n-1) + (n-2) + \cdots + 1 = \frac{n(n+1)}{2}$
因此时间复杂度为 $O(n^2)$ 。若使用堆（优先队列）优化，可以降低到 $O((n+|E|)\log n)$ 。

3.8 LS 算法的震荡问题

当链路代价随流量变化时，可能出现路由震荡：

第1轮计算结果    第2轮计算结果    第3轮计算结果
  顺时针路由  ->  逆时针路由  ->  顺时针路由  -> ...

解决方法：让每个路由器随机化发送链路状态广播的时间，避免所有路由器同步执行算法。

4. 距离向量算法 DV（Bellman-Ford）

4.1 核心思想

DV 算法是分散式、迭代式、异步的：

分散：每个节点只和直接相连的邻居交换信息
迭代：不断重复计算，直到没有更新为止
异步：不需要所有节点同步执行
关键思路：“告诉我你到每个目的地的代价，我来决定经过你走是否更划算。”

4.2 Bellman-Ford 方程

设 $d_x(y)$ 为节点 $x$ 到节点 $y$ 的最小代价路径代价，则：
$d_x(y) = \min_v \{ c(x, v) + d_v(y) \}$
其中 $v$ 遍历 $x$ 的所有邻居节点。
直观理解：从 $x$ 到 $y$ ，必须先经过某个邻居 $v$ ，总代价 = $x$ 到 $v$ 的链路代价 + $v$ 到 $y$ 的最短路径代价。取所有邻居中的最小值即为答案。
验证（图5.3，从 $u$ 到 $z$ ）：
$d_u(z) = \min\{ \underbrace{c(u,v)}_{2} + \underbrace{d_v(z)}_{5},\; \underbrace{c(u,x)}_{1} + \underbrace{d_x(z)}_{3},\; \underbrace{c(u,w)}_{5} + \underbrace{d_w(z)}_{3} \} = \min\{7, 4, 8\} = 4$

4.3 每个节点维护的信息

每个节点 $x$ 保存：

直接链路代价 $c (x, v)$ ：到每个邻居的代价
自己的距离向量 $D_x = [D_x(y) : y \in N]$ ：对全网各节点的代价估计
邻居的距离向量 $D_v$ ：每个邻居发来的距离向量

4.4 DV 算法伪代码（含注释）

节点 x 的算法：
初始化：
    对所有目的节点 y：
        Dx(y) = c(x, y)        // 邻居设为链路代价，否则设为 INF
    对所有邻居 w：
        Dw(y) = 未知            // 邻居的距离向量暂时未知
    向所有邻居发送自己的距离向量 Dx
循环（永久执行）：
    等待以下任一事件：
        a) 检测到某条直连链路代价变化
        b) 收到某个邻居的新距离向量
    对所有目的节点 y：
        Dx(y) = min_v { c(x,v) + Dv(y) }   // Bellman-Ford 更新
    如果 Dx 有任何变化：
        向所有邻居发送新的 Dx               // 通知邻居

4.5 C++ 完整实现（距离向量算法）

#include <iostream>
#include <vector>
#include <climits>
#include <string>
const int N = 3;   // 教材图5.6 三节点示例：x=0, y=1, z=2
const int INF = INT_MAX / 2;
std::string nodeName = "xyz";
// 每个节点维护的路由表：dist[i][j] 表示节点 i 认为到节点 j 的最短代价
int dist[N][N];
// 直连链路代价矩阵（对称，不变）
int link[N][N];
// 打印当前所有节点的距离向量
void printDistVectors(int round) {
    std::cout << "\n=== 第 " << round << " 轮 ===\n";
    for (int i = 0; i < N; i++) {
        std::cout << "节点 " << nodeName[i] << " 的距离向量: [";
        for (int j = 0; j < N; j++) {
            if (dist[i][j] == INF)
                std::cout << "INF";
            else
                std::cout << dist[i][j];
            if (j < N - 1) std::cout << ", ";
        }
        std::cout << "]\n";
    }
}
// 执行一轮 DV 更新，返回是否有任何节点的距离向量发生变化
bool dvUpdate() {
    bool changed = false;
    // 临时保存新的距离向量，防止同轮更新互相影响（模拟同步更新）
    int newDist[N][N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            newDist[i][j] = dist[i][j];
    // 对每个节点 x
    for (int x = 0; x < N; x++) {
        // 对每个目的节点 y
        for (int y = 0; y < N; y++) {
            if (x == y) {
                newDist[x][y] = 0;
                continue;
            }
            // Bellman-Ford: Dx(y) = min_v { c(x,v) + Dv(y) }
            int minCost = INF;
            for (int v = 0; v < N; v++) {
                // v 是 x 的邻居（直连链路代价不为 INF）
                if (link[x][v] < INF && dist[v][y] < INF) {
                    int cost = link[x][v] + dist[v][y];
                    if (cost < minCost) {
                        minCost = cost;
                    }
                }
            }
            if (minCost < newDist[x][y]) {
                newDist[x][y] = minCost;
                changed = true;
            }
        }
    }
    // 将新结果写回 dist
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            dist[i][j] = newDist[i][j];
    return changed;
}
int main() {
    // 教材图5.6 三节点网络
    // x=0, y=1, z=2
    // 链路代价：c(x,y)=2, c(y,z)=1, c(x,z)=7
    link[0][0] = 0;   link[0][1] = 2;   link[0][2] = 7;
    link[1][0] = 2;   link[1][1] = 0;   link[1][2] = 1;
    link[2][0] = 7;   link[2][1] = 1;   link[2][2] = 0;
    // 初始化距离向量（只知道直连链路代价）
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            dist[i][j] = link[i][j]; // 非邻居初始化为 INF（link 矩阵中已设置）
    std::cout << "距离向量（DV / Bellman-Ford）算法演示\n";
    std::cout << "节点：x=0, y=1, z=2\n";
    std::cout << "链路代价：c(x,y)=2, c(y,z)=1, c(x,z)=7\n";
    printDistVectors(0); // 打印初始状态
    // 迭代直到收敛
    int round = 1;
    while (true) {
        bool changed = dvUpdate();
        printDistVectors(round);
        if (!changed) {
            std::cout << "\n算法已收敛！\n";
            break;
        }
        round++;
    }
    return 0;
}

编译运行：

g++ -o dv_bellman dv_bellman.cpp && ./dv_bellman

预期输出（对应图5.6）：

=== 第 0 轮（初始）===
节点 x 的距离向量: [0, 2, 7]
节点 y 的距离向量: [2, 0, 1]
节点 z 的距离向量: [7, 1, 0]
=== 第 1 轮 ===
节点 x 的距离向量: [0, 2, 3]   <- x到z由7变为3（经过y）
节点 y 的距离向量: [2, 0, 1]
节点 z 的距离向量: [3, 1, 0]   <- z到x由7变为3（经过y）
=== 第 2 轮 ===  （无变化，收敛）

4.6 DV 算法执行过程演示（图5.6）

初始状态：
  节点x知道：到y代价2，到z代价7
  节点y知道：到x代价2，到z代价1
  节点z知道：到x代价7，到y代价1
第1轮交换后，x收到y的距离向量[2,0,1]：
  x计算到z：min(c(x,y)+Dy(z), c(x,z)+Dz(z))
           = min(2+1, 7+0) = min(3, 7) = 3
  --> x更新 Dx(z) = 3 (经过y)
第2轮：无变化，算法收敛。

4.7 链路代价变化：好消息与坏消息

好消息传播快

当某条链路代价降低时（如 $\to x$ 从4降到1）：

t0: y 检测到代价变化，更新 Dy(x)=1，通知 z
t1: z 收到更新，计算 Dz(x)=min(1+1, 50)=2，通知 y
t2: y 收到更新，Dy(x) 不变，算法收敛

只需 2 次迭代，好消息迅速传播。

坏消息传播慢：无穷计数问题

当某条链路代价增加时（如 $\to x$ 从4增到60）：

初始：Dy(x)=4, Dz(x)=5（z经过y到x）
t0: y 检测代价变成60，计算新路径：
    Dy(x) = min(60+0, 1+Dz(x)) = min(60, 1+5) = 6  <-- 错！z的路径实际经过y
    但 y 不知道 z 的路径是经过自己的！
t1: y 发送 Dy(x)=6 给 z
    z 计算：Dz(x) = min(50, 1+6) = 7
t2: z 发送 Dz(x)=7 给 y
    y 计算：Dy(x) = min(60, 1+7) = 8
... 如此反复，需要 44 次迭代才能收敛！

这就是无穷计数问题（Count-to-Infinity）。

迭代轮次  Dy(x)  Dz(x)
   0        6      5
   1        6      7
   2        8      7
   3        8      9
   ...     ...    ...
   44       51     50  <- z 最终发现直连代价50更小，切换路由

4.8 毒性逆转（Poisoned Reverse）

思路：如果 $z$ 经过 $y$ 到达 $x$ ，则 $z$ 告诉 $y$ 它到 $x$ 的代价是无穷大（说谎），防止 $y$ 以为可以经过 $z$ 到 $x$ 。

正常情况：
  z 路由到 x 经过 y
  z 告诉 y：Dz(x) = INF （毒性逆转）
当 c(y,x) 从 4 变为 60：
  t0: y 计算 Dy(x) = 60（只能直连，因为 z 说自己到 x 是 INF）
  t1: y 通知 z：Dy(x)=60
  t2: z 改走直连 z->x（代价50），通知 y：Dz(x)=50
  t3: y 更新 Dy(x)=51（经过z），对 z 施加毒性逆转：告诉 z Dy(x)=INF
  --> 快速收敛！

局限性：毒性逆转只能解决两节点之间的路由环路，涉及三个及以上节点的环路无法被检测。

5. LS 与 DV 算法对比

5.1 三个维度的比较

消息复杂度

算法	消息量	说明
LS	$\cdot \|E\|)$	每个节点需广播链路状态给所有节点
DV	只和邻居通信	消息量少，但收敛慢

收敛速度

算法	收敛速度	问题
LS（Dijkstra）	$O(n^2)$	可能出现震荡
DV	可能很慢	存在无穷计数问题、路由环路

健壮性

场景	LS	DV
路由器发送错误信息	只影响该节点自己的转发表	错误信息会扩散到全网
历史案例	较隔离	1997年一个小 ISP 的故障导致大面积断网数小时

5.2 LS vs DV 决策树

需要选择路由算法？
         |
    +---------+
    | 网络规模 |
    +---------+
    /           \
  小型           大型
  网络           网络
    |               |
  DV可接受      考虑LS
                    |
             +------------+
             | 对健壮性    |
             | 要求高吗？  |
             +------------+
             /             \
           是               否
           |                |
       优选LS            DV也可以
  (错误影响范围小)   (消息量小，实现简单)

5.3 现实应用

协议	类型	算法基础	应用场景
OSPF	链路状态	LS / Dijkstra	单个 ISP 内部路由
BGP	路径向量	DV 的变种	互联网 AS 之间路由（“胶水”）
RIP	距离向量	DV / Bellman-Ford	小型网络，已逐渐淘汰

总结

控制平面
├── 控制方式
│   ├── Per-router（OSPF, BGP）
│   └── 集中控制（SDN）
│
└── 路由算法
    ├── LS（链路状态）
    │   ├── 需要全局信息
    │   ├── Dijkstra 算法，O(n²)
    │   ├── 收敛快，但可能震荡
    │   └── 代表：OSPF
    │
    └── DV（距离向量）
        ├── 只需邻居信息
        ├── Bellman-Ford 方程迭代
        ├── 可能有无穷计数问题
        ├── 毒性逆转可部分解决
        └── 代表：RIP, BGP

两种算法没有绝对的优劣之分，互联网中两者都在使用。

乐奇 Rokid 开放社区

更多推荐

AI眼镜的赢家不在硅谷，在一个县城

乐奇 Rokid 开放社区

ChatGPT流量不到Google的1%，机会在智能体搜索

乐奇 Rokid 开放社区

极刻觅镜 | AI眼镜日报｜智能眼镜日报：XREAL AURA发布、参议员质询Meta隐私

乐奇 Rokid 开放社区

所有评论(0)

查看更多评论

虾球xz

@TM1695648164

已为社区贡献6条内容

计算机网络自顶向下方法第九版学习:第4章 复习题与习题详解

虾球xz

目录

一、复习题解答

Section 4.1

R2. 数据平面和控制平面的主要功能分别是什么？

Section 4.2

R6. 路由器各组件哪些用硬件实现，哪些用软件实现？

每个输入端口保存一份完整转发表的副本，可以并行、独立地完成转发决策，大幅提升吞吐量。 R8. 什么是目的地转发？它与广义转发有何不同？SDN采用哪种？

SDN 采用广义转发（OpenFlow 流表）。

Section 4.3

R23. DHCP 获取信息（概念说明） DHCP 客户端通常可以获取并查看以下信息（以 Linux 为例用 ip addr 和 ip route 命令查看）：

Section 4.4

二、习题详解

P1. 路由器A的转发表

P2. 交换结构并行传输分析

P3. 不同交换结构的最大输入排队延迟

P4. 时隙调度（HOL vs 最优）

P5. WFQ 权重 0.5、0.25、0.25 的服务顺序

P6. 四种调度策略对比（时隙分析）

P8. 最长前缀匹配转发表（32位地址）

a. 转发表（使用 a.b.c.d/x 记法）：

P9. 8位地址空间，最长前缀匹配

给定前缀表：

P10. 8位地址，另一组前缀表

汇总：

P11. 三个子网的地址分配

P14. 子网划分

P17. MP3 分片数计算

P18. NAT 转换表

条件： 路由器公网IP 24.34.112.235，内网 192.168.1.0/24，5台主机，每台2个TCP连接到 128.119.40.86:80。 a. 内网地址分配（示例）：

b. NAT转换表（6条，每台主机2个连接，只列3台示例）：

P20. OpenFlow 流表设计（s2）

P23. 防火墙流表设计（四种情形）

P24. ICMP 是网络层协议还是传输层协议？

三、附录：C++ 代码演示

WFQ 调度模拟与延迟计算（对应 P5/P6）

四、总结速查表

网络层：控制平面 详细解析

目录

1. 控制平面概述

1.1 什么是控制平面？

网络层分为两个平面：

1.2 两种控制方式

方式一：每个路由器单独控制（Per-router Control）

方式二：逻辑集中控制（Logically Centralized Control / SDN）

2. 路由算法基础：图模型

2.1 用图来描述网络

2.2 最小代价路径

2.3 路由算法的三种分类

分类一：集中式 vs 分散式

分类二：静态 vs 动态

3. 链路状态算法 LS（Dijkstra）

3.1 核心思想

3.2 算法符号定义

3.3 算法伪代码（含详细注释）

3.4 C++ 完整实现（Dijkstra 算法）

3.5 图5.3 网络拓扑示意

3.6 算法执行过程（Table 5.1 可视化）

3.7 算法复杂度

3.8 LS 算法的震荡问题

4. 距离向量算法 DV（Bellman-Ford）

4.1 核心思想

4.2 Bellman-Ford 方程

4.3 每个节点维护的信息

4.4 DV 算法伪代码（含注释）

4.5 C++ 完整实现（距离向量算法）

4.6 DV 算法执行过程演示（图5.6）

4.7 链路代价变化：好消息与坏消息

好消息传播快

坏消息传播慢：无穷计数问题

4.8 毒性逆转（Poisoned Reverse）

5. LS 与 DV 算法对比

5.1 三个维度的比较

消息复杂度

收敛速度

健壮性

5.2 LS vs DV 决策树

5.3 现实应用

总结

计算机网络自顶向下方法第九版学习:第4章复习题与习题详解

每个输入端口保存一份完整转发表的副本，可以并行、独立地完成转发决策，大幅提升吞吐量。
R8. 什么是目的地转发？它与广义转发有何不同？SDN采用哪种？

R23. DHCP 获取信息（概念说明）
DHCP 客户端通常可以获取并查看以下信息（以 Linux 为例用 `ip addr` 和 `ip route` 命令查看）：

条件：路由器公网IP `24.34.112.235`，内网 `192.168.1.0/24`，5台主机，每台2个TCP连接到 `128.119.40.86:80`。
a. 内网地址分配（示例）：

网络层：控制平面详细解析