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

马谦马谦马谦 2017年10月27日22:45:23 发表评论
文章最后编辑于:2017-11-18 17:35:53

一、概述

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

以太网中的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次还不能成功时,抛弃当前数据包,向上层应用报告。

 

本文共执行47次查询,耗时0.282秒!
马谦马谦马谦

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: