«计算机网络»笔记：第9章重点小梳理

缩写大全

CS 代表载波监听（Carrier Sense）

MA 代表多点接入（多路访问）（Multiple Access，用这个的肯定是总线型）

CD 代表冲突检测（Collision Detection）

ALOHA：一种带 ACK 的早期 MA 协议。

CSMA/CD：发送时检测冲突，一旦发现冲突就停止发送。

MACA：~~一种南美洲萝卜。~~ CA 代表冲突避免

DVR：距离向量路由

RIP：路由信息协议，基于 DVR

LSP：链路状态路由，当收到了所有节点的 LSP，计算出以自己为根的最短路径树，构造出路由表。用于 ISIS 和 OSPF。

VSLM：可变长子网掩码，扩展网络号的位数的技术

CIDR：无分类域间路由，取消 IP 地址的分类

英文术语

简单的就略过了。

英文	翻译
time slot	时隙
additive	加法的，累计的
aggregate	合计，聚合
amplitude modulation	调幅
bidirectional	双向的
blast out	输出
chop up	切分
congestion	拥塞
consecutive	连续的
constellation	星座
contention slot	竞争时槽
convergence	收敛
negligible	可忽略的
optical fiber	光纤
piggyback	捎带确认
redundancy	冗余信息

QoS 指标

带宽/吞吐量
时延
抖动（时延导数）
丢包率
误码率

平均传输次数的计算

例：假设错误率是 $p$，通过请求重传处理差错，求正确发送一帧的平均传输次数?

解：

$$ \sum_{k=1}^{\infty}k(1-p)p^{k-1}=\frac{1}{1-p}=\dfrac{1}{s} $$

其中 $s$ 是成功率

例：一个分组被分为 10 帧，每帧成功达到率是 0.8，如果没有差错控制，平均传多少次交付？

解：全部成功的概率：$0.8^{10}=0.107$

平均传输次数：$1/(0.107)=9.3$

信道有效带宽的计算

最高频率与最低频率之差

数据传输速率的计算

例：一个 8kHz 的无噪声信道每毫秒采样 1 次，最大数据率是多少？

解：采样频率 1000Hz，信号速率是 1000 Baud

例：信噪比 20dB，3kHz 信道，二进制数据。最大数据率是多少？

信噪比分贝形式和功率形式的转换：

$\operatorname{SNR}=10\log_{10}(S/N)$

解：根据香农定理，$R_m=3\times 10^3 \log_2(1+S/N)$. 另有 $20=10 \log_{10}(S/N)$，解得 $S/N=100$,因此 $R_m=19.975 \text{kbps}$

根据采样定理，$R_m = 2B \log_2L=6\text{kbps}$

二者取较小值，是 $6\text{kbps}$

信道星座图怎么看

将信号连接到极坐标原点，同一轴向不同半径代表不同幅值。不同轴向代表不同相位。

（a）有四个不同相位信号，四个级别的信号

（b）QAM-16 有 12 级相位，三种级别的赋值，构成 16 级的信号

（c）QAM-64 有 64 级的信号

转义/填充总结

PPP

识别 06 7E 25 7D 5E 16 7D 5D 7E A8 FF 中 PPP 帧的内容。（不含首尾标志）

PPP 协议采用字节填充

编码：

分割使用 7E

7E 转义为 7D 5E

7D 转义为 7D 5D

解：06 7E 25 7D 5E 16 7D 5D 7E A8 FF 中 PPP 帧为：

25 7D 5E 16 7D 5D，反转义为：25 7e 16 7d

汉明码的编码和校验

详情见计组或前面章节。

$m+r+1 \leq 2^r$，m 为信息位，r 为检查位。

小练习：计算合适的校验位：

0101 0011
1101
1111 1
1010 101

CRC 校验

见计组或前面章节。

带宽时延积、信道利用率计算

GBN

最大发送窗口：$W=2^n-1$，利用率 $W/(1+2a)$，$a=t_\text{trans}/t_\text{send}$

SR：

