随机接入：CSMA/CD协议

媒体接入控制——动态接入控制——随机接入简介

在上节课中，我们介绍了媒体接入控制的其中一类方式，也就是静态划分信道。本节课我们介绍随机接入，它属于媒体接入控制的另一类方式即动态接入控制。

如图所示，多个主机连接到一根总线上，各主机随机发送帧。当两个或多个主机同时发送帧时，代表帧的信号就会产生碰撞，或称为冲突。又或者，当某个主机正在使用总线发送帧的过程中，另一台主机也要发送帧，这同样也会产生碰撞。很显然，如何协调总线上各主机的工作，尽量避免产生碰撞，是一个必须要解决的重要问题。

CSMA/CD(Carrier Sense Multiple Access/Collision Detection)载波监听多址接入碰撞检测技术

早期的共享式以太网采用载播监听多指接入碰撞检测，也就是CSMA/CD协议来解决该问题。

多址接入MA：多个主机也可成为站点或站连接在一条总线上，竞争使用总线。

载波监听CS：每一个站在发送帧之前，先要检测一下总线上是否有其他站点在发送帧，可比喻为先听后说。

• 若检测到总线空闲 96 比特时间，则发送这个帧。

• 若检测到总线忙，则继续检测并等待总线转为空闲 96 比特时间，然后发送这个帧。

帧间最小间隔：96 比特时间是指发送 96 比特所耗费的时间，也称为帧间最小间隔，其作用是使接收方可以检测出一个帧的结束，同时也使得所有其他站点都能有机会平等竞争信道并发送帧。

碰撞检测CD：每一个正在发送帧的站边发送帧边检测碰撞，可比喻为边说边听。

• 一旦发现总线上出现碰撞，则立即停止发送，退避一段随机时间后再次重新发送。可比喻为一旦冲突立即停说，等待时机重新再说。

举例说明载波监听多址接入碰撞检测

多指接入的概念比较简单，即多个主机连接到一根总线上，各主机随机发送帧。

假设主机 c 要发送帧，他首先进行载播监听，检测到总线空闲 96 比特时间后，就可以发送帧了。假设在主机 c 使用总线发送帧的过程中，主机 b 也要发送帧，主机 b 进行载播监听，发现走线忙，于是持续检测总线，一旦发现总线空闲 96 比特时间，则立即发送帧。边发送帧还要边检测碰撞，只要没检测到碰撞，则可继续发送帧的剩余部分。

03:23
假设在主机 b 发送帧的过程中，主机 c 也要发送帧，主机 c 进行载播监听，发现总监空闲 96 比特时间后，立即发送帧，这必然会产生碰撞。在产生碰撞的时刻，主机 b 和主机 c 都在边发送帧边检测碰撞，但都检测不到碰撞。碰撞信号沿总线传播，主机 c 会比主机 b 更早检测到碰撞，并停止发送退避一段。随机时间后，重新再发送之前所发送的帧。当主机 b 检测到碰撞后，立即停止发送，退避一段随机时间，重新再发送之前所发送的帧。

04:09
以太网还采取了一种叫做强化碰撞的措施，这就是当发送帧的站点一旦检测到碰撞，除了立即停止发送帧外，还要再继续发送 32 比特或 48 比特的人为干扰信号，以便有足够多的碰撞信号，使所有站点都能检测出碰撞。接下来我们介绍征用期的概念。如图所示，主机 a 和 d 处于总线型以太网的两端，以太网单程端到端的传播时延即为套，纵坐标为时间。假设在时刻0，主机 a 要发送帧，当检测到总线空闲 96 比特时间后，立即发送帧。在时刻套检德尔塔主基地也要发送帧。当检测到总线空闲 96 比特时间后，立即发送帧。需要注意的是，主基地检测到总线空闲，但实际上总线并不空闲，只是主基地检测不出来，这必然会产生碰撞。发生碰撞的时刻为套，减去二分之德尔塔。之后碰撞信号会陆续传播到主基地和主基a。主基地检测到碰撞的时刻为套，而主基 a 检测到碰撞的时刻为二套，减去德尔塔。从该图可知，主机最多经过二套，也就是德尔塔趋近于0，就可检测到本次发送是否遭受了碰撞。因此，以太网的端到端往返传播时延，二套就称为征用期或碰撞窗口。

05:54
发送帧的主机经过征用期这段时间还没有检测到碰撞，才能肯定这次发送不会产生碰撞。每一个主机在自己发送帧之后的一小段时间内存存在着遭遇碰撞的可能性，这一小段时间是不确定的，它取决于另一个发送帧的主机到本主机的距离，但不会超过总线的端到端往返传播时延。

