介质访问控制

介质访问控制所要完成的主要任务是,为使用介质的每个结点隔离来自同一信道上其他结点所传送的信号,以协调活动结点的传输。

信道划分介质访问控制

当传输介质的带究超过传输单个信号所需的带宽时,人们就通过在一条介质上同时携带多个传输信号的方法来提高传输系统的利用率,这就是所谓的多路复用,也是实现信道划分介质访问控制的途径。

1. 频分多路复用(FDM)
2. 时分多路复用(TDM)
3. 波分多路复用(WDM)
4. 码分多路复用(CDM)

频分多路复用(FDM)

• 频分多路复用是一种将多路基带信号调制到不同频率载波上,再叠加形成一个复合信号的多路复用技术。
• 每个子信道传输一种信号,这就是频分多路复用
• 每个子信道分配的带宽可不相同,但它们的总和必须不超过信道的总带宽

相关信息

频分多路复用的优点在于充分利用了传输介质的带究,系统效率较高:由于技术比较成熟, 实现也较容易。

时分多路复用(TDM)

• 时分多路复用是将一条物理信道按时问分成若千时间片,轮流地分配给多个信号使用
• 由于计算机数据的突发性,一个用户对已经分配到的子信道的利用率一般不高

统计时分多路复用(STDM)

STDM 帧并不固定分配时隙,而按需动态地分配时隙,当终端有数据要传送时,才会分配到时间片,因此可以提高线路的利用率

波分多路复用(WDM)

波分多路复用即光的频分多路复用,它在一根光纤中传输多种不同波长(频率)的光信号,由于波长(频率)不同,各路光信号互不干扰,最后再用波长分解复用器将各路波长分解出来。

码分多路复用(CDM)

• 既共享信道的频率,又共享时间
• 每个站点被指派一个唯一的$m$位码片序列
• 当两个或多个站点同时发送时,各路数据在信道中线性相加
• 为从信道中分离出各路信号,要求各个站点的码片序列相互正交
• 两个向量要求相互正交。向量中的分量,就是所谓的码片

假如站点 A 的码片序列被指派为 00011011,则A站发送00011011就表示发送比特1,发送11100100 就表示发送比特0。为了方便,按惯例将码片中的0写为-1,將1写为+1,因此A站的码片序列是-1-1-1+1+1-1+1+1。

令向量$S$表示$A$站的码片向量，令$T$表示$B$站的码片向量

• 两个不同站的码片序列正交，即向量$S$和$T$的规格化内积是$0$,即:

$$S\cdot T=\frac{1}{m}\displaystyle\sum_{i=1}^{m}S_{i}T_{i}=0$$

• 任何一个码片向量和该码片向量自身的规格化内积都是$1$
• 任何一个码片向量和该码片反码的向量的规格化内积是$-1$

$$S\cdot S=\frac{1}{m}\sum_{i=1}^mS_{i}S_{i}=\frac{1}{m}\sum_{i=1}^mS_{i}^2=\frac{1}{m}\sum_{i=1}^m(\pm 1)^2=1$$

当$A$站点向$C$站点发动数据$1$时，就发送了向量$(-1 -1-1+1+1-1+1+1)$
同理$B$站向$C$站发送数据$0$时，就发送了向量$(+1+1-1+1-1-1-1+1)$
两个向量到了公共信道上就进行叠加，实际上就是线性相加，得到

$$S+T=(\begin{matrix} 0& 0 & -2& 2&0 & -2& 0 &2 \end{matrix})$$

到达$C$站后，用$S$和$S+T$进行规格化内积。根据叠加原理,其他站点的信号都在内积的结果中被过滤掉了,内积的相关项都是 0,而只剩下 A站发送的信号。得到

$$S\cdot(S+T)=1$$

故$A$站点发出的数据时$1$，同理$B$站点的数据是$0$

相关信息

码分多路复用技术具有频谱利用率高、抗干扰能力强、保密性强、语音质量好等优点,还可以滅少投资和降低运行成本,主要用于无线通信系统,特别是移动通信系统。

随机访问介质访问控制

提示

• 常用的协议有ALOHA协议、CSMA协议、CSMA/CD协议和CSMA/CA协议等,它们的核心思想都是:胜利者通过争用获得信道, 从而获得信息的发送权。因此,随机访问介质访问控制协议又称争用型协议
• 随机介质访问控制实质上是一种将广播信道转化为点到点信道的行为