$W_t + W_r \leq 2^n$ 利用率 $W/(2+2\alpha)$ 利用率最高要求 $W\geq 2+2\alpha$

例子：一条 3000 公里长的 T1 中继线路使用协议 5 来传输 64 字节长的数据帧。如果传播速度为 6 微妙/公里，需要多少位序列号？

分析：

$$ W = 2^n-1\geq 1+2\alpha = 1+2(t_p/t_s) = 1+2\frac{ 3\cdot6 }{ 64\cdot 8 / 1536 }=109\\ n\geq \lceil\log_2(110)\rceil=7 $$

最小帧长、竞争时隙计算

竞争时隙：就是传播时延x2

最小帧长：竞争时隙x通信速率

距离矢量路由算法

X 地址有多少个

问：B 类地址有多少个网络？

B 类地址使用前 2x8=16 bit

前缀用掉两bit，所以有 $2^{16-2}= 2^{14} = 个$

每个网络的主机数为剩余位数-1，例如 B 类网络剩余 16bit，网络数 65,534

掩码下的主机数

$$ 2^{z}-2 $$

其中 $z$ 为掩码中0的个数，减去2，是减去 x.x.x.0 的网络地址和 255.255.255.255 的广播地址

IP 地址分配

A large number of consecutive IP addresses are available starting at 198.16.0.0. Suppose that four organizations, A, B, C, and D, request 4000, 2000, 4000, and 8000 addresses, respectively, and in that order. For each of these, give the first IP address assigned, the last IP address assigned, and the mask in the w.x.y.z/s notation.

$$ 4000 < 4096 = 2^{12}\\ 2000 < 2048 = 2^{11}\\ 8000 < 8192 = 2^{13} $$

0000 0000 A 		0
0001 0000 A_MAX+1 	16		// A+= 2^12
0001 0000 B			16
0001 1000 B_MAX+1	24
0010 0000 C 		32
0011 0000 C_MAX+1	48
0100 0000 D 		64
0110 0000 D 		96

分配如下：

A: 198.16.0.0/20
B: 198.16.16.0/21
C: 198.16.32.0/20
D: 198.16.64.0/19

IP 包分片的计算

分片规则： 选择最接近MTU的8倍数的八位组。

【例子】 链路 MTU=512B，链路帧头 8B. 传送头部 20B 数据 900B 的 TCP 报文。计算分片情况。（假定IP 头部 20B）

【分析与解答】

首先计算真实传输的数据长度。TCP 报文整体作为 IP 的 Payload 传输，数据大小 900+20=920B.

再看链路的最大支持长度。512-8=504B.

显然这是要分两个分组。分组数据长：504-20=484，484/8=60.5 只能向下取整，60 作为第二分片的 OFFSET。分组实际数据长 60*8=480B. 分组包头 20B.

因此

分组 1：LEN=480+20=500B, DF=0, MF=1, OFF=0 分组 2：LEN=920-480+20=460B, DF=0, MF=1, OFF=60

注意 DF=1 不代表未分组，而是代表告诉接下来的链路都不要分组！一般是不能设为 1 的！

路由聚合划分问题

IP 29.18.0.0 to 29.18.127.255 聚合到 29.18.0.0/17。结果现在有 29.18.60.0 to 29.18.63.255 要从另一条线出。要不要重新划分聚合？

【分析与解答】 首先 29.18.0.0/17 的范围是 29.18.0.0~29.18.127.255，显然与新来的有交叉。但是新来的可以表示为：29.18.48.0/20，比 17 的范围要小，只需要单独添加这一条规则，利用最长匹配即可。

不同层的数据传输单元（PDU）叫法

报文（message）：应用层。你的网页源码。

报文段，数据段（segment）：传输层。你的网页源码太长了，被分成一系列分片（segment）。TCP 包头+数据。

分组（packet）：又叫数据包，网络层的 PDU。

数据报（datagram）：无连接的 PDU。

帧（frame）：数据链路层的 PDU。

数据位（bit）：梳理曾的 PDU。

（吐槽一下翻译）

协议分析题

注意：包头长乘以4，偏移量乘以 8