一、什么是网络管理？

网络管理的定义（来自 Saydam 1996）：

网络管理包括对硬件、软件和人力资源的部署、集成与协调，以监控、测试、轮询、配置、分析、评估和控制网络及其元素资源，从而以合理的成本满足实时、运营性能和服务质量（QoS）的要求。
简单来说：网络管理就是让网络"跑得好、不出问题，出了问题能快速修"。

二、网络管理框架的核心组件

下图展示了网络管理的五大核心组件（对应教材图 5.20）：

+------------------+           网络管理协议           +------------------------+
|  Managing Server |  <-----------------------------> |   Managed Device       |
|  (管理服务器)     |                                  |   (被管理设备)          |
|                  |                                  |  +------------------+  |
| 网络管理员(人)   |                                  |  | Agent (代理程序)  |  |
|                  |                                  |  +------------------+  |
| config & ops     |                                  |  | Device Data      |  |
| data store       |                                  |  | (设备数据/状态)   |  |
+------------------+                                  +------------------------+

1. 管理服务器（Managing Server）

• 运行在网络运营中心（NOC）中的应用程序
• 有网络管理员（人）参与其中
• 负责：收集、处理、分析、下发网络管理信息和命令
• 实际网络中可能有多个管理服务器

2. 被管理设备（Managed Device）

• 网络中任何需要被管理的设备：主机、路由器、交换机、调制解调器、温度计……
• 每台设备都有很多可管理的组件（如网络接口、路由协议配置等）

3. 数据（Data / State）

被管理设备上存储着三类数据：

数据类型	含义	示例
配置数据（Configuration data）	管理员主动配置的信息	分配给接口的 IP 地址、接口速率
运行数据（Operational data）	设备运行过程中自动获取的信息	OSPF 邻居列表
设备统计（Device statistics）	设备运行时更新的计数/状态	接口丢包数、风扇转速

---

4. 网络管理代理（Network Management Agent）

• 运行在被管理设备上的软件进程
• 负责与管理服务器通信
• 在管理服务器的指令下，在本地设备上执行操作
• 类似于路由器中的"路由代理"

5. 网络管理协议（Network Management Protocol）

• 运行在管理服务器与被管理设备之间
• 允许管理服务器查询设备状态、通过代理执行操作
• 代理可主动向管理服务器报告异常事件（如组件故障、性能阈值超标）
• 重要区分：协议本身不"管理"网络，它只是提供了管理网络所需的能力工具

三、三种网络管理方式对比

方式一：CLI（命令行）
  管理员 --[SSH/Telnet]--> 设备（逐台手动配置）
  优点：灵活直接
  缺点：命令复杂、易出错、不易自动化扩展
方式二：SNMP/MIB
  管理服务器 --[SNMP PDU]--> 设备代理（查询/设置MIB对象）
  优点：标准化、适合监控
  缺点：配置能力弱、不易大规模管控
方式三：NETCONF/YANG
  管理服务器 --[XML over TLS/TCP]--> 设备（原子化批量配置）
  优点：强配置管理、支持多设备原子操作、正确性约束
  缺点：较新、复杂度更高

四、SNMP 与 MIB 详解

4.1 SNMP 基本工作模式

SNMPv3（简单网络管理协议第3版）工作在应用层，主要有两种工作模式：
模式一：请求-响应（Request-Response）

管理服务器                    代理（Agent）
    |                              |
    |--- GetRequest/SetRequest --> |
    |                              |（执行操作）
    |<---------- Response ---------|

模式二：陷阱（Trap）— 代理主动上报

管理服务器                    代理（Agent）
    |                              |
    |                         [异常事件发生]
    |<------- Trap Message --------|
    |（无需强制响应）               |

4.2 MIB（管理信息库）

MIB 是被管设备上所有"可管理对象"的集合，就像设备的"状态数据库"。

• MIB 对象用 SMI（管理信息结构） 数据描述语言来定义
• 相关 MIB 对象聚合成 MIB 模块
• 截至 2024 年底，已有超过 400 个 MIB 相关 RFC，加上大量厂商私有 MIB
  MIB 对象示例（来自 RFC 4293）：

-- 该对象统计：成功交付给上层协议的 IP 数据报总数
ipSystemStatsInDelivers OBJECT-TYPE
    SYNTAX      Counter32          -- 32位计数器类型
    MAX-ACCESS  read-only          -- 只读（不能通过SNMP修改）
    STATUS      current            -- 当前有效
    DESCRIPTION
        "The total number of datagrams successfully
         delivered to IP user-protocols (including ICMP).
         ..."
    ::= { ipSystemStatsEntry 18 }  -- 对象标识符（OID）中的编号

注释说明：

• SYNTAX Counter32：数据类型为32位无符号整数（会滚动）
• MAX-ACCESS read-only：网络管理员只能读，不能写
• ::= { ipSystemStatsEntry 18 }：该对象在 MIB 树中的位置（OID）

4.3 SNMPv3 的七种 PDU（协议数据单元）

---

PDU 类型	方向	用途说明
GetRequest	管理器 → 代理	获取一个或多个 MIB 对象的值
GetNextRequest	管理器 → 代理	获取列表/表格中下一个 MIB 对象的值（用于遍历）
GetBulkRequest	管理器 → 代理	批量获取大块数据（如整张表），减少往返次数
SetRequest	管理器 → 代理	设置一个或多个 MIB 对象的值
InformRequest	管理器 → 管理器	通知远端管理器某些 MIB 值（管理器之间通信）
Response	代理 → 管理器	对上述请求的回复，包含请求的数据或操作结果
SNMPv2-Trap	代理 → 管理器	异步通知管理器某个异常事件（不需要管理器先发请求）

---

GetRequest / GetNextRequest / GetBulkRequest 的区别：

GetRequest:      任意获取一批指定OID的MIB值
                 如：同时拿到 OID-A, OID-C, OID-Z
GetNextRequest:  按顺序遍历MIB表，一次取一个"下一个"
                 适合顺序扫描整张路由表
GetBulkRequest:  一次请求，返回大量数据（如整张ARP表）
                 避免多次 GetRequest 的往返延迟

4.4 SNMP 传输层选择

• SNMP PDU 通常封装在 UDP 数据报中传输（RFC 3417 指定 UDP 为首选）
• UDP 是不可靠传输，不保证请求或响应一定到达
• SNMP 标准不强制规定重传机制，只要求管理服务器"负责任地"处理重传
• 这也是 SNMP 主要用于"监控"而非"控制"的原因之一

4.5 SNMP 三个版本演进

SNMPv1 → SNMPv2 → SNMPv3
  基础功能  性能增强   + 安全性 + 管理功能
  安全性弱  部分改进   加密、认证、访问控制

