ALOHA网：竞争技术的起源

在总线形局域网中，共享传输媒质的最常用方法是：当某一用户要传送信息时，就与网中的其它用户进行竞争，以达到占用传输媒质（即信道）的目的。竞争技术的产生来源于著名的ALOHA网。它是由美国夏威夷大学在70年代设计，用于研究散布在各海岛上的计算机的通信方法。ALOHA网的成功研究，不仅为无线信道计算机网络创造了经验，同时为总线形局域网的访问技术奠定了理论基础。在这里仅简单介绍ALOHA的协议，然后研究在此基础上发展起来的总线存取技术。

1、纯ALOHA协议

纯ALOHA协议的基本思想是利用完全随机的方法来解决多个用户争夺传输媒质的冲突。因为是无线网络，所以各结点计算机要传送就必须争夺作为信号传播媒质的某一通信波段，而为实现广播式传送，这个波段又必须是公共的。公共信道必定会产生信号发送冲突，纯ALOHA协议就是要解决这个冲突。

图8.2.1　信道的占用情况

纯ALOHA协议的工作过程是：当网上某用户有报文要发送时，先将报文分成报文分组，其中包含数据、目的结点与源结点地址以及差错校验码等控制信息，然后将报文分组发送出去，发送一结束立即起动一个定时器。如果这个报文分组成功地到达目的结点，发送端就会在超时间隔内收到应答；如果在超时间隔内没有收到应答，则认为这个报文分组在传输途中丢失或损坏（从差错校验码得知）。由于网上各用户可随时发送报文分组，因此碰撞是不可避免的，而碰撞又将使报文分组损坏。目的结点收到一个被破坏的报文分组将不进行应答。当发送端定时器超时，发送端得知这个报文分组出错，等待一段时间后再重发这个报文分组。等待的时间必须是随机的，以免同时发送的报文分组再次碰撞，上述过程如图8.2.1所示。

现简单分析一下纯ALOHA协议的性能。设报文分组是等长的，报文分组传送时间为T，其等于报文分组长度（b）除以数据速率（b/s）。首先找出一个报文分组（例如报文分组X）不产生碰撞的条件。从图8.2.2可见，如在（t0+T）时间范围内，有其它用户发送的报文分组，则该分组的前端将与X的未端碰撞。同样，如在（t0+T）到（t0+2T）的时间范围内遇到其它用户发送的报文分组，则X的前端将与其相碰撞。因此，在2T时间内报文分组重叠就将产生碰撞，所以把2T称为易损时间。

图8.2.2　报文分组X受损时间范围

假设可将时间T分为N个相等的子间隔h，即h=T/N，若N→∞，则h→0.按Poisson条件，每一个子间隔有两种可能：发生一个事件或不发生事件。若用1和0分别表示发生或者不发生事件，则有（二项分布）

其中，λ为单位时间内的平均事件数（平均概率）。按Poisson分布，在T时间内出现k次事件的概率为

P（x=k）=e-λt（λt）k/k！k=0，1，2，…

设有无限多个用户，生成k个报文的概率由Poisson分布决定，在T时间内

令提供给网络的负荷（含控制分组，重发分组等）为G，即G=λT，则有

所以在T时间内一个分组也不产生的概率为

P0（T）=e-G

在第二个T内仅产生一个分组的概率为

P1（T）=e-GG

在2T时间仅有一个用户发送的概率为上述两个概率之积，即

Pc（2T）=P0（T）P1（T）=e-Ge-GG=e-2GG

在2T时间内正确传送报文分组的平均时间为Pc·2T，在单位时间内正确传送分组的平均数为

Pc·2T/2T=Pc

亦即平均吞吐量（生成并成功传送了的分组率）为

S=Ge-2G

对S求导，得

S'=e-2G-2Ge-2G

令S'=0，得G=0.5时，S有极大值

Smax=0.5e-1≈0.18

由此可见，纯ALOHA协议的效率是很低的，大部分的信道占用率被相互的竞争所浪费。产生此问题的原因在于各个用户想发就发，冲突后也仅靠随机的延迟来解决，故这种完全随机的控制方法效率低是必然的。在后来的研究中，又提出了时间片ALOHA，预约ALOHA，此处不再赘述。

2、CSMA 协议

虽然纯ALOHA协议的效率很低，但这种竞争共享信道的方法启发了后人。在对其进行逐步改进后，产生了用于共享总线信道的载波检测多路存取协议（Carrier Sense Multiple Access，CSMA）。纯ALOHA协议效率低的主要原因是任何用户在发送时都不关心外界的信息，完全以一种“旁若无人”的态度对待公共信道，即使别人已经在发送过程中占据了信道，它也照发不误。因此，若在发送前能够知道其它用户对信道的占用情况，就可以大大地提高效率。这就是载波检测多路存取协议的基本点。所谓载波检测，是指在发送前首先查看信道是否已被其它用户占用，而多路存取则是指多个用户共享信道。这种方法也被形象地称为“说前听”，简记为LBT（Listen Before Talking）。

