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

2023-03-28 17:00:50 浏览数 (1)

文章目录

  • 一、 CSMA/CD 协议
  • 二、 传播时延对于 载波监听 的影响
  • 三、 单程端到端传播时延 相关概念
  • 四、 碰撞后重传时机 ( 截断二进制指数规避算法 )
  • 五、截断二进制指数规避算法 计算示例
  • 六、最小帧长问题

一、 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

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

A

到

B

传播 , 需要

t

纳秒 ;

②

A

发送数据到

B

一半 :

0

纳秒 时刻 ,

A

向

B

发送数据时 , 预计

t

纳秒后 , 到达到

B

站点 ;

③

B

发送数据到

A

:

B

在

cfrac{t}{2}

纳秒 时刻 , 突然

A

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

B

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

④ 出现冲突 :

B

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

A

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

cfrac{3t}{4}

纳秒

⑤ 碰撞 :

B

的信号 与

A

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

⑥

B

站点检测到碰撞 :

B

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

B

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

t

纳秒 ;

⑦

A

站点检测到碰撞 :

A

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

A

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

cfrac{3t}{2}

纳秒

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

引入一组概念 :

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

tau

;

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

2tau

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

③

2tau

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

只要经过

2tau

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

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

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

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

2tau

;

② 重传次数 : 定义参数

k

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

k

公式 :

k

取值不超过

10

, 公式为

k=min( 重传次数 , 10 )

;

  • 当重传次数 不超过
10

时 :

k = 重传次数
  • 当重传次数 大于
10

时 :

k=10

;

③ 取随机数 : 从整数集合

[0, 2^k - 1]

中 , 取出随机数

r

, 重传时间就是

r times 2tau

;

④ 重传次数限制 : 当重传

16

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

示例 :

① 第

1

次重传 ,

k=1

, 从

[0, 1]

区间中 , 即

{ 0 , 1}

中随机取一个值 ,

r

;

  • 如果
r = 0

, 重传时间是

0

;

  • 如果
r = 1

, 重传时间是

2tau

;

② 第

1

次重传 ,

k=2

, 从

[0, 3]

区间中 , 即

{ 0 , 1 , 2 ,3}

中随机取一个值 ,

r

;

  • 如果
r = 0

, 重传时间是

0

;

  • 如果
r = 1

, 重传时间是

2tau

;

  • 如果
r = 2

, 重传时间是

4tau

;

  • 如果
r = 3

, 重传时间是

6tau

;

③ 第

3

次重传 ,

k=3

, 从

[0, 7]

区间中 , 即

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

中随机取一个值 ,

r

;

  • 如果
r = 0

, 重传时间是

0

;

  • 如果
r = 1

, 重传时间是

2tau

;

  • 如果
r = 2

, 重传时间是

4tau

;

  • 如果
r = 3

, 重传时间是

6tau

;

  • 如果
r = 4

, 重传时间是

8tau

;

  • 如果
r = 5

, 重传时间是

10tau

;

  • 如果
r = 6

, 重传时间是

12tau

;

  • 如果
r = 7

, 重传时间是

14tau

;

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

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

11

次后 , 随机数

r

的选择范围是多少

?

随机数

r

是根据 参数

k

确定的 , 参数

k

是重传次数 和

10

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

10

次时 ,

k = 重传次数

, 重传次数大于等于

11

次时 ,

k = 10

;

随机数

r

的取值范围是

[0, 2^k - 1]

, 代入

k=10

;

取值范围是

[0 , 2^{10} - 1]

, 随机数

r

的 范围 是

[0 , 1023]

之间的值 ;

六、最小帧长问题

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

帧的传输时延 至少要 大于

2tau

;

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

最小帧长度是

2tau times 数据传输速率

比特 ;

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

二进制 数据 算法 网络 协议

0 人点赞