多路访问协议

1. ALOHA

ALOHA 系统上所有的用户终端共享同一个上行频率给 中央计算机发送帧。其中包括了一个简单而巧妙的方法来解决信道分配问题。ALOHA 系统的基本思想非常简单:当用户有数据需要发送时就传输。

两个版本的 ALOHA区别:
纯 ALOHA ：时间是连续的
分槽 ALOHA：时间分成离散槽,所有帧都必须同步到时间槽中。 ALOHA系统的吞吐量与负载关系

利用分槽 ALOHA,可以达到的最佳信道利用率是 1/e 。 因为每个站都可以随意地发送数据,它并不知道其他站是否也在发送数据。所以,频繁地 发生冲突是难免的。然而,在局域网中,站是完全有可能检测到其他站当前在做什么,然 后再根据情况调整自己的行为。这些网络可以获得比 1/e好得多的利用率。下面就可以用到载波监听多路访问协议。

2. 载波监听多路访问协议

在一个协议中,站监昕是否存在载波(即是否有传输),并据此采取相应的动作, 则这样的协议称为载波侦听协议( carriersense protocol)。

坚持和非坚持 CSMA

  1. 1-坚持载波检测多路访问
    这是最简单的 CSMA 方案。当一个站有数据要发送时,它首先侦 昕信道,确定当时是否有其他站正在传输数据:如果信道空闲,它就发送数据。否则,如 果信道忙,该站等待直至信道变成空闲:然后,站发送一帧。如果发生冲突,该站等待一 段随机的时间,然后再从头开始上述过程。这样的协议之所以称为 1-坚持,是因为当站发 现信道空闲时,它传输数据的概率为 1。

  2. 非坚持 CSMA (nonpersistent CSMA) 和前一个协议一样,站在发送数 据之前要先侦昕信道。如果没有其他站在发送数据,则该站自己开始发送数据。然而,如 果信道当前正在使用中,则该站并不持续对信道进行监听,以便传输结束后立即抓住机会 发送数据。相反,它会等待一段随机时间,然后重复上述算法。因此,该算法将会导致更好的信道利用率,但是比起 1一坚持 CSMA,也带来了更大的延迟。

信道使用率与负载比较

坚持和非坚持 CSMA 协议无疑是对 ALOHA 的改进,因为这些协议都确保了信道忙时, 所有的站都不再传送数据。然而,如果两个站侦听到信道为空,并且同时开始传输,则它们的信号仍然会产生冲突。下面的改进就用到带冲突检测的 CSMA。

带冲突检测的 CSMA

每个站快速检测到发生冲突后立即停止传 输帧(而不是继续完成传输〉,因为这些帧己经无可挽回地成为乱码。这种策略可以节省时间和带宽。这种协议称为带冲突检测的 CSMA CCSMA/CD, CSMA with Collision Detection)。它是经典以太局域网的基础。

CSMA/CD 模型将由交替出现的竞争期、传输期,以及当所有站都育事止的空 闲期〈比如没有传输任务〉 组成：

CSMNCD 可能处于竞争、传输或空闲状态

在 CSMA/CD 中,一旦站已经确定无疑地抓住了信道,冲突就不会再发生:尽管如此, 在竞争期中冲突仍有可能发生。这些冲突严重地影响了系统的性能,特别是当带宽延迟积 很大,比如电缆很长(即 τ 很大)而帧的长度又很短时。冲突不仅降低了带宽,而且使得 发送一个帧的时间变得动荡不定,这样就无法很好地适应实时流量 , 比如 E 语音。而且 CSMA/CD 也不是普遍适用的。下面就用到无冲突协议。

3. 无冲突协议

根本不可能产生冲突的方式解决了信道竞争问 题,即使在竞争期中也不会发生冲突。大多数这样的协议目前并没有被用在主流系统中。

位图协议

基本位图法( basic bitmap me也od),每个竞争 期正好包含 N 个槽。如果 0 号站有一帧数据要发送,则它在第 0 个槽中传送 l 位。在这个 槽中,不允许其他站发送。不管 0 号站做了什么, 1 号站有机会在 1 号槽中传送 l 位,但 是只有当它有帧在排队等待时才这样做。一般地, j 号站通过在 j 号槽中插入 1 位来声明自 己有帧要发送。当所有 N 个槽都经过后,每个站都知道了哪些站希望传送数据。这时候, 它们便按照数字顺序开始传送数据了。 位图协议

令牌传递