1. 1.ALOHA协议
2. 2.CSMA协议
3. 3.CSMA/CD协议
4. 4.CSMA/CA协议

1.ALOHA协议

(1)纯 ALOHA 协议

当网络中的任何一个站点需要发送数据时,可以不进行任何检测就发送数据。如果在一段时间内未收到确认,那么该站点就认为传输过程中发生了冲突。发送站点需要等待一段时间后再发送数据,直至发送成功。

吞吐量

假设网络负载($T0$时问内所有站点发送成功的和未成功而重传的帧数)为$G$,则纯ALOHA 网络的吞吐量($T0$时间内成功发送的平均帧数)为$S=Ge^{-2G}$。当$G=0.5$时,$S=0.5e^{-1}\approx 0.184$,这是吞吐量S可能达到的极大值。

(2)时隙 ALOHA 协议

时隙ALOHA协议把所有各站在时间上同步起来,并将时间划分为一段段等长的时隙,规定只能在每个时隙开始时才能发送一个帧。从而避免了用户发送数据的随意性,减少了数据产生冲突的可能性,提高了信道的利用率。

吞吐量

• 时隙ALOHA 网络的吞吐量 $S$ 与网络负载$G$的关系是$S=Ge^{-G}$。当$G=1$时,$S=e^{-1}\approx 0.368$
• 这是吞吐量S可能达到的极大值。可见,时隙 ALOHA 网络比纯 ALOHA 协议的吞吐量大了 1倍。

2.CSMA协议

提示

• 若每个站点在发送前都先监听一下共用信道,发现信道空闲后再发送,则就会大大降低冲突的可能,从而提高信道的利用率
• 与ALOHA协议的主要区别是多了一个载波监听装置。

(1)1-坚持CSMA

监听到信道忙后,继续坚持监听信道;监听到信道空闲后,发送帧的概率为1,即立刻发送数据。

(2)非坚持CSMA

一个结点要发送数据时,首先监听信道:如果信道空闲,那么立即发送数据:如果信道忙,那么放弃监听,等待一个随机的时间后再重复上述过程。

(3)$p$-坚持CSMA

一个结点要发送数据时, 首先监听信道:如果信道忙,就持续监听,直至信道空闲;如果信道空闲,那么以概率$p$发送数据,以概率$1-p$推迟到下一个时隙;如果在下一个时隙信道仍然空闲,那么仍以概率$p$发送数据,以概率$1-p$推迟到下一个时隙:这个过程一直持续到数据发送成功或因其他结点发送数据而检测到信道忙为止,若是后者,则等待下一个时隙再重新开始监听。

image.png

3.CSMA/CD协议

工作流程

先听后发,边听边发,冲突停发,随机重发

image.png

相关信息

显然,在使用CSMA/CD协议时,一个站不可能同时进行发送和接收^[1](但必须边发送边监听信道)。因此使用CSMA/CD协议的以太网不可能进行全双工通信而只能进行双向交替通信(半双工通信) 。

争用期

把以太网端到端往返时间$2\tau$称为争用期(又称冲突窗口或碰撞窗口)。只有经过争用期这段时间还未检测到碰撞时,才能确定这次发送不会发生碰撞。

最小帧长

• 某站点发送一个很短的帧,但在发送完毕之前并没有检测出碰撞^[2],为了避免这种情况，以太网规定了一个最短帧长（争用期内可发送的数据长度，在争用期内如果检测到碰撞,站点就会停止发送,此时己发送出去的数据一定小于最短帧长,因此凡长度小于这个最短帧长的帧都是由于冲突而异常中止的无效帧。最小帧长的计算公式为

$$\text{最小帧长}=\text{总线传播时延}\times \text{数据传输速率}\times 2$$

• 若发送的帧长度不足最小帧长，则需要在MAC子层中于数据字段的后面加入一个整数字节的填充字段

截断二进制指数退避算法

CSMA/CD采用截断二进制指数退避算法来解决碰撞问题。算法如下:

截断二进制指数退避算法

1. 确定基本退避时间,一般取两倍的总线端到端传播时延 $2\tau$(即争用期)。
2. 定义参数$k$,它等于重传次数,但$k$不超过$10$,即$k=\min[\text{重传次数},10]$。当重传次数不超过$10$时,$k$等于重传次数;当重传次数大于$10$时,$k$就不再增大而一直等于$10$^[3]
3. 从离散的整数集合$[0,1,\dots,2^k-1]$中随机取出一个数$r$,重传所需退避的时间就是$r$倍的基本退避时间,即$2r\tau$
4. 当重传达$16$次仍不能成功时，说明网络太拥挤，认为此帧永远无法正确发出，抛弃此帧并向高层报告错误

