计算机网络——问题复习法（3）

问题1 (Question 1):

比较电路交换（Circuit Switching）与分组交换（Packet Switching）的基本原理、特点及差异。

答案 (Answer):

1. 电路交换（Circuit Switching）
• 基本原理：通信前建立专用端到端连接（如电话网络），独占链路资源。

• 特点：

• 固定带宽分配：链路资源被独占，即使空闲也不共享。

• 低灵活性：不适合突发流量（如网页浏览）。

• 实时性差：端到端时延不可预测（需预先建立连接）。

2. 分组交换（Packet Switching）
• 基本原理：数据拆分为分组，通过存储转发机制独立传输（如IP网络）。

• 特点：

• 资源共享：链路按需动态分配（统计复用），高效利用带宽。

• 支持突发流量：分组可排队等待传输。

• 适合实时服务：无需预先建立连接，时延更低（如VoIP）。

3. 核心差异
| 对比项 | 电路交换 | 分组交换 | | -------- | -------------- | ------------------ | | 资源分配 | 预先独占 | 按需动态共享 | | 灵活性 | 低（固定连接） | 高（适应突发流量） | | 适用场景 | 传统电话网络 | 互联网、实时通信 |

问题2 (Question 2):

描述互联网的层次化架构（Network of Networks），包括网络边缘（Edge）、接入网络（Access）、核心网络（Core）及ISP的作用。

答案 (Answer):

1. 互联网层次架构
| 层次 | 组成与功能 | | -------- | ------------------------------------------------------------ | | 网络边缘 | 终端设备（如手机、服务器），生成和消费数据（HTTP、P2P）。 | | 接入网络 | 连接边缘与核心（如光纤、Wi-Fi、DSL），由ISP（运营商）提供。 | | 核心网络 | 高速路由器互联，跨区域转发数据（如骨干网）。 | | ISP互联 | 不同ISP通过IXP（互联网交换点）或对等协议互联，形成“网络的网络”。 |

2. 关键点
• ISP层级：

• Tier 1 ISP（全球骨干，如AT&T） ↔︎ Tier 2（区域） ↔︎ Tier 3（本地）。

• 互联原则：下层ISP必须接入上层ISP或IXP以实现全球连通。

问题3 (Question 3):

对比TCP/IP模型与OSI模型的协议分层架构，说明各层功能及服务依赖关系。

答案 (Answer):

1. TCP/IP模型（4层）
| 层 | 功能 | | ---------- | ---------------------------------------- | | 应用层 | 提供用户服务（HTTP、DNS）。 | | 传输层 | 端到端可靠传输（TCP）或尽力而为（UDP）。 | | 网络层 | 路由与寻址（IP、ICMP）。 | | 网络接口层 | 物理传输（以太网、Wi-Fi）。 |

2. OSI模型（7层）
| 层 | 功能 | | ---------- | ------------------------------ | | 应用层 | 用户接口（HTTP、SMTP）。 | | 表示层 | 数据格式转换（加密、压缩）。 | | 会话层 | 建立/管理会话（RPC）。 | | 传输层 | 可靠传输（类似TCP）。 | | 网络层 | 路由（类似IP）。 | | 数据链路层 | 帧传输与错误检测（如以太网）。 | | 物理层 | 比特流传输（电缆、光纤）。 |

3. 关键差异
• TCP/IP更简化：合并OSI的上三层为应用层，下两层为网络接口层。

• 服务依赖：上层依赖下层（如HTTP依赖TCP，TCP依赖IP）。

总结
1. 交换技术：电路交换资源独占，分组交换动态共享。
2. 互联网架构：边缘-接入-核心-ISP互联，分层协作。
3. 协议模型：TCP/IP实用，OSI理论完整，均体现分层服务思想。

问题4 (Question 4):

解释Web缓存/代理服务器（Web Caching/Proxy Server）和条件GET（Conditional GET）的工作原理，并结合流量强度计算分析本地缓存（Local Caching）对网络性能的影响。

答案 (Answer):

1. Web缓存与代理服务器
• 原理：

