计算机网络笔记 部分例题和知识点

发表于 更新于

学期初这个老师提到了往届学生对他不调分的政策的「好评如潮」, 然后他表示为了解决这个问题, 他决定在每章的 PPT 最后放上一些「有助于应试」的例题.

然后因为课程时间不够了九个章节他只有前三个章节放了例题, byd 还没我记笔记坚持的时间长.

概述#

网络层次模型#

名称 (Name) 主要功能 (What it does) 传输单位 (PDU) 关键协议/设备 (Keywords) 考试重点/人话解释
应用层
(Application)		 为应用程序提供网络服务接口. 用户直接打交道的一层. 报文 (Message) HTTP/HTTPS, FTP, SMTP, DNS, Telnet 点外卖.
你要发邮件, 看网页, 就在这一层.
表示层
(Presentation)		 数据格式化, 加密解密, 压缩解压. 确保一个系统的应用层发送的数据能被另一个系统读取. 数据 (Data) ASCII, JPEG, MPEG, SSL/TLS 打包/翻译.
把你的中文翻译成英语, 或者把文件压缩打包, 加密.
会话层
(Session)		 建立, 管理和终止会话. 控制两个通信应用之间的对话. 数据 (Data) RPC, SQL, NFS 打电话.
负责建立连接 (拨通), 保持连接 (通话), 断开连接 (挂机).
传输层
(Transport)		 提供端到端的可靠 (或不可靠) 传输. 负责流量控制, 差错控制. 区分进程 (端口号). 段 (Segment) - TCP
用户数据报 - UDP		 TCP (可靠), UDP (不可靠)
端口号 (Port)		 快递公司.
不管你怎么运, 反正我保证把货送到对方手里 (TCP), 或者扔过去就不管了 (UDP). **重点: 端口号在这里! **
网络层
(Network)		 逻辑寻址 (IP 地址) 和路由选择. 决定数据包从源到目的地的最佳路径. 包/分组 (Packet) IP, ICMP, ARP, OSPF, BGP
路由器 (Router)		 导航仪.
看地图, 查 IP 地址, 决定走哪条路 (路由) 能最快到达目的地. **重点: 路由器, IP 地址! **
数据链路层
(Data Link)		 物理寻址 (MAC 地址), 成帧, 差错检测. 在相邻节点间传输数据. 帧 (Frame) Ethernet (以太网), WiFi, PPP
交换机 (Switch), 网桥		 交警/路牌.
只负责如果你要从这个路口去下个路口怎么走. **重点: MAC 地址, 交换机, VLAN! **
物理层
(Physical)		 传输比特流. 定义电压, 接口形状, 线缆规格等物理特性. 比特 (Bit) 双绞线, 光纤, 集线器 (Hub), 中继器 修路的.
网线, 光缆, 电流信号 0 和 1. 不管内容, 只管发信号.
TCP/IP 层级 (4 层标准) 对应 OSI 层级 功能简述 核心协议 (背下来必考)
应用层
(Application)		 应用层
表示层
会话层		 处理特定的应用程序细节, 涵盖了 OSI 上三层的功能. HTTP (80), HTTPS (443), DNS (53), FTP (21), SMTP (25), SSH (22), DHCP
传输层
(Transport)		 传输层 提供端到端的数据传输服务. TCP (三次握手, 四次挥手, 可靠)
UDP (直播, 视频, 快但不靠谱)
互联网层
(Internet)		 网络层 处理分组在网络中的活动 (路由). IP (IPv4/IPv6), ICMP (Ping 命令用这个), ARP (IP 查 MAC), RARP
网络接口层
(Network Interface)		 数据链路层
物理层		 处理与电缆 (或其他传输介质) 的物理接口细节. Ethernet, Wi-Fi, 驱动程序

一个系统具有 n 层协议的层次结构. 应用层产生长度为 M 字节的消息, 在每一层加上长度为 h 字节的头. 头所占的网络带宽比例是多少?

看题干: nhM+nh\frac{nh}{M+nh}

考虑实际 OSI 模型: 物理层不加头, 题目「默认应用层的报头在消息长度内」, 所以是(n−2)hM+(n−2)h\frac{(n-2) h}{M+(n-2) h}

我觉得应用层到底有没有头这个问题非常唐, 实际考试建议直接问监考老师.

物理层#

傅里叶变换#

跑到哪都逃不掉傅里叶变换, 真的是阴魂不散.

计算函数 f(t)=t(0⩽t⩽1)f (t)=t \quad (0 \leqslant t \leqslant 1) 的傅里叶系数.

