计算机网络——33多点访问协议

多点访问协议

多路访问链路和协议

两种类型的链路（一个子网内部链路连接形式）

• 点对点
  • 拨号访问的PPP
  • 以太网交换机和主机之间的点对点链路
• 广播
  • 传统以太网
  • HFC上行链路
  • 802.11无线局域网

多路访问协议

单个共享的广播型链路
2个过更多结点同时传送：冲突

• 多个结点在同一个时刻发送，则会收到2个或多个信号叠加

多路访问协议（介质访问控制协议：MAC）

• 分布式算法 - 决定节点如何使用共享信道，即：决定节点什么时候可以发送
• 关于共享控制的通信必须用借助信道本身传输
  • 没有外带的信道，各节点使用其协调信道使用
  • 用于传输控制信息

理想的多路访问协议

给定：Rbps的广播信道
必要条件

1. 当一个节点要发送时，可以R速率发送
2. 当M个节点要发送，每个可以以R/M的平均速率发送
3. 完全分布的
   • 没有特殊节点协调发送
   • 没有时钟和时隙的同步
4. 简单

MAC（媒体访问控制）协议：分类

3大类

• 信道划分
  • 把信道划分为小片（时间、频率、编码）
  • 分配片给每个节点专用
• 随机访问
  • 信道不划分，允许冲突
  • 冲突后恢复
• 依次轮流
  • 节点依次轮流
  • 但是有很多数据传输的节点可以获得较长的信道使用权

信道划分MAC协议

TDMA

TMDA：time division multiple access

• 轮流使用信道，信道的时间分为周期
• 每个站点使用每周期中固定的时隙（长度 = 帧传输时间）传输帧
• 如果站点无帧传输，时隙空闲 -> 浪费
• 如：6站LAN：1,3,4有数据报，时隙2,5,6空闲

FDMA

FDMA：frequency division multiple access

• 信道的有效频率范围被分为一个个小的频段
• 每个站点被分配一个固定的频段
• 分配给站点的频段如果没有被使用，则空闲
• 例如：6站的LAN，1,3,4有数据报，频段2,5,6空闲

码分多路访问（CDMA）

• CDMA(code division multiple access)
  • 所有站点在整个频段上同时进行传输，采用编码原理加以区分
  • 完全无冲突
  • 假定：信号同步很好，线性叠加
• 比方
  • TDM：不同的人在不同的时刻讲话
  • FDM：不同的组在不同的小房间里通信
  • CDMA：不同的人使用不同的语言讲话

随机存取协议

• 当节点有帧要发送时
  • 以信道带宽的全部R bps发送
  • 没有节点间的预先协调
• 两个或更多节点同时传输，会发生 -> 冲突
• 随机存取协议规定
  • 如何检测冲突
  • 如何从冲突中恢复（如：通过稍后的重传）
• 随机MAC协议
  • 时隙ALOHA
  • ALOHA
  • CSMA、CSMA/CD、CSMA/CA

时隙ALOHA

假设

• 所有的帧都是等长的
• 时间被划分成相等的时隙，每个时隙可发送一帧
• 节点只在时隙开始时发送帧
• 节点在时钟上是同步的
• 如果两个或多个节点在一个时隙传输，所有的站点都能检测到冲突

运行

• 当节点获取新的帧，在下一个时隙传输
• 传输时没有检测到冲突，成功
  • 节点能够在下一时刻发送新帧
• 检测时如果检测到冲突，失败
  • 节点在每一个随后的时隙以概率p重传帧直到成功

优点

• 节点可以以信道带宽全部连续传输
• 高度分布：仅需要节点之间在间隙上的同步
• 简单

缺点

• 存在冲突，浪费时间
• 即使有帧要发送，仍然有可能存在空闲的时隙
• 节点检测冲突的时间 < 帧传输的时间
  • 必须传完
• 需要时钟上同步

时隙ALOHA的效率

效率：当有很多节点，每个节点有很多帧要发送时，x%的时隙是成功传输帧的时隙

• 假设N个节点，每个节点都有很多帧要发送，在每个时隙中的传输概率是p
• 一个节点成功传输概率是$p(1-p{)}^{N-1}$
• 任何一个节点的成功概率是$Np(1-p{)}^{N-1}$
• N个节点的最大效率：求出使$f(P)=Np(1-p{)}^{N-1}$ 最大的$p^{\ast }$
• 代入$p^{\ast }$得到最大$f(p^{\ast })$
• N为无穷大时的极限为1/e = 0.37