• 代理服务器缓存热门资源（如网页、视频），后续请求直接返回缓存内容，减少源服务器负载。

• 本地缓存（浏览器或机构内缓存）：存储用户近期访问的资源，避免重复下载。

• 流量强度计算（基于用户图片）：

• 无缓存时：

◦ 局域网流量强度 = (请求速率 × 请求大小) / 带宽 = (15请求/s × 1Mb) / 100Mbps = 0.15。  

◦ 接入链路流量强度 = (15 × 1Mb) / 15Mbps = 1（拥塞）。

• 启用缓存后：

◦ 假设50%请求命中缓存，则接入链路流量强度降至 0.5，显著缓解拥塞。

2. 条件GET（Conditional GET）
• 原理：客户端发送请求时附加If-Modified-Since头部，若资源未更新，服务器返回304 Not Modified，节省带宽。

• 示例：

• 浏览器缓存了index.html，再次请求时携带该文件的最后修改时间。

• 服务器比对时间戳，未变化则返回304，浏览器直接使用缓存。

3. 性能优化效果
• 降低流量强度：缓存减少重复传输，避免接入链路拥塞（如用户图中带宽瓶颈）。

• 减少延迟：本地缓存响应速度远快于远程服务器。

问题5 (Question 5):

解释DNS系统的层次结构、基本功能与查询过程（迭代与递归），并说明其采用分布式设计的原因。

答案 (Answer):

1. DNS层次结构
| 层级 | 功能 | 示例 | | ------- | ------------------------------------------- | ----------------------- | | 根DNS | 返回顶级域（TLD）服务器地址。 | a.root-servers.net | | TLD DNS | 管理通用域（如.com）或国家域（如.cn）。 | gtld-servers.net | | 权威DNS | 存储具体域名（如www.example.com）的IP。 | ns1.example.com | | 本地DNS | 缓存查询结果，减少上游请求。 | 运营商提供的DNS服务器。 |

2. 查询过程
• 递归查询（客户端→本地DNS）：

• 本地DNS代表客户端完成所有查询，最终返回IP。

• 迭代查询（本地DNS→其他服务器）：

• 根DNS、TLD DNS仅返回下一级服务器地址，由本地DNS逐步查询。

3. 分布式设计原因
• 避免单点故障：单一服务器崩溃会导致全网DNS瘫痪。

• 提升扩展性：分层分担查询压力（如用户图片中提到的“可扩展性”）。

• 负载均衡：同一域名可映射到多个IP（如CDN节点）。

4. 查询顺序示例（查找www.newpool.org）
1. 客户端 → 本地DNS（无缓存） → 根DNS。
2. 根DNS → 返回.org的TLD服务器地址。
3. 本地DNS → TLD服务器 → 返回newpool.org的权威DNS地址。
4. 本地DNS → 权威DNS → 获取www.newpool.org的IP并缓存。

总结
1. Web缓存：通过代理和条件GET降低流量强度，优化性能（如用户图的拥塞分析）。
2. DNS系统：分布式层次结构实现高可用、低延迟的域名解析（如用户图关联的“无单点故障”）。

问题 (Question):

描述回退N帧协议（Go-Back-N, GBN）可靠数据传输的主要原理，结合其窗口机制（Window Mechanism）说明以下机制如何协同工作：校验和（Checksum）、定时器/超时（Timer/Timeout）、序号（Sequence Number）、确认（Acknowledgment）和流水线（Pipelining）。

重传的是大于或等于这个超时分组，在这个分组之前的都是默认已经被确认的分组！

答案 (Answer):

1. GBN的核心原理
• 窗口机制：发送方维护一个大小为N的滑动窗口，允许最多N个连续的未确认分组在传输中。

• 累积确认（Cumulative ACK）：接收方发送ACK(n)表示所有序号≤n的分组均已正确接收（如ACK(3)确认序号1/2/3）。

• 超时重传：仅对窗口中最旧的未确认分组（如序号n）启动定时器；若超时，重传该分组及窗口内所有后续分组。

2. 关键机制协同作用