g(t)=12c+∑n=1∞ansin⁡(2πnft)+∑n=1∞bncos⁡(2πnft)g (t) = \frac{1}{2}c + \sum_{n=1}^\infty a_n \sin (2 \pi nft) + \sum_{n=1}^\infty b_n \cos (2 \pi nft)

f=1Tf = \frac{1}{T}: 基频

an,bna_n, b_n: n 次谐波 (Harmonics) Fourier 分量的正弦和余弦振幅

an=2T∫0Tg(t)sin⁡(2πnft)dta_n = \frac{2}{T} \int_0^T g (t)\sin (2\pi nft) dt

bn=2T∫0Tg(t)cos⁡(2πnft)dtb_n = \frac{2}{T} \int_0^T g (t)\cos (2\pi nft) dt

c=2T∫0Tg(t)dtc = \frac{2}{T}\int_0^Tg (t) dt

香浓公式和奈奎斯特公式#

香农公式: 考虑噪声的物理极限

C=B×log⁡2(1+S/N)C = B \times \log_2(1 + S/N)

奈奎斯特公式: 由编码方式决定的传输速率

C=2B×log⁡2(V)C = 2B \times \log_2(V)

在一条信噪比为 40dB40\text{dB} 的信道上发送一个 5GHz5\text{GHz} 的二进制信号, 最大数据速率的最低上界为多少? 解释你的答案.

CShannon=5×109×log⁡2(1+10,000)C_{\text{Shannon}} = 5 \times 10^9 \times \log_2(1 + 10,000)

CNyquist=2×B×log⁡2(2)C_{\text{Nyquist}} = 2 \times B \times \log_2(2)

答案 10Gbps.

每 1ms 对一条无噪声 3kHz 信道采样一次, 最大数据速率是多少? 如果信道上有
噪声, 且信噪比是 30dB, 最大数据速率将如何变化?

典中典之钓鱼题, 无噪声信道每个码元的信息量可以无限大, 因此最大数据速率无限大.

如果默认采用二进制信道, 每个码元信息量是 1bit, 速率 1000bps.

30dB 情况用香农定理即可.

CDMA 码分复用#

点乘一下, 为-1 是发送了 0, 为 1 是发送了 1, 为 0 是什么都没发.

这是为数不多我觉得我会了的内容之一, 所以我就不放例题了.

分组交换的延迟#

假定在一个数据包交换网络中用户数据长度为 x 位, 将以一系列数据包的形式沿
着一条 k 跳路径传输,每个数据包包含位数据和 h 位包头,这里 x>>p 十 h, 线路的比特率
为 b 位/秒,传播延迟忽略不计. 什么样的 p 值使得总延迟最小?

包越小 (pp 小): 头部的比例 (hh) 就越高, 浪费的带宽越多 (拆快递拆得累死).

包越大 (pp 大): 虽然头部比例小了, 但是因为是存储转发机制, 大包在每个路由器的等待转发时间变长了 (堵车).

总延迟的计算方法: 所有数据包的发送时间 + 最后一个数据包在路径上产生的延迟

数据总量: xx

每个包的数据量: pp

包的数量: N=⌈x/p⌉≈x/pN = \lceil x/p \rceil \approx x/p (因为 x≫px \gg p, 忽略向上取整的微小差异)

每个包的总长度: p+hp + h (数据+头)

单跳传输一个包的时间: tpacket=p+hbt_{packet} = \frac{p+h}{b}

T=源主机发送所有N个包的时间+最后一个包穿过剩余(k−1)跳的时间T = \text{源主机发送所有N个包的时间} + \text{最后一个包穿过剩余}(k-1)\text{跳的时间}

代入, 求导找极值点即可.

数据链路层#

检错码#

海明距离为 dd, 可以检测到所有长度为 d−1d-1 的错误, 纠正长度为 d−12\frac{d-1}{2} 的错误.

偶校验: 1 的个数是偶数. 奇校验同理.

数据 10101111, 偶校验, 求海明码.

4 个校验位, 分别在 1, 2, 4, 8, 结果为 101001001111.

接收方收到一个 12 位的奇校验和海明码, 其十六进制值为 0xB4D. 该码的原始值是多少? 假设至多发生了一位错.

二进制为 1011 0100 1101, 分别检查.

纠错码#

为了纠正所有的单个错误和两个错误, 需要在 mm 位消息上增加 rr 个冗余位, 请给出 rr 的下界公式.

码字总长度 n=m+rn = m + r, 总共有 2n2^n 种可能, 需要覆盖没有错 + 一位错 + 两位错的情况, 有:

2r≥1+(m+r)+(m+r)(m+r−1)22^r \ge 1 + (m+r) + \frac{(m+r)(m+r-1)}{2}

