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

基带与频带

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

• 不归零码（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）

Selective Repeat（SR）

从部分逻辑上说，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 次仍然不成功则放弃。

以太网

以太网的特性：

• 无连接：发送方与接收方之间没有「握手」过程。

• 不可靠：发送方不知晓接收方接收情况。差错帧直接丢弃。

• 半双工时，使用二进制指数规避 CSMA/CD。

以太网帧的结构：

前导码（8 字节）用于时钟同步，通常不计入帧长。故以太网帧的最短长度为 64 字节，最长为 1518 字节。相应的，载荷的最短长度为 46 字节，最长为 1500 字节。

1500 字节称为此以太网的最大传输单元（MTU）。

以太网交换机

Switch？Switch！

他得到了想要的 Switch 作为圣诞节礼物。图源 Reddit。

交换机是二层网络设备，通过以太网帧中的 MAC 字段决定帧的去向。交换机是自学习的，在内部维护有交换表（记录着每个 MAC 地址的设备在哪个接口），如下：

对于目的 MAC 地址在上表中的帧，直接向对应的接口转发；对于不在其中的，则进行泛洪——将帧转发给所有接口。