机制 在GBN中的作用
校验和 检测传输中的比特错误，出错则丢弃分组（接收方不发送ACK，触发发送方超时重传）。
序号 标识分组顺序，确保接收方能检测丢失或乱序（如期待序号4却收到5，仍返回ACK(3)）。
累积确认 减少ACK数量（如ACK(4)可替代ACK(1)/ACK(2)/ACK(3)），但可能导致重复ACK（如接收方多次发送ACK(3)等待序号4）。
单个定时器 仅跟踪窗口最旧分组的超时（如序号1超时则重传1/2/3/4），简化计时器管理。
流水线 通过窗口允许连续发送多个分组，提高信道利用率（与停等协议对比）。

问题 (Question):

路由器中的排队（Queuing）发生在何处？为什么会出现排队现象？

答案 (Answer):

1. 排队发生的位置
| 位置 | 触发条件 | | ------------ | ------------------------------------------------------------ | | 输出端口排队 | 当交换结构速率（Rswitch）远大于线路速率（Rline）的N倍时，输出端口处理能力不足导致积压。 | | 输入端口排队 | 当交换结构速率（Rswitch）过慢，无法及时处理输入数据时，输入端口缓存溢出。 |

解释 (Explanation):

1. 输出端口排队
• 原理（基于用户图片）：

• 若交换结构速率 Rswitch = N × Rline（N为输入端口数），输出端口的线路速率（Rline）可能无法及时转发所有数据。

• 示例：

◦ 输入端口数N=4，R<sub>switch</sub>=4Gbps，R<sub>line</sub>=1Gbps → 输出端口需在1秒内处理4Gb数据，但只能发送1Gb，剩余3Gb排队。

• 影响：增加端到端时延，可能引发丢包。

2. 输入端口排队
• 原理（基于用户图片）：

• 若交换结构速率 Rswitch < N × Rline，输入端口的数据无法及时被交换结构处理。

• 示例：

◦ N=4，R<sub>line</sub>=1Gbps，R<sub>switch</sub>=2Gbps → 每秒有4Gb数据到达，但仅能处理2Gb，剩余2Gb在输入端口排队。

• 影响：输入缓冲区溢出，触发主动队列管理（如RED）或直接丢包。

3. 关键参数关系
• 避免排队的理想条件：Rswitch ≥ N × Rline（输出端口无排队）。

• 设计权衡：

• 提高Rswitch成本高，需平衡速率与硬件成本。

总结 (Summary):
• 输出端口排队：因交换速率远高于线路速率，输出带宽成为瓶颈。

• 输入端口排队：因交换速率低于总输入速率，交换结构成为瓶颈。

问题 (Question):

关于IPv4数据报分片（Fragmentation），假设发送一个4000字节的IP数据报（首部20字节）到MTU为1500字节的链路，以下哪项描述是正确的？
A. 生成3个分片，偏移量字段值分别为0、1000、2000
B. 生成3个分片，偏移量字段值分别为0、185、370
C. 生成3个分片，偏移量字段值分别为0、1000、1000
D. 以上都不对

image-20250429151932115

答案 (Answer):
✅ B. 生成3个分片，偏移量字段值分别为0、185、370

解释 (Explanation):

1. IPv4分片规则
• MTU限制：每个分片的总长度（首部+数据） ≤ MTU（1500字节）。

• 分片计算：

  1. 原始数据报：4000字节 = 20字节首部 + 3980字节数据。

  2. 分片1：
    ◦ 数据部分 = 1480字节（1500 MTU - 20字节新首部）。

    ◦ 偏移量 = 0（起始位置）。

    ◦ 标志位（Flag）= 1（表示还有后续分片）。

  3. 分片2：
    ◦ 数据部分 = 1480字节。

    ◦ 偏移量 = 1480 / 8 = 185（单位是8字节块）。

    ◦ 标志位 = 1。

  4. 分片3：
    ◦ 数据部分 = 3980 - 1480×2 = 1020字节。

    ◦ 偏移量 = (1480 + 1480) / 8 = 370。

    ◦ 标志位 = 0（最后一个分片）。