最好情况，信道利用率为37%

纯ALOHA

• 无时隙ALOHA：简单、无需节点间在时间上同步
• 当有帧需要传输：马上传输
• 冲突的概率增加：
  • 帧在$t_0$发送，和其他在$[t_0 - 1,t_0 + 1]区间内开始发送的帧冲突
  • 和当前帧冲突的区间（其他帧再次区间开始传输）增大了一倍

纯ALOHA的效率

P(指定节点成功) = P(节点传输)
P(其他节点在$[t_0-1,t_0]$不传)
P(其他节点在$[t_0,t_0+1]$不传)
= $p\cdot (1-p{)}^{N-1}\cdot (1-p{)}^{N-1}=p\cdot (1-p{)}^{2(N-1)}$
选择最佳的p、N趋向无穷大
= 1/(2e) = 17.5%

效率比时隙ALOHA更差了

CSMA冲突

冲突仍然可能发生
由传播延迟造成：两个节点可能侦听不到正在进行的传输

冲突
整个冲突帧的传输时间都被浪费了，是无效的传输（红黄区域）

注意
传播延迟（距离）决定了冲突的概率
节点依据本地的信道使用情况来判断全部信道的使用情况

CSMA/CD（冲突检测）

CSMA/CD

• 载波倾听CSMA：和在CSMA中一样发送前倾听信道
• 没有传完一个帧就可以在短时间内检测到冲突
• 冲突发生时则传输终止，减少对信道的浪费

冲突检测CD技术，有线局域网中容易实现

• 检测信号强度，比较传输与接收到的信号是否相同
• 通过周期的过零点检测

人类类比：礼貌的对话人

以太网CSMA/CD算法

1. 适配器获取数据报，创建帧
2. 发送前：监听信道CS
   1. 闲：开始传输帧
   2. 忙：一直等到闲再发送
3. 发送过程中，冲突检测CD
   1. 没有冲突：成功
   2. 检测到冲突：放弃，之后尝试重发
4. 发送方适配器检测到冲突，除放弃外，还发送一个Jam信号，所有听到冲突的适配器也是如此
   强化冲突：让所有站点都知道冲突
5. 如果放弃，适配器进入指数退避状态
   在第m次失败后，适配器随机选择一个(0,1,2,…,$2^{m-1}$)中K，等待$K^{\ast }512$位时，然后转到步骤2
   exponential backoff 二进制指数退避算法

指数退避

• 目标：适配器试图适应当前负载，在一个变化的碰撞窗口中随机选择时间点尝试重发
  • 高负载：重传窗口时间大，减少冲突，但等待时间长
  • 低负载：使得各站点等待时间少，但冲突概率大
• 首次碰撞：在{0,1}选择K，延迟$K^{\ast }512$位时
• 第2次碰撞：在{0,1,2,3}选择K
• 第10次碰撞：在{0,1,2,3,…,1023}选择K

CSMA/CD效率

• $T_{prop}$ = LAN上2个节点的最大传播延迟
• $t_{trans}$ = 传输最大帧的时间
  $efficiency=\frac{1}{1+5t_{prop}/t_{trans}}$
• 效率变为1
  • 当$t_{prop}$变成0时
  • 当$t_{trans}$变为无穷大时
• 比起ALOHA更好的性能，而且简单，廉价，分布式

无线局域网CSMA/CA

WLAN构成

• 基站：AP
• 无线链路
• 移动主机节点

无线局域网中的MAC：CSMA/CA

• 冲突：$2^{+}$站点（AP或者站点）在同一时刻发送
• 802.11：CSMA - 发送前侦听信道
  • 不会和其他节点正在进行的传输发生冲突
• 802.11：没有冲突检测
  • 无法检测冲突：自身信号远远大于其他信号节点
  • 即使能CD：冲突 != 成功
  • 目标：avoid collisions：CSMA/C(collision)A(voidance)
    • 无法CD：一旦发送一股脑全部发送完毕，不CD
    • 为了避免无CD带来的信道利用率低的问题，事前进行冲突避免

无线局域网：CSMA/CA

发送方