在令牌环 Ctoken ring)协议中,网络的拓扑结构被用来定义站的发送顺序。所有站连 接成一个单环结构,一个站依次连接到下一个站。因 此令牌传递到下一站只是单纯地从一个方向上接收 令牌和在另一个方向上发送令牌。帧 也按令牌方向传输。这样,它们将绕着环循环,到达 任何一个目标站。然而,为了阻止帧陷入无限循环(像 令牌一样),一些站必须将它们从环上取下来。这个 站或许是最初发送帧的原始站,在帧经历了一个完整 的环游后将它取下来,或者是帧的指定接收站。

令牌环

二进制倒计数

如果一个站想要使用信道,它就以二进制位串的形式广播自己的地址, 从高序的位开始。假定所有地址都有同样的长度。不同站地址中相同位在同时发送时被信 道布尔或 CBOOLEAN OR)在一起。我们把这样的协议称为二进制倒计数 Cbinary countdown)协议。为了避免冲突,必须使用一条仲裁规则:一个站只要看到自己的地址位中的 0 值位置 被改写成了 1,则它必须放弃竞争。 二进制倒计数协议

4. 有限竞争协议

如何在一个广播网络中获取信道,我们已经考虑了两种基本策略:一种是竞争的方法, 如同 CSMA 的做法那样:另一种是无竞争协议。每一种都可以用两个重要性能指标来衡量: 低负载下的延迟,以及高负载下的信道利用率。

在负载较轻的情况下,竞争方法(即纯 ALOHA 或者分槽 ALOHA)更为理想,因为它的延迟较短(冲突很少发生)。随着负载的 增加,竞争方法变得越来越缺乏吸引力,因为信道仲裁所需要的开销变得越来越大。而对 于无冲突协议,则结论刚好相反。在低负载情况下,它们有相对高的延迟,但是随着负载 的增加,信道的效率反而得到提高(因为开销是固定的)。

有限竞争协议( limited-contention protocol)把竞争协议和无冲突协议的优势结合起来。这样得 到的新协议在低负载下来用竞争的做法而提供较短的延迟,但在高负载下来用无冲突技术, 从而获得良好的信道效率。

5. 无线局域网协议

无线局域网具有某些和有线局域网不同的属性,这些属性导致了无线局域网不同的 MAC 协议。

无线局域网传递数据的问题：

使用无线 LAN 的一种单纯想法是尝试使用 CSMA:每个站侦听是否有其他站在传输, 并且只有当没有其他站在传送数据时它才传输。这种方法的麻烦在于协议并未考虑无线传 输特性,因为这里的冲突发生在接收方,而不是发送方。 如下图的问题：

一个无线LAN

上图无线电的覆盖范围是这样的： A 和 B 都在对方的范围内,可能潜在 地相互之间有干扰: C 也可能潜在地干扰到 B 和 D,但不会干扰 A。

  1. 当 A 和 C 向 B 传送数据时的情形,如图 (a)所示。如果 A 开始发送, 然后 C 立即进行侦昕介质,它将不会听到 A 的传输,因为 A 在它的覆盖范围之外。因此 C 错误地得出结论:它可以向 B 传送数据。如果 C 传送数据,将在 B 处产生冲突,从而扰乱 A 发来的帧。(我们假设没有类似 CDMA 的编码模式可以提供多信道传输,因此冲突会扰 乱信号,从而破坏两个帧)我们需要一个 MAC 协议,它能防止这种冲突的发生.由于竞争者离得太远而导致站无法检测到潜在的竞争者,这个问题称为隐藏终端问题( hidden station problem)。

  2. B 向 A 传送数据,同时 C 想给 D 发送数据,如 图 4-11 Cb)所示。如果 C 侦听介质,它会昕到有一个传输正在进行,从而会错误地得出 结论:它不能向 D 发送数据(图中的虚线表示)。事实上, C 所昕到的传输只会搞坏 B 和 C 之间区域中的接收,但是,两个接收方都不在这个危险区域。我们需要一个 MAC 协议, 它能防止此类延迟传输的发生。这个问题称为暴露终端问题( exposed station problem)。

解决的协议MACA：

处理无线 LAN 这些问题的一个早期且有影响力的协议是冲突避免多路访问 (MACA, Multiple Access with Collision Avoidance) (Karn, 1990)。 MACA 的基本思想是 发送方剌激接收方输出一个短帧,以便其附近的站能检测到该次传输,从而避免在接下去 进行的(较大)数据帧传输中也发送数据。这项技术被用来替代载波侦听。 如下图：

MACA协议

如果一个站听到了 RTS 帧,那么它一定离 A 很近,它必须保持沉默,至少等待足够长的时间以便在无冲突情况下 CTS 被返回给 A。如果一个站昕到了 CTS,则它一定离 B 很近,在接下来的数据传送过程 中它必须一直保持沉默,只要检查 CTS 帧,该站就可以知道数据帧的长度(即数据传输要 持续多久)。