SNMPv3 核心改进：安全性（认证 + 加密）。正因 v1/v2 安全性不足，SetRequest（写操作）在早期版本几乎不被使用——没人敢用不安全的协议去修改设备配置。

五、NETCONF 与 YANG 详解

5.1 为什么需要 NETCONF？

2002 年，互联网架构委员会（IAB）召开的网络管理研讨会（RFC 3535）指出：

• SNMP/MIB 适合监控，但对于设备配置和大规模管理有明显不足
• 需要一种更强调"配置管理"、支持"原子操作"、能"整体看待网络"的新方法
  于是 NETCONF + YANG 应运而生。

5.2 NETCONF 会话流程

对应教材图 5.21，NETCONF 会话流程如下：

管理服务器（客户端）              被管设备（服务端）
       |                                |
       |--- 建立安全连接（TLS/TCP） --->|
       |<--- 安全连接建立 --------------|
       |                                |
       |--- <hello> ------------------>|  // 宣告己方支持的能力（capabilities）
       |<--- <hello> ------------------|  // 交换彼此能力
       |                                |
       |--- <rpc>（操作请求）--------->|  // 如 get-config, edit-config 等
       |<--- <rpc-reply>（操作结果）---|
       |                                |
       |                       [设备发生事件]
       |<--- <notification> -----------|  // 设备主动推送通知
       |                                |
       |--- <rpc> ---------------------->|
       |<--- <rpc-reply> ---------------|
       |                                |
       |--- <close-session> ----------->|  // 关闭会话
       |<--- <rpc-reply> ok ------------|

关键术语注意：NETCONF 协议中，“管理服务器"被称为"客户端”（因为它主动发起连接），“被管设备"被称为"服务端”。

5.3 NETCONF 重要操作

---

操作	说明
<get-config>	检索设备的配置数据（全部或部分），设备始终有一个 running 配置
<get>	同时检索配置状态数据和运行状态数据
<edit-config>	修改指定配置（可以只改一部分），成功返回 <ok>，失败返回 <rpc-error> 并可回滚
<lock> / <unlock>	锁定/解锁设备的配置数据存储，防止多个管理源（SNMP、CLI、其他NETCONF）同时修改
<create-subscription> / <notification>	订阅事件通知，设备异步推送指定类型的事件

---

原子操作是 NETCONF 的重要特性：

场景：同时修改 10 台路由器的配置
SNMP 方式：逐台修改，如果第 7 台失败，前 6 台已经改了，网络处于不一致状态
NETCONF 方式：
  - 向所有设备下发配置
  - 要么全部成功（提交生效）
  - 要么任一失败 → 全部回滚到修改前状态
  → 网络始终处于一致的状态

5.4 NETCONF 与 SNMP 核心对比

---

维度	SNMP	NETCONF
传输协议	UDP（不可靠）	TLS over TCP（可靠、加密）
数据格式	SMI/ASN.1	XML
数据建模语言	SMI	YANG
主要用途	监控为主	配置管理为主
多设备原子操作	不支持	支持
正确性约束	弱	强（YANG 约束）
发展年代	1980年代末	2000年代中后期

---

六、YANG 数据建模语言

6.1 YANG 是什么？

YANG（RFC 6020）是专门为 NETCONF 设计的数据建模语言，作用类似于 SNMP 中的 SMI：
$$\text{YANG 之于 NETCONF}\approx \text{SMI 之于 SNMP}$$

• 精确定义网络管理数据的结构、语法、语义
• 所有 YANG 定义组织在模块（module）中
• 从 YANG 模块可以自动生成描述设备能力的 XML 文档
• 支持指定配置的正确性约束（如取值范围、依赖关系）
• 也用于定义 NETCONF 通知（notifications）

6.2 YANG 与 SMI 的对比

---

特性	SMI（用于SNMP）	YANG（用于NETCONF）
内置类型	少量基础类型（Counter32等）	内置类型 + 自定义约束
正确性约束	弱	强（must、when 等约束语句）
表达能力	偏向只读监控	面向读写配置
生态	400+ RFC MIB模块	持续增长中

---

七、整体架构对比总结

网络管理三大方法的定位：
CLI          SNMP/MIB         NETCONF/YANG
  |               |                  |
  v               v                  v
[精细控制]    [大规模监控]      [大规模配置管理]
[单台设备]    [单台设备]        [多设备协同]
[手动/脚本]   [自动化查询]      [自动化 + 原子操作]
[无标准化]    [部分标准化]      [强标准化 + 约束]
[安全靠SSH]  [安全靠SNMPv3]    [安全靠TLS]

信息流示意（NETCONF 场景）

八、关键概念速查表

---

术语	全称	一句话解释
NOC	Network Operations Center	网络运营中心，管理员工作的地方
MIB	Management Information Base	设备"状态数据库"，存放所有可管理对象
SMI	Structure of Management Information	MIB 对象的定义语言（用于SNMP）
OID	Object Identifier	MIB 树中每个对象的唯一编号路径
PDU	Protocol Data Unit	SNMP 协议中传输的消息单元
Trap	—	代理主动发给管理器的异常通知消息
NETCONF	Network Configuration Protocol	专注配置管理的网络管理协议
YANG	Yet Another Next Generation	NETCONF 使用的数据建模语言
RPC	Remote Procedure Call	远程过程调用，NETCONF 的消息交换范式
TLS	Transport Layer Security	NETCONF 使用的安全传输层协议
SLA	Service Level Agreement	服务等级协议，约定网络性能指标

---

九、本节知识结构图

第五章 习题详解

复习题（Review Questions）

R1. 基于逐路由器控制（Per-Router Control）的控制平面

什么是逐路由器控制？
每台路由器自己运行路由算法，自己计算转发表，路由器之间互相交换路由信息（如链路状态、距离向量）。
"单体实现"是什么意思？
数据平面（转发）和控制平面（路由计算）都在同一台路由器硬件内实现，紧密耦合在一起，没有分离。就像一个人既负责"决策走哪条路"又负责"实际搬运货物"，二者不可分割。

路由器A                    路由器B
+------------------+      +------------------+
| 控制平面(路由算法)|<---->| 控制平面(路由算法)|
| 数据平面(转发)   |      | 数据平面(转发)   |
+------------------+      +------------------+
    单体 = 两者在同一设备内，紧耦合

R2. 基于逻辑集中控制（Logically Centralized Control）的控制平面

什么是逻辑集中控制？
有一个（逻辑上的）集中控制器统一计算所有路由器的转发表，然后下发给各个路由器执行。路由器只负责按表转发数据。
数据平面和控制平面在同一设备吗？
不在同一设备。控制平面在远端的 SDN 控制器上运行；数据平面在各个网络设备（交换机/路由器）上运行。

      [SDN 控制器]  ← 控制平面（集中，远端）
       /    |    \
      /     |     \
