2.2、广播链路MAC协议.md

# 广播链路MAC协议

两种类型链路

* 点到点链路：PPP、HDLC

* 广播链路

  <img src="https://img-blog.csdnimg.cn/2021011219274741.png" alt="image-20210104211457235"  width="40%"/>

  * 多台主机连接到同一个、共享的广播信道上
  * 一台主机发送数据（帧），其他节点都能收到



多路访问协议

* 碰撞/冲突（collision）：多个节点同时发送帧，这些帧相互干扰，导致接收方都不能正确收到帧。
* 多路访问问题：如何协调多台主机之间的通信？



三类协议

* 信道划分协议

  * 多路复用技术（时间、频带、码片划分）
  * FDMA、TDMA、WDMA、CDMA

* 随机访问协议

  * 信道不划分，允许冲突，等待一个随机时延再发送，直到发送成功
  * ALOHA、S-ALOHA、CSMA、CSMA/CD
    * CSMA/CD应用于以太网
    * CSMA/CA应用802.11无线局域网

* 轮流协议

  * 轮询协议：指定主节点，循环的方式轮询每个节点（ZigBee协议，蓝牙协议）
  * 令牌传递协议：没有主节点，令牌（token）在节点之间以某个固定的次序交换（光纤分布式接口FDDI协议，IEEE802.5令牌环协议）



## 信道划分MAC 协议

* TDMA: time division multiple access
  * “周期性”接入信道
  * 每个站点在每个周期，占用固定长度的时隙(e.g.长度=分组传输时间)
  * 未用时隙空闲(idle)
  * 例如：6-站点LAN，1,3,4传输分组，2,5,6空闲

* 道划分MAC 协议：FDMA
  * 信道频谱划分为若干频带(frequency bands)
  * 每个站点分配一个固定的频带
  * 无传输频带空闲
  * 例如: 6站点LAN, 1,3,4频带传输数据, 2,5,6频带空闲。



## 随机访问MAC 协议

* 当结点要发送分组时：
  * 利用信道全部数据速率R发送分组
  * 没有事先的结点间协调
* 两个或多个结点同时传输：➜ “冲突”
* 随机访问MAC协议需要定义:
  * 如何检测冲突
  * 如何从冲突中恢复 (e.g., 通过延迟重传)
* 典型的随机访问MAC协议：
  * 时隙(sloted)ALOHA
  * ALOHA
  * CSMA、CSMA/CD、CSMA/CA



时隙ALOHA 协议

<img src="https://img-blog.csdnimg.cn/20210112192809892.png" alt="image-20210104224235741"  width="40%"/>

* 假定：
  * 所有帧大小相同
  * 时间被划分为等长的时隙 (每个时隙可以传输1个帧)
  * 结点只能在时隙开始时刻发送帧
  * 结点间时钟同步
  * 如果2个或2个以上结点在同一时隙发送帧，结点即检测到冲突
* 运行:
  * 当结点有新的帧时，在下一个时隙(slot)发送
  * 如果无冲突：该结点可以在下一个时隙继续发送新的帧
  * 如果冲突：该结点在下一个时隙以概率p重传该帧，直至成功
* 优缺点:
  * 优点
    * 单个结点活动时，可以连续以信道全部速率传输数据
    * 高度分散化：只需同步时隙
    * 简单
  * 缺点:
    * 冲突，浪费时隙
    * 空闲时隙
    * 结点也许能以远小于分组传输时间检测到冲突
    * 时钟同步
* 效率(efficiency) :  长期运行时，成功发送帧的时隙所占比例 ( 很多结点，有很多帧待发送)
  * 假设: N个结点有很多帧待传输，每个结点在每个时隙均以概率p发送数据
  * 对于给定的一个结点，在一个时隙将帧发送成功的概率= $p(1-p)^{N-1}$
  * 对于任意结点成功发送帧的概率= $Np(1-p)^{N-1}$
  * 最大效率: 求得使$Np(1-p)^{N-1}$ 最大的p*
  * 对于很多结点，求$Np*(1-p*)^{N-1}$当N趋近无穷时的极限，可得最大效率= 1/e = 0.37