2. 用户图片验证
• 图片中明确标注：

• 分片1：长度=1500，偏移=0，标志=1。

• 分片2：长度=1500，偏移=185，标志=1。

• 分片3：长度=1040（含首部20字节，数据1020字节），偏移=370，标志=0。

3. 为什么其他选项错误？
• A选项：偏移量单位错误（应为8字节块，不是直接字节数）。

• C选项：偏移量重复且单位错误。

• D选项：B正确，排除D。

4. IPv6与IPv4分片区别
• IPv6：

• 不支持路由器分片：仅源主机可分片，通过“分片扩展头”实现。

• MTU发现：依赖ICMPv6的“Packet Too Big”报文动态调整。

总结 (Summary):
• IPv4分片：基于MTU强制分片，偏移量以8字节为单位计算。

• 关键计算：

• 分片数据长度 = MTU - 20字节首部。

• 偏移量 = 前一分片数据长度累计 / 8。

• IPv6改进：分片责任移交源主机，简化路由器处理。

Cyclic Redundancy Check (CRC) 原理与计算

核心：确定位数——补0——除法——尾部添加余数——接收端除法验证！

问题描述： 消息 $ D = 1010001101 $ 使用 CRC 方法传输，生成多项式为 $ G = x^5 + x^4 + x^2 + 1 $。

(a) 传输的消息 $ T $ 是什么？ (b) 接收方如何检查消息 $ T $ 是否无错误传输？

解答与解释：

(a) 计算传输的消息 $ T $ CRC 的核心思想是在原始消息 $ D $ 后附加一个校验码（余数 $ R $），使得最终的传输消息 $ T $ 能被生成多项式 $ G $ 整除。

步骤如下：

  1. 将生成多项式 $ G $ 转换为二进制形式： • $ G = x^5 + x^4 + x^2 + 1 $

    • 对应二进制：$ 110101 \(（从高次到低次，\) x^5 $ 到 $ x^0 $）。

  2. 在原始消息 $ D $ 后补 $ k $ 个 0： • $ G $ 的最高次是 5，所以补 5 个 0。

    • 补 0 后的消息：$ D_{} = 101000110100000 $。

  3. 用 $ D_{} $ 除以 $ G $ 计算余数 $ R $： • 除法规则：按位异或（XOR）。

    • 计算过程：

    1
    101000110100000 ÷ 110101
    ◦ 逐步进行 XOR 除法，最终得到余数 $ R = 01110 $（补到 5 位）。

  4. 构造传输消息 $ T $： • 将余数 $ R $ 附加到原始消息 $ D $ 后。

    • $ T = D R = 1010001101 = 101000110101110 $。

答案： $ T = 101000110101110 $

(b) 接收方如何检查消息 $ T $ 是否无错误？ 接收方通过以下步骤验证传输的正确性：

  1. 用接收到的消息 $ T $ 除以生成多项式 $ G $： • 如果余数为 0，说明传输无错误。

    • 如果余数不为 0，说明传输过程中发生了错误。

  2. 数学原理： • 发送方构造的 $ T $ 满足 $ T = D ^k R $，且 $ T $ 能被 $ G $ 整除。

    • 接收方计算 $ T G $：

    ◦ 如果 $ T $ 无错误，余数为 0。

    ◦ 如果 $ T $ 有错误，余数不为 0（CRC 能检测所有奇数位错误、突发错误等）。

答案： 接收方计算 $ T / G $，若余数为 0，则传输无错误；否则有错误。

总结： • (a) 传输消息 $ T $： $ 101000110101110 $（原始消息 + 余数）。

• (b) 校验方法： 接收方用 $ G $ 除 $ T $，余数为 0 则无错误。

Hierarchical Routing: Intra-AS/Inter-AS Routing and Hot-Potato Routing

问题描述： 1. 什么是分层路由（Hierarchical Routing）？
2. 解释 Intra-AS 和 Inter-AS 路由的区别。
3. 什么是热土豆路由（Hot-Potato Routing）？

解答与解释：

1. 分层路由（Hierarchical Routing） 原理：
• 互联网规模庞大，如果所有路由器都维护完整的路由表，会导致存储和计算开销过大。