[路由器1][路由器2][路由器3]  ← 数据平面（分布，本地）
  只转发    只转发    只转发

R3. 集中式 vs 分布式路由算法

---

对比维度	集中式（Centralized）	分布式（Distributed）
全局知识	需要完整网络拓扑	只需知道邻居信息
计算位置	在一个节点计算全网	每个节点自己计算
收敛速度	快（信息完整）	慢（迭代交换）
鲁棒性	单点故障风险	更健壮
代表协议	OSPF（链路状态，LS）	RIP/BGP（距离向量，DV）

---

• 集中式例子：OSPF —— 每个路由器广播自己的链路状态，最终所有路由器都有完整拓扑图，然后各自用 Dijkstra 算法计算最短路
• 分布式例子：RIP —— 路由器只和邻居交换距离向量，迭代收敛

R4. 链路状态（LS） vs 距离向量（DV）

---

对比维度	链路状态（LS）	距离向量（DV）
信息内容	广播自己所有链路的代价	只告诉邻居"我到各目的地的距离"
算法	Dijkstra（集中计算）	Bellman-Ford（分布迭代）
收敛速度	快	慢，可能出现无穷计数
消息复杂度	$O(nE)$，n节点E条链路	每次只和邻居交换
鲁棒性	节点可能广播错误链路代价	节点可能向邻居广播错误路径代价
代表协议	OSPF	RIP

---

Bellman-Ford 公式（DV 核心公式）：
Dx(y)=min⁡v{c(x,v)+Dv(y)}D_x(y) = \min_v \{ c(x,v) + D_v(y) \}Dx​(y)=vmin​{c(x,v)+Dv​(y)}
其中 $D_x(y)$ 是节点 $x$ 到目的地 $y$ 的最小代价估计，$v$ 是 $x$ 的邻居。

R5. 距离向量中的"无穷计数"问题（Count-to-Infinity）

场景：假设 x—y—z，x 到 y 代价为 1，y 到 z 代价为 1。
当 x—y 链路断开后：

初始状态：x --1-- y --1-- z
x到z最短路 = 2，经由y
链路x-y断开后：
y认为：我到z=1；我到x=∞？不，y看到z声称"z到x=2（经由y）"
y更新：D_y(x) = 1 + 2 = 3
z看到y说到x=3：D_z(x) = 1 + 3 = 4
y再看z说4：D_y(x) = 1 + 4 = 5
... 如此无限递增直到∞

根本原因：y 和 z 互相引用对方的路径，形成路由环路，距离值不断增大。
解决方案：毒性逆转（Poisoned Reverse）—— 如果 z 经由 y 到达 x，则 z 告诉 y：“我到 x 的距离是无穷大”，打破环路。

R6. 各自治系统必须使用相同的 AS 内路由协议吗？

不必须。 不同 AS 可以自由选择各自的 AS 内（intra-AS）路由协议。
原因：

• AS 内路由协议只在本 AS 内部使用，外界不需要知道
• AS 之间通过 BGP 进行通信，BGP 屏蔽了内部实现细节
• 各组织有权根据自己的规模、需求选择（OSPF、RIP、EIGRP 等）

R7. 为什么 Internet 使用不同的 AS 间和 AS 内协议？

---

	AS 内（Intra-AS）	AS 间（Inter-AS）
目标	性能最优（最短路）	策略优先（商业关系）
关注	延迟、带宽等技术指标	路由策略、商业协议、安全
规模	单个组织内，规模有限	覆盖全球，规模巨大
协议	OSPF、RIP	BGP

---

AS 间路由必须考虑"不是所有路都能走"（比如竞争对手的网络），这是纯技术性的 AS 内协议无法处理的。

R8. OSPF 路由器发送链路状态信息，是否只发给直接相连邻居？

错误（False）。
OSPF 的链路状态通告（LSA）会被**洪泛（flooding）**到整个 AS 中的所有路由器，而不仅是直接相连的邻居。每台路由器收到 LSA 后，转发给除了来源方向以外的所有邻居，最终全网所有路由器都收到。

R9. OSPF 中"区域（Area）"的概念

什么是区域？
将一个大型 AS 划分成多个小区域，每个区域内部独立运行 OSPF，区域间通过骨干区域（Backbone Area，即 Area 0）连接。
为什么引入区域？

• 大型网络中路由器数量很多，全网洪泛 LSA 会产生巨大开销
• 区域内部的链路状态变化只影响区域内部，不影响其他区域
• 大幅减少路由表大小和 LSA 洪泛量，提升可扩展性

R10. 子网、前缀、BGP 路由的区别

---

术语	定义	示例
子网（Subnet）	直接物理连接的一组设备，共享同一网络前缀	192.168.1.0/24 这段地址空间
前缀（Prefix）	IP 地址的网络部分，用 CIDR 表示	192.168.1.0/24
BGP 路由（BGP Route）	前缀 + 一组 BGP 属性（AS路径、下一跳等）	192.168.1.0/24, AS-PATH: AS2 AS3, NEXT-HOP: 1.2.3.4

---

BGP 路由 = 前缀 + 如何到达它的"路线描述"。

R11. BGP 如何使用 NEXT-HOP 和 AS-PATH 属性？

NEXT-HOP：告诉路由器"要去往这个前缀，下一跳应该发给哪个路由器的 IP 地址"。即使路径跨越多个 AS，NEXT-HOP 记录的是最近的 AS 边界路由器地址。
AS-PATH：记录这条路由通告经过了哪些 AS（按顺序列出 AS 编号）。用于：

1. 防环：如果收到的路径中包含自己的 AS 号，则丢弃
2. 路径选择：优先选择 AS-PATH 更短的路径（跳过更少 AS）

R12. 上层 ISP 管理员如何通过 BGP 实施策略？

管理员可以通过配置 BGP 的路由过滤和属性操控来实施策略：

• 路由过滤：只向特定邻居通告特定前缀（如只对付费客户通告路由）
• LOCAL-PREF 属性：在 AS 内部设置偏好值，影响出站路径选择
• MED 属性：告诉邻居 AS 希望流量从哪个入口进入
• 社区属性（Community）：给路由打标签，控制传播范围
  例如：ISP 不向对等网络（peer）通告客户以外的路由，避免成为"免费中转"。

R13. BGP 路由器收到通告路径后，必须加上自己的 AS 号并发给所有邻居吗？

错误（False）。
BGP 路由器可以根据策略决定是否传播路由。例如：