06:21
借一个征用期时间，显然，在以太网中，发送帧的主机越多，端到端往返传播时延越大，发送碰撞的概率就越大。因此，共享是以太网不能连接太多的主机，使用的总线也不能太长。带宽为 10 兆比特每秒的以太网把征用期定为 512 比特，发送时间 g 51. 2 微秒，因此其总线长度不能超过 5120 米。但考虑到其他一些因素，如信号衰减等，以太网规定总线长度不能超过 2500 米。

07:03
接下来我们介绍最小帧长的概念，假设主机 a 正在给主机 d 发送一个很短的帧，边发送边检测碰撞，主机 a 很快就将该帧发送完毕了，之后就不再帧对该帧检测碰撞。在该帧的传输过程中，主机 c 也要发送帧。主机 c 检测到总线空闲 96 比特时间后就立即发送帧，尽管总线实际上并不空闲，这必然会产生碰撞。主机 d 最终会收到主机 a 发送的并遭遇碰撞的帧，主基地会将该帧丢弃。但对于主机 a 而言，他并不知道自己已发送完毕的该帧在总线上传输的过程中遭遇了碰撞，因此不会重发该帧。很显然，使用 c s m a C d 协议的以太网的帧长不能太短。以太网规定最小贞长为 64 字节，即 512 个比特，而发送 512 个比特的时间即为征用期。如果要发送的数据非常少，那么必须加入一些填充字节，使帧长不小于 64 字节。以太网的最小帧长确保了主机可在帧发送完成之前就检测到该帧在发送过程中是否遭遇了碰撞。如果在征用期，也就是共发送 64 字节所耗费的时间内没有检测到碰撞，那么后续发送的数据就一定不会发生碰撞。如果在征用期内检测到碰撞，就立即终止发送，这时已经发送出去的数据一定小于 64 字节。因此，凡长度小于 64 字节的帧都是由于碰撞而异常终止的无效帧。

09:05
既然以太网规定了最小贞长，那么是否还规定了最大贞长？我们来举例说明。假设主机 a 正在给主机 d 发送一个很长的帧，这会使得主机 a 长时间占用总线，而总线上的其他主机迟迟拿不到总线的使用权。另外，由于帧很长，还可能导致主基地的接收缓冲区无法装下该帧而产生溢出，因此以太网的帧长应该有其上限。

09:38
例如，这是以太网版本 2 的马克帧格式，其数据载核的最大长度为 1500 字节，加上首部和尾部共 18 字节，帧的最大长度为 1518 字节，而数据载荷的最小长度不能小于 46 字节。这样加上首部和尾部共 18 字节，正好满足帧的最小长度为 64 字节，这是插入微滥标记字段后的 802. 1 Q 帧，其数级载荷的最大长度为 1500 字节，加上首部和尾部共 22 字节，帧的最大长度为 1522 字节。而数据载和的最小长度不能小于 42 字节，这样加上首部和尾部共 22 字节，正好满足帧的最小长度为 64 字节。

10:32
接下来我们介绍退避时间的计算方法，也就是截断二进制指数退币算法。退币时间等于基本退避时间乘以随机数r，其中基本退避时间的取值为征用 72 套，而随机数 r 是从离散的整数集合零一直到 2 的 k 次减 1 中随机选出的一个数k，从重传次数和数值时装取小者，这也是该算法名称中截断二进制指数这种称谓的由来。

11:12
我们来举例说明退避时间的计算，假设这是第一次重传 k 从重传次数 1 和时装取小者，也就是 1 则离散的整数集合为0，一则可能的退避时间为 0 乘以 2 套， 1 乘以 2 套。假设这是第二次重传k，从重传次数 2 和 10 中取小者，也就是 2 则离散的整数集合为0123，则可能的退避时间为 0* 2 套、 1* 2 套、 2* 2 套、 3* 2 套。假设这是第 12 次重传 k 层重传次数 12 和 10 周取小者，也就是 10 则离散的整数集合为012，一直到1023，则可能的退避时间为 0* 2 套、 1* 2 套、 2* 2 套，一直到 1023* 2 套。

12:19
从该地可以看出，若连续多次发生碰撞，就表明可能有较多的主机参与竞争信道。但使用上述推比算法可使重船需要推迟的平均时间随重船次数而增大，这也称为动态退避，因而减小发生碰撞的概率，有利于整个系统的稳定。当重传多达 16 次仍不能成功时，表明同时打算发送帧的主机太多，以至于连续发生碰撞则丢弃该帧并向高层报告。