ALOHA 协议

<img src="https://img-blog.csdnimg.cn/20210112192631395.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" alt="image-20210104224941738"  width="40%"/>

* 非时隙(纯)Aloha：更加简单，无需同步

* 有新的帧生成时：立即发送

* 冲突可能性增大：在t0 时刻发送帧，会与在[t0 -1, t0 +1]期间其他结点发送的帧冲突

* 效率

  P(给定结点成功发送帧) = P(该结点发送) * P(无其他结点在[t0 -1, t0 ]期间发送帧)*P(无其他结点在[t0 , t0 +1]期间发送帧)
  = p * $(1-p)^{N-1}$ * $(1-p)^{N-1}$
  = p*$(1-p)^{2(N-1)}$



ALOHA

* ALOHAnet

  * 中心主机
  * 分散在夏威夷各岛上的二级节点两个信道（不同的频段）：上行信道和下行信道

* ALOHA协议

  * 节点有数据，立即发送
  * 如碰撞（没有收到中央主机返回的确认帧），等待随机时间重发
  * 每个节点等待的随机时间不同，降低第二次冲突的概率

* 吞吐率（效率）：在单位时间（一个帧时），一个节点成功传输帧的概率 1/2e =0.18（时隙ALOHA 效率：1/e=0.37）



CSMA

* 载波侦听多路访问（ carrier sense multiple access ）
  * 应用：局域网
* CSMA基本思想
  * 传输节点在发送数据前，先侦听信道
  * 信道空闲：立即发送
  * 信道忙：不发送
* 三种CSMA
  * 1-坚持CSMA：侦听到信道“忙”，持续侦听，一旦“空闲”，立即发送
  * 0-坚持CSMA：侦听到信道“忙”，等待一随机时间，重新侦听，一旦空闲，立即发送
  * P-坚持CSMA：侦听到信道“忙”，持续侦听，一旦空闲，P概率发送，(1-P)概率延迟1个时隙进行侦听

* CSMA/CD

  *  冲突的帧，节点不知道，继续传输，造成信道浪费冲突检测（CD），检测到冲突，节点立即停止传输
  *  冲突检测
     * 有线局域网易于实现：测量信号强度，比较发射信号与接收信号
     * 无线局域网很难实现：接收信号强度淹没在本地发射信号强度下
  *  要求：L / R ≥ $2d_{max}$  / V
     * 网络带宽：R bps
     * 数据帧最小长度：$L_{min}$  (bits)
     * 信号传播速度：V (m/s)



对比

* 发送时机判断

  * 时隙 ALOHA：时钟起始时刻
  * ALOHA ：有就发

  * CSMA：侦听信道，空闲再发

* 冲突检测

  * 时隙 ALOHA / ALOHA / CSMA：用超时判断
  * CSMA/CD：冲突检测



## 轮转访问MAC协议

比较

* 信道划分MAC协议：
  * 网络负载重时，共享信道效率高，且公平
  * 网络负载轻时，共享信道效率低！
* 随机访问MAC协议：
  * 网络负载轻时，共享信道效率高，单个结点可以利用信道的全部带宽
  * 网络负载重时，产生冲突开销
* 轮转访问MAC协议：
  * 综合两者的优点！



轮询(polling):

<img src="https://img-blog.csdnimg.cn/20210112192653448.png" alt="image-20210104232447984"  width="20%"/>

* 主结点轮流“邀请”从属结点发送数据
* 典型应用：“哑(dumb)” 从属设备
* 问题：轮询开销、等待延迟、单点故障



令牌传递(token passing):

<img src="https://img-blog.csdnimg.cn/20210112192719457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" alt="image-20210104232559019"  width="20%"/>

* 控制令牌依次从一个结点传递到下一个结点.
* 令牌：特殊帧
* 问题：令牌开销、等待延迟、单点故障