• 对等（peering）关系：通常不把从一个对等方学到的路由再通告给另一个对等方
• 只把从客户（customer）学到的或自己产生的路由，通告给提供商（provider）和对等方
  所以"必须发给所有邻居"是错的，BGP 的核心特点就是策略驱动的路由选择和通告。

R14. SDN 控制器三层结构的作用

+----------------------------------+
| 网络控制应用层（北向）            |  ← 路由、负载均衡、防火墙等应用
| Network-Control Application Layer|
+----------------------------------+
| 网络范围状态管理层                |  ← 维护全网拓扑、流表、统计信息
| Network-Wide State-Mgmt Layer    |
+----------------------------------+
| 通信层（南向）                    |  ← 与物理设备通信（OpenFlow等）
| Communication Layer              |
+----------------------------------+
          |  OpenFlow  |
    [交换机1][交换机2][交换机3]

• 通信层：负责控制器与被控设备之间的消息传递（如 OpenFlow 协议）
• 状态管理层：维护全网的"上帝视角"——拓扑图、链路状态、流表、统计数据
• 网络控制应用层：利用全局状态实现具体功能（路由算法、访问控制、流量工程）

R15. 在 SDN 控制平面中实现新路由协议，应在哪一层？

应在**网络控制应用层（Network-Control Application Layer）**实现。
原因：路由协议属于"控制逻辑"，需要访问全网状态（通过状态管理层提供的 API），并生成转发规则（通过通信层下发给设备）。通信层和状态管理层是基础设施，路由协议是在其之上运行的"应用"。

R16. SDN 控制器南向/北向 API 上流通的消息类型

南向 API（Southbound，控制器 → 设备）：

• 流表安装/修改/删除命令
• 接收来自设备的：数据包上报（packet-in）、端口状态变化、统计信息
  北向 API（Northbound，应用 → 控制器）：
• 网络控制应用发出的请求：查询拓扑、安装路由规则、获取统计数据
  消息接收方：
• 南向：被控网络设备（交换机、路由器）
• 北向发送方：网络控制应用程序（路由应用、负载均衡应用等）

R17. OpenFlow 消息举例

设备 → 控制器（2种）：

1. Packet-in：设备收到一个数据包，没有匹配的流表项，将数据包上报给控制器处理
2. Port-status：设备某个端口状态发生变化（链路 up/down），通知控制器更新拓扑
   控制器 → 设备（2种）：
3. Flow-mod：安装、修改或删除设备中的流表项，告诉设备"遇到什么包就怎么处理"
4. Packet-out：控制器直接指示设备从某个端口发出一个数据包

R18. OpenDaylight SDN 控制器中服务抽象层（SAL）的目的

服务抽象层（Service Abstraction Layer）的作用是屏蔽底层设备的差异性。
不同厂商的设备可能使用不同协议（OpenFlow、NETCONF、OVSDB 等），SAL 提供统一的抽象接口，使上层网络控制应用无需关心底层用的是哪种协议——就像操作系统的驱动层屏蔽了硬件差异。

R19. ICMP 消息的四种类型

1. Echo Request / Echo Reply（类型 8 / 类型 0）：ping 命令使用，测试主机是否可达
2. Destination Unreachable（类型 3）：目的不可达（如端口不存在、网络不可达）
3. Time Exceeded（类型 11）：TTL 超时，traceroute 利用此消息
4. Source Quench（类型 4）：源端抑制，请求发送方降低发送速率（已较少使用）

R20. Traceroute 程序在发送主机收到的两种 ICMP 消息

1. TTL Exceeded（Time Exceeded，类型 11）：中间路由器 TTL 减为 0 时返回，用于确定沿途路由器
2. Port Unreachable（Destination Unreachable，类型 3，代码 3）：目的主机收到探测包后，因端口不存在而返回，标志 traceroute 结束

R21. SNMP 相关术语定义

• 管理服务器（Managing Server）：运行在网络运营中心（NOC）的应用程序，负责发出查询/配置命令，是网络管理的"大脑"
• 被管设备（Managed Device）：网络中受管理的设备（路由器、交换机等），包含管理代理
• 网络管理代理（Network Management Agent）：运行在被管设备上的软件进程，响应管理服务器的指令并上报状态
• MIB（管理信息库）：被管设备上所有可管理对象的集合，定义了设备暴露哪些状态数据供查询/修改

R22. SNMP GetRequest 和 SetRequest 消息的用途

• GetRequest：管理服务器向代理请求一个或多个 MIB 对象的当前值（只读查询）。例如：查询某接口当前的丢包计数
• SetRequest：管理服务器向代理写入一个或多个 MIB 对象的值（写操作/配置）。例如：关闭某个接口

R23. SNMP Trap 消息的用途

Trap 是代理主动、异步发给管理服务器的通知消息，用于报告异常事件，不需要管理服务器先发出请求。
常见 Trap 事件：

• 设备冷启动或热启动
• 链路接口 up 或 down
• 邻居丢失
• 认证失败
  好处：无需管理服务器轮询，事件发生时立即通知，节省带宽。

计算题（Problems）

P1. 从 y 到 u 的无环路径（图1网络）

图1链路（从图片读取）：

节点：x, y, z, t, v, w, u
链路：
  z-x: 8    z-y: 12
  x-y: 6    x-v: 3    x-w: 6
  y-v: 8    y-t: 7
  v-t: 4    v-w: 4    v-u: 3
  t-u: 2    w-u: 3

网络结构（ASCII）：

z
|\ 
8  12
|   \
x----y----t
|\   |\ /|
6 \  8 X 7
|  \ |/ \|
|   v----+
3   |\ 4 |
|   3  \ 2
|   |   \|
w---+----u
 6  4    3

从 y 到 u 的所有无环路径：
枚举（不经过已访问节点）：

1. $y\to v\to u$（代价 $8+3=11$）
2. $y\to v\to w\to u$（代价 $8+4+3=15$）
3. $y\to v\to t\to u$（代价 $8+4+2=14$）
4. $y\to t\to u$（代价 $7+2=9$）
5. $y\to t\to v\to u$（代价 $7+4+3=14$）
6. $y\to t\to v\to w\to u$（代价 $7+4+4+3=18$）
7. $y\to x\to v\to u$（代价 $6+3+3=12$）
8. $y\to x\to v\to t\to u$（代价 $6+3+4+2=15$）
9. $y\to x\to v\to w\to u$（代价 $6+3+4+3=16$）
10. $y\to x\to w\to u$（代价 $6+6+3=15$）
11. $y\to x\to w\to v\to u$（代价 $6+6+4+3=19$）
12. $y\to x\to w\to v\to t\to u$（代价 $6+6+4+4+2=22$）
    （还有含 z 的路径，但 z 只连接 x 和 y，且我们来自 y，所以经过 z 的路径：$y\to x\to z\to \dots$ 无法再回到未访问节点到达 u，因 z 只有 x 和 y 两个邻居）

