计算机网络 2：物理层与链路层

2023 年 5 月 24 日

基带与频带 #

基带即原始的数字信号，不利于传输。频带则是将基带调制到模拟信号上，适合进行传输。基带传输的类型有：

不归零码（NRZ）；
归零码（RZ）；
曼彻斯特编码：下边沿为 1，上边沿为 0；
差分曼彻斯特编码：本周期开始有跳变为 0，无跳变为 1。或者，视作曼彻斯特编码时，上周期编码与本周期不同为 1。

频带传输的类型有：

二进制数字调制家族（2ASK、2FSK 和 2PSK）。2FSK 频带利用率最低（调频在频谱上占有宽度较宽）。
多进制数字调制。
正交幅值调制。

波特率与信道容量 #

波特是指一个完整的信号码元，即传输在介质上的最小单位。1 个波特可以表示若干个比特。

信道容量指信道无差错传输信息的最大平均信息速率。单位是 bps。

Nyquist 信道容量公式——理想、无噪声的信道容量 $C= 2B\log_2 M$
- 其中 $C$ 是信道容量（bps），$B$ 是信道带宽（Hz），$M$ 是信号的状态数。
- 此为理想信道的极限容量。
Shannon 信道容量公式——有噪声信道的容量 $C=B\log_2(1+S/N)$
- 其中 $S/N$ 是信噪比。
- $1,\mathrm{dB}=10\lg(S/N)$

差错控制 #

汉明距离 #

两个码字之间对应位不同的数目。例如：

不加任何校验信息的原始编码，汉明距离为 1。
将原消息重复 3 次，汉明距离为 3。（改变 1 位，会造成 3 位同时改变）

对于检错码，如果汉明距离为 $d=r+1$，则可以检测 $r$ 位出错。对于纠错码，如果汉明距离为 $d=2r+1$，则可以纠正 $r$ 位出错。

CRC #

首先选定一个 $r+1$ 位的「生成比特模式」$G$。例如，选定 $r=4$，可取 $G$ 为 10011。

CRC 的生成：在源消息 $D$ 后先增加 $r$ 个零，然后计算此消息 $[D|00..0]$ 除以 $G$ 的余数，将余数替换到原先的 $r$ 个零上。
CRC 的校验：将带有 CRC 的消息除以 $G$，检查余数是否为零。

滑动窗口的可靠传输 #

信道利用率 #

滑动窗口的信道利用率是

$$ U=\dfrac{W_S\times t_{seg}}{t_{seg}+RTT+t_{ack}}=\dfrac{W_S\times L_{seg}}{L_{seg}+2d_p+L_{ack}} $$

其中，$W_S$ 是滑动窗口的大小。$L_{seg}$ 是一帧的长度，$L_{ack}$ 是一帧 ACK 的长度。

Go-Back-N（GBN） #

![Screenshot 2023-05-24 150043](assets/Screenshot 2023-05-24 150043-20230524150101-guj0qjk.png)

Selective Repeat（SR） #

![Screenshot 2023-05-24 150256](assets/Screenshot 2023-05-24 150256-20230524150315-7x2jjhd.png)

从部分逻辑上说，GBN 可以看成接收窗口大小为 1 的 SR——GBN 的接收方只能接受按序的下一个分组，而 SR 的接收方可以接受多个乱序的分组。但在行为上仍然有区别：GBN 的发送方如果超时，则重传从当前窗口基序号开始的所有分组；SR 的发送方如果超时，则只重传该个未确认的分组。

窗口大小的选择 #

为了防止因序号溢出回滚造成的错误判断，滑动窗口协议需要满足

$$ W_S+W_R\leqslant2^k $$

其中 $k$ 是序号的位数；即 $2^k$ 是序号总数。

对于 GBN，因为 $W_R=1$，所以 $W_S\leqslant2^k-1$。
对于典型的 SR，$W_R=W_S$，所以 $W_S\leqslant2^{k-1}$。
对于单帧的停-等协议，$W_R=W_S=1$，所以 $k\geqslant1$。

多路访问控制 / 介质访问控制（MAC） #

MAC 的内容是：在广播信道中，采取一定的措施，使得两对结点之间的通信不会发生互相干扰的情况。可以分为 3 类：信道划分（多路复用，不会冲突）、随机访问（冲突必然，从中恢复）和轮转（轮流使用（宏观上的分时，不是 TDMA），不会冲突）。

信道划分的 MAC #

采用信道划分的 MAC 有 4 种：

TDMA：时分复用，在不同时隙接入信道。
FDMA：频分复用，在不同频带接入信道。
WDMA：波分复用，特指光的 FDMA（表述光时波长更常用），本质是 FDMA。
CDMA：码分复用，使用不同的编码方式区分不同的信号。

随机访问的 MAC #

不事先约定，需要检测冲突并从冲突中恢复。

ALOHA：不用同步，当有新的帧生成时立即发送。
如果冲突：等待随机时间后尝试重传。
时隙 ALOHA：所有结点同步时钟，以时隙为单位立即发送。
如果冲突：等待随机时隙后尝试重传。
载波监听多路访问协议（CSMA）：发前先守听。
如果信道空闲：发完整的帧。
如果信道正忙：推迟发送。
- 1-坚持 CSMA：监听到忙后，继续监听；一旦空闲，立即发送（发送的概率为 1）。
- 非坚持 CSMA：监听到忙后，不再监听，等待随机时间后再重试（发送的概率为零）。
- p-坚持 CSMA：需要时隙支持。即使信道空闲，以 p 的概率发送，以 (1-p) 的概率推迟到下一时隙（然后重新监听判断）；若信道忙，则继续监听至空闲。
由于传播延迟的存在，这三种方式都可能造成冲突。
CSMA/CD：加上冲突检测。「先听后发，边听边发，冲突停发，随机重发」。
最小帧长 = 两倍的介质内最长传播时间——对应最差情况：我的信号马上就要给到你（还没有给到）时你发了信号。以太网规定「两倍的介质内最长传播时间」是 51.2 us，即对于 10 Mbps 的以太网，最小帧长 512 比特即 64 字节。
截断二进制指数退避算法：
- 确定基本退避时间即争用时间（以太网为 51.2 us）
- 令 $k$ 为已经重传的次数，上限为 10。然后，从数集 ${0,1,2,4,\cdots,2^k-1}$ 中选择一个数。这个数乘以基本退避时间就是重传等待的时间。
- 重传 16 次仍然不成功则放弃。