• 分层路由 将网络划分为多个自治系统（Autonomous Systems, AS），每个 AS 内部独立管理路由（Intra-AS），而 AS 之间通过边界路由器（Border Routers）进行通信（Inter-AS）。

功能：
• 减少路由表规模（AS 内部仅需存储本地路由，外部路由由边界路由器处理）。

• 提高可扩展性（适用于大规模网络）。

• 支持不同的路由策略（不同 AS 可采用不同的路由协议）。

2. Intra-AS 和 Inter-AS 路由的区别 | 特性 | Intra-AS Routing（内部网关协议） | Inter-AS Routing（外部网关协议） | | -------- | ---------------------------------- | -------------------------------- | | 范围 | 单个 AS 内部 | 不同 AS 之间 | | 目标 | 优化内部路径（最短路径、负载均衡） | 策略优先（经济、政治因素） | | 协议 | RIP, OSPF, EIGRP | BGP | | 路由决策 | 基于最短路径（如 Dijkstra） | 基于策略（如 AS 间的商业协议） | | 更新频率 | 频繁（链路状态变化时） | 较少（仅策略变化时） |

举例：
• Intra-AS（OSPF）：某公司内部网络使用 OSPF 计算最短路径。

• Inter-AS（BGP）：ISP 之间通过 BGP 协商最佳出口路径。

3. 热土豆路由（Hot-Potato Routing）

贪心思想！

原理：
• “尽快把数据包扔给下一个 AS”（像扔热土豆一样）。

• 当一个 AS 有多个出口路由器时，选择 到边界路由器最短路径的出口，而不考虑后续 AS 的路径成本。

功能：
• 减少 AS 内部流量负担（尽快把数据包交给其他 AS）。

• 可能导致次优全局路径（因为只优化本地出口，不关心外部路径）。

举例：
• 某 AS 有两个出口路由器：

• 出口 A：内部距离 2 跳，但后续 AS 路径长。

• 出口 B：内部距离 5 跳，但后续 AS 路径短。

• 热土豆路由会选择出口 A（因为内部距离更短），即使全局路径可能更长。

总结： 1. 分层路由：通过 AS 划分减少路由开销，提高可扩展性。
2. Intra-AS：AS 内部路由（如 OSPF），关注最短路径。
3. Inter-AS：AS 间路由（如 BGP），关注策略。
4. 热土豆路由：优先选择本地最短出口，可能牺牲全局最优。

考试重点：
• Intra-AS vs. Inter-AS 的区别（协议、目标、范围）。

• 热土豆路由的优缺点（本地优化 vs. 全局次优）。

CSMA/CD (Carrier Sense Multiple Access with Collision Detection) 原理

问题描述： 简述 CSMA/CD（载波监听多路访问/冲突检测）的工作原理。

解答与解释：

1. CSMA/CD 的核心思想 CSMA/CD 是一种用于 共享介质网络（如以太网） 的介质访问控制（MAC）协议，主要解决 多节点竞争信道时的冲突问题。其核心思想是：
• 先监听，再发送（避免盲目占用信道）。

• 发送时检测冲突（发现冲突后立即停止）。

• 冲突后随机退避（减少重复冲突的概率）。

2. 工作流程（基于图片中的步骤） 1. 载波监听（Carrier Sense）
• 节点在发送数据前，先检测信道是否空闲。

• 如果信道忙：等待直到空闲。

• 如果信道空闲：开始传输数据。

  1. 冲突检测（Collision Detection）
    • 在传输过程中，持续监听信道。

    • 如果检测到其他节点也在传输（信号叠加导致电压变化）：

    ◦ 立即停止传输，并发送 冲突强化信号（Jam Signal） 通知其他节点。

  2. 随机退避（Random Backoff）
    • 冲突发生后，节点等待一个 随机时延（如二进制指数退避算法）。

    • 重新尝试发送数据。

3. 关键机制 • 冲突窗口（Collision Window）：

• 冲突只能在数据发送的 前 64 字节（512 比特） 内被检测到（以太网规定）。