P3. Dijkstra 算法：从 x 出发（图1网络）

链路列表（从图片完整读取）：

链路	代价
x-y	6
x-v	3
x-w	6
x-z	8
y-z	12
y-v	8
y-t	7
v-t	4
v-w	4
v-u	3
t-u	2
w-u	3

---

Dijkstra 算法步骤：
初始化：$D(x)=0$，其余 $=\infty$
$$D(x)=0,D(y)=6,D(v)=3,D(w)=6,D(z)=8,D(t)=\infty ,D(u)=\infty$$
步骤表：

步骤	已确定集合 S	D(t)	D(u)	D(v)	D(w)	D(x)	D(y)	D(z)
初始	{x}	∞	∞	3,x	6,x	0	6,x	8,x
1	{x,v}	7,v	6,v	3	6,x	0	6,x	8,x
2	{x,v,u}	7,v	6	3	6,x	0	6,x	8,x
3	{x,v,u,w}	7,v	6	3	6	0	6,x	8,x
4	{x,v,u,w,y}	7,v	6	3	6	0	6	8,x
5	{x,v,u,w,y,t}	7	6	3	6	0	6	8,x
6	{x,v,u,w,y,t,z}	7	6	3	6	0	6	8

---

最终最短路径：

目的节点	最短距离	路径
v	3	x → v
u	6	x → v → u
w	6	x → w
y	6	x → y
t	7	x → v → t
z	8	x → z

---

P3 的 C++ 完整实现（Dijkstra 算法）

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <climits>
using namespace std;
// 节点名称映射：0=t, 1=u, 2=v, 3=w, 4=x, 5=y, 6=z
const string NODE_NAME = "tuvwxyz";
const int N = 7; // 节点数量
// Dijkstra 算法
// graph[i][j] 表示节点i到节点j的边权重，-1表示无边
void dijkstra(int src, vector<vector<int>>& graph) {
    // dist[i] 存储从src到i的当前最短距离
    vector<int> dist(N, INT_MAX);
    // prev[i] 存储最短路径中i的前驱节点
    vector<int> prev(N, -1);
    // inS[i] 表示节点i是否已加入确定集合S
    vector<bool> inS(N, false);
    dist[src] = 0;
    // 打印表头
    cout << "步骤\t已确定集合S\t";
    for (int i = 0; i < N; i++) {
        cout << "D(" << NODE_NAME[i] << ")\t";
    }
    cout << endl;
    for (int step = 0; step < N; step++) {
        // 在未确定节点中找距离最小的节点 u
        int u = -1;
        for (int i = 0; i < N; i++) {
            if (!inS[i] && (u == -1 || dist[i] < dist[u])) {
                u = i;
            }
        }
        if (dist[u] == INT_MAX) break; // 剩余节点不可达
        inS[u] = true; // 将u加入已确定集合
        // 打印当前步骤
        cout << step + 1 << "\t{";
        bool first = true;
        for (int i = 0; i < N; i++) {
            if (inS[i]) {
                if (!first) cout << ",";
                cout << NODE_NAME[i];
                first = false;
            }
        }
        cout << "}\t\t";
        for (int i = 0; i < N; i++) {
            if (dist[i] == INT_MAX) cout << "∞\t";
            else {
                cout << dist[i];
                if (prev[i] != -1) cout << "(" << NODE_NAME[prev[i]] << ")";
                cout << "\t";
            }
        }
        cout << endl;
        // 用u更新其邻居的距离（松弛操作）
        for (int v = 0; v < N; v++) {
            if (!inS[v] && graph[u][v] != -1) {
                // 如果经由u到v的路径更短，则更新
                if (dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                    prev[v] = u; // 记录前驱
                }
            }
        }
    }
    // 输出最终结果
    cout << "\n最终最短路径（从节点" << NODE_NAME[src] << "出发）：\n";
    for (int i = 0; i < N; i++) {
        if (i == src) continue;
        cout << NODE_NAME[src] << " -> " << NODE_NAME[i] << ": 距离=" << dist[i] << ", 路径=";
        // 回溯路径
        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--) {
            cout << NODE_NAME[path[j]];
            if (j > 0) cout << "->";
        }
        cout << endl;
    }
}
int main() {
    // 节点编号：0=t, 1=u, 2=v, 3=w, 4=x, 5=y, 6=z
    // -1 表示两节点间无直接链路
    vector<vector<int>> graph(N, vector<int>(N, -1));
    // 根据图1填入链路代价（无向图，双向填入）
    auto addEdge = [&](int a, int b, int cost) {
        graph[a][b] = cost;
        graph[b][a] = cost;
    };
    // t=0, u=1, v=2, w=3, x=4, y=5, z=6
    addEdge(0, 1, 2);  // t-u: 2
    addEdge(0, 2, 4);  // t-v: 4
    addEdge(0, 5, 7);  // t-y: 7
    addEdge(1, 2, 3);  // u-v: 3
    addEdge(1, 3, 3);  // u-w: 3
    addEdge(2, 3, 4);  // v-w: 4
    addEdge(2, 5, 8);  // v-y: 8
    addEdge(3, 4, 6);  // w-x: 6
    addEdge(4, 2, 3);  // x-v: 3
    addEdge(4, 5, 6);  // x-y: 6
    addEdge(4, 6, 8);  // x-z: 8
    addEdge(5, 6, 12); // y-z: 12
    // 从节点x(编号4)出发运行Dijkstra
    cout << "=== 从节点 x 出发的 Dijkstra 算法 ===" << endl;
    dijkstra(4, graph); // 4 = x
    return 0;
}

P5. 距离向量算法：节点 z 的距离表（图2网络）

图2网络链路（从图片读取）：

节点：u, v, x, y, z
链路：
  u-v: 1    u-y: 2
  v-x: 3    v-z: 6
  x-y: 3    x-z: 2

