计算机网络：数据链路层 - CSMA/CD协议
计算机网络：数据链路层 - CSMA/CD协议
- 媒体接入控制
- CSMA/CD协议
- 截断二进制指数退避算法
- 帧长与帧间间隔
- 信道利用率
媒体接入控制
如图所示，这是一根同轴电缆，有多台主机连接到这根同轴电缆上，他们共享这根传输媒体，形成了一个总线型的局域网。各主机竞争使用总线随机的在信道上发送数据。
如果恰巧有两个或更多的站点在同一时刻发送数据，那么信号在共享媒体上就要产生碰撞，即发生了冲突，使得这些站点的发送都失败。
共享信道要着重考虑的一个问题就是如何协调多个发送和接收站点对一个共享传输媒体的占用，也就是媒体接入控制。
媒体接入控制技术主要分为两类，静态划分信道和动态接入控制。
静态划分信道：
静态划分信道主要有频分多址，时分多址，波分多址，码分多址。
静态划分信道，也就是预先固定分配好信道。这类方法非常不灵活，对于突发性数据传输，信道利用率会很低。通常在无线网络的物理层中使用，而不是在数据链路层中使用。该方面知识我已在物理层讲解：[计算机网络：物理层 - 信道复用]
动态接入控制：
动态接入控制又可以分为两类，一类是受控接入，另一类是随机接入。
受控接入
用户要遵循一定的规则发送数据，而不能随意的发送数据
随机接入：
所有站点通过竞争随机的在信道上发送数据
随机接入存在一个问题，因为站点发送信息是随机的，如果恰巧有两个或更多的站点在同一时刻发送数据，那么信号在共享媒体上就要产生碰撞，使得这些站点的发送都失败。因此，随机接入这类协议要解决的关键问题是如何尽量避免冲突，以及在发生冲突后如何尽快恢复通信。
著名的共享式以太网采用的就是随机接入。需要注意的是，随着技术的发展，交换技术的成熟和成本的降低，具有更高性能的使用点对点链路和链路层交换机的交换式局域网在有限领域已完全取代了共享式局域网，但由于无线信道的广播天性，无线局域网仍然使用的是共享媒体技术。
CSMA/CD协议
如图所示，多个主机连接到一根总线上，各主机随机发送帧：
当两个或多个主机同时发送帧时，代表帧的信号就会产生碰撞或成为冲突。又或者当某个主机正在使用总线发送帧的过程中，另一台主机也要发送帧，这同样也会产生碰撞。
很显然，如何协调总线上各主机的工作，尽量避免产生碰撞是一个必须要解决的重要问题。早期的共享式以太网采用载波监听，多点接入，碰撞检测，也就是CSMA/CD协议来解决该问题。
多点接入MA：多个主机连接在一条总线上，竞争使用总线
载波监听CS：每一个站点在发送帧之前，先要检测一下总线上是否有其他站点在发送帧
碰撞检测CD：每一个正在发送帧的同时，一边发送帧一边检测。一旦发现总线上出现碰撞，则立即停止发送，退避一段随机时间后再次重新发送
这三个特性都还比较好理解，多点接入也就是一条线上有多个主机，它们随机发送信息就有可能产生碰撞；载波监听就是再发送数据前，要先检测一下现在有没有其他主机在发送，如果有就先不发送；碰撞检测就是在发送数据的时候，要确保数据发送的时候没有发生碰撞。
而三者的英文缩写分别是MA，CS，CD，因此该协议称为CSMA/CD协议。
第一个问题就是，主机明明在发送数据之前，就已经检测了信道上有没有主机在发送数据，为什么还有可能会发生碰撞？
我们看到以下情况：
现在整个信道上都没有信号传输，A检测到信道空闲，发送数据。
A发送信号不久后，此时信号还没有传送到D，D也想发送信号，D检测到信道空闲，也发送了信号。于是两个信号就会发生碰撞：
也就是说，电磁波在信道上传播的速率是有限的，当计算机监听到信道空闲而发送数据时，有可能已经有其它计算机在发送数据了。
现在规定，一条信道中，最远的两台主机之间发送信号所需的时延为 τ \tau τ， τ \tau τ音同“涛”。以上例子中，A和D就是该信道里面最远的两台主机，假设A发送数据的时间节点为0，那么该数据到达D的时间节点就是 τ \tau τ，而D在 τ − δ \tau - \delta τ−δ时刻发送了数据：
那么有以下重要时间点：
发生碰撞的时间为 τ − δ 2 {\color{red}\tau - \frac{\delta}{2}} τ−2δ
D检测到碰撞的时间为 τ {\color{red}\tau} τ
A检测到碰撞的时间为 2 τ − δ {\color{red}2\tau - \delta} 2τ−δ
δ \delta δ可以视为是在即将接收到A信号前的 δ \delta δ时间，D发送了数据。当 δ \delta δ趋近于0，那么A检测到碰撞的时间就越接近 2 τ {\color{red}2\tau} 2τ。因为此时A和D已经是信道中最远的两台主机了，因此可以理解为一台主机发送一个信号，最多经过 2 τ {\color{red}2\tau} 2τ的时间，就可以确定自己是否发生了碰撞。因为只有在 2 τ {\color{red}2\tau} 2τ时间内，才有可能有其他主机发送数据产生碰撞，一旦过了 2 τ {\color{red}2\tau} 2τ的时间，所有主机一旦想发送数据，就会先进性载波监听，发现信道已经被占用了，就不会再发送数据了。
其中 2 τ {\color{red}2\tau} 2τ被称为争用期或者碰撞窗口，以太网中争用期被规定为 51.2 μ s 51.2\mu s 51.2μs。主机发送数据的同时，只需要进行 2 τ 2\tau 2τ时间的载波监听，就可以不再进行监听了，因为后续传送的数据一定不会发生碰撞。
显然，在以太网中主机越多，端到端的往返时延越大，发生碰撞的概率就越大。因此共享式以太网不能连接太多主机，使用的总线也不能太长。
10Mb/s的以太网把争用期定为512比特发送时间，即 51.2 μ s 51.2\mu s 51.2μs，因此其总线长度不能超过5120m，但是由于一些其它因素，比如信号衰减等，以太网规定总线长度不能超过2500m。
现在我们讲解完了什么情况下会碰撞，以及如何检测出碰撞。那么两个信号发生碰撞后，要怎么办呢？
截断二进制指数退避算法
当两个主机发送的数据发生碰撞后，都要进行一个退避操作，简单来说就是过一会再发送一次，那么过一会是多久呢？如果说退避时长差不多，那么两主机过一段时间后同时发送，又会发生碰撞，因此这个退避时间必须是随机的。在CSMA/CD协议中，采用了截断二进制指数退避算法来进行退避操作，以产生随机的数值进行退避，确保主机碰撞后退避的时间不同。
算法如下：
- 规定基本退避时间为 2 τ 2\tau 2τ
- 定义参数 k = min(重传次数, 10)
- 从整数区间[0, 2 k − 1 2^{k} - 1 2k−1]随机选一个数字r，最后的退避时间为 r × 2 τ {\color{Red} r \times 2\tau } r×2τ
- 如果重传16次依然不成功，丢弃该帧并向高层汇报
接下来我再详细讲解以上算法的执行过程。
首先要设置一个基本的退避时间，该时间被设置为 2 τ 2\tau 2τ。而最后的总退避时间，就等于一个随机数r乘以这个基本退避时间 2 τ 2\tau 2τ，也就是 r × 2 τ {\color{Red} r \times 2\tau } r×2τ。
那么现在的问题就是，要如何生成这个随机数r。该随机数r取自一个区间[0, 2 k − 1 2^{k} - 1 2k−1]，而这个k不是一个固定的数值，其与重传次数相关。
- 如果重传次数小于10，那么 k 就是重传次数
- 如果重传此处大于10，那么 k = 10
比如说当前是第2次重传，那么k = 2，r的取值范围就是[0, 2 2 − 1 2^{2} - 1 22−1]，也就是[0, 3]。最后r在这个区间内随机取一个值，最终的退避时间就是 r × 2 τ r \times 2\tau r×2τ。
再比如当前是第14次重传，由于重传次数超过10，那么k = 10，r的取值范围就是[0, 2 10 − 1 2^{10} - 1 210−1]，也就是[0, 1023]。最后r在这个区间内随机取一个值，最终的退避时间就是 r × 2 τ r \times 2\tau r×2τ。
随机数 r 是从离散的整数集合[0, 2 k − 1 2^{k} - 1 2k−1]中随机选出的一个数，这也是该算法名称截断二进制指数称谓的由来。
帧长与帧间间隔
最短帧长：
假设主机 A 正在给主机 D 发送一个很短的帧，边发送边检测碰撞，主机 A 很快就将该帧发送完毕了，之后就不再对该帧检测碰撞：
在该帧的传输过程中，主机 C 也要发送帧，主机 C 检测到总线空闲后就立即发送帧。
这必然会产生碰撞，主机 D 最终会收到主机 A 发送的并遭遇碰撞的帧。主机 D 会将该帧丢弃，但对于主机 A 而言，他并不知道自己已发送完毕的该帧在总线上传输的过程中遭遇了碰撞，因此不会重发该帧。很显然，使用CSMA/CD协议的以太网的帧长不能太短。
以太网规定最小帧长为 64 字节，即 512 个比特，而发送 512 个比特的时间即为争用期。如果要发送的数据非常少，那么必须加入一些填充字节，使帧长不小于 64 字节。以太网的最小帧长确保了主机可在帧发送完成之前就检测到该帧在发送过程中是否遭遇了碰撞。
最大帧长：
假设主机 A 正在给主机 D 发送一个很长的帧：
这会使得主机 A 长时间占用总线，而总线上的其他主机迟迟拿不到总线的使用权。另外，由于帧很长，还可能导致主机 D 的接收缓冲区无法装下该帧而产生溢出，因此以太网的帧长应该有其上限。
例如这是以太网版本 2 的MAC帧格式：
-
最大帧长：其数据载荷的最大长度为 1500 字节，加上首部和尾部共 18 字节，帧的最大长度为 1518 字节
-
最短帧长：数据载荷的最小长度不能小于 46 字节，这样加上首部和尾部共 18 字节，正好满足帧的最小长度为 64 字节
帧间间隔：
另外，以太网还规定帧间最小间隔为 9.6 μ s 9.6\mu s 9.6μs。在没有发生碰撞的情况下，一台计算机即使检测到信道空闲，也要等 9.6 μ s 9.6\mu s 9.6μs才能再次发送数据。
这是为例使刚刚收到数据帧的计算机的缓存来得及清理，为接收下一帧做好准备。
信道利用率
接下来我们来讨论一下使用 CSMA/CD 协议的共享式以太网的信道利用率。如图所示，横坐标为时间：
总线上的某个主机可能发生多次碰撞，进行多次退避后成功发送了一个帧，最后帧经过发送时延 T 0 T_{0} T0把数据发送了出去。
在最极端的情况下，两台主机处于总线两端，因此还要经过一个单程端到端的传播时延后，总线才能完全进入空闲状态。因此发送一帧所需的平均时间为多个争用期 2 τ 2\tau 2τ 加上一个帧的发送时延 T 0 T_{0} T0，再加上一个单程端到端的传播时延 τ \tau τ ：
发送一帧的时间 = n × 2 τ + T 0 + τ 发送一帧的时间 = n \times 2\tau + T_{0} +\tau 发送一帧的时间=n×2τ+T0+τ
考虑以下这种理想情况，各主机发送帧都不会产生碰撞，总线一旦空闲，就有某个主机立即发送帧。发送一帧所占用总线的时间为 T 0 T_{0} T0，加上传播时延 τ \tau τ。这样就可得出极限信道利用率的表达式：
S max = T 0 T 0 + τ S_{\max }=\frac{T_{0}}{T_{0}+\tau} Smax=T0+τT0
在以太网中，我们把参数a定为 τ \tau τ与 T 0 T_{0} T0之比：
a = τ T 0 a=\frac{\tau}{T_{0}} a=T0τ
因此极限信道利用率可以写为：
S max = T 0 T 0 + τ = 1 1 + a S_{\max }=\frac{T_{0}}{T_{0}+\tau}=\frac{1}{1+a} Smax=T0+τT0=1+a1
为了提高信道利用率，参数 a 的值应尽量小，要是参数 a 的值尽量小，则 τ \tau τ的值应该尽量小。这意味着端到端的距离应受到限制，不应太长，而 T 0 T_{0} T0 的值应当尽量大。这意味着以太网的帧长应尽量大一些。