提示

使用截断二进制指数退避算法可使重传需要推迟的平均时间随重传次数的增大而增大(这也称动态退避),因而能降低发生碰撞的概率,有利于整个系统的稳定。

4.CSMA/CA协议

CSMA/CD 协议己成功应用手使用有线连接的局域网,但在无线局域网环境下,却不能简单地搬用 CSMA/CD 协议,特别是碰撞检测部分。主要有两个原因:

相关信息

1. 接收信号的强度往往会远小于发送信号的强度,且在无线介质上信号强度的动态变化范围很大,因此若要实现碰撞检测,则硬件上的花费就会过大。
2. 在无线通信中,并非所有的站点都能够听见对方,即存在“隐蔽站”问题。

• 相比较于CSMA/CD协议，把碰撞检测改为碰撞避免，并不是指协议可以完全避免碰撞,而是指协议的设计要尽量降低碰撞发生的概率。
• 一旦站点开始发送一个帧,就会完全地发送该帧,但碰撞存在时仍然发送整个数据帧(尤其是长数据帧)会严重降低网络的效率,因此要采用碰撞避免技术降低碰撞的可能性。

为了尽量避免碰撞,802.11 规定,所有的站完成发送后,必须再等待一段很短的时间(继续监听)才能发送下一帧。这段时间称为帧问间隔 (Enter Frame Space, IFS)。帧问间隔的长短取決于该站要发送的帧的类型。802.11 使用了下列三种 IFS:

1. SIFS (短IFS):最短的IFS, 用来分隔属于一次对话的各帧,使用 SIFS 的帧类型有 ACK 帧、CTS 帧、分片后的数据帧,以及所有回答 AP 探询的帧等。
2. PIFS（点协调 IFS)：中等长度的IFS，在PCF 操作中使用。
3. DIFS(分布式协调 IFS)^[4]：最长的 IFS，用于异步帧竞争访问的时延

CSMA/CA 的退避算法和CSMA/CD协议的稍有不同。信道从忙态变为空闲态时,任何一个站要发送数据帧,不仅都要等待一个时间间隔,而且要进入争用窗口,计算随机退避时间以便再次试图接入信道,因此降低了碰撞发生的概率。当且仅当检测到信道空闲且这个数据帧是要发送的第一个数据帧时,才不使用退避算法。其他所有情况都必须使用退避算法,具体为:

1. 在发送第一个帧前检测到信道忙
2. 每次重传
3. 每次成功发送后要发送下一帧。

CSMA/CA算法归纳

1. 若站点最初有数据要发送(而不是发送不成功再进行重传),且检测到信道空闲,在等待时间DIFS 后,就发送整个数据帧。
2. 否则,站点执行 CSMA/CA 退避算法,选取一个随机回退值。一旦检测到信道忙,退避计时器就保持不变。只要信道空闲,退避计时器就进行倒计时。
3. 当退避计时器减到0时(这时信道只可能是空闲的),站点就发送整个帧并等待确认。
4. 发送站若收到确认,就知道已发送的帧被目的站正确接收^[5]。这时如果要发送第二帧,就要从步骤2)开始,执行 CSMA/CA 退避算法,随机选定一段退避时间。
   若发送站在规定时间(由重传计时器控制)内没有收到确认帧 ACK,就必须重传该帧,再次使用 CSMA/CA 协议争用该信道,直到收到确认,或经过若干次重传失败后放弃发送。

CSMA/CD 与 CSMA/CA 主要区别

1. CSMA/CD 可以检测冲突,但无法避免;CSMA/CA 发送数据的同时不能检测信道上有无冲突,本结点处没有冲突并不意味着在接收结点处就没有冲突,只能尽量避免。
2. 传输介质不同。CSMA/CD 用于总线形以太网,CSMA/CA 用于无线局域网 802.11a/b/g/n等。
3. 检测方式不同。CSMA/CD 通过电缆中的电压变化来检测;而 CSMA/CA 采用能量检测、载波检测和能量载波混合检测三种检测信道空闲的方式。

CSMA/CA 协议的基本思想是在发送数据时先广播告知其他结点,让其他结点在某段时间内不要发送数据,以免出现碰撞。CSMA/CD 协议的基本思想是发送前监听,边发送边监听,一旦出现碰撞马上停止发送。