1. 如果站点检测到信道空闲持续DIFS长，则传输整个帧(no CD)
2. 如果检测到信道忙碌，那么选择一个随机回退值，并在信道空闲时递减该值；如果信道忙碌，回退值不会变化；到数到0时（只生在信道闲时）发送整个帧，如果没有收到ACK，增加回退值并对之进行重复

802.11接收方

• 如果帧正确，则在SIFS后发送ACK

无线链路特性，需要每帧确认；例如：由于隐藏终端问题，在接收端可能形成干扰，接收方没有正确的收到，链路层可靠机制）

IEEE 802.11 MAC 协议：CSMA/CA

在count down时，侦听到了信道空闲为什么不发送，而要等到0时再发送

• 2个站点有数据帧需要发送，第三个节点正在发送
• LAN CD：让2者听完第三个节点发完，立即发送
  • 冲突：放弃当前的发送，避免了信道的浪费于无用冲突帧的发送
  • 代价不昂贵
• WLAN:CA
  • 无法CD，一旦发送就必须发完，如冲突信道浪费严重，代价高昂
  • 思想：尽量事先避免冲突，而不是在发生冲突时放弃然后重发
  • 听到发送的站点，分别选择随机值，回退到0发送
    • 不同的随机值，一个站点会胜利
    • 失败站点会冻结计数器，当胜利节点发完再发

无法完全避免冲突

• 两个站点相互隐藏
  • A，B相互隐藏，C在传输
  • A，B选择了随机回退值
  • 一个节点如A胜利了，发送
  • 而B节点收不到，顺利count down到0发送
  • A，B的发送在C附近形成了干扰
• 选择了非常靠近的随机回退值
  • A，B选择的值非常近
  • A到0后发送
  • 但是这个信号还没到达B时
  • B也到0了，发送
  • 冲突

冲突避免 RTS - CTS交换

思路：允许发送方“预约”信道，而不是随机访问该信道：避免长数据帧的冲突（可选项）

• 发送方首先使用CSMA向BS发送一个小的RTS分组
  • RTS可能会冲突（但是由于比较短，浪费信道较少）
• BS广播 clear - to - send CTS，作为RTS的相应
• CTS能够被所有涉及到的节点听到
  • 发送方发送数据帧
  • 其他节点抑制发送

采用小的预约分组，可以完全避免数据帧的冲突

线缆接入网络

• 多个40Mps 下行（广播）信道，FDM
  • 下行：通过FDM分成若干信道，互联网、数字电视等
  • 互联网信道：只有1个CMTS在其上传输
• 多个30Mps 上行的信道，FDM
  • 多路访问：所有用户使用：接着TDM分成微时隙
  • 部分时隙分配，部分时隙竞争

DOCSIS：TDM上行信道

• 采用TDM的方式将上行信道分成若干微时隙：MAP指定
• 站点采用分配给他的微时隙上行数据传输：分配
• 在特殊的上行微时隙中，各站点请求上行微时隙：竞争
  • 各站点对于该时隙的使用是随机访问的
  • 一旦碰撞（请求不成功，结果是：在下行的MAP中没有为他分配，则二进制退避）选择时隙上传输

轮流 MAC 协议

信道划分MAC协议：

• 共享信道在高负载时是有效和公平的
• 在低负载时效率低下
  • 只能等到自己的时隙开始发送或者利用1/N的信道频率发送
  • 当只有一个节点有帧传时，也只能够得到1/N个带宽分配

随机访问MAC协议

• 在低负载时效率高：单个节点完全可以利用信道全部带宽
• 高负载时，冲突开销较大，效率极低，时间很多浪费在冲突中

轮流协议

• 有二者的优点

轮询

• 主节点邀请从节点依次传送
• 从节点一般比较“dumb”
• 缺点
  • 轮询开销：轮训本身消耗信道带宽
  • 等待时间：每个节点需等到主节点轮询后开始传输，即使只有一个节点，也需要等到轮询一周后才能够发送
  • 单点故障：主节点失效时造成整个系统无法工作

令牌传递

• 控制令牌(token)循环从一个节点到下一个节点传递
• 令牌报文：特殊的帧
• 缺点
  • 令牌开销：本身消耗带宽
  • 延迟：只有等到抓住令牌，才可传输
  • 单点故障
    • 令牌丢失系统级故障，整个系统无法传输
    • 复杂机制重新生成令牌