计算机网络 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 | 6 | 6 | 2 | 46—1500 | 4 |
---|---|---|---|---|---|---|
结构 | 前导码* | 目的地址 | 源地址 | 类型 / 长度 | 载荷 | FCS(校验和,CRC) |
前导码(8 字节)用于时钟同步,通常不计入帧长。故以太网帧的最短长度为 64 字节,最长为 1518 字节。相应的,载荷的最短长度为 46 字节,最长为 1500 字节。
1500 字节称为此以太网的最大传输单元(MTU)。
以太网交换机
Switch?Switch!
他得到了想要的 Switch 作为圣诞节礼物。图源 Reddit。
交换机是二层网络设备,通过以太网帧中的 MAC 字段决定帧的去向。交换机是自学习的,在内部维护有交换表(记录着每个 MAC 地址的设备在哪个接口),如下:
MAC 地址 | 接口 | 存活时间(TTL) |
---|---|---|
11:22:33:44:55:66 | 1 | 60 |
0f:20:00:1a:2b:3c | 3 | 60 |
…… | …… | …… |
对于目的 MAC 地址在上表中的帧,直接向对应的接口转发;对于不在其中的,则进行泛洪——将帧转发给所有接口。