跳转至

Abandoned-cap7to9-chara3

谢希仁《计算机网络(第8版)》第7至9章【第三类题】硬核演算手册

范围说明:本册严格仅收录第7章《网络安全》、第8章《互联网上的音频/视频服务》、第9章《无线网络和移动网络》的【第三类:建议刷的巩固计算与推导题】(共 12 题:7-13, 7-14, 7-20, 7-22, 7-23, 7-25;8-15, 8-20, 8-33, 8-36;9-13, 9-15)。


一、 第7章《网络安全》第三类题(共 6 题,P368–369)

1. 7-13 & 7-14 对称加密、报文鉴别码 MAC 与公钥数字签名的符号推导与开销计算

  • 题目要点:
  • 7-13:A 和 B 共享对称密钥 \(K_{AB}\)。A 收到用 \(K_{AB}\) 加密的报文,能否向第三方证明该报文必为 B 所发(B 不能抵赖)?
  • 7-14:比较图 7-5(具有机密性的数字签名)与图 7-6(使用报文鉴别码 MAC),哪一种更有利于鉴别?

  • 符号表达式与定量对比:

  • 对称加密表达式(7-13): \(A \leftarrow B : E_{K_{AB}}(X)\)
    • 结论:A 不能向第三方证明报文必出自 B。因为 A 和 B 均持有相同的对称密钥 \(K_{AB}\),A 完全可以自己计算出 \(E_{K_{AB}}(X)\) 进行伪造,故不具备不可抵赖性。
  • 图 7-5 具有机密性的数字签名表达式(7-14): \(A \to B : E_{PK_B}\Big(X \,\big\|\, D_{SK_A}\big(H(X)\big)\Big)\)
    • 运算步骤与次数:发送方需执行 1 次散列运算 \(H(X)\) + 1 次私钥签名运算 \(D_{SK_A}\)(大数模幂运算,慢) + 1 次加密运算 \(E_{PK_B}\)。
    • 鉴别能力:由于全球仅 A 拥有私钥 \(SK_A\),任何第三方均可用公开的 \(PK_A\) 验证签名,同时实现源点鉴别、完整性校验与不可抵赖性(更有利于全面鉴别)。
  • 图 7-6 报文鉴别码 MAC 表达式(7-14): \(A \to B : X \,\big\|\, H(X \,\|\, K_{AB})\)

    • 运算步骤与次数:收发双方仅需执行 1 次带共享密钥 \(K_{AB}\) 的散列运算(极快,无公钥大数运算开销),但不具备第三方不可抵赖性。
  • 【附:第7章必会定量计算公式】

  • \(N\) 个用户两两保密通信所需密钥总数:
    • 无中心对称密码体制:\(K = C_N^2 = \mathbf{\frac{N(N-1)}{2}}\);
    • 有中心 KDC(如 Kerberos)对称体制:长期主密钥数为 \(\mathbf{N}\);
    • 公钥密码体制(RSA):公私钥对总数为 \(N\) 对(即 \(\mathbf{2N}\) 把密钥)。
  • RSA 公私钥手算公式:已知素数 \(p, q\) 及公钥 \(e\):
    1. 模数 \(n = p \times q\);
    2. 欧拉函数 \(\varphi(n) = (p-1)(q-1)\);
    3. 私钥 \(d\) 满足:\(e \times d \equiv 1 \pmod{\varphi(n)}\);
    4. 加密:\(C = M^e \bmod n\);解密:\(M = C^d \bmod n\)。

2. 7-20 中间人攻击(MITM)交互过程符号推导与防御

  • 攻击交互公式(设攻击者为 \(C\),篡改未认证的公钥交换):
  • \(B \to C(\text{截获}) : PK_B\),随后攻击者替换为自己的公钥:\(C \to A : PK_C\);
  • \(A\) 误将 \(PK_C\) 当作 \(B\) 的公钥加密明文 \(X\):\(A \to C(\text{截获}) : E_{PK_C}(X)\);
  • \(C\) 用自己的私钥解密窃取明文:\(D_{SK_C}\big(E_{PK_C}(X)\big) = X\),随后用 \(B\) 的真公钥重新加密发给 \(B\):\(C \to B : E_{PK_B}(X)\)。

  • 防御算式(CA 数字证书绑定): \(\text{Cert}_B = \text{ID}_B \,\big\|\, PK_B \,\big\|\, D_{SK_{\text{CA}}}\Big(H(\text{ID}_B \,\|\, PK_B)\Big)\) \(A\) 用预置的 CA 公钥 \(PK_{\text{CA}}\) 验证签名,攻击者 \(C\) 因无 \(SK_{\text{CA}}\) 无法伪造证书。


