【计算机网络】数据链路层 : CSMA/CD 协议 ( 载波监听多点接入 / 碰撞检测协议 | 单程端到端传播时延 | 截断二进制指数规避算法 | 计算示例 | 最小帧长问题 )★

韩曙亮

发布于 2023-03-28 17:00:50

1.3K0

发布于 2023-03-28 17:00:50

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、 CSMA/CD 协议

CSMA/CD 协议 :

① 全称 : Carrier Sense Multiple Access With Collision Detection , 载波监听多点接入 / 碰撞检测协议 ;

② CS : Carrier Sense , 载波监听 , 每个站点发送数据前 , 和发送数据过程中 , 先检测总线上是否有其它站点在发送数据 ;

③ MA : Multiple Access , 多点接入 , 多个主机连接在同一条总线上 ; 该协议应用于总线型网络中 ;

④ CD : Collision Detection , 碰撞检测 , 适配器一边发送 , 一边监听 , 检测信道上电压变化用于判断本站点发送数据时 , 其它站点是否也在发送你数据 ; 由此可以看出 , 该协议用于半双工网络中 ;

电磁波传输时间导致冲突 : 先监听了信道 , 但是还是会发生冲突 , 电磁波在信道上是以有限速度传播的 , 如果电磁波没有到本站点 , 当时检测肯定是没有信号 , 但是等到本站点向外发出数据时 , 突然检测到有信号 , 这里电磁波传输的时间差 , 就造成了这种误差 ;

ALOHA 协议与 CSMA 协议对比 :

ALOHA 协议 , 不听就说 ;
CSMA 协议 , 先听再说 ;
CSMA/CD 协议 , 先听再说 , 边听边说 ;

二、传播时延对于载波监听的影响

传播时延对于载波监听的影响 :

① 前提 : 信道两端是

A, B

两台主机 , 两个站点单程端到端 , 电磁波从

到

传播 , 需要

纳秒 ;

②

发送数据到

一半 :

纳秒时刻 ,

向

发送数据时 , 预计

纳秒后 , 到达到

站点 ;

③

发送数据到

在

\cfrac{t}{2}

纳秒时刻 , 突然

发送数据 , 此时检测到信道没有电磁波 , 因为此时电磁波还没有到达

站点 ; 因此检测到信道没有信号传输 ;

④ 出现冲突 :

如果传输数据 , 肯定会在某时刻与

已经发送的数据产生冲突 ; 此时时刻时

\cfrac{3t}{4}

纳秒

⑤ 碰撞 :

的信号与

的信号叠加在一起 , 称为碰撞 ; 此时两个信号都被污染了 , 无法解析使用 ;

⑥

站点检测到碰撞 :

接收到碰撞后的信号 , 校验肯定不通过 , 出现帧错误 , 此时检测到发生了碰撞 ,

站点暂停数据发送 ; 该时刻是

纳秒 ;

⑦

站点检测到碰撞 :

接收到碰撞后的信号 , 校验肯定不通过 , 出现帧错误 , 此时检测到发生了碰撞 ,

站点暂停数据发送 ; 此时时刻时

\cfrac{3t}{2}

纳秒

三、单程端到端传播时延相关概念

引入一组概念 :

① 单程端到端传播时延 : 记作

\tau

;

② 碰撞检测最长时间 : 站点发出数据后 , 最多两倍的单程端到端时延

2\tau

后就可以得知出现了碰撞 ;

③

2\tau

概念 : 又称为 , 总线端到端往返传播时延 , 争用期 , 冲突窗口 , 碰撞窗口 ;

只要经过

2\tau

没有检测到碰撞 , 本次发送 , 一定没有碰撞 ;

四、碰撞后重传时机 ( 截断二进制指数规避算法 )

截断二进制指数规避算法 :

① 争用期 : 确定基本退避时间 , 也就是争用期 , 两倍的单程端到端传播时延

2\tau

;

② 重传次数 : 定义参数

, 一定程度上相当于重传次数 ;

公式 :

取值不超过

, 公式为

k=min( 重传次数 , 10 )

;

当重传次数不超过

时 :

k = 重传次数

当重传次数大于

时 :

k=10

;

③ 取随机数 : 从整数集合

[0, 2^k - 1]

中 , 取出随机数

, 重传时间就是

r \times 2\tau

;

④ 重传次数限制 : 当重传

次都失败时 , 说明网络拥塞严重 , 直接丢弃该帧 , 向上层报告出错 ;

示例 :

① 第

次重传 ,

k=1

, 从

[0, 1]

区间中 , 即

\{ 0 , 1\}

中随机取一个值 ,

;

如果

r = 0

, 重传时间是

;

如果

r = 1

, 重传时间是

2\tau

;

② 第

次重传 ,

k=2

, 从

[0, 3]

区间中 , 即

\{ 0 , 1 , 2 ,3\}

中随机取一个值 ,

;

如果

r = 0

, 重传时间是

;

如果

r = 1

, 重传时间是

2\tau

;

如果

r = 2

, 重传时间是

4\tau

;

如果

r = 3

, 重传时间是

6\tau

;

③ 第

次重传 ,

k=3

, 从

[0, 7]

区间中 , 即

\{ 0 , 1 , 2 ,3 , 4, 5, 6, 7\}

中随机取一个值 ,

;

如果

r = 0

, 重传时间是

;

如果

r = 1

, 重传时间是

2\tau

;

如果

r = 2

, 重传时间是

4\tau

;

如果

r = 3

, 重传时间是

6\tau

;

如果

r = 4

, 重传时间是

8\tau

;

如果

r = 5

, 重传时间是

10\tau

;

如果

r = 6

, 重传时间是

12\tau

;

如果

r = 7

, 重传时间是

14\tau

;

五、截断二进制指数规避算法计算示例

在以太网二进制回退算法中 , 碰撞

次后 , 随机数

的选择范围是多少

随机数

是根据参数

确定的 , 参数

是重传次数和

中较小的值 , 重传次数小于等于

次时 ,

k = 重传次数

, 重传次数大于等于

次时 ,

k = 10

;

随机数

的取值范围是

[0, 2^k - 1]

, 代入

k=10

;

取值范围是

[0 , 2^{10} - 1]

, 随机数

的范围是

[0 , 1023]

之间的值 ;

六、最小帧长问题

检测到碰撞时 , 需要暂停帧的发送 , 如果帧太短 , 就会导致一次性发送完毕 , 无法暂停 , 这里需要在检测到碰撞时 , 帧还没有发送结束 ;

帧的传输时延至少要大于

2\tau

;

帧的传输时延 = \cfrac{帧长度 ( 比特 )}{ 数据传输速率 }

\cfrac{帧长度 ( 比特 )}{ 数据传输速率 } \geq 2\tau

帧长度 ( 比特 )\geq 2\tau \times 数据传输速率

最小帧长度是

2\tau \times 数据传输速率

比特 ;

以太网规定最短帧长度是 64 字节 , 小于 64 字节的帧都是由于冲突终止的无效帧 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-08-19，如有侵权请联系 cloudcommunity@tencent.com 删除

二进制

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度