logoChat01.ai

《计算机网络课程》 第五章 作业与思考 作业题 1. 一个数据报网络允许路由器在必要的时候丢弃数据包...

Criado em: 22 de junho de 2025

Respondido usando O3 por Chat01

Pergunta

《计算机网络课程》
第五章 作业与思考
作业题

  1. 一个数据报网络允许路由器在必要的时候丢弃数据包。路由器丢弃一个数据包的概率为
    p。请考虑这样的情形：源主机连接到源路由器，源路由器连接到目标路由器，然后目标路
    由器连接到目标主机。如果任何一台路由器丢掉了一个数据包，则源主机最终会超时，然
    后再重新发送。如果主机至路由器以及路由器至路由器之间的线路都计为一跳，试问：
    （a） 每次传输数据包的平均跳数是多少？
    （b） 数据包的平均传输次数是多少？
    （c） 每个接收到数据包所需的平均跳数？
    2.有一通信子网可用(A,B,12)(B,C,3) (C,D,5) (A,E,6)(E,C,8) (E,F,7) (F,D,2) (B,F,9) 表示,假设
    采用距离矢量路由算法。网络才启动时，A 的初始路由表如下图所示，其它节点初始时刻路
    由表可类推，试画出第一次交换相邻路由表后 A 的路由表。说明经过多少次交换之后路由
    表达到稳定状态。
    A - -
    B 12 B
    E 6 E
  2. Internet 上的一个 B 类网的子网屏蔽为 255.255.240.0。每个子网最多有多少台主机？
  3. 子网划分可以使得一个大的地址段更便于管理，假设某大学获得了一个 B 类地址段
    178.32.0.0/16. 网络管理中心需要为学校各个学院进行地址分配，假设计算机学院需要地址
    较多，至少需要 1500 个地址，电气电子学院和行政办公楼需要至少 500 个地址。外语院等
    文史类学院 4 个，每个至少需要 50 个地址，请为各个学院和办公楼分配地址，设置网络地
    址和掩码，要求尽量利用可变长子网掩码，使得能满足各学院和机关的基本要求，并尽量分
    配相邻地址段，同时所剩未分配地址最多。请给出为各学院分配的子网号和掩码位数，说明
    这样划分的理由。
    6.一个路由器刚刚接收到以下新的 IP 地址：57.6.96.0/21、57.6.104.0/21、57.6.112.0/21 和
    57.6.120.0/21.如果所有这些地址都使用同一条出境线路，试问它们可以被聚合吗？如果可以，
    它们被聚合到哪个地址上？如果不可以，请问为什么？
  4. 从 29.18.0.0 到 29.27.128.255 的一组 IP 地址已经被聚合到 29.18.0.0/17.然而，这里有一个
    空闲地址块，即从 29.18.60.0 到 29.28.63.255 之间的 1024 个地址还没有被分配。现在这块空
    闲地址突然要被分配给一台使用不同出境线路的主机。试问是否有必要将聚合地址分割成几
    块，然后把新的地址块加入到路由表中，再来看是否可以重新聚合？如有没有必要这样做，
    请问该怎么办呢？
    8.一台路由器的路由表有如下部分（CIDR）表项：
    地址/掩码 下一跳
    135.46.56.0/22 接口 0
    135.46.60.0022 接口 1
    192.53.40.0/23 路由器 1
    默认 路由器 2
    一个到达的分组的目标地址为下列 IP 地址，请解释路由器如何选择下一跳？
    (a)192.53.40.7（b）135.46.58.15 (c) 135.46.52.2

思考题

  1. 虚电路网络是否需要数据报子网中的路由表，为什么？既然虚电路不携带目的地址，它
    又是如何进行分组路由的？
  2. 分组交换的两种实现是虚电路与数据报，两者实现上的不同，各自的优缺点
  3. 距离向量路由算法和链路状态路由算法的工作原理。哪个是需要获取全局网络拓扑的？
    哪个有无穷数数问题
    4..解释分级路由策略与平面路由策略相比的好处，IP 路由时是如何实现分级路由策略的。
    论述因特网中路由器收到一个 IP 分组之后的整个操作过程。
  4. NAT 地址转换使得多个用户可以共用一个 IP 地址，请解释当数据包通过 NAT 转换的时
    候，进出数据包分别发生了什么变化？NAT 地址盒最多一次容纳多少个 TCP 或 UDP 数据
    流，为什么？
  5. ARP 跨网段是如何工作的?
  6. 为什么 ICMP 报文可以被用来测试网络状态和拓扑的？
  7. 在一个面积为 h×h 的区域内随机撒入 K 个传感器节点,传感器网络的汇聚点位于正方形
    区域的某个顶点处，假设可通信的最大距离距离是 r, 设计一个模拟仿真程序，
    测试（1）存在孤立点的概率（即该传感器节点无法和任何其他节点相连）
    （2）无法到达汇聚点的传感器节点是哪些点。给出模拟程序实现的基本思想和方法。

Python