3. 7-22 & 7-23 IPsec 协议族封装结构与安全关联 SA 复用计算

  • 7-22 IPsec 核心组件:
  • AH(鉴别首部,协议号 51):提供源点鉴别 + 数据完整性 + 防重放,不提供加密。
  • ESP(封装安全有效载荷,协议号 50):提供机密性(加密) + 源点鉴别 + 数据完整性 + 防重放。
  • IKE(互联网密钥交换):自动协商建立安全关联 SA 与交换会话密钥。

  • 7-23 发送 6 个分组需建立几次安全关联 SA:

  • 只需在发送第 1 个分组前建立 1 次单向安全关联 SA!
  • 后续接连发送的全部 6 个分组共享并复用同一个 SA(仅将每个分组 ESP 首部中的 32 位防重放序号依次递增为 \(1, 2, 3, 4, 5, 6\))。

4. 7-25 运输层安全协议 TLS 四步握手密钥推导过程

  1. 协商算法与交换明文随机数:\(A \to B : R_A\),\(B \to A : R_B\);
  2. 证书验证:\(B \to A : \text{Cert}_B\)(内含 \(PK_B\)),\(A\) 用 \(PK_{\text{CA}}\) 校验通过;
  3. 传递预主密钥并导出会话密钥:\(A\) 生成随机秘密数 \(S\)(Pre-master Secret),发送密文 \(E_{PK_B}(S)\);\(B\) 计算 \(D_{SK_B}\big(E_{PK_B}(S)\big) = S\)。随后双方各自通过伪随机函数计算出会话密钥: \(K_{\text{session}} = \text{PRF}(S,\ R_A,\ R_B)\)

  4. 握手完成校验:双方用 \(K_{\text{session}}\) 加密发送握手结束(Finished)报文验证完整性。


二、 第8章《互联网上的音频/视频服务》第三类题(共 4 题,P402–404)

5. 8-15 实时音频流固定播放时延与接收端缓存队列长度逐时刻计算

  • 已知条件:每隔 \(10\text{ ms}\) 发送 1 个音频分组。前 10 个分组通过网络的时延 \(d_i\)(\(i=1\sim 10\))依次为:\(45, 50, 53, 46, 30, 40, 46, 49, 55, 51\text{ ms}\)。接收端设定还原时的恒定端到端总时延为 \(D = 75\text{ ms}\)。
  • 完整计算表与标准答案(设第 1 个分组在 \(t = 0\text{ ms}\) 发出):
  • 发送时刻公式:\(t_{\text{send}}(i) = 10(i - 1)\text{ ms}\)
  • 到达接收端时刻公式:\(t_{\text{arr}}(i) = t_{\text{send}}(i) + d_i\)
  • 第(2)问:在接收端缓存中应增加的时延公式:\(d_{\text{buf}}(i) = 75\text{ ms} - d_i\)
  • 还原播放(出缓存)时刻公式:\(t_{\text{play}}(i) = t_{\text{send}}(i) + 75\text{ ms}\)