假设数据以块形式传输, 每块大小为 1000 比特. 在什么样的最大错误率下, 错误检测和重传机制 (每块 1 个校验位) 比使用海明码更好? 假设比特错误相互独立, 并且在重传过程中不会发生比特错误.

设出错率为 ee.

计算海明码的开销: 2r≥m+r+12^r \ge m + r + 1

r = 9 不中, r = 10 中嘞, 所以海明码固定开销 10bit.

检错重传开销: 出错率约为 1−(1−e)1000≈1000e1 - (1-e)^{1000} \approx 1000e

平均期望开销为 (1000e)×1000(1000e) \times 1000

比较即可.

校验和#

使用 Internet 校验和 (4 位字) 发送一条消息: 1001 1100 1010 0011, 校验和是什么?

二进制反码求和: 四位一组相加, 进位加到最后, 最后取反.

最后检验时加起来应该全是 1.

0011 + 1010 = 1101

1101 + 1100 = 1001 + 1 = 1010

1010 + 1001 = 0011 + 1 = 0100

取反: 1011.

停等协议#

考虑一个具有 4kb/s 速率和 20ms 传输延迟的信道, 帧的大小在什么范围内, 停-等式协议才能获得至少 50%的效率?

U信道利用率=T发送一帧需要的时间T发送一帧需要的时间+2×T传输时延U_{信道利用率} = \frac{T_{发送一帧需要的时间}}{T_{发送一帧需要的时间} + 2 \times T_{传输时延}}

乘 2 是因为发过去之后还要接收 ACK.

滑动窗口协议#

局域网与介质访问控制#

CSMA/CD#

试问在下列两种情况下 CSMA/CD 的竞争时间槽长度是多少?(1) 一个 2 千米长的双导电缆 (信号的传播速度是信号在真空中传播速度的 82%)?(2) 40 千米长的多模光纤 (信号的传播速度是信号在真空中传播速度的 65%)?

直接算传输时间然后乘 2 就可以了.

考虑建立一个 CSMA/CD 网络, 在 1km 的线缆上运行速度为 1Gb/s, 线缆中间没有中继器. 线缆上的信号速度为 200 000km/s. 最小帧长度是多少?

发送时间大于上一题算出来的争用期 (传播时间乘 2) 就可以了.

一个通过以太网传送的 IP 数据包长 60 字节, 其中包括所有的头. 如果没有使用 LLC,需要往以太网帧中填补字节吗?如果需要, 那么需要填补多少字节?

以太网的最小帧长是 64 字节.

但是这里要加上:

目的地址 (MAC): 6 字节
源地址 (MAC): 6 字节
类型 (Type): 2 字节
数据 (Payload/IP Packet): 60 字节 (题目给的)
FCS (校验尾): 4 字节

然后就够了, 不用填补.

考虑两个以太网网络: 在网络 A 中, 站通过全双工的线缆连接到集线器; 在网络 B 中, 站通过半双工的线缆连接到一台交换机. 对于这两个网络中的每一个, 为什么需要或者不需要 CSMA/CD?

如果是集线器 Hub, 一定需要 CSMA/CD;

如果是交换机 Nintendo Switch, 全双工线缆就不用, 半双工就用.

补充题: 描述 CSMA/CD 和 CSMA/CA 的基本原理.

我在这里坐了几个小时受不了了所以我直接上 AI 了.

1. CSMA/CD (用于有线以太网)

载波侦听, 冲突检测, 二进制指数退避算法.

  • 核心: 冲突检测.
  • 过程:
    1. 先听后发: 监听信道, 空闲才发送.
    2. 边发边听: 发送时继续监测电压.
    3. 冲突停发: 发现电压异常 (冲突), 立即停止发送并广播干扰信号.
    4. 随机重发: 等待一个随机时间 (二进制指数退避) 后再试.

2. CSMA/CA (用于无线 WiFi)

载波侦听, 冲突避免, 随机退避算法.

  • 核心: 冲突避免 (因为无线网无法做到「边发边听」).
  • 过程:
    1. 预约/等待: 监听到信道空闲, 也要先等待一段随机时间 (降低碰撞概率), 然后再发.
    2. ACK 确认: 发完数据后, 必须收到接收方的 ACK 确认帧.
    3. 重传: 如果没收到 ACK, 就默认为发生了冲突, 进行重传.
    4. RTS/CTS (可选): 发送前先发请求 (RTS), 对方同意 (CTS) 后再发, 解决隐蔽站问题.

补充题: 局域网内安装一台新的交换机, 简要说明其工作机理.