python
import sympy as sp
p=sp.symbols('p')
expr = p + 2*p*(1-p) + 3*(1-p)**2
sp.expand(expr)


p**2 - 3*p + 3

Python

python
nodes = ['A','B','C','D','E','F']
edges = {('A','B'):12, ('B','C'):3, ('C','D'):5, ('A','E'):6, ('E','C'):8, ('E','F'):7, ('F','D'):2, ('B','F'):9}
# make undirected
edge_cost = {}
for (u,v),c in edges.items():
    edge_cost.setdefault(u,{})[v]=c
    edge_cost.setdefault(v,{})[u]=c

# distance vector iterative
dist = {u:{v:(0 if u==v else (edge_cost[u][v] if v in edge_cost[u] else math.inf)) for v in nodes} for u in nodes}
next_hop = {u:{v:(None if v==u else (v if v in edge_cost[u] else None)) for v in nodes} for u in nodes}
def iterate(dist):
    changed=False
    for u in nodes:
        for v in nodes:
            if v==u: continue
            best = dist[u][v]
            best_nh = next_hop[u][v]
            for n,cost in edge_cost[u].items():
                if dist[n][v] + cost < best:
                    best = dist[n][v] + cost
                    best_nh = n
            if best < dist[u][v]:
                dist[u][v]=best
                next_hop[u][v]=best_nh
                changed=True
    return changed

iters=0
while iterate(dist):
    iters+=1
print(iters)
# show A
print(dist['A'])
print(next_hop['A'])

Pensamento

Calculating path costs after exchange

For destination F, A calculates:

  • Route via E: A->E (6) + E->F (7) = 13.
  • Route via B: A->B (12) + B->F (9) = 21. So, A chooses the route via E.

For destination D, there's no route yet because E doesn't know how to reach it. The cost to D stays infinite after the first exchange.

Convergence should happen in at most 5 iterations with the distance vector algorithm, given its asynchronous nature.

Finalizing routing and subnet allocation

After a couple of exchanges, the routing table becomes stable, with A routing as follows:

  • B: cost 12 via B
  • E: cost 6 via E
  • C: cost 14 via E
  • F: cost 13 via E
  • D: cost 15 via E

For subnetting, I begin with a /16 network address (178.32.0.0). For the computer science department, a /21 subnet will support 2046 hosts. For electrical, electronic, and admin departments, /23 subnets will offer 510 hosts each. Finally, smaller subnets (/26) fit the four colleges needing 62 hosts each.

Subnet allocation and aggregation

For the subnetting task, I use /23 subnets for Electrical/Electronic and Admin departments, which need 512 addresses each.

Then I allocate /26 subnets for the four language departments: starting with 178.32.12.0 for the first and moving sequentially.

Regarding address aggregation, combining the networks 57.6.96.0/21, 104.0/21, 112.0/21, and 120.0/21 into a supernet yields a /19 network. For 29.18.0.0 to 29.27.128.255, I initially consider /17 but re-evaluate, concluding it might require a /13 supernet address.

Thought for 51 seconds

Resposta

下面给出《计算机网络课程》第五章“作业题”和“思考题”的参考答案与推导过程，全部使用中文说明，便于直接学习、核对与复习。如有符号或格式要求，可再告诉我。

一、作业题

1 . 数据报网络中路由器按概率 p 丢包

设主机→源路由器、源路由器→目标路由器、目标路由器→目标主机各算一跳。两台路由器独立丢包，主机链路不丢包。

事件概率本次尝试经历跳数
第 1 个路由器丢包p1
第 1 个路由器成功、第 2 个丢包(1-p)p2
两个路由器都成功(1-p)²3

(a) 每次尝试的平均跳数

Ehop=p⋅1+(1−p)p⋅2+(1−p)2⋅3=3−3p+p2E_{\text{hop}} = p\cdot1 + (1-p)p\cdot2 + (1-p)^2\cdot3 = 3 - 3p + p^{2}

(b) 平均尝试次数
一次尝试成功概率 q=(1−p)2q=(1-p)^2。尝试次数服从几何分布：

Etry=1q=1(1−p)2E_{\text{try}}=\frac1{q}=\frac1{(1-p)^2}

(c) 每个成功数据包平均耗费的跳数

Esucc hop=Ehop×Etry=3−3p+p2(1−p)2E_{\text{succ\,hop}} = E_{\text{hop}}\times E_{\text{try}} = \frac{3-3p+p^{2}}{(1-p)^2}

2 . 距离矢量路由——第一次表交换及收敛轮数

网络边 (带权)：

text
(A,B,12) (B,C,3)  (C,D,5)
(A,E,6)  (E,C,8)  (E,F,7)
(F,D,2)  (B,F,9)

A 的初始路由表

目的网代价下一跳
B12B
E6E

第一次与邻居 (B,E) 交换后：

目的网代价下一跳说明
B12B直接链路
E6E直接链路
C6+8 = 14EA→E→C
F6+7 = 13EA→E→F
D∞–暂未知