13:00
接下来我们来讨论一下使用 c s m a C d 协议的共享式以太网的信道利用率。如图所示，横坐标为时间。总线上的某个主机可能发生多次碰撞，进行多次退避后成功发送了一个帧，帧的发送时延即为T0。在最极端的情况下，原主机在总线的一端，而目的主机在总线的另一端，因此还要经过一个单程端到端的传播实验套后，总线才能完全进入空闲状态，因此发送 1 帧所需的平均时间为多个征用期。 2 套加上一个帧的发送时延T0，再加上一个单程端到端的传播时延套。考虑以下这种理想情况，各主机发送帧都不会产生碰撞，总线一旦空闲，就有某个主机立即发送帧，因此这部分时间就不存在了。

14:06
发送一帧所占用总线的时间为T0，加上套，而帧本身的发送时间为T0，这样就可得出极限信道利用率的表达式，将分子分母同除以T0，将套除以 T0 记为参数a。为了提高信道利用率，参数 a 的值应尽量小，要是参数 a 的值尽量小，则掏的值应该尽量小。这意味着以太往端到端的距离应受到限制，不应太长，而 T0 的值应当尽量大，这意味着以太网的珍藏应尽量大一些。接下来，我们给出c，s，m， a C， d 协议的帧发送流程图，这是在播监听部分，这是碰撞检测部分，这是检测到碰撞后的处理部分。再来看 c s，m， a C、 d 协议的帧接收流程图，若接收到的帧的长度小于最短帧长，则认为该帧遭遇到了碰撞，丢弃该帧。若接收到的帧的目的 mark 地址与接收方的 Mac 地址相同或是广播地址，则继续进行后续判断，否则丢弃该帧。若使用循环荣誉校验检查出帧，在传输过程中出现了误码，则丢弃该帧。只有正确通过上述三个检查主机才能接受所收到的帧。

15:49
接下来我们来做几个相关的练习题，这是计算机专业考研全国统考计算机网络部分 2015 年的题。36。请大家暂停播放视频思考一下，给出你的答案。答案是选项b，大家都选对了吗？我们来一起分析一下。选项 a 描述的是碰撞检测或称冲突检测，这是 c s m a C d。协议中的一部分。描述正确。选项 b 的描述错误，因为 c s m a C d 协议并不适用于无线网络，对于无线网络可以使用 c s， m a C a 协议。选项 c 中给出的网络跨距相当于给出了端到端传播时延套，进而可以得出征用期二套，再乘以数据传输速率记为最小帧长。描述正确，选项 d 描述正确。这可以从极限信道利用率的计算公式看出，当套趋近于 0 时，信道利用率趋近于百分之百。

17:12
再来看 2009 年的提37，请大家暂停播放视频，思考一下，给出你的答案。答案是选项d，大家都选对了吗？我们来一起分析一下。本题考察的是采用 CSM ACD 协议的共享式以太网的最小珍藏的相关概念。设最远两个站点之间的距离为 d 米，最小甄长为l，比特最小帧长等于征用期乘以数据传输速率。将题目所给的各已质量统一单位后，与之前所设的两个未知量 d 和 l 带入上市，就可以得出最远两个站点之间的距离。 d 与最小侦查 l 的关系是，很显然，若最小帧长减少 800 比特，最远的两个站点之间的距离至少会减少 80 米。再来看 2010 年的提 47 的第一问，请大家暂停播放视频，思考一下，给出你的答案。我们来一起分析一下。根据提议可画出如下所示的示意图，只有两主机同时发送数据，才能使得他们从开始发送数据时刻起，到他们都检测到冲突时刻值所经过的时间最短。如图所示，这段时间包括主机发送的数据信号传播到距离终点处所耗费的传播时延，以及发生碰撞后的碰撞信号传播回主机所耗费的时间。这与之前的传播时延是相等的，因此这段时间实际上是两主机间单程的传播时延。计算如下。

19:24
再来看这样一种情况，主机甲发送的数据信号传播到无限接近主机乙的某个时刻，主机乙也要发送数据，他检测到信道空闲，但实际上信道此时并不空闲，就立刻开始发送数据，这必然会导致碰撞。如图所示，主机乙会首先检测到碰撞，一段时间后，主机甲也会检测到碰撞，如图所示。很显然，从开始发送数据时刻起，到两台主机均检测到碰撞时刻纸最长需要经过的时间为两台主机间信号传播的往返时延，也就是征用期二套计算如下。

20:24
本节课到这里就结束了，我们将本节课的内容小结如下，需要提醒大家注意的是， c s m a C d。协议曾经用于各种总线结构以太网和双角线以太网的早期版本中。现在的以太网基于交换机和全双工连接，不会有碰撞，因此没有必要使用 c s m a C d。协议。同学们，我们下节课再见。