假设交换机是全新的, MAC 地址表为空. 当一个帧从端口进入时:

  1. 自学习 (记源地址):
    提取帧的 源 MAC 地址 和 进入的端口号, 记录到交换机的 MAC 地址表中.
  2. 转发决策 (查目的地址):
    查看帧的 目的 MAC 地址:
    • 情况 A (表中没有): 找不到目的地址, 进行泛洪(向除了入口之外的所有端口转发).
    • 情况 B (表中有): 查到了对应的端口, 进行精确转发(只发给那个端口).
    • 情况 C (在同一端口): 目的地址就在入口的网段内, 直接丢弃(不转发).
  3. 更新与老化:
    表中的记录有生存时间, 长时间不通信会自动删除.

网络层#

链路状态算法和距离矢量算法#

例题略, 因为我很懒.

漏桶算法和令牌桶算法#

一台计算机使用一个容量为 500MB 的令牌桶,速率为 5MB/s. 当该桶包含 300MB 时.计算机每秒产生 15MB 的数据. 请问它发送 1000MB 的数据要花多长时间?

数据到达速率 15MB/s, 令牌生成速率 5MB/s, 故令牌消耗速率为 10MB/s, 一开始令牌桶包含 300MB 令牌, 在 30s 时令牌消耗完毕, 此时一共发送了 15MB/s x 30s = 450MB 的数据, 剩下 550MB 的数据只能以 5MB/s 的速率发送完毕, 需要 110s 发送完成, 故总需 140s.

Internet 协议#

IP 分片#

假设主机 A 和路由器 R1 连接, R1 又与另一个路由器 R2 连接, R2 与主机 B 连接, 假定一个要发给主机 B 的 TCP 消息被传递给主机 A 的 IP 代码, 其中包含了 900 个字节的数据包和 20 个字节的 TCP 头. 请写出在三条链路上传输的每个数据包中 IP 头部的 Totallength, Identification, DF, MF, 和 Fragment Offset 字段. 假定链路 A-R1 链路可以支持的最大帧长为 1024 字节, 其中包括 14 字节的帧头; 链路 R1-R2 可以支持的最大帧长为 512 字节, 其中包括 8 字节的帧头; 链路 R2-B 可以支持的最大帧长为 512 字节, 其中包括 12 字节的帧头.

  • 原始 IP 数据报总长度 = 20 (IP 头) + 20 (TCP 头) + 900 (数据) = 940 字节.
  • 需要运输的净负荷 (Payload) = 20 (TCP 头) + 900 (数据) = 920 字节.
    IP 分片切的是这 920 字节.

MTU (最大传输单元, 即 IP 层能发出的最大包大小)

  • 链路 A-R1: 1024 - 14 = 1010 字节 (MTU)
  • 链路 R1-R2: 512 - 8 = 504 字节 (MTU)
  • 链路 R2-B: 512 - 12 = 500 字节 (MTU)

第一段链路: 主机 A -> 路由器 R1

  • 路况: MTU = 1010 字节.
  • 我们的车: 总长 940 字节.
  • 结论: 940 < 1010, 不用拆! 直接过.

