五、介质访问控制 ★★
1、介质访问控制 ★
介质访问控制 : 使 广播网络 中 , 两个节点之间的通信不会发生干扰的措施 ; 可以划分为以下两种类型 :
静态划分信道
动态划分信道
静态划分信道 : 信道划分 介质访问控制 ;
① 频分多路复用 FDM ( Frequency )
② 时分多路复用 TDM ( Time )
③ 波分多路复用 WDM ( Wave )
④ 码分多路复用 CDM ( Code )
动态分配信道 :
① 轮询访问 介质访问控制 : 令牌环传递协议 ;
② 随机访问 介质访问控制 :
ALOHA 协议
CSMA 协议
CSMA / CD 协议
CSMA / CA 协议
参考博客 : 【计算机网络】数据链路层 : 信道划分 介质访问控制 ( 数据链路 | 介质访问控制分类 | 频分多路复用 FDM | 时分多路复用 TDM | 波分复用 WDM | 码分多路复用 CDM 计算 )★
2、静态划分信道 ★
1 . 频分多路复用 FDM :
① 一直持有频带 : 用户 分配到 频带 后 , 通信过程中 一直占用该 频带 ;
② 频率带宽资源 ( Hz ) : 频分复用 所有用户 , 同样式样 占用 不同的 频率带宽 资源 , 频率带宽是 赫兹 单位 ;
频分多路复用 FDM 优点 :
① 效率高 : 充分利用 介质 带宽 , 传输 效率 较高 ;
② 实现简单 : 该技术比较成熟 , 实现简单 ;
2 . 时分多路复用 TDM :
① 划分等长帧 : 将 时间 划分为 若干 等长 的 时分复用帧 ( TDM 帧 ) ;
② TDM 帧 : 是在 物理层 传送的 比特流 所划分的帧 , 标志一个周期 ;
③ 固定时隙 : 每个 时分复用 用户 , 在每个 TDM 帧 中 , 占用 固定序号的时隙 ;
④ 轮流使用 : 所有用户 轮流 占用信道 ;
整个信道的速率是 8000 比特 / 秒 , 如果将信道划分为 4 44 个 TDM 帧 , 那么每个用户的速率最高是 2000 比特 / 秒 ;
3 . 波分复用 WDM :
① 本质 : 光的 频分多路复用 ;
② 不同波长光 : 在光纤中 , 传输 多种 不同 波长的 光信号 , 波长不同 , 各路光信号互不干扰 ;
③ 分离信号 : 使用 波长分解复用器 将 各路播放分解出来 ;
4 . 码分多路复用 CDM :
码分多址 ( CDMA ) 是 码分多路复用 CDM 的一种重要形式 ;
1 11 个 比特 分为 多个 码片 ( 芯片 ) , 每个站点被指定一个唯一的 m mm 位 芯片序列 ;
发送 1 11 时 , 站点发送 芯片序列 , 发送 0 00 时 , 站点发送 芯片序列 反码 ;
A , B A , BA,B 两个主机 , 发送数据到 C CC 主机 ;
主机 A AA 发送 0 00 数据 , 主机 B BB 发送 1 11 数据 , 其发送的每个 比特 , 都对应一个 m mm 位的 芯片序列 , 一般情况下 芯片序列的长度是 64 6464 或 128 128128 位 , 这里为了方便演示 , 设置芯片序列 长度为 8 88 位 ;
数据不冲突 前提 ( 芯片序列正交 ) : 多个站点 , 同时发出数据时 , 各个站点 , 芯片序列 必须满足 相互正交 的前提 ; 只要芯片正交 , 就不会出现冲突 ;
芯片序列正交 计算 : 芯片序列 对应位 相乘 , 然后相加 , 除以总位数 ;
数据合并 : 将信道中的 芯片序列 按位 线性相加 , 合并后的芯片序列位数相同 ;
数据分离 : 合并的数据 和 源站芯片序列 规格化内积 ;
规格化内积计算 : 合并后的数据 与 源站芯片序列 , 按位相乘 , 再相加 , 最后除以 芯片序列位数 , 如果得到 + 1 +1+1 说明是数据 1 11 , 如果得到 − 1 -1−1 说明是数据 0 00 ;
芯片序列 与 芯片序列 反码 :
A AA 主机中的 1 11 数据 , 对应 芯片序列 ( + 1 , − 1 , − 1 , + 1 , + 1 , + 1 , + 1 , − 1 ) ( +1 , -1 , -1 , +1 , +1 , +1 , +1 , -1 )(+1,−1,−1,+1,+1,+1,+1,−1) ;
A AA 主机中的 0 00 数据 , 对应 芯片序列 ( − 1 , + 1 , + 1 , − 1 , − 1 , − 1 , − 1 , + 1 ) ( -1 , +1 , +1 , -1 , -1 , -1 , -1 , +1 )(−1,+1,+1,−1,−1,−1,−1,+1) , 0 00 数据的芯片序列是 1 11 数据芯片序列的反码 ;
B BB 主机中的 1 11 数据 , 对应 芯片序列 ( − 1 , + 1 , − 1 , + 1 , − 1 , + 1 , + 1 , + 1 ) ( -1 , +1 , -1 , +1 , -1 , +1 , +1 , +1 )(−1,+1,−1,+1,−1,+1,+1,+1) ;
B BB 主机中的 0 00 数据 , 对应 芯片序列 ( + 1 , − 1 , + 1 , − 1 , + 1 , − 1 , − 1 , − 1 ) ( +1 , -1 , +1 , -1 , +1 , -1 , -1 , -1 )(+1,−1,+1,−1,+1,−1,−1,−1) , 0 00 数据的芯片序列是 1 11 数据芯片序列的反码 ;
芯片序列正交 验证 计算 : 如果 A , B A,BA,B 两台主机之间的芯片序列可以正交 , 那么其发送数据就不会冲突 ;
主机 A AA 的 1 11 数据 芯片序列 ( + 1 , − 1 , − 1 , + 1 , + 1 , + 1 , + 1 , − 1 ) ( +1 , -1 , -1 , +1 , +1 , +1 , +1 , -1 )(+1,−1,−1,+1,+1,+1,+1,−1) , 与
主机 B BB 中 1 11 数据 芯片序列 ( − 1 , + 1 , − 1 , + 1 , − 1 , + 1 , + 1 , + 1 ) ( -1 , +1 , -1 , +1 , -1 , +1 , +1 , +1 )(−1,+1,−1,+1,−1,+1,+1,+1) 正交 ;
正交计算 : 每个对应位 按位相乘 , 然后相加 , 除以位数 ; 如果为 0 00 , 说明两个芯片序列正交 ;
( + 1 × − 1 ) + ( − 1 × + 1 ) + ( − 1 × − 1 ) + ( + 1 × + 1 ) + ( + 1 × − 1 ) + ( + 1 × + 1 ) + ( + 1 × + 1 ) + ( − 1 × + 1 ) 8 = − 1 + ( − 1 ) + 1 + 1 + ( − 1 ) + 1 + 1 + ( − 1 ) 8 = 0
(+1×−1)+(−1×+1)+(−1×−1)+(+1×+1)+(+1×−1)+(+1×+1)+(+1×+1)+(−1×+1)8=−1+(−1)+1+1+(−1)+1+1+(−1)8=0
(+1×−1)+(−1×+1)+(−1×−1)+(+1×+1)+(+1×−1)+(+1×+1)+(+1×+1)+(−1×+1)8=−1+(−1)+1+1+(−1)+1+1+(−1)8=0
8
(+1×−1)+(−1×+1)+(−1×−1)+(+1×+1)+(+1×−1)+(+1×+1)+(+1×+1)+(−1×+1)
=
8
−1+(−1)+1+1+(−1)+1+1+(−1)
=0
数据合并 : 将 芯片数据 线性相加即可 ;
A AA 主机发送 0 00 数据 , B BB 主机发送 1 11 数据 , 那么对应的合并的数据是 :
A AA 主机 0 00 数据对应芯片序列 ( − 1 , + 1 , + 1 , − 1 , − 1 , − 1 , − 1 , + 1 ) ( -1 , +1 , +1 , -1 , -1 , -1 , -1 , +1 )(−1,+1,+1,−1,−1,−1,−1,+1)
B BB 主机 1 11 数据对应芯片序列 ( − 1 , + 1 , − 1 , + 1 , − 1 , + 1 , + 1 , + 1 ) ( -1 , +1 , -1 , +1 , -1 , +1 , +1 , +1 )(−1,+1,−1,+1,−1,+1,+1,+1)
( − 1 − 1 , + 1 + 1 , + 1 − 1 , − 1 + 1 , − 1 − 1 , − 1 + 1 , − 1 + 1 , + 1 + 1 ) = ( − 2 , + 2 , 0 , 0 , − 2 , 0 , 0 , + 2 )
(−1−1,+1+1,+1−1,−1+1,−1−1,−1+1,−1+1,+1+1)=(−2,+2,0,0,−2,0,0,+2)
(−1−1,+1+1,+1−1,−1+1,−1−1,−1+1,−1+1,+1+1)=(−2,+2,0,0,−2,0,0,+2)
(−1−1,+1+1,+1−1,−1+1,−1−1,−1+1,−1+1,+1+1)
=(−2,+2,0,0,−2,0,0,+2)
数据分离 :
C CC 设备收到 ( − 2 , + 2 , 0 , 0 , − 2 , 0 , 0 , + 2 ) ( -2 , +2 , 0, 0 , -2, 0 , 0 , +2)(−2,+2,0,0,−2,0,0,+2) 芯片序列 , 将该序列与 A AA 主机 芯片序列 进行 规格化内积 ;
规格化内积 : 对应位相乘 , 求总和 , 然后除以 芯片序列 总的位数 8 88 ;
规格化内积 计算过程 : 对应位相乘 , 然后将 8 88 个相乘结果相加 , 最后除以 8 88 ;
主机 A AA 芯片序列是 ( + 1 , − 1 , − 1 , + 1 , + 1 , + 1 , + 1 , − 1 ) ( +1 , -1 , -1 , +1 , +1 , +1 , +1 , -1 )(+1,−1,−1,+1,+1,+1,+1,−1) ;
规 格 化 内 积 = ( − 2 , + 2 , 0 , 0 , − 2 , 0 , 0 , + 2 ) ∙ ( + 1 , − 1 , − 1 , + 1 , + 1 , + 1 , + 1 , − 1 ) = ( − 2 × + 1 ) + ( + 2 × − 1 ) + ( 0 × − 1 ) + ( 0 × + 1 ) + ( − 2 × + 1 ) + ( 0 × + 1 ) + ( 0 × + 1 ) + ( + 2 × − 1 ) 8 = − 2 − 2 + 0 + 0 − 2 + 0 + 0 + − 2 8 = − 1
规格化内积=(−2,+2,0,0,−2,0,0,+2)∙(+1,−1,−1,+1,+1,+1,+1,−1)=(−2×+1)+(+2×−1)+(0×−1)+(0×+1)+(−2×+1)+(0×+1)+(0×+1)+(+2×−1)8=−2−2+0+0−2+0+0+−28=−1
规格化内积=(−2,+2,0,0,−2,0,0,+2)∙(+1,−1,−1,+1,+1,+1,+1,−1)=(−2×+1)+(+2×−1)+(0×−1)+(0×+1)+(−2×+1)+(0×+1)+(0×+1)+(+2×−1)8=−2−2+0+0−2+0+0+−28=−1
规格化内积=(−2,+2,0,0,−2,0,0,+2)∙(+1,−1,−1,+1,+1,+1,+1,−1)
=
8
(−2×+1)+(+2×−1)+(0×−1)+(0×+1)+(−2×+1)+(0×+1)+(0×+1)+(+2×−1)
=
8
−2−2+0+0−2+0+0+−2
=−1
计算结果是 − 1 -1−1 , 说明 主机 A AA 发送的数据是 0 00 ;
参考博客 : 【计算机网络】数据链路层 : 信道划分 介质访问控制 ( 数据链路 | 介质访问控制分类 | 频分多路复用 FDM | 时分多路复用 TDM | 波分复用 WDM | 码分多路复用 CDM 计算 )★
3、动态划分信道 ( 轮询访问 ) ★
令牌传递协议 :
① 令牌帧 : 特殊格式的 MAC 控制帧 , 没有任何信息 ;
② 令牌 作用 : 控制信道使用 , 确保 同一时刻 , 只有一个站点 独占信道 ;
③ 发送数据前提 : 每个节点 都可以在 令牌持有时间内 , 获得发送数据的权利 , 该时间并不是无限持有的 , 有时间限制 ;
令牌传递协议 特点 :
① 优点 : 令牌环网 没有 数据碰撞冲突 ;
② 缺点 :
令牌开销
等待延迟
单点故障
令牌传递协议 应用场景 : 令牌传递协议 应用于 令牌环网 ;
物理上是 星型拓扑 结构
逻辑上是 环形拓扑 结构
令牌传递协议 , 常用于负载较重 , 通信量较大的网络 ;
参考博客 : 【计算机网络】数据链路层 : 轮询访问 介质访问控制 ( 轮询协议 | 令牌传递协议 )
4、动态划分信道 ( 随机访问 ) ★
1 . ALOHA 协议
( 1 ) 纯 ALOHA 协议 :
不 监听 信道 ;
随机发送 : 不按照 时间槽 发送 , 也就是随机发送 ;
想发就发 ;
冲突检测、处理 :
① 出现冲突 : 如果发送时 , 出现了冲突 , 数据被丢弃 , 或部分出错 , 发送失败 ;
② 接收方处理 : 接收方没有收到数据 , 或 收到错误数据 , 那么向发送方 发送 错误信息 , 或者 干脆 不回送 确认信息 ;
③ 发送方处理 : 如果 发送方在 超时时间 内 没有收到 接收方的 确认信息 , 那么就重传之前的数据 ;
( 2 ) 时隙 ALOHA 协议 :
① 时间片分割 : 将 时间 分成 若干 相同的时间片 ;
② 接入信道 : 所有 用户 在 每个时间片开始时 , 同步接入网络信道 ;
③ 冲突机制 : 如果 接入信道时 某 用户 与 其它用户 发生冲突 , 那么 等到下一个时间片再开始发送 ;
参考博客 : 【计算机网络】数据链路层 : ALOHA 协议 ( 纯 ALOHA 协议 | 时隙 ALOHA 协议 )
2 . CSMA 协议 ( 载波监听多路访问协议 )
CSMA 协议 :
① 全称 : Carrier Sense Multiple Access , 载波监听多路访问协议 ;
② CS : Carrier Sense , 载波监听 , 每个站点 发送数据前 , 先检测总线上是否有其它 站点 在发送数据 ;
③ MA : 多点接入 , 多个 主机 连接在同一条 总线 上 ;
ALOHA 协议 与 CSMA 协议 对比 :
ALOHA 协议 , 不听就说 ;
CSMA 协议 , 先听再说 ;
参考博客 : 【计算机网络】数据链路层 : CSMA 协议 ( 载波监听多路访问协议 | 监听 | 1-坚持 CSMA | 非坚持 CSMA | p-坚持 CSMA )
3 . 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 协议 , 先听再说 , 边听边说 ;
参考博客 : 【计算机网络】数据链路层 : CSMA/CD 协议 ( 载波监听多点接入 / 碰撞检测 协议 | 单程端到端传播时延 | 截断二进制指数规避算法 | 计算示例 | 最小帧长问题 )★
4 . CSMA/CA 协议 : ( 仅作了解 )
① 全称 : Carrier Sense Multiple Access With Collision Avoidance , 载波监听多点接入 / 碰撞避免 协议 ;
② CS : Carrier Sense , 载波监听 , 每个站点 发送数据前 , 和 发送数据过程中 , 先检测总线上是否有其它 站点 在发送数据 ;
③ MA : Multiple Access , 多点接入 , 多个 主机 连接在同一条 总线 上 ; 该协议 应用于 总线型网络 中 ;
④ CA : Collision Avoidance , 碰撞避免 ;
随机访问 介质访问控制 协议 对比 :
ALOHA 协议 , 不听就说 ;
CSMA 协议 , 先听再说 ;
CSMA/CD 协议 , 先听再说 , 边听边说 ;
CSMA/CA 协议 , 先听再说 , 边听边说 ;
参考博客 : 【计算机网络】数据链路层 : CSMA/CA 协议 ( 载波监听多点接入 / 碰撞避免 协议 | CSMA/CA 协议工作原理 | CSMA/CD 协议 与 CSMA/CA 协议对比 )
5、CSMA/CD 相关计算 ★
1 . 引入一组概念 :
① 单程端到端传播时延 : 记作 τ \tauτ ;
② 碰撞检测最长时间 : 站点发出数据后 , 最多 两倍的 单程端到端时延 2 τ 2\tau2τ 后就可以得知出现了碰撞 ;
③ 2 τ 2\tau2τ 概念 : 又称为 , 总线端到端往返传播时延 , 争用期 , 冲突窗口 , 碰撞窗口 ;
只要经过 2 τ 2\tau2τ 没有检测到碰撞 , 本次发送 , 一定没有碰撞 ;
2 . 截断二进制指数规避算法 :
① 争用期 : 确定基本退避时间 , 也就是争用期 , 两倍的 单程端到端传播时延 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τ ;
3 . 截断二进制指数规避算法 计算示例 :
在 以太网 二进制回退算法中 , 碰撞 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] 之间的值 ;
4 . 最小帧长问题
检测到碰撞时 , 需要暂停帧的发送 , 如果帧太短 , 就会导致一次性发送完毕 , 无法暂停 , 这里需要在检测到碰撞时 , 帧还没有发送结束 ;
帧的传输时延 至少要 大于 2 τ 2\tau2τ ;
帧 的 传 输 时 延 = 帧 长 度 ( 比 特 ) 数 据 传 输 速 率 帧的传输时延 = \cfrac{帧长度 ( 比特 )}{ 数据传输速率 }帧的传输时延=
数据传输速率
帧长度(比特)
帧 长 度 ( 比 特 ) 数 据 传 输 速 率 ≥ 2 τ \cfrac{帧长度 ( 比特 )}{ 数据传输速率 } \geq 2\tau
数据传输速率
帧长度(比特)
≥2τ
帧 长 度 ( 比 特 ) ≥ 2 τ × 数 据 传 输 速 率 帧长度 ( 比特 )\geq 2\tau \times 数据传输速率帧长度(比特)≥2τ×数据传输速率
最小帧长度是 2 τ × 数 据 传 输 速 率 2\tau \times 数据传输速率2τ×数据传输速率 比特 ;
以太网 规定 最短帧长度是 64 字节 , 小于 64 字节的帧都是由于冲突终止的无效帧 ;