在CSMA协议中，每个用户在发送前都要侦听一下总线，看看是否存在载波信号。若没有信号，则证明信道此刻空闲，可以立即发送；若存在信号，则说明信道正被某用户占用，它就不去打扰正在发送的用户，等待信道空闲后再发送，从而避免了大量的碰撞冲突。但在侦听到总线忙时如何处理，不同的方法就有不同的协议。

第一种载波检测协议是1—坚持CSMA协议，其工作过程为：当某站要发送数据时，它首先侦听总线上是否有载波，即信道是否被占用。如果信道“忙”，这个站就等到信道空闲时再发送；当侦听到空闲的信道，该站立即发送一个报文分组。如果发生碰撞，各站等待一段随机时间后再重复上述过程。所谓“坚持”是指当一个站侦听到载波之后，侦听工作一直坚持下去，而“1”是指当某站发现信道空闲时发送概率为1.这种协议产生碰撞的原因是：

①传播延时的影响

在一个站开始发送后的一小段时间内，另一个作好发送准备的站侦听到空闲的信道，因而开始发送，结果发生碰撞。信道传播时间越长，其影响越大。

②几个站同时发送

如果有两个站在第三个站发送期间都作好了发送准备，并侦听信道，因都侦听到“忙”信道，因而它们必须等待。一旦第三站发送结束，这两个站准确地同时发送，结果发生碰撞。

第二种载波检测协议是不坚持CSMA协议。虽然1—坚持CSMA协议的性能比ALOHA协议有所改善，但由于各站太“固执”，都坚持侦听载波，一旦信道空闲又都抢着发送，从而将造成较多的碰撞。不坚持CSMA协议的工作过程为：当一个站要发送时先侦听信道，如果信道空闲，即开始发送；如果信道被占用，则不继续（坚持）侦听信道，而是等待一个随机时间后，再重复上述过程。显然，这种协议能较好地利用信道，但延迟较1—坚持CSMA协议长。

第三种载波检测协议是P—坚持CSMA协议。这种协议是按时间片工作的，其工作过程为：当一个站要发送时先侦听信道，如果信道空闲，它发送的概率是P，推迟到下一个时间片发送的概率是Q（Q=1-P）；如果下一个时间片内信道也空闲，它或是发送或是再次推迟，其概率仍分别为P和Q，这个过程一直重复下去，直到它的报文分组发送完毕或者另一个站“抓住”信道。如果别的站抓住了信道，则该站等待一段随机时间再重发。若一开始就侦听到信道被占用，它就等到下一个时间片重复上述过程。

CSMA协议大大地提高了效率。各类CSMA协议的效率曲线如图8.2.3所示，具体的推导与ALOHA类似，此处从略。(www.xing528.com)

图8.2.3　各类CSMA协议的效率曲线

仔细研究CSMA协议可发现，当信道上的信号传播延迟太大时（例如采用卫皇信道），侦听到的信道状态将不是当前用户发送信息的状态，从而CSMA协议的控制作用就逐渐丧失。因此，务必注意只有当信道的传播延迟远远地小于报文分组的传送时间时，CSMA才有效。另外，由于采用LBT方式，在发送前侦听，一旦发送开知道并处理。如果能够一发生碰撞便　始侦听便告结束，即使发生碰撞冲突，也要在整个报文分组发送完成后才能中止当前传播，效率肯定还会有所提高。这便是CSMA/CD协议。

3、CSMA/CD协议

CSMA/CD（Collision Detect）协议是在CSMA协议的基础上增加了碰撞检测功能。由于这种协议性能较好，最终获得了应用，成为Ethernet的协议。它继承了CSMA协议的优点，同时减少了因碰撞而造成的带宽浪费。

CSMA/CD协议的工作过程概括如下：

①发送站发送时首先侦听载波（载波检测）；

②如果网络（总线）空闲，发送站开始发送它的报文分组；

③如果网络（总线）已被占用，发送站继续侦听载波并推迟发送直到网络空闲；

④发送站在发送过程中侦听碰撞（碰撞检测）；

⑤如果检测到碰撞，发送站立即停止发送，这意味着所有卷入碰撞的站都停止发送；

⑥每个卷入碰撞的站都进入退避周期，即按一定的退避算法等一段随机时间后进行重发，亦即重复上述1～6步骤，直至发送成功。

图8.2.4　CSMA/CD协议的工作原理

CSMA/CD协议的工作原理可利用图8.2.4所示的模型进一步说明。设在时刻t0某站完成了一个报文分组的发送，另一个有报文分组要发送的站此刻检测到一个空闲的信道，于是它开始发送。如果有两个或多个站同时发送，则将发生碰撞。经过一段时间（争用时间片），发送站检测到了碰撞，它立即中止发送并进入退避周期，等一段随机时间后再试图重发上述报文分组。可能需经过一次或几次争夺才能成功地发送一个报文分组，所以，CSMA/CD的工作实际上是争夺与发送的交替，只有所有站都停止工作才出现空闲期。