• 超过此窗口后，认为传输成功（无冲突）。

• 二进制指数退避：

• 第 $ n $ 次冲突后，随机选择 $ 0 2^n-1 $ 倍的时隙时间（Slot Time）。

• 最多重试 16 次，超过则丢弃帧。

4. 举例说明 假设节点 A 和 B 同时检测到信道空闲并开始发送数据：
1. 发送后，双方检测到冲突（信号叠加）。
2. 立即停止发送，并各自等待 随机时间（如 A 等 1ms，B 等 3ms）。
3. A 先重试并成功占用信道，B 检测到信道忙后继续等待。

总结： • CSMA/CD 三步曲：监听 → 发送（检测冲突）→ 退避（冲突时）。

• 适用场景：传统以太网（半双工），现代全双工以太网已不再需要。

• 对比 CSMA/CA：

• CSMA/CD 用于有线网络（检测冲突），CSMA/CA 用于无线网络（避免冲突）。

考试重点：
• 冲突检测和退避机制。

• 与 CSMA/CA 的区别。

问题描述： 解释链路层交换机（Link-Layer Switch）如何通过 自学习（Self-Learning） 构建交换表（Switch Table），并说明其工作原理。

解答与解释：

1. 交换表（Switch Table）的作用 • 交换机需要知道 哪个设备（MAC 地址）连接在哪个端口，以便正确转发数据帧。

• 交换表存储 MAC 地址 → 端口号 的映射关系。

2. 自学习（Self-Learning）的工作原理 交换机通过观察数据帧的 源 MAC 地址 和 输入端口 来动态更新交换表，无需手动配置。

具体步骤：
1. 初始状态：交换表为空。
2. 接收数据帧：
• 当交换机从某个端口收到一个数据帧时，会检查该帧的 源 MAC 地址（Source MAC）。

• 记录映射关系：将该 MAC 地址与接收端口存入交换表（或更新已有条目）。

  1. 转发数据帧：
    • 检查数据帧的 目标 MAC 地址（Destination MAC）：

    ◦ 如果目标 MAC 在交换表中：从对应端口转发（单播）。

    ◦ 如果目标 MAC 不在交换表中：向 所有其他端口 泛洪（Flooding）。

  2. 老化机制（Aging）：
    • 交换表中的条目会设置 生存时间（TTL），超时后自动删除（防止过时信息）。

3. 示例说明 假设交换机有 3 个端口（Port 1, Port 2, Port 3）：

  1. 主机 A（MAC_A） 从 Port 1 发送数据给 主机 B（MAC_B）。
    • 交换机记录：MAC_A → Port 1。

    • 由于 MAC_B 不在表中，数据帧被泛洪到 Port 2 和 Port 3。

  2. 主机 B（MAC_B） 从 Port 2 回复数据给 主机 A（MAC_A）。
    • 交换机记录：MAC_B → Port 2。

    • 查表发现 MAC_A 对应 Port 1，直接转发（不再泛洪）。

最终交换表：
| MAC 地址 | 端口 | | -------- | ------ | | MAC_A | Port 1 | | MAC_B | Port 2 |

4. 自学习的优缺点 • 优点：

• 自动适应网络拓扑变化（无需手动配置）。

• 减少不必要的泛洪（提高效率）。

• 缺点：

• 初始泛洪可能造成短暂拥塞。

• 无法防止 MAC 地址欺骗攻击（需结合安全机制）。

总结： • 自学习 是交换机动态构建交换表的核心机制。

• 关键步骤：记录源 MAC + 端口，按目标 MAC 决定转发或泛洪。

• 考试重点：交换表更新逻辑、泛洪条件、老化机制。

1. Network Address Translation and Private Network (NAT) 原理

问题描述： 解释 网络地址转换（NAT） 的工作原理及其在私有网络中的作用。

解答与解释：

NAT 的核心功能 • 解决 IPv4 地址短缺问题：允许多个设备共享一个公网 IP 地址。

• 隐藏内部网络结构：外部网络无法直接访问私有 IP 地址。

