计算机网络——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 p(1-p)^{N-1} p(1p)N1
  • 任何一个节点的成功概率是 N p ( 1 − p ) N − 1 Np(1-p)^{N-1} Np(1p)N1
  • N个节点的最大效率:求出使 f ( P ) = N p ( 1 − p ) N − 1 f(P) = Np(1-p)^{N-1} f(P)=Np(1p)N1 最大的 p ∗ p^ * p
  • 代入 p ∗ p^* p得到最大 f ( p ∗ ) f(p^{*}) f(p)
  • N为无穷大时的极限为1/e = 0.37

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

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

在这里插入图片描述

纯ALOHA的效率

P(指定节点成功) = P(节点传输)
P(其他节点在 [ t 0 − 1 , t 0 ] [t_0 - 1,t_0] [t01,t0]不传)
P(其他节点在 [ t 0 , t 0 + 1 ] [t_0,t_0 + 1] [t0,t0+1]不传)
= p ⋅ ( 1 − p ) N − 1 ⋅ ( 1 − p ) N − 1 = p ⋅ ( 1 − p ) 2 ( N − 1 ) p \cdot (1-p)^{N-1} \cdot (1-p)^{N-1} =p \cdot (1-p)^{2(N-1)} p(1p)N1(1p)N1=p(1p)2(N1)
选择最佳的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 2^{m-1} 2m1)中K,等待 K ∗ 512 K^*512 K512位时,然后转到步骤2
    exponential backoff 二进制指数退避算法

指数退避

  • 目标:适配器试图适应当前负载,在一个变化的碰撞窗口中随机选择时间点尝试重发
    • 高负载:重传窗口时间大,减少冲突,但等待时间长
    • 低负载:使得各站点等待时间少,但冲突概率大
  • 首次碰撞:在{0,1}选择K,延迟 K ∗ 512 K^*512 K512位时
  • 第2次碰撞:在{0,1,2,3}选择K
  • 第10次碰撞:在{0,1,2,3,…,1023}选择K
CSMA/CD效率
  • T p r o p T_{prop} Tprop = LAN上2个节点的最大传播延迟
  • t t r a n s t_{trans} ttrans = 传输最大帧的时间
    e f f i c i e n c y = 1 1 + 5 t p r o p / t t r a n s efficiency = \frac{1}{1 + 5t_{prop}/t_{trans}} efficiency=1+5tprop/ttrans1
  • 效率变为1
    • t p r o p t_{prop} tprop变成0时
    • t t r a n s t_{trans} ttrans变为无穷大时
  • 比起ALOHA更好的性能,而且简单,廉价,分布式
无线局域网CSMA/CA

在这里插入图片描述

WLAN构成

  • 基站:AP
  • 无线链路
  • 移动主机节点
无线局域网中的MAC:CSMA/CA
  • 冲突: 2 + 2^+ 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)循环从一个节点到下一个节点传递
  • 令牌报文:特殊的帧
  • 缺点
    • 令牌开销:本身消耗带宽
    • 延迟:只有等到抓住令牌,才可传输
    • 单点故障
      • 令牌丢失系统级故障,整个系统无法传输
      • 复杂机制重新生成令牌

在这里插入图片描述

相关推荐

  1. 计算机网络网络协议

    2024-04-02 18:56:02       2 阅读
  2. 计算机网络——HTTP协议

    2024-04-02 18:56:02       21 阅读

最近更新

  1. 【Python-第三方库】cv2

    2024-04-02 18:56:02       0 阅读
  2. All in One mini主机搭建全屋主路由方案

    2024-04-02 18:56:02       0 阅读
  3. 程序员最好的笔记Typora使用教程

    2024-04-02 18:56:02       0 阅读
  4. 学习总结!

    2024-04-02 18:56:02       0 阅读
  5. 每天一个数据分析题(二百七十)

    2024-04-02 18:56:02       0 阅读

热门阅读

  1. Windows 11 中Docker的安装教程

    2024-04-02 18:56:02       6 阅读
  2. terraform读取tfvars的变量

    2024-04-02 18:56:02       5 阅读
  3. MATLAB如何批量更改文件名

    2024-04-02 18:56:02       6 阅读
  4. 人工智能的实现流程

    2024-04-02 18:56:02       5 阅读
  5. Webshell网络安全应急响应概述

    2024-04-02 18:56:02       8 阅读
  6. Linux关机命令

    2024-04-02 18:56:02       6 阅读
  7. 冥想第一千一百一十七天

    2024-04-02 18:56:02       6 阅读
  8. 在linux上设置nginx上自动启动

    2024-04-02 18:56:02       6 阅读