文章目录
一、 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, BA,B 两台主机 , 两个站点 单程 端到端 , 电磁波 从 A AA 到 B BB 传播 , 需要 t tt 纳秒 ;
② A AA 发送数据到 B BB 一半 : 0 00 纳秒 时刻 , A AA 向 B BB 发送数据时 , 预计 t tt 纳秒后 , 到达到 B BB 站点 ;
③ B BB 发送数据到 A AA : B BB 在 t 2 \cfrac{t}{2}
2
t
纳秒 时刻 , 突然 A AA 发送数据 , 此时检测到信道没有电磁波 , 因为此时电磁波还没有到达 B BB 站点 ; 因此检测到信道没有信号传输 ;
④ 出现冲突 : B BB 如果传输数据 , 肯定会在某时刻与 A AA 已经发送的数据 产生冲突 ; 此时时刻时 3 t 4 \cfrac{3t}{4}
4
3t
纳秒
⑤ 碰撞 : B BB 的信号 与 A AA 的信号叠加在一起 , 称为碰撞 ; 此时两个信号都被污染了 , 无法解析使用 ;
⑥ B BB 站点检测到碰撞 : B BB 接收到 碰撞后的信号 , 校验肯定不通过 , 出现帧错误 , 此时检测到发生了碰撞 , B BB 站点暂停数据发送 ; 该时刻是 t tt 纳秒 ;
⑦ A AA 站点检测到碰撞 : A AA 接收到 碰撞后的信号 , 校验肯定不通过 , 出现帧错误 , 此时检测到发生了碰撞 , A AA 站点暂停数据发送 ; 此时时刻时 3 t 2 \cfrac{3t}{2}
2
3t
纳秒
三、 单程端到端传播时延 相关概念
引入一组概念 :
① 单程端到端传播时延 : 记作 τ \tauτ ;
② 碰撞检测最长时间 : 站点发出数据后 , 最多 两倍的 单程端到端时延 2 τ 2\tau2τ 后就可以得知出现了碰撞 ;
③ 2 τ 2\tau2τ 概念 : 又称为 , 总线端到端往返传播时延 , 争用期 , 冲突窗口 , 碰撞窗口 ;
只要经过 2 τ 2\tau2τ 没有检测到碰撞 , 本次发送 , 一定没有碰撞 ;
四、 碰撞后重传时机 ( 截断二进制指数规避算法 )
截断二进制指数规避算法 :
① 争用期 : 确定基本退避时间 , 也就是争用期 , 两倍的 单程端到端传播时延 2 τ 2\tau2τ ;
② 重传次数 : 定义参数 k kk , 一定程度上相当于重传次数 ;
k kk 公式 : k kk 取值不超过 10 1010 , 公式为 k = m i n ( 重 传 次 数 , 10 ) k=min( 重传次数 , 10 )k=min(重传次数,10) ;
当重传次数 不超过 10 1010 时 : k = 重 传 次 数 k = 重传次数k=重传次数
当重传次数 大于 10 1010 时 : k = 10 k=10k=10 ;
③ 取随机数 : 从整数集合 [ 0 , 2 k − 1 ] [0, 2^k - 1][0,2
k
−1] 中 , 取出随机数 r rr , 重传时间就是 r × 2 τ r \times 2\taur×2τ ;
④ 重传次数限制 : 当重传 16 1616 次都失败时 , 说明网络拥塞严重 , 直接丢弃该帧 , 向上层报告出错 ;
示例 :
① 第 1 11 次重传 , k = 1 k=1k=1 , 从
[ 0 , 1 ] [0, 1][0,1] 区间中 , 即 { 0 , 1 } \{ 0 , 1\}{0,1}
中随机取一个值 , r rr ;
如果 r = 0 r = 0r=0 , 重传时间是 0 00 ;
如果 r = 1 r = 1r=1 , 重传时间是 2 τ 2\tau2τ ;
② 第 1 11 次重传 , k = 2 k=2k=2 , 从
[ 0 , 3 ] [0, 3][0,3] 区间中 , 即 { 0 , 1 , 2 , 3 } \{ 0 , 1 , 2 ,3\}{0,1,2,3}
中随机取一个值 , r rr ;
如果 r = 0 r = 0r=0 , 重传时间是 0 00 ;
如果 r = 1 r = 1r=1 , 重传时间是 2 τ 2\tau2τ ;
如果 r = 2 r = 2r=2 , 重传时间是 4 τ 4\tau4τ ;
如果 r = 3 r = 3r=3 , 重传时间是 6 τ 6\tau6τ ;
③ 第 3 33 次重传 , k = 3 k=3k=3 , 从
[ 0 , 7 ] [0, 7][0,7] 区间中 , 即 { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } \{ 0 , 1 , 2 ,3 , 4, 5, 6, 7\}{0,1,2,3,4,5,6,7}
中随机取一个值 , r rr ;
如果 r = 0 r = 0r=0 , 重传时间是 0 00 ;
如果 r = 1 r = 1r=1 , 重传时间是 2 τ 2\tau2τ ;
如果 r = 2 r = 2r=2 , 重传时间是 4 τ 4\tau4τ ;
如果 r = 3 r = 3r=3 , 重传时间是 6 τ 6\tau6τ ;
如果 r = 4 r = 4r=4 , 重传时间是 8 τ 8\tau8τ ;
如果 r = 5 r = 5r=5 , 重传时间是 10 τ 10\tau10τ ;
如果 r = 6 r = 6r=6 , 重传时间是 12 τ 12\tau12τ ;
如果 r = 7 r = 7r=7 , 重传时间是 14 τ 14\tau14τ ;
五、截断二进制指数规避算法 计算示例
在 以太网 二进制回退算法中 , 碰撞 11 1111 次后 , 随机数 r rr 的选择范围是多少 ? ??
随机数 r rr 是根据 参数 k kk 确定的 , 参数 k kk 是重传次数 和 10 1010 中较小的值 , 重传次数 小于等于 10 1010 次时 , k = 重 传 次 数 k = 重传次数k=重传次数 , 重传次数大于等于 11 1111 次时 , k = 10 k = 10k=10 ;
随机数 r rr 的取值范围是 [ 0 , 2 k − 1 ] [0, 2^k - 1][0,2
k
−1] , 代入 k = 10 k=10k=10 ;
取值范围是 [ 0 , 2 10 − 1 ] [0 , 2^{10} - 1][0,2
10
−1] , 随机数 r rr 的 范围 是 [ 0 , 1023 ] [0 , 1023][0,1023] 之间的值 ;
六、最小帧长问题
检测到碰撞时 , 需要暂停帧的发送 , 如果帧太短 , 就会导致一次性发送完毕 , 无法暂停 , 这里需要在检测到碰撞时 , 帧还没有发送结束 ;
帧的传输时延 至少要 大于 2 τ 2\tau2τ ;
帧 的 传 输 时 延 = 帧 长 度 ( 比 特 ) 数 据 传 输 速 率 帧的传输时延 = \cfrac{帧长度 ( 比特 )}{ 数据传输速率 }帧的传输时延=
数据传输速率
帧长度(比特)
帧 长 度 ( 比 特 ) 数 据 传 输 速 率 ≥ 2 τ \cfrac{帧长度 ( 比特 )}{ 数据传输速率 } \geq 2\tau
数据传输速率
帧长度(比特)
≥2τ
帧 长 度 ( 比 特 ) ≥ 2 τ × 数 据 传 输 速 率 帧长度 ( 比特 )\geq 2\tau \times 数据传输速率帧长度(比特)≥2τ×数据传输速率
最小帧长度是 2 τ × 数 据 传 输 速 率 2\tau \times 数据传输速率2τ×数据传输速率 比特 ;
以太网 规定 最短帧长度是 64 字节 , 小于 64 字节的帧都是由于冲突终止的无效帧 ;