分组序号 \(i\) 发送时刻 \(t_{\text{send}}\) 网络时延 \(d_i\) (1) 到达时刻 \(t_{\text{arr}}\) (2) 缓存应增加的时延 \(d_{\text{buf}}\) 播放(出缓存)时刻 \(t_{\text{play}}\)
#1 \(0\text{ ms}\) \(45\text{ ms}\) \(45\text{ ms}\) \(75 - 45 =\) \(30\text{ ms}\) \(75\text{ ms}\)
#2 \(10\text{ ms}\) \(50\text{ ms}\) \(60\text{ ms}\) \(75 - 50 =\) \(25\text{ ms}\) \(85\text{ ms}\)
#3 \(20\text{ ms}\) \(53\text{ ms}\) \(73\text{ ms}\) \(75 - 53 =\) \(22\text{ ms}\) \(95\text{ ms}\)
#4 \(30\text{ ms}\) \(46\text{ ms}\) \(76\text{ ms}\) \(75 - 46 =\) \(29\text{ ms}\) \(105\text{ ms}\)
#5 \(40\text{ ms}\) \(30\text{ ms}\) \(70\text{ ms}\) (比#3,#4先到!) \(75 - 30 =\) \(45\text{ ms}\) \(115\text{ ms}\)
#6 \(50\text{ ms}\) \(40\text{ ms}\) \(90\text{ ms}\) \(75 - 40 =\) \(35\text{ ms}\) \(125\text{ ms}\)
#7 \(60\text{ ms}\) \(46\text{ ms}\) \(106\text{ ms}\) \(75 - 46 =\) \(29\text{ ms}\) \(135\text{ ms}\)
#8 \(70\text{ ms}\) \(49\text{ ms}\) \(119\text{ ms}\) \(75 - 49 =\) \(26\text{ ms}\) \(145\text{ ms}\)
#9 \(80\text{ ms}\) \(55\text{ ms}\) \(135\text{ ms}\) \(75 - 55 =\) \(20\text{ ms}\) \(155\text{ ms}\)
#10 \(90\text{ ms}\) \(51\text{ ms}\) \(141\text{ ms}\) \(75 - 51 =\) \(24\text{ ms}\) \(165\text{ ms}\)
  • 第(3)问:接收端缓存中的分组数 \(N(t)\) 随时间变化分段函数(到达 \(+1\),播放 \(-1\)):
  • \(0 \le t < 45\text{ ms}\):\(0\) 个
  • \(45 \le t < 60\text{ ms}\)(#1到):\(1\) 个
  • \(60 \le t < 70\text{ ms}\)(#2到):\(2\) 个
  • \(70 \le t < 73\text{ ms}\)(#5提前到):\(3\) 个
  • \(73 \le t < 75\text{ ms}\)(#3到):\(4\) 个
  • \(75 \le t < 76\text{ ms}\)(#1播放出队):\(3\) 个
  • \(76 \le t < 85\text{ ms}\)(#4到):\(4\) 个
  • \(85 \le t < 90\text{ ms}\)(#2播放出队):\(3\) 个
  • \(90 \le t < 95\text{ ms}\)(#6到):\(4\) 个
  • \(95 \le t < 105\text{ ms}\)(#3出队):\(3\) 个
  • \(105 \le t < 106\text{ ms}\)(#4出队):\(2\) 个
  • \(106 \le t < 115\text{ ms}\)(#7到):\(3\) 个
  • \(115 \le t < 119\text{ ms}\)(#5出队):\(2\) 个
  • \(119 \le t < 125\text{ ms}\)(#8到):\(3\) 个
  • \(125 \le t < 135\text{ ms}\)(#6出队):\(2\) 个
  • \(135 \le t < 141\text{ ms}\)(\(t=135\) 时 #9 到达同时 #7 出队,净增为 \(0\)):\(2\) 个
  • \(141 \le t < 145\text{ ms}\)(#10到):\(3\) 个
  • \(145 \le t < 155\text{ ms}\)(#8出队):\(2\) 个
  • \(155 \le t < 165\text{ ms}\)(#9出队):\(1\) 个
  • \(t \ge 165\text{ ms}\)(#10出队):\(0\) 个。

6. 8-20 先进先出(FIFO)、公平排队(FQ)与加权公平排队(WFQ)虚拟完结时间公式

  • FIFO:按到达时间 \(t_{\text{arr}}\) 排序,无流隔离。
  • FQ(逐字节公平排队,2025-选5 核心公式):设第 \(k\) 个队列的第 \(i\) 个分组长度为 \(L_i\),到达时刻为 \(R_i\),则该分组的虚拟完结轮次 \(F_i\) 为: \(F_i = \max\big(F_{i-1},\ R_i\big) + L_i\) 每次从所有非空队列中选择 \(F_i\) 最小的分组优先发送。

  • WFQ(加权公平排队):引入队列权重 \(w_k\),将虚拟完结时间修正为: \(F_i = \max\big(F_{i-1},\ R_i\big) + \frac{L_i}{w_k}\)


7. 8-33 IP 电话(VoIP)多层首部封装后的数据率与开销增长百分比计算

  • 已知条件:发送方每秒产生 \(8000\text{ B}\) 话音数据。每隔 \(20\text{ ms}\) 把得到的数据块加上 RTP 首部(无选项,固定 \(12\text{ B}\))和 UDP 首部(固定 \(8\text{ B}\))后,交给 IP 层(固定首部 \(20\text{ B}\))发送。求发送 IP 数据报的数据率(\(\text{kbit/s}\))及比原始话音数据率增加了百分之多少?
  • 分步算式与答案:
  • 原始话音数据率 \(R_{\text{raw}}\): \(R_{\text{raw}} = 8000\text{ B/s} \times 8\text{ bit/B} = 64000\text{ bit/s} = \mathbf{64\text{ kbit/s}}\)
  • 每个分组的话音数据载荷与每秒分组数:
    • 每隔 \(20\text{ ms} = 0.02\text{ s}\) 封装 1 个分组,故每秒发送分组数 \(= \frac{1\text{ s}}{0.02\text{ s}} = \mathbf{50\text{ 个分组/秒}}\);
    • 每个分组携带的原始话音字节数 \(= 8000\text{ B/s} \times 0.02\text{ s} = \mathbf{160\text{ B}}\)。
  • 加上 RTP + UDP + IP 首部后的单个 IP 数据报总长度: \(\text{总长度} = 160\text{ B (话音)} + 12\text{ B (RTP首部)} + 8\text{ B (UDP首部)} + 20\text{ B (IP首部)} = \mathbf{200\text{ B}} = 1600\text{ bit}\)
  • 发送 IP 数据报的数据率 \(R_{\text{IP}}\): \(R_{\text{IP}} = 50\text{ 个/s} \times 1600\text{ bit/个} = 80000\text{ bit/s} = \mathbf{80\text{ kbit/s}}\)
  • 数据率增加的百分比: \(\eta = \frac{80\text{ kbit/s} - 64\text{ kbit/s}}{64\text{ kbit/s}} \times 100\% = \frac{40\text{ B (首部)}}{160\text{ B (数据)}} \times 100\% = \mathbf{25\%}\)

8. 8-36 流媒体播放器缓存抽空(暂停)与注满时间计算(必会追及/水池问题!)

  • 已知条件:客户机应用程序缓存最大容量 \(B_{\max} = 100\text{ Mbit}\)。当缓存内数据达到启动阈值 \(B_{\text{start}} = 30\text{ Mbit}\) 时,播放器开始以 \(R_{\text{out}} = 3\text{ Mbit/s}\) 的速率读取数据播放视频。
  • 两问分步算式与答案:
  • (1) 当输入速率 \(R_{\text{in}} = 2\text{ Mbit/s} < R_{\text{out}} = 3\text{ Mbit/s}\) 时:
    • 播放多久后暂停(缓存被抽空):从存有 \(30\text{ Mbit}\) 开始播放,一边以 \(2\text{ Mbit/s}\) 往里注水,一边以 \(3\text{ Mbit/s}\) 往外放水,净消耗速率为 \(R_{\text{out}} - R_{\text{in}} = 3 - 2 = 1\text{ Mbit/s}\)。故把 \(30\text{ Mbit}\) 存量全部抽空所需播放时间为: \(t_{\text{play}} = \frac{30\text{ Mbit}}{3\text{ Mbit/s} - 2\text{ Mbit/s}} = \mathbf{30\text{ s}}\)
    • 暂停多久后才能继续播放:暂停期间播放器停止读取(\(R_{\text{out}} = 0\)),TCP 继续以 \(R_{\text{in}} = 2\text{ Mbit/s}\) 向缓存注入数据,直到重新积攒够启动阈值 \(30\text{ Mbit}\) 时恢复播放,故暂停时间为: \(t_{\text{pause}} = \frac{30\text{ Mbit}}{2\text{ Mbit/s}} = \mathbf{15\text{ s}}\)
  • (2) 当输入速率改为 \(R_{\text{in}} = 4\text{ Mbit/s} > R_{\text{out}} = 3\text{ Mbit/s}\) 时(求从开始传数据到 \(100\text{ Mbit}\) 缓存完全存满的总时间):
    • 第一阶段(从 \(0\) 充到 \(30\text{ Mbit}\) 播放器启动前,只进不出): \(t_1 = \frac{30\text{ Mbit}}{4\text{ Mbit/s}} = \mathbf{7.5\text{ s}}\)
    • 第二阶段(从 \(30\text{ Mbit}\) 充到存满 \(100\text{ Mbit}\),边进边播,净注入速率为 \(4 - 3 = 1\text{ Mbit/s}\)): \(t_2 = \frac{100\text{ Mbit} - 30\text{ Mbit}}{4\text{ Mbit/s} - 3\text{ Mbit/s}} = \frac{70\text{ Mbit}}{1\text{ Mbit/s}} = \mathbf{70\text{ s}}\)
    • 总共花费时间: \(T_{\text{total}} = t_1 + t_2 = 7.5\text{ s} + 70\text{ s} = \mathbf{77.5\text{ s}}\)

三、 第9章《无线网络和移动网络》第三类题(共 2 题,P443)

9. 9-13 CSMA/CA 退避计时器冻结(Freezing)剩余时间计算模型

  • 定量规则:设站点 A 抽取的初始退避时间为 \(T_{\text{backoff}} = 10\) 个时隙。当倒计时进行了 \(t_1 = 3\) 个时隙后检测到信道变忙(站点 B 开始发送帧耗时 \(T_B\)),此时 A 的退避计时器立即冻结在剩余值 \(10 - 3 = 7\) 个时隙。
  • 待 B 发送完毕且收到 ACK、信道重新空闲并等待完一个 \(\text{DIFS}\) 后,A 直接从剩余的 \(7\) 个时隙继续倒计时(而非重抽或回退到 10),从而保证先等待的站点比后加入的站点剩余时隙更少、优先获得信道。

10. 9-15 802.11 MAC 帧首部中四地址字段(地址 1 ~ 地址 4)精确填写表

  • 题目要点:用具体例子说明 802.11 MAC 帧首部中“地址 3”的作用,并掌握有固定基础设施(经 AP 转发)时的地址填写规则。
  • 完整填写公式表(必背铁律:地址1 = 无线直接接收方 RA,地址2 = 无线直接发送方 TA):
帧传输方向 去往AP
To DS
来自AP
From DS
地址 1
(无线直接接收端)
地址 2
(无线直接发送端)
地址 3
(起关键桥梁作用!)
地址 4
(仅无线分布式系统WDS用)
移动站 \(A \to\) 接入点 \(\text{AP}\)
(欲发往路由器 \(R\))
1 0 \(\text{AP}\) 的 MAC
(BSSID)
源站 \(A\) 的 MAC 目的端(或路由器 \(R\) 接口)的 MAC 不用
接入点 \(\text{AP} \to\) 移动站 \(A\)
(由路由器 \(R\) 发来)
0 1 目的站 \(A\) 的 MAC \(\text{AP}\) 的 MAC
(BSSID)
源端(或路由器 \(R\) 接口)的 MAC 不用
  • 具体实例说明(图 9-21 场景:路由器 \(R\) 向无线站点 \(A\) 发送数据):
  • 在有线以太网段(\(R \to \text{AP}\))传输的是 802.3 帧:目的地址 = \(A\) 的 MAC,源地址 = \(R\) 的 MAC。
  • \(\text{AP}\) 收到后将其转换为 802.11 无线帧发给 \(A\)(此时 To DS = 0, From DS = 1):其中 地址 1 填接收站 \(A\) 的 MAC,地址 2 填发送端 \(\text{AP}\) 的 MAC;若没有 地址 3 填入路由器 \(R\) 的 MAC 地址,移动站 \(A\) 收到该帧后将只知道是 \(\text{AP}\) 转发来的,而无法得知该帧在局域网中的原始发送方是路由器 \(R\)(同理,当 \(A\) 发帧经 \(\text{AP}\) 给路由器 \(R\) 时,\(\text{AP}\) 必须依靠读取 地址 3 才能知道把转换后的 802.3 有线帧发往哪个目的 MAC 地址)!