填写字段:

  • Total Length (总长度): 940
  • Identification (ID): 随便给个号, 比如 666(同一个包的所有分片ID必须一样).
  • DF (Don't Fragment): 0 (允许分片).
  • MF (More Fragments): 0 (后面没有分片了).
  • Fragment Offset (片偏移): 0 (这是开头).

第二段链路: 路由器 R1 -> 路由器 R2 (重难点! )

  • 路况: MTU = 504 字节.
  • 我们的车: 940 字节.
  • 结论****: 940 > 504, 必须拆分!

MTU 是 504, 减去 20 字节 IP 头, 剩下 484 字节 给数据.
但是 IP 协议规定, 除了最后一片, 前面所有分片的数据长度必须是 8 字节的倍数.

  • 484 除以 8 = 60.5

  • 所以我们只能向下取整: 60×8=48060 \times 8 = 480.

  • **结论: 每个分片最多只能带 480 字节的数据. **

  • 第一片 (分片 1):

    • 装货: 480 字节.
    • 总长: 480 (数据) + 20 (IP 头) = 500 字节.
    • MF = 1 (后面还有货).
    • Offset = 0.

  • 第二片 (分片 2):

    • 剩多少货? 总货量 920 - 运走的 480 = 440 字节.
    • 440 + 20 (IP 头) = 460 字节. 这个长度小于 MTU (504), 能装下.
    • 总长: 460 字节.
    • MF = 0 (这是最后一片了).
    • Offset = 480/8=60480 / 8 = 60 (片偏移的单位是 8 字节, 所以填 60).

第三段链路: 路由器 R2 -> 主机 B

  • 路况: MTU = 500 字节.
  • 来的车: R1 发过来的两个分片.
    • 分片 1: 总长 500 字节.
    • 分片 2: 总长 460 字节.
  • 结论:
    • 分片 1: 500 <= 500, 刚好能过, 不用再拆.
    • 分片2: 460 <= 500, 能过, 不用再拆.
    • 所以, R2 这一站没有发生新的分片, 原样转发.

假设 Identification (ID) 设为 x (比如 100), 最终答案:

链路 包序号 Total Length (总长) ID (标识) DF MF Fragment Offset (偏移)
A -> R1 原始包 940 x 0 0 0
R1 -> R2 分片 1 500 x 0 1 0
(发生分片) 分片 2 460 x 0 0 60
R2 -> B 分片 1 500 x 0 1 0
(透传) 分片 2 460 x 0 0 60

注意点:

  1. Offset 怎么算? ** 是用前面的数据量**除以 8. 比如第二片的 Offset 是 480/8=60480 / 8 = 60.
  2. 数据要对齐 8 字节: 虽然 MTU 允许带 484 字节数据, 但必须砍掉 4 字节变成 480.
  3. Total Length 包含头: 填表的时候, 长度一定要加上 20 字节的 IP 头.
  4. **R2-B 为什么没分片? ** 因为 R1 分好的片 (500 字节) 刚好等于 R2-B 的 MTU (500 字节). 如果有哪怕多出 1 个字节, 就要再次分片.

IP 地址#

Internet 上一个网络的子网掩码为 255.255.240.0. 试问它最多能容纳多少主机.

全 0 全 1 不使用, 212−22^{12}-2.

从 198.16.0.0 开始有大量连续的 IP 地址可以使用. 假设 4 个组织 A, B, C, D 按照顺序依次申请 4000, 2000, 4000, 和 8000 个地址. 对于每一个申请, 请用 w.x.y.z/s 的形式写出所分配的第一个 IP 地址, 最后一个 IP 地址以及掩码.

这里有一个错位问题, 原理我没怎么搞明白, 马上考试了我也没空搞明白了.

A: 198.16.0.0-198.16.15.255 written as 198.16.0.0/20
B: 198.16.16.0 -198.16.23.255 writtenas 198.16.16.0/21
C:198.16.32.0 -198.16.47.255 writtenas 198.16.32.0/20
D: 198.16.64.0 -198.16.95.255 writtenas 198.16.64.0/19

一个路由器刚刚接收到以下新的 IP 地址:57.6.96.0/21,57.6.104.0/21,57.6.112.0/21 和 57.6.120.0./21. 如果所有这些地址都使用同一条出境线路, 试问它们可以被聚合吗?如果可以, 将被聚合到哪个地址上?

聚合地址为 57.6.96.0/19.

转成二进制找最长前缀.

传输层#

TCP 五元组#

<源/目的IP地址, 源/目的端口号, 协议>

慢启动算法#

考虑在一条往返时间为 10 毫秒的无拥塞线路上使用慢速启动算法的效果. 接收窗口为 24KB, 最大段长为 2KB. 试问需要多长时间才能首次发送满窗口的数据?

0ms-2KB;10ms-4KB;20ms-8KB;30ms-16KB,40ms-min (32KB, 24KB)

假设 TCP 的拥塞窗口被设置为 18KB, 并且发生了超时. 如果接下来的 4 次突发传输全部成功, 试问拥塞窗口将达到多大?假设最大段长为 1KB.

由于超时, 所以接下来的第一次突发还是 1K, 到第四次即为 8K.

考虑一个使用 TCP Reno 的连接. 该连接的初始拥塞窗口大小为 1KB, 初始的阈值是 64. 假设加法递增使用了一个 1KB 的步进大小. 如果最初一轮传输称为第 0 轮, 那么, 在第 8 轮传输中, 拥塞窗口的大小是多少?

66KB.

如果 TCP 往返时间 RTT 的当前值是 30 毫秒, 紧接着分别在 26, 32, 24 毫秒确认到达, 那么, 若使用 Jacobson 算法, 试问新的 RTT 估计值为多少? a=0.9.

image-20260112235928393

一台 TCP 主机正在通过一跳 1Gb/s 的信道发送满窗口的 65535 字节数据, 该信道的单向延迟为 10ms,可以达到的最大吞吐量是多少? 线路的效率是多少?

RTT 为 20ms,因此理论上每秒可以发送 50 个窗口的数据. 最后算出来是 2.6%.