工作原理 1. 私有 IP 与公有 IP 的映射： • 内部设备（如 192.168.1.2）发送数据包时，NAT 路由器将其 源 IP 替换为公网 IP（如 203.0.113.1）。

• NAT 维护一个 转换表，记录内部 IP + 端口与外部 IP + 端口的映射关系。

  1. 数据包返回时的处理： • 外部服务器响应时，NAT 根据转换表将 目标 IP 还原为私有 IP，再转发给内部设备。

  2. 端口多路复用（NAPT）： • 通过不同端口区分内部设备（如 203.0.113.1:5000 → 192.168.1.2:3000）。

私有网络的作用 • 私有 IP 范围（不可路由）：

• 10.0.0.0/8、172.16.0.0/12、192.168.0.0/16。

• 安全性：外部无法直接扫描内部设备。

举例 • 内部主机 192.168.1.2 访问百度：

• NAT 将源 IP 改为 203.0.113.1，端口改为 5000。

• 百度响应到 203.0.113.1:5000，NAT 转换回 192.168.1.2:3000。

问题描述： 描述 链路状态算法（Dijkstra） 的计算步骤，并计算下图中 A 到 D 的最短路径（假设链路成本已标出）。

1
2
3
4
5
A --2-- B --3-- D
 \     / \     /
  1   4   2   5
   \ /     \ /
    C --7-- E

解答与解释：

Dijkstra 算法步骤 1. 初始化： • 设置起点（A）的距离为 0，其他节点为 ∞。

• 优先队列：A(0), B(∞), C(∞), D(∞), E(∞)。

  1. 迭代过程： • 第1步：取出 A，更新邻居：

    ◦ B = min(∞, 0+2) = 2

    ◦ C = min(∞, 0+1) = 1

    ◦ 队列：B(2), C(1), D(∞), E(∞)。

    • 第2步：取出 C（距离最小），更新邻居：

    ◦ B = min(2, 1+4) = 2（不更新）

    ◦ E = min(∞, 1+7) = 8

    ◦ 队列：B(2), E(8), D(∞)。

    • 第3步：取出 B，更新邻居：

    ◦ D = min(∞, 2+3) = 5

    ◦ E = min(8, 2+2) = 4

    ◦ 队列：E(4), D(5)。

    • 第4步：取出 E，更新邻居：

    ◦ D = min(5, 4+5) = 5（不更新）

    ◦ 队列：D(5)。

  2. 结果： • A → D 的最短路径：A → B → D，总成本 = 5。

关键点 • 复杂度：O(n²)（n 为节点数）。

• 对比距离向量算法：链路状态算法收敛更快，但需全局信息。

3. IP Datagram off the Subnet 原理

问题描述： 解释 IP 数据报如何跨子网传输，并说明路由器的作用。

解答与解释：

跨子网传输流程 1. 源主机判断目标是否在同一子网： • 通过 子网掩码 计算目标 IP 的网络地址。

• 若不同子网，发送到 默认网关（路由器）。

  1. 路由器处理： • 检查目标 IP 的路由表，选择下一跳。

    • 修改数据包的 MAC 地址（源 MAC 改为路由器接口 MAC，目标 MAC 改为下一跳 MAC）。

  2. ARP 协议的作用： • 若路由器无下一跳 MAC，发送 ARP 请求 解析。

举例 • 主机 192.168.1.2/24 访问 10.0.0.2/8：

  1. 判断 10.0.0.2 不在 192.168.1.0/24 子网。
  2. 发送数据包到默认网关 192.168.1.1（路由器）。
  3. 路由器查询路由表，转发到下一跳（如 10.0.0.1）。

关键点 • TTL 减 1：每经过一个路由器，TTL 减 1，防止环路。

• 分片与重组：若 MTU 不同，路由器可能分片。

总结：

  1. NAT：映射私有 IP 到公网 IP，依赖转换表和端口复用。
  2. 链路状态算法：Dijkstra 计算最短路径，全局信息驱动。
  3. 跨子网传输：依赖路由器、ARP 和路由表，修改 MAC 地址转发。