Computer Network
Computer Network
Curriculm
教材：自顶向下
这是我在中文互联网目前见到的质量最高的有关计算机网络的中文课程，没有之一
而且我认为对于这种知识点密集的课程，听母语课程会比对着半生不熟的英文课程的效果要好一些
老师目前把课程公开在了B站和MOOC
好的大学
没有围墙
- @中科大-郑烇
计算机网络的知识太多太杂，体系庞大，不好记录
看心情写不写这个了
Index
Chapter 1
1.1
- R1
1 | |
- R2
1 | |
- R3
1 | |
1.2
- R4
1 | |
- R5
1 | |
- R6
1 | |
- R7
1 | |
- R8
1 | |
- R9
1 | |
- R10
1 | |
| 特性 | Wi-Fi | 4G LTE | 5G |
|---|---|---|---|
| 覆盖范围 | 短距离（几十米到几百米） | 广泛（城市、乡村） | 广泛（城市为主，逐步扩展） |
| 速度 | 几百 Mbps - 1 Gbps | 100 Mbps - 1 Gbps | 1 Gbps - 10 Gbps |
| 成本 | 低（路由器或宽带费用） | 较高（SIM 卡和数据套餐） | 较高（5G 套餐） |
| 移动性 | 低（固定或低速移动） | 高（支持高速移动） | 极高（支持超高速移动） |
| 延迟 | 较低 | 较低 | 极低（1 毫秒以下） |
| 适用场景 | 家庭、办公室、公共场所 | 移动设备、偏远地区 | 超高速移动、实时应用、物联网 |
1.3
- R11
$$
\frac{L}{R_1} + \frac{L}{R_2}
$$
- R12
| 特性 | 电路交换网络 | 分组交换网络 |
|---|---|---|
| 带宽分配 | 固定带宽，专用于通信双方 | 动态分配，共享带宽 |
| 延迟 | 低，适合实时应用 | 较高，可能受拥塞影响 |
| 资源利用率 | 较低，带宽可能浪费 | 较高，资源共享 |
| 复杂性 | 简单，实现容易 | 复杂，需要路由和拥塞控制 |
| 适合场景 | 电话通话、视频会议 | 数据传输、网页浏览 |
| 成本 | 较高，需要专用资源 | 较低，资源共享 |
- TDM vs FDM
| 特性 | TDM（时分复用） | FDM（频分复用） |
|---|---|---|
| 带宽分配方式 | 时间划分，时隙分配 | 频谱划分，频段分配 |
| 适合信号类型 | 数字信号 | 模拟信号 |
| 资源利用率 | 高效，避免浪费 | 较低，频段可能未充分利用 |
| 实现复杂性 | 简单，技术成熟 | 复杂，需要频谱管理 |
| 灵活性 | 高，可动态调整时隙 | 较低，频段固定 |
| 应用场景 | 数字通信、数据传输 | 广播、电视、无线通信 |
- R13
1 | |
- R14
1 | |
- R15
1 | |
1.4
- R16
1 | |
- R17
1 | |
- R18
1 | |
- R19
1 | |
- R20
1 | |
- R21
1 | |
1.5
- R22
1. 物理层（Physical Layer）
- 任务：
- 传输比特流（0 和 1）。
- 定义物理介质的电气、机械和功能特性（如电压、电缆类型）。
- 处理物理连接的建立和断开。
- 管理信号的调制和解调。
- 提供物理层错误检测（如奇偶校验）。
2. 数据链路层（Data Link Layer）
- 任务：
- 将比特流封装成帧（Frame）。
- 提供物理地址寻址（如 MAC 地址）。
- 进行错误检测和纠正（如 CRC 校验）。
- 管理链路访问（如 CSMA/CD 用于以太网）。
- 处理帧的同步和流量控制。
3. 网络层（Network Layer）
- 任务：
- 提供逻辑地址寻址（如 IP 地址）。
- 路由数据包（选择最佳路径）。
- 处理分组交换和拥塞控制。
- 进行分片和重组（当数据包超过 MTU 时）。
- 提供网络层错误检测和流量控制。
4. 传输层（Transport Layer）
- 任务：
- 提供端到端的通信（如 TCP 或 UDP）。
- 进行流量控制和拥塞控制。
- 提供可靠的数据传输（如 TCP 的确认机制）。
- 进行错误检测和恢复（如 TCP 的重传机制）。
- 处理分段的重组（如 TCP 的序号和确认号）。
5. 应用层（Application Layer）
- 任务：
- 提供用户接口（如 Web 浏览器、电子邮件客户端）。
- 处理应用层协议（如 HTTP、FTP、SMTP）。
- 进行数据加密和解密（如 SSL/TLS）。
- 提供会话管理和同步（如 RPC、RMI）。
- 处理数据格式化和语义（如 XML、JSON）。
任务是否由多个层次执行？
是的，某些任务可能由多个层次共同执行。例如：
-
错误检测：
- 物理层可能进行简单的奇偶校验。
- 数据链路层使用 CRC 进行更复杂的错误检测。
- 传输层（如 TCP）也进行错误检测和恢复。
-
流量控制：
- 数据链路层（如以太网）进行基本的流量控制。
- 传输层（如 TCP）进行更复杂的流量控制和拥塞控制。
-
地址寻址：
- 数据链路层使用 MAC 地址进行本地寻址。
- 网络层使用 IP 地址进行全局寻址。
总结
| 层次 | 任务 |
|---|---|
| 物理层 | 传输比特流、定义物理介质、管理物理连接、信号调制、错误检测 |
| 数据链路层 | 封装帧、MAC 地址寻址、错误检测、链路访问、流量控制 |
| 网络层 | IP 地址寻址、路由数据包、分组交换、分片重组、错误检测 |
| 传输层 | 端到端通信、流量控制、可靠传输、错误检测、分段重组 |
| 应用层 | 用户接口、应用协议、数据加密、会话管理、数据格式化 |
某些任务（如错误检测和流量控制）可能由多个层次共同执行。
- R23
- 重要!
1 | |
- R24
1 | |
- R25
1 | |
- R26
1 | |
- R27
1 | |
- R28
1 | |
习题1
- P1
| Msg name | purpose |
|---|---|
| HELO |
Let server know that there is a card in the ATM machine . ATM card transmits user ID to Server |
| PASSWD |
User enters PIN, which is sent to server . BALANCE User requests balance |
| WITHDRAWL |
User asks to withdraw money . BYE user all done |
从服务器至ATM机器的信息（显示）
| Msg name | purpose |
|---|---|
| PASSWD | Ask user for PIN (password) |
| OK | last requested operation (PASSWD, WITHDRAWL) OK |
| ERR | last requested operation (PASSWD, WITHDRAWL) in ERROR |
| AMOUNT |
sent in response to BALANCE request |
| BYE | user done, display welcome screen at ATM |
正确回应：
| client | server |
|---|---|
| HELO (userid) | --------------> (check if valid userid) |
| <------------- PASSWD | |
| PASSWD |
--------------> (check password) |
| <------------- OK (password is OK) | |
| BALANCE | --------------> |
| <------------- AMOUNT |
|
| WITHDRAWL |
--------------> check if enough $ to cover withdrawl |
| <------------- OK | |
| ATM dispenses $ | |
| BYE | --------------> |
| <------------- BYE |
钱不够的情况下：
| client | server |
|---|---|
| HELO (userid) | --------------> (check if valid userid) |
| <------------- PASSWD | |
| PASSWD |
--------------> (check password) |
| <------------- OK (password is OK) | |
| BALANCE | --------------> |
| <------------- AMOUNT |
|
| WITHDRAWL |
--------------> check if enough $ to cover |
| withdrawl | |
| <------------- ERR (not enough funds) | |
| error msg displayed | |
| no $ given out | |
| BYE | --------------> |
| <------------- BYE |
- P2
$$
t_{0}=N\frac{L}{R}
$$
$$
t_{1}=(P-1)\frac{L}{R}
$$
$$
t_{总}=t_{0}+t_{1}=(P+N-1)\frac{L}{R}
$$ - P3
1 | |
- P5
1 | |
- P6
1 | |
- P7
1 | |
- P8
1 | |
c. $$\binom{120}{n}p^n(1-p)^{120-n}$$
d. $$1-\sum_{n=0}^{20}\binom{120}{n}p^n(1-p)^{120-n}$$
$$根据中心极限定理：令X_j为独立随机变量P(X_j=1)=p ；$$
$$P(21或更多用户)=1−P(\sum_{j=1}^{120}X_j≤21)$$
$$P(\sum_{j=1}^{120}X_j≤21)=P\left ( \frac{\sum_{j=1}^{120}X_j-12}{\sqrt{120\cdot 0.1\cdot0.9}}\leq \frac{9}{\sqrt{120\cdot 0.1\cdot0.9}} \right )≈P(Z≤9/3.2869)=P(Z≤2.74)=0.997$$
$$因此 P(21或更多用户)≈0.003$$
$$这公式真有人背吗，不都是查表吗$$
- P9
$$a. \frac{1Gpbs}{1Mpbs}=10^4$$
$$b. \sum_{n=N+1}^{M}\binom{M}{n}p^n(1-p)^{M-n}$$ - P10
1 | |
- P11
$$d_{end2end}=L/R+d_1/s_1+d_2/s_2+d_3/s_3$$
$$D=D_{prop}+L/R=20+16+4+6=46ms$$ - P12
1 | |
- P13
1 | |
- P14
$$a.传输延迟为L/R。总延迟是\frac{IL}{R(1-I)}+\frac{L}{R}=\frac{\frac{L}{R}}{1-I}$$
$$ b.以 L/R 为函数：$$
$$令 x = L/R： L/R(1-I) = x/(1-ax)$$
$$函数经过原点，在 x = 1/a 处趋于无穷$$
- P15
$$μ=\frac{R}{L} 所以 \frac{L}{1-I}R=\frac{1}{μ-a}$$ - P16
1 | |
- P17
$$a.有Q节点(源主机和Q-1路由器)。设d_{proc}^{q}表示q节点处的处理延迟。设R^q为第q个链路的传输速率，则$$
$$d_{proc}^{q}=L/R^q。$$
$$设d_{prop}^{q}是穿越q个链路的传播延迟。然后d_{end-end}=\sum_{q=1}^{Q}\begin{bmatrix}
d_{proc}^{q}+d_{trans}^{q}+d_{prop}^{q}
\end{bmatrix}$$
$$b.设d_{queue}^{q}是结点q的排队延迟。那么$$
$$d_{end-end}=\sum_{q=1}^{Q}\begin{bmatrix}
d_{proc}^{q}+d_{trans}^{q}+d_{prop}^{q}+d_{queue}^{q}
\end{bmatrix}$$
- P18
Tracing route to www.targethost.com [104.21.112.1]
over a maximum of 30 hops:
| 跳数 | IP 地址 | RTT 1 (ms) | RTT 2 (ms) | RTT 3 (ms) | 备注 |
|---|---|---|---|---|---|
| 1 | * | * | * | * | 请求超时 |
| 2 | 192.168.. | 2 | 1 | 2 | 本地路由器 |
| 3 | 119.39.. | 6 | 5 | 15 | 本地 ISP 路由器 |
| 4 | 119.39.. | * | 5 | 5 | 本地 ISP 路由器 |
| 5 | 119.39.. | 6 | 5 | 6 | 本地 ISP 路由器 |
| 6 | 219.158.. | 15 | * | 16 | 主干 ISP 路由器 |
| 7 | 219.158.. | 18 | 24 | 21 | 主干 ISP 路由器 |
| 8 | 219.158.. | 24 | 22 | 23 | 主干 ISP 路由器 |
| 9 | 219.158.. | 246 | 246 | 247 | 主干 ISP 路由器 |
| 10 | 219.158.. | * | 244 | * | 主干 ISP 路由器 |
| 11 | 141.101.72.27 | 240 | 240 | 244 | 目标主机所在网络的路由器 |
| 12 | 104.21.112.1 | * | 171 | 171 | 目标主机 |
Tracing route to a.w.bilicdn1.com [112.83.140.12]
over a maximum of 30 hops:
| 跳数 | IP 地址 | RTT 1 (ms) | RTT 2 (ms) | RTT 3 (ms) | 备注 |
|---|---|---|---|---|---|
| 1 | 172.19.. | * | 12 | * | 本地网络设备 |
| 2 | 192.168.. | 3 | 12 | 4 | 本地路由器 |
| 3 | 119.39.. | 4 | 4 | 4 | 本地 ISP 路由器 |
| 4 | 119.39.. | 5 | 3 | 5 | 本地 ISP 路由器 |
| 5 | * | * | * | * | 请求超时 |
| 6 | 219.158.. | 21 | 22 | 23 | 主干 ISP 路由器 |
| 7 | 58.241.. | 26 | 44 | 27 | 主干 ISP 路由器 |
| 8 | * | * | * | * | 请求超时 |
| 9 | * | * | * | * | 请求超时 |
| 10 | * | * | * | * | 请求超时 |
| 11 | * | * | * | * | 请求超时 |
| 12 | * | * | * | * | 请求超时 |
| 13 | 112.83.140.12 | 23 | 24 | 32 | 目标主机所在网络的路由器 |
Tracing route to anfsity.top [76.76.21.21]
over a maximum of 30 hops:
| 跳数 | IP 地址 | RTT 1 (ms) | RTT 2 (ms) | RTT 3 (ms) | 备注 |
|---|---|---|---|---|---|
| 1 | * | * | * | * | 请求超时 |
| 2 | 192.168.. | 2 | 2 | 2 | 本地路由器 |
| 3 | 119.39.. | 9 | 8 | 6 | 本地 ISP 路由器 |
| 4 | 119.39.. | 11 | * | 9 | 本地 ISP 路由器 |
| 5 | * | * | * | * | 请求超时 |
| 6 | 219.158.. | 18 | 15 | 14 | 主干 ISP 路由器 |
| 7 | 219.158.. | 17 | 14 | 15 | 主干 ISP 路由器 |
| 8 | 219.158.. | 23 | 23 | 22 | 主干 ISP 路由器 |
| 9 | 219.158.. | 58 | 55 | 54 | 主干 ISP 路由器 |
| 10 | 219.158.. | 71 | 75 | 61 | 主干 ISP 路由器 |
| 11 | * | * | * | * | 请求超时 |
| 12 | * | * | * | * | 请求超时 |
| 13 | * | * | * | * | 请求超时 |
| 14 | * | * | * | * | 请求超时 |
| 15 | * | * | * | * | 请求超时 |
| 16 | * | * | * | * | 请求超时 |
| 17 | 76.76.21.21 | 55 | 54 | 54 | 目标主机 |
| 还是挺有意思的 |
- P19
1 | |
- P20
$$ \min(R_s, R_c, R/M) $$
- P21
$$max ( min(R_{1}^{1},R_2^1,…,R_N^1),min(R_1^2,R_2^2,…,R_N^2),…,min(R_1^M,R_2^M,…R_M^M))$$
$$使用 M 条：\sum_{k=1}^{M}min(R_1^k,R_2^k,…,R_N^k)$$
- P22
不丢包概率为 1 - p， N 个路由器， 因此总的不丢包概率$$p_s=(1−p)^N$$
$$在客户端成功接收数据包之前需要执行的传输数是具有成功概率p_s的几何随机变量。因此，所需传输的平均次数为：1/p_s。然后，所需重传的平均次数为：1/p_s-1。$$
- P23
a.$$L/R_s$$
b.可能，因为第二个分组 (用 P2 表示) 可能在第一个分组 (P1) 被推出之前到达；
P1 被完全推出的时间 $$t_1 = L/R_s + L/R_c + d_{prop}$$
P2 到达路由器的时间 $$t_2 = 2L/R_s + d_{prop} + T$$
要求t2 > t1:即 $$T > L/R_c - L/R_s$$
因此T至少是$$L/R_c - L/R_s$$
- P24
1 | |
- P25
$$a.t_{prop} = 20000km / 2.5*10^8m/s = 0.08s$$
$$R * t_{prop} = 1.6 * 10^5 bits$$
$$b.1.6 * 10^5 bits 见c$$
$$c.链路上的最大比特数量$$
$$d.20000km / 1.6*10^5 = 125m这比足球场长(正规足球场场地：长105米、宽68米)$$
$$e.s/R $$
- P26
1 | |
- P27
$$ \ a. R * d_{prop} = 8 * 10^7 bits$$
$$b. \ 8 * 10^5 bits$$
$$c. \ s/R = 0.25m$$
- P28
a.$$t_{trans} + t_{prop} = 0.48s$$
b.$$20*(t_{trans}+t_{prop})=20*(0.02+0.08)s=2s$$
c.分解一个文件需要更长的时间来传输，因为每个数据包及其相应的确认包都会添加它们自己的传播延迟。
- P29
a. $$d_{prop} = 36000km / (2.4 \times 10^8) = 0.15s$$
b.$$
R \times d_{prop} = 10 \ \text{Mbps} \times 0.15 \ \text{s} = 1.5 \times 10^6 \ \text{bits}
$$
c. $$60s \times 10Mbps = 6 \times 10^8 bits$$
- P30
1 | |
- P31
1 | |
- P33
$$有F/S包。每个包S=80位。在第一路由器接收最后一个数据包的时间是\frac{S+80}{R}\times \frac{F}{S}秒。$$ $$此时，第一个F/S-2分组位于目的地，F/S-1分组位于第二路由器。$$$$最后一个数据包随后必须由第一个路由器和第二个路由器发送，每一个传输都需要\frac{S+80}{R}秒。$$ $$因此，发送整个文件的延迟为\frac{S+80}{R}\times (\frac{F}{S}+2)，以计算导致最小延迟的S值$$$$延迟为：\frac{\mathrm{d} }{\mathrm{d} x}delay=0 \Rightarrow S=\sqrt{40F}。$$
- p34
1 | |