以太网中的 CSMA/CD 协议及二进制指数退避算法详解

一、概述

CSMA/CD 是一种基于竞争的 MAC 协议,用于协调共享以太网中多个站点数据发送。

主要分为三个要点:载波监听多点接入 以及冲突检测,应用在物理链路层。

1.1 载波监听

载波监听 是指每个连接在以太网上的站点在发送数据之前,都要先检测总线上是否有数据在传输。如果有,则暂时不发送数据,避免 数据冲突;如果没有,则发送数据。

1.2 多点接入

多点接入表示多个计算机站点以多点接入的方式连接到同一根总线上。

1.3 冲突检测

冲突检测 的意思是在某一空闲时刻,可能有多个站点同时发送数据导致数据冲突,此时站点应该检测是否有数据冲突,如果有数据冲突,应立即停止数据发送。

二、争用期

电信号在介质上传输的速率是有限的,传输也会产生时延,在一条一千米的电缆上传播时延约为 5μs

由于以太网的限制,站点之间最长允许 2.5km 的连接 (4 个中继站点连接 5 根 500 米电缆),站点间来回一共 5km 需要 25μs 延时。

假设 A 、 B 两个站点之间的距离刚好为 2500m ,数据的传输时间为τ ,A 向 B 发送一个帧,B 要经过时间τ 后才能收到 A 的数据。这段时间内,B 可以认为线路是空闲的,如果这个时间段向 A 发送一个帧,两个帧在线路中途相遇就会发生冲突。

为了解决这种冲突,CSMA/CD 首先采用了载波监听的策略,监听到空闲就发送数据,载波监听 的作用是确保发送的时候线路是空闲的。数据发送后,站点还要监听,监听数据发送中途是否有冲突产生,如果听到冲突发生,站点应立即停止发送数据,等待一定的时间后再发送,而由于时延的存在,冲突是不可避免的。一个数据冲突的模型为:

图中,A 向 B 发送数据,传播时间为τ,在 A 发送后的 t(t<τ) 时间,B 站也发送数据,此时中途数据就会发生碰撞。由图可以得知,A 站点要检测到冲突,最多需要 2τ时间。即当δ为 0 的时候,也就是在 A 的数据到达 B 的前一刻 B 站也发送数据的时候。如果 A 发送数据后经过 2τ时间还没有收到碰撞信号的话,就说明数据没有产生碰撞,A 数据发送成功。

正常情况下,站点检测到冲突后,除了立即停止正常发送以外,还要发送若干比特的人为干扰信号强化冲突,使得所有的站点都能收到冲突信号。

这个 的时间称为争用期,或者是碰撞窗口,在这段时间内如果没有检测到碰撞,那么本次发送就不会产生冲突了。

以太网把争用期设置为 51.2μs,这个时间的得来没有找到合适的答案,一个比较有说服力的说法是:端到端 5000m 时延需要 25μs,来回需要经过 8 个中继站,信号在中继站中转的途中也会消耗时间,总共约为 20μs,再加上发送强化冲突数据的时间一共 51.2μs

三、二进制指数退避算法

在数据发生冲突后,站点需要立即停止数据的发送,并等待一定的时间后再次发送,这个时间由二进制指数退避算法得来。

二进制指数退避算法的具体表现为:

  • 把争用期 作为基本退避时间
  • 从整数集合 {0, 1, ..., (2^k) - 1}中抓取一个整数,记为 r ,推迟发送的时间为 r*2τ,其中 k 的取值规则为:当重传次数不超过十次时,k 等于重传次数,超过 10 次时,k 不再增大,一直等于 10 。
  • 当重发次数到达 16 次还不能成功时,抛弃当前数据包,向上层应用报告。

 

发表评论