初始状态（每个节点只知道直连邻居代价）：
节点 z 的初始距离向量 $D_z$：
$$D_z(u)=\infty ,D_z(v)=6,D_z(x)=2,D_z(y)=\infty ,D_z(z)=0$$
z 的邻居是 v 和 x。
第一轮迭代（z 收到邻居的距离向量）：
从 v 得到：$D_v=[u:1,v:0,x:3,y:\infty ,z:6]$（v 只知道直连）
从 x 得到：$D_x=[u:\infty ,v:3,x:0,y:3,z:2]$
用 Bellman-Ford 更新 Dz(dest)=min⁡n{c(z,n)+Dn(dest)}D_z(dest) = \min_n\{c(z,n) + D_n(dest)\}Dz​(dest)=minn​{c(z,n)+Dn​(dest)}：
Dz(u)=min⁡{c(z,v)+Dv(u), c(z,x)+Dx(u)}=min⁡{6+1, 2+∞}=7D_z(u) = \min\{c(z,v)+D_v(u),\ c(z,x)+D_x(u)\} = \min\{6+1,\ 2+\infty\} = 7Dz​(u)=min{c(z,v)+Dv​(u), c(z,x)+Dx​(u)}=min{6+1, 2+∞}=7
Dz(v)=min⁡{c(z,v)+Dv(v), c(z,x)+Dx(v)}=min⁡{6+0, 2+3}=5D_z(v) = \min\{c(z,v)+D_v(v),\ c(z,x)+D_x(v)\} = \min\{6+0,\ 2+3\} = 5Dz​(v)=min{c(z,v)+Dv​(v), c(z,x)+Dx​(v)}=min{6+0, 2+3}=5
Dz(x)=min⁡{c(z,v)+Dv(x), c(z,x)+Dx(x)}=min⁡{6+3, 2+0}=2D_z(x) = \min\{c(z,v)+D_v(x),\ c(z,x)+D_x(x)\} = \min\{6+3,\ 2+0\} = 2Dz​(x)=min{c(z,v)+Dv​(x), c(z,x)+Dx​(x)}=min{6+3, 2+0}=2
Dz(y)=min⁡{c(z,v)+Dv(y), c(z,x)+Dx(y)}=min⁡{6+∞, 2+3}=5D_z(y) = \min\{c(z,v)+D_v(y),\ c(z,x)+D_x(y)\} = \min\{6+\infty,\ 2+3\} = 5Dz​(y)=min{c(z,v)+Dv​(y), c(z,x)+Dx​(y)}=min{6+∞, 2+3}=5
第一轮后 z 的距离表：

目的	经由 v	经由 x	$D_z$ (最小)
u	7	∞	7
v	6	5	5
x	9	2	2
y	∞	5	5
z	6	2	0

---

第二轮迭代（各节点更新后再次交换）：
收到 v 的新向量（v 已更新）：$D_v(u)=1,D_v(y)=4$（v 经由 x 到 y: 3+3=6 或 v 经由 u 到 y: 1+2=3… 取决于 v 的邻居情况）
经过多轮迭代后，最终稳定的 z 距离向量：
$$D_z(u)=6,D_z(v)=5,D_z(x)=2,D_z(y)=5,D_z(z)=0$$

P6. 距离向量算法最多需要多少轮迭代收敛？

结论：最多需要 $n-1$ 轮迭代（$n$ 为节点数）。
证明思路：
设网络中两个距离最远的节点之间的最短路径经过 $k$ 条链路（$k\le n-1$）。

• 第 0 轮：每个节点知道直连邻居（路径长度 1）
• 第 1 轮：通过 1 次交换，知道路径长度 $\le 2$ 的信息
• 第 $i$ 轮：知道路径长度 $\le i+1$ 的信息
  因此，经过 $k-1$ 轮交换后，所有路径信息传播到位。由于 $k\le n-1$，最多 $n-1$ 轮迭代即可收敛。
  $$\text{最大迭代次数}=n-1$$
  其中 $n$ 是网络中的节点数。

P7. 距离向量：节点 x 的情况（图3网络）

图3：x 连接 w（代价2）和 y（代价5），w 到 u 最短为 5，y 到 u 最短为 6。
a. x 到 w, y, u 的距离向量
$$D_x(w)=c(x,w)=2$$
$$D_x(y)=c(x,y)=5$$
Dx(u)=min⁡{c(x,w)+Dw(u), c(x,y)+Dy(u)}=min⁡{2+5, 5+6}=7D_x(u) = \min\{c(x,w)+D_w(u),\ c(x,y)+D_y(u)\} = \min\{2+5,\ 5+6\} = 7Dx​(u)=min{c(x,w)+Dw​(u), c(x,y)+Dy​(u)}=min{2+5, 5+6}=7
所以 $D_x=[w:2,y:5,u:7]$（经由 w 到 u）
b. 使 x 需要通告新最短路径到 u 的链路代价变化
当前 $D_x(u)=7$（经由 w）。若 $c(x,w)$ 减小，使得经由 w 的路径更短，或经由 y 的路径变得更短，x 就会更新并通告。
例如：将 $c(x,w)$ 从 2 减小到 1：
Dx(u)=min⁡{1+5, 5+6}=6<7D_x(u) = \min\{1+5,\ 5+6\} = 6 < 7Dx​(u)=min{1+5, 5+6}=6<7
，x 更新，通告新距离。
或将 $c(x,y)$ 从 5 减小到 0：
Dx(u)=min⁡{2+5, 0+6}=6<7D_x(u) = \min\{2+5,\ 0+6\} = 6 < 7Dx​(u)=min{2+5, 0+6}=6<7
，x 更新，通告新距离。
c. 使 x 不需要通告新最短路径到 u 的链路代价变化
若 $c(x,w)$ 增大，但 $D_x(u)$ 不变（经由 y 的路径接管）：
例如：将 $c(x,w)$ 从 2 增大到 4：
Dx(u)=min⁡{4+5, 5+6}=9>7D_x(u) = \min\{4+5,\ 5+6\} = 9 > 7Dx​(u)=min{4+5, 5+6}=9>7
，x 更新为 9，会通告（这其实会通告）
若将 $c(x,y)$ 从 5 增大到任意值（但经由 w 的路径不变）：
经由 w 仍为 7，$D_x(u)$ 不变，x 不通告。
例如：$c(x,y)$ 从 5 增大到 10：
Dx(u)=min⁡{2+5, 10+6}=7D_x(u) = \min\{2+5,\ 10+6\} = 7Dx​(u)=min{2+5, 10+6}=7
，最小值不变，x 不通告。

P8. 三节点拓扑的距离向量迭代