图8.2.5　争用时间片的说明

这里应当回答一个问题，即争用时间片该有多长？也就是说某个站从开始发送后需多长时间才能知道发生了碰撞。设网络中相距最远的两个站之间的传输信号所需时间为d（见图8.2.5），站A开始发送的时刻为零。在站A的信号传播到站B之前，站B将检测到空闲的信道，因此站B可以发送。设站B在（d-2ε）时刻开始发送，ε时后与站A发送的信号在C点碰撞，碰撞后的信号返回到站A所需的时间为d-ε.因此，站A从发送开始需2（d-ε）的时间才能感知到碰撞。在ε→0的极端情况下，一个站从开始发送到检测到碰撞需2d时间。如果在2d时间内没有检测到碰撞，才能肯定地说这个站“抓”住了信道。因此，2d是影响以太网性能的重要参数，被称为争用时间片。

碰撞后的退避算法对CSMA/CD协议也是十分重要的。两个或多个站碰撞后延迟的时间必须是随机的，只有这样才能保证下次重发不发生碰撞。Metcalfe和Boggs提出一种“二进制指数退避算法”。这种算法以争用时间片为延迟时间的时间单位，第1次碰撞后的重发延迟时间W的计算公式为

W=R×（争用时间片）

式中，R为0到（2i-1）间均匀分布的随机整数，i=碰撞次数，0＜i≤10.这个公式的意义是：从第一次发送一个报文分组起，若出现i次碰撞，则第i次碰撞后的重发延迟共有2i种选择，选择哪一种是随机的。这样在第i次碰撞后，卷入碰撞的各站选用同一重发延迟的可能性是2-i，从而使再次发生碰撞的可能很小。这种算法的优点是当网络载荷增加时能自动适应载荷，但碰撞次数不能无限地增加，其上限为10次。因此，这算法亦称截尾二进制指数退避算法。

除了二进制指数退避算法外，常用的还有线性退避算法。其计算公式为

W=2d+k×R

式中，k为常数，通常取1.5为最佳。

现简略分析一下CSMA/CD协议在重载荷下的性能。设共有Q个站已准备好要发送的报文分组，若每个站在某争用时间片内发送的概率均为P，则某站在该时间片内获得信道的概率是

A=QP（1-P）Q-1

当P=1/Q时，A=Amax=（1-1/Q）Q-1；当Q→∞时，Amax→1/e.经过J个争用时间片发送成功的概率是A（1-A）J-1，因此每次争夺间隔的平均争用时间片数为

因为每个争用时间片为2d，所以平均争夺间隔为

当P=1/Q时，每次争夺的平均争用时间片数决不会大于（e-1），因此，平均争夺间隔D'最多是2d（e-1）≈3.4d.若报文分组长为p，传输速率为C，则信道的利用率为

4、应答式CSMA/CD协议

在前面的讨论中，对数据单位采用了报文分组这个笼统的名称。但在实际传送过程中，报文分组中具有数据分组、应答分组等多种类型。由于干扰的存在，分组可能被破坏，需要对通信的过程进行确认。如果应答分组和其它分组一样，也要参与争夺信道，将导致应答的响应时间加长，使不该重发的数据分组也重发，继而引起网络载荷加重，传输效率下降。日本庆应大学的ToKoro等人为解决此问题，提出了应答式CSMA/CD协议。

应答式CSMA/CD协议是以优先权为基础的，发送应答的优先权高于发送数据的优先权。其特点如下：

①发送站要发送一个数据分组，首先要检测载波，这与CSMA/CD是一样的，不同之处在于检测到空闲信道后再等待一段时间，这个时间叫做基本等待时间，记为BWT.在BWT之后，如信道仍是空闲的才能开始发送数据分组。如果发生碰撞也按一定的退避算法重发，这与CSMA/CD是相同的；

②接收站接收完数据分组后立即向发送站发送应答报文分组，若发生碰撞则按出错处理；

③基本等待时间BWT≥2d（争用时间片）。这样的BWT既保证了应答分组优先发送，又不产生碰撞。由于BWT与报文分组传送时间相比是很短的，因此可提高传输效率，减少响应时间。

图8.2.6描述了应答式CSMA/CD协议的工作原理。图中表示的情况是：站A向站C发送一个数据分组，在该报文分组发送过程中B也产生发送要求。站C接收完毕后，立即发送应答报文分组，该应答报文分组通过站B时，它正处于BWT的等待之中，故不会发生碰撞。图8.2.7给出了应答式CSMA/CD的发送、接收流程图。

图8.2.6　应答式CSMA/CD协议的工作原理