隐蔽站问题

相关信息

站$A$和$B$都在$AP$的覆盖范围内,但 A 和B相距较远,彼此都听不见对方。当A和B检测到信道空闲时,都向 AP 发送数据,导致碰撞的发生,这就是隐蔽站问题。

• 为了避免该问题,802.11 允许发送站对信道进行预约。源站要发送数据帧之前先广播一个很短的请求发送 RTS (Request To Send)控制帧,它包括源地址、目的地址和这次通信(含相应的确认帧)所持续的时间,该帧能被其范围内包括 AP 在内的所有站点听到。
• 若信道空闲, 则 AP 广播一个允许发送CTS (Clear To Send)控制帧,它包括这次通信所需的持续时间(从RTS 帧复制),该帧也能被其范围内包括 A 和B 在内的所有站点听到。B 和其他站听到CTS 后, 在 CTS 帧中指明的时间内将抑制发送。
• CTS 帧有两个目的:
  • 1.给源站明确的发送许可;
  • 2.指示其他站点在预约期内不要发送。
• 信道预约不是强制性规定,各站可以自己决定使用或不使用信道预约。只有当数据帧长度超过某一数值时,使用 RTS 和 CTS 帧才比较有利。

轮询访问:令牌传递协议

• 在令牌传递协议中,一个令牌(Token)沿着环形总线在各结点计算机间依次传递
• 令牌是一个特殊的 MAC 控制帧,它本身并不包含信息,仅控制信道的使用,确保同一时刻只有一个站点独占信道。
• 当环上的一个站点希望传送帧时,必领等待令牌。一旦收到令牌,站点便可启动发送帧。帧中包括目的站点地址,以标识哪个站点应接收此帧。站点只有取得令牌后才能发送数据帧,因此令牌环网不会发生碰撞。站点在发送完一帧后,应释放令牌,以便让其他站使用^[6]。
• 由于令牌在网环上是按顺序依次传递的,因此对所有入网计算机而言,访问权是公平的。

令牌环网中令牌和数据的传递过程

1. 网络空闲时,环路中只有令牌帧在循环传递。
2. 令牌传递到有数据要发送的站点时,该站点就修改令牌中的一个标志位,并在令牌中附加自己需要传输的数据,将令牌变成一个数据帧,然后将这个数据帧发送出去。
3. 数据帧沿着环路传输,接收到的站点一边转发数据,一边查看帧的目的地址。如果目的地址和自己的地址相同,那么接收站就复制该数据帧以便进一步处理。
4. 数据帧沿着环路传输,直到到达该帧的源站点,源站点收到自己发出去的帧后便不再转发。同时,通过检验返回的帧来查看数据传输过程中是否出错,若有错则重传。
5. 源站点传送完数据后,重新产生一个令牌,并传递给下一站点,以交出信道控制权。

注意

传输介质的物理拓扑不必是一个环,但是为了把对介质访问的许可从一个设备传递到另一个设备,令牌在设备间的传递通路逻辑上必须是一个环。

提示

• 轮询介质访问控制非常适合负载很高的广播信道。
• 轮询介质访问控制既不共享时间,也不共享空间,它实际上是在随机介质访问控制的基础上, 限定了有权力发送数据的结点只能有一个。

---

1. 否则说明发生了碰撞，需要重传 ↩︎

2. 甲先发送数据,当数据即将到达乙时,乙也开始发送数据,此时乙将立刻检测到冲突,而甲要检测到冲突还需等待冲突信号从乙传播到甲。两台主机均检测到冲突的时间最长。此时发送很短帧的站点无法检测出碰撞 ↩︎

3. 王道3.5.4选择题 13 题(2024 考研) ↩︎

4. 当站点要发送数据帧时,若载波监听到信道空闲,需等待 DIFS 后发送 RTS 预约信道(王道3.5.3选择题 31 题-2024 考研-2020 统考真题) ↩︎

5. ACK 帧是 CSMA/CA 避免冲突的机制之一,也就是说,只有当发送方收到接收方发回的 ACK 帧后,才确认发出的数据帧己正确到达目的地。(王道3.5.3选择题24题-2024 考研-2011 统考真题) ↩︎

6. 令牌环网使用令牌在各个结点之间传递来分配信道的使用权,每个结点都可在一定的时间内(令牌持有时问)获得发送数据的权利,而并非无限制地持有令牌。 ↩︎