节点：x, y, z；链路代价：$c(x,y)=3,c(y,z)=6,c(z,x)=4$
初始化步骤（每个节点只知道直连邻居）：
$$D_x=[x:0,y:3,z:4]$$
$$D_y=[x:3,y:0,z:6]$$
$$D_z=[x:4,y:6,z:0]$$
第一轮迭代：
$D_x$ 更新：
Dx(z)=min⁡{c(x,y)+Dy(z), c(x,z)+Dz(z)}=min⁡{3+6, 4+0}=4（不变）D_x(z) = \min\{c(x,y)+D_y(z),\ c(x,z)+D_z(z)\} = \min\{3+6,\ 4+0\} = 4 \text{（不变）}Dx​(z)=min{c(x,y)+Dy​(z), c(x,z)+Dz​(z)}=min{3+6, 4+0}=4（不变）
Dx(y)=min⁡{c(x,y)+Dy(y), c(x,z)+Dz(y)}=min⁡{3+0, 4+6}=3（不变）D_x(y) = \min\{c(x,y)+D_y(y),\ c(x,z)+D_z(y)\} = \min\{3+0,\ 4+6\} = 3 \text{（不变）}Dx​(y)=min{c(x,y)+Dy​(y), c(x,z)+Dz​(y)}=min{3+0, 4+6}=3（不变）
$D_y$ 更新：
Dy(z)=min⁡{c(y,x)+Dx(z), c(y,z)+Dz(z)}=min⁡{3+4, 6+0}=6（不变）D_y(z) = \min\{c(y,x)+D_x(z),\ c(y,z)+D_z(z)\} = \min\{3+4,\ 6+0\} = 6 \text{（不变）}Dy​(z)=min{c(y,x)+Dx​(z), c(y,z)+Dz​(z)}=min{3+4, 6+0}=6（不变）
Dy(x)=min⁡{c(y,x)+Dx(x), c(y,z)+Dz(x)}=min⁡{3+0, 6+4}=3（不变）D_y(x) = \min\{c(y,x)+D_x(x),\ c(y,z)+D_z(x)\} = \min\{3+0,\ 6+4\} = 3 \text{（不变）}Dy​(x)=min{c(y,x)+Dx​(x), c(y,z)+Dz​(x)}=min{3+0, 6+4}=3（不变）
$D_z$ 更新：
Dz(y)=min⁡{c(z,x)+Dx(y), c(z,y)+Dy(y)}=min⁡{4+3, 6+0}=6（不变）D_z(y) = \min\{c(z,x)+D_x(y),\ c(z,y)+D_y(y)\} = \min\{4+3,\ 6+0\} = 6 \text{（不变）}Dz​(y)=min{c(z,x)+Dx​(y), c(z,y)+Dy​(y)}=min{4+3, 6+0}=6（不变）
Dz(x)=min⁡{c(z,x)+Dx(x), c(z,y)+Dy(x)}=min⁡{4+0, 6+3}=4（不变）D_z(x) = \min\{c(z,x)+D_x(x),\ c(z,y)+D_y(x)\} = \min\{4+0,\ 6+3\} = 4 \text{（不变）}Dz​(x)=min{c(z,x)+Dx​(x), c(z,y)+Dy​(x)}=min{4+0, 6+3}=4（不变）
结论：初始化后即已收敛（无更新），第一轮迭代后距离表与初始化相同，算法终止。

节点	D(x)	D(y)	D(z)
x	0	3	4
y	3	0	6
z	4	6	0

---

P9. 减小链路代价是否会引发无穷计数问题？

减小链路代价：不会引发无穷计数问题。
原因：距离值只会减小，距离向量的更新是单调非增的（参见P10），不会出现无限递增的情况。减小代价只会让路径变短，节点很快收敛到新的更小值。
新增一条链路（原本没有连接的两节点之间）：不会引发无穷计数问题。
原因：新增链路等价于将一条链路的代价从 $\infty$ 减小到某个有限值，属于"减小代价"的情况，同样只会使距离值减小，不会触发无穷计数。
只有链路代价增大（特别是变为无穷大，即链路断开）才可能引发无穷计数问题。

P10. DV 算法中 $D_x(y)$ 单调非增且有限步内稳定

论证：

1. 初始值有限或为 $\infty$：初始化时，$D_x(y)$ 要么是直连代价（有限），要么是 $\infty$。
2. 更新只会减小或不变：Bellman-Ford 更新为：
   Dx(y)←min⁡v{c(x,v)+Dv(y)}D_x(y) \leftarrow \min_v \{ c(x,v) + D_v(y) \}Dx​(y)←vmin​{c(x,v)+Dv​(y)}
   取最小值，所以更新后的值 $\le$ 当前值，即单调非增。
3. 有限步收敛：图中节点有限（设 $n$ 个），最短路径的边数至多 $n-1$。经过 $n-1$ 轮迭代，所有最短路径信息都已传播完毕。由于值单调非增且有下界（所有边代价为正，最短路有限），必然在有限步内稳定。

P21. 请求-响应模式 vs 陷阱（Trap）模式对比

---

对比维度	请求-响应（Request-Response）	陷阱（Trapping）
开销（Overhead）	高：管理服务器需要持续轮询所有设备，大量消息	低：只在事件发生时才发消息
异常事件通知时间	慢：最多等待一个轮询周期才能发现问题	快：事件发生时立即通知
消息丢失鲁棒性	较好：请求丢失会重试；但若response丢失，会重发请求	较差：Trap 消息丢失则管理服务器永远不知道该事件

---

综合建议：通常混合使用——定期轮询（获取统计数据）+ Trap（及时响应异常）。

P22. 为什么 SNMP 选择 UDP 而非 TCP？

主要原因如下：

1. 简单轻量：UDP 没有连接建立/拆除开销，适合简短的查询-响应交互
2. 避免死锁风险：若网络拥塞，TCP 会触发流控和拥塞控制，而管理流量此时恰恰最需要传输。UDP 不受 TCP 拥塞控制约束，更能在网络故障时传递管理信息
3. 设备资源受限：被管设备（如早期路由器）资源有限，维护大量 TCP 连接（每个被管设备一个）代价较高
4. SNMP 本身处理可靠性：SNMP 管理端自行决定是否重传，无需依赖 TCP 的可靠性机制
5. 管理消息通常短小：单个 UDP 数据报足以承载 SNMP PDU，不需要 TCP 的分段机制

编程题：分布式异步距离向量路由（图7网络）

图7网络（4个节点）：

  0 ---1--- 1
  |  \      |
  7   3     1
  |      \  |
  3 ---2--- 2

链路：0-1: 1, 0-2: 3（对角线）, 0-3: 7, 1-2: 1, 3-2: 2

完整 C++ 实现