再交换一次后即稳定（共 2 轮），因为新矢量继续传递可得到
A→E→F→DA\to E\to F\to D，代价 6+7+2 = 15：

目的网代价下一跳
B12B
C14E
D15E
E6E
F13E

4 . 子网掩码 255.255.240.0

掩码 /20，主机位 12 位 ⇒ 每个子网可用主机

212−2=40942^{12}-2 = 4094

5 . 可变长子网划分（178.32.0.0/16）

部门需主机数选用前缀可用主机子网地址
计算机学院≥1500/212046178.32.0.0/21
电气电子学院≥500/23510178.32.8.0/23
行政办公楼≥500/23510178.32.10.0/23
文史学院 ①≥50/2662178.32.12.0/26
文史学院 ②≥50/2662178.32.12.64/26
文史学院 ③≥50/2662178.32.12.128/26
文史学院 ④≥50/2662178.32.12.192/26

理由：

  • 先按需求从大到小分配，避免碎片。
  • 块与块相邻，管理方便。
  • /13 余量（178.32.13.0 及以后）保持未分配，后续扩容空间最大。

6 . 前缀聚合

四段 /21 网络：

text
57.6.96.0/21
57.6.104.0/21
57.6.112.0/21
57.6.120.0/21

第三字节 96,104,112,120 连续且均为 8 的倍数，能组成一个块长
4×211=81924 \times 2^{11}=8192 地址的 /19 网络。
结果：57.6.96.0/19。

7 . 已聚合块与新增空洞

  • 现路由持有聚合条目 29.18.0.0/17。
  • 要把 “29.18.60.0 – 29.28.63.255” （1024 地址，/22）指向不同出口。

无需拆分原 /17：在路由表中新增更长前缀
（例如 29.18.60.0/22）指向新出口即可，基于 最长前缀匹配，
这 1024 个地址会走新路径，其余仍由 /17 处理。

8 . CIDR 查找-最长前缀匹配

目标地址命中前缀下一跳
(a) 192.53.40.7192.53.40.0/23路由器 1
(b) 135.46.58.15135.46.56.0/22接口 0
(c) 135.46.52.2无更具体匹配默认 → 路由器 2

二、思考题要点

  1. 虚电路是否需要路由表？
    需要，但形式不同。每台交换节点维护 VCI→(出接口, 新 VCI) 的映射表，而非完整目标地址 → 下一跳表。分组携带虚电路号，由交换节点查表快速转发。

  2. 虚电路 vs 数据报

特性虚电路数据报
建链需连接建立阶段无需
转发开销小（查 VCI）大（查完整地址）
可靠性可保证顺序、拥塞控制自行保证
失败恢复重新建链慢路由可绕行快
适用ATM、MPLSIP
  1. 距离向量 vs 链路状态
项距离向量 (DV)链路状态 (LS)
交换内容到各目的的距离自身与邻居链路状态
视图无全局拓扑构造全网拓扑
计算贝尔曼-福德Dijkstra
问题计数到无穷——
收敛速度较慢较快

  1. 分级路由优势 & IP 实现

    • 减少路由表规模与更新流量。
    • IP 采用：网络号/子网号/主机号三级；CIDR 再次聚合前缀。
    • IP 数据报处理流程：检验首部 → 查最长前缀 → TTL-- → 重新计算校验和 → 转发。

  2. NAT 转换过程与流数量上限

    • 出站：私有 IP:port → 公网 IP:新-port，写入 NAT 表。
    • 入站回包：查表反向还原。
    • 一条 UDP/TCP 流唯一由五元组确定；端口 16 位 ⇒ 单个公网地址最多 65 536 条并发映射（实际上 0-1023 为系统保留，故略少）。

  3. ARP 跨网段

    • 本网广播 ARP 只在局域网内生效。
    • 路由器充当 Proxy ARP：为另一网段 IP 回应 MAC，或使用 ARP+RARP relay。
    • 或在 L3 交换机/网关上配置 ARP proxy / Gratuitous ARP 实现跨网段解析。

  4. ICMP 用于网络探测的原因

    • 协议内含 Echo、Time-Exceeded、Destination-Unreachable 等报文。
    • 路由器/主机必须回显，故可借 ping 测连通、traceroute 逐跳递减 TTL 得到路径拓扑。

  5. 随机传感器网络模拟思想

    1. 随机在 [0,h]×[0,h][0,h]\times[0,h] 内生成 K 个节点坐标。

    2. 构建图：两节点距离 ≤ r 视为连边。

    3. 孤立点概率：统计度为 0 的节点数 / K，多次 Monte-Carlo 取平均。

    4. 不可达节点：对每次实验从汇聚点（假设顶点 (0,0)）做 BFS/DFS，标记未被访问的节点。

    可用 Python / MATLAB 生成随机点、计算欧氏距离矩阵并分析连通性。若需要完整代码示例，可以再告诉我。

如需对某一题深入推导、验证数值，或查看模拟源码，请随时提出！

Compartilhar esta Q&A