#include <iostream>
#include <vector>
#include <climits>
#include <iomanip>
using namespace std;
const int N = 4;    // 节点数量
const int INF = INT_MAX / 2; // 用 INF 表示无穷大，避免加法溢出
// 链路代价矩阵（无向图）
// cost[i][j] = 节点i到节点j的直接链路代价，INF表示无直接链路
int cost[N][N] = {
    // 0    1    2    3
    {  0,   1, INF,   7 },  // 节点0的直连代价
    {  1,   0,   1, INF },  // 节点1的直连代价
    {INF,   1,   0,   2 },  // 节点2的直连代价
    {  7, INF,   2,   0 }   // 节点3的直连代价
};
// dist[i][j] = 节点i当前估计的到节点j的最短距离
int dist[N][N];
// next[i][j] = 节点i到节点j的下一跳
int nexthop[N][N];
// 初始化所有节点的距离表
void initialize() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            // 初始时，只知道直连代价
            dist[i][j] = cost[i][j];
            if (cost[i][j] < INF && i != j) {
                nexthop[i][j] = j; // 直连邻居，下一跳就是目的节点
            } else if (i == j) {
                nexthop[i][j] = i;
            } else {
                nexthop[i][j] = -1; // 不可达
            }
        }
    }
}
// 打印节点 node 的距离表
void printDistTable(int node, int iteration) {
    cout << "--- 节点" << node << " 的距离表（第" << iteration << "轮）---\n";
    cout << "目的\t";
    for (int j = 0; j < N; j++) cout << "节点" << j << "\t";
    cout << endl;
    cout << "距离\t";
    for (int j = 0; j < N; j++) {
        if (dist[node][j] >= INF) cout << "INF\t";
        else cout << dist[node][j] << "\t";
    }
    cout << endl;
    cout << "下一跳\t";
    for (int j = 0; j < N; j++) {
        if (nexthop[node][j] == -1) cout << "-\t";
        else cout << nexthop[node][j] << "\t";
    }
    cout << "\n\n";
}
// 执行同步距离向量算法
// 返回是否发生了更新
bool updateOnce() {
    // 临时保存新的距离表（同步更新）
    int newDist[N][N];
    int newNext[N][N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            newDist[i][j] = dist[i][j];
            newNext[i][j] = nexthop[i][j];
        }
    bool changed = false;
    // 对每个节点 i
    for (int i = 0; i < N; i++) {
        // 对每个目的节点 dest
        for (int dest = 0; dest < N; dest++) {
            if (dest == i) continue;
            // 枚举所有邻居 v（直连，cost[i][v] < INF）
            for (int v = 0; v < N; v++) {
                if (cost[i][v] >= INF) continue; // v 不是 i 的直连邻居
                // Bellman-Ford: 经由 v 的代价
                int via_v = cost[i][v] + dist[v][dest];
                if (via_v < newDist[i][dest]) {
                    newDist[i][dest] = via_v;
                    newNext[i][dest] = v; // 下一跳更新为 v
                    changed = true;
                }
            }
        }
    }
    // 更新全局距离表
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            dist[i][j] = newDist[i][j];
            nexthop[i][j] = newNext[i][j];
        }
    return changed;
}
int main() {
    // 初始化
    initialize();
    cout << "=== 分布式距离向量路由算法模拟 ===\n";
    cout << "网络拓扑：\n";
    cout << "  0 --1-- 1\n";
    cout << "  |  \\    |\n";
    cout << "  7   3   1\n";
    cout << "  |    \\  |\n";
    cout << "  3 --2-- 2\n\n";
    // 打印初始状态
    cout << "==== 初始化状态 ====\n";
    for (int i = 0; i < N; i++) printDistTable(i, 0);
    // 迭代执行距离向量算法
    int iteration = 1;
    while (true) {
        bool changed = updateOnce();
        cout << "==== 第" << iteration << "轮迭代 ====\n";
        for (int i = 0; i < N; i++) printDistTable(i, iteration);
        if (!changed) {
            cout << "算法已收敛！\n";
            break;
        }
        iteration++;
    }
    // 打印最终路由表
    cout << "\n=== 最终路由表 ===\n";
    for (int i = 0; i < N; i++) {
        cout << "节点" << i << "的路由表：\n";
        cout << setw(6) << "目的" << setw(8) << "最短距离" << setw(8) << "下一跳" << endl;
        for (int j = 0; j < N; j++) {
            cout << setw(6) << j << setw(8);
            if (dist[i][j] >= INF) cout << "INF";
            else cout << dist[i][j];
            cout << setw(8) << nexthop[i][j] << endl;
        }
        cout << endl;
    }
    return 0;
}

运行后预期输出（收敛后的路由表）：

节点0路由	目的	距离	下一跳
	1	1	1
	2	2	1
	3	4	1

---

路径说明：

• 0→1：代价1，直连
• 0→2：代价2，经由1（0→1→2，代价1+1=2，比直接对角线3更短）
• 0→3：代价4，经由1→2→3（1+1+2=4，比直连7更短）

P14. BGP 路由学习路径（图4网络）

图4：AS1(RIP), AS2(OSPF?→实为运行RIP?), AS3(OSPF), AS4(RIP)，前缀 x 在 AS4 中(连接到路由器4a)。
a. 路由器 3c 通过什么协议学到前缀 x？
eBGP。AS4 的边界路由器（4c）通过 eBGP 将前缀 x 的路由通告给 AS3 的边界路由器（3c）。
b. 路由器 3a 通过什么协议学到前缀 x？
OSPF（AS3 的 AS 内协议）。3c 通过 eBGP 学到 x 后，通过 iBGP 或 AS3 的内部路由协议（OSPF）将路由传播给 AS3 内的其他路由器（如 3a）。严格说是 iBGP（BGP 在 AS 内部的运行形式）。
c. 路由器 1c 通过什么协议学到前缀 x？
eBGP。AS3 的边界路由器（3a）通过 eBGP 将含 x 的路由通告给 AS1 的边界路由器（1c）。
d. 路由器 1d 通过什么协议学到前缀 x？
RIP（AS1 的 AS 内路由协议）或 iBGP。1c 学到 x 后，通过 AS1 内部协议（RIP）传播给 1d。

P15. 路由器 1d 转发表中 x 的出接口

a. I 等于 I1 还是 I2？
I = I1。（假设只有 AS3 路径可用）从 AS1 只能通过 AS3 到达 x（AS1→AS3→AS4→x），因此 1d 选择出口 I1（朝向 AS3 方向的接口）。
b. 若 AS2 和 AS4 之间有直接链路，I = I1 还是 I2？
这时 1d 可经由 AS3 或 AS2 到达 x：

• 经由 AS3：AS-PATH = AS3, AS4
• 经由 AS2：AS-PATH = AS2, AS4（若存在 AS2-AS4 直连）
  两条路径 AS-PATH 长度相同（均为2），此时需要用热土豆路由（Hot Potato Routing）：选择到 AS 出口点 IGP 代价最小的路径。取决于 1d 到 1c（出口AS3）和 1b（出口AS2）的内部代价，无法确定。
  c. 若路径经过 AS5（AS2→AS5→AS4），I = I1 还是 I2？
• 经由 AS3：AS-PATH = AS3, AS4（长度2）
• 经由 AS2：AS-PATH = AS2, AS5, AS4（长度3）
  I = I1（选择 AS-PATH 更短的路径，即经由 AS3）。