多路访问：信道划分、随机访问与轮流访问

多路访问问题

链路分为两类：点对点链路只连接一对结点，而广播链路让多个结点连接到同一个共享信道上，任何一个结点发送的帧都会被其他所有结点收到。当两个或更多结点同时发送时，它们的信号在信道上叠加，接收方无法正确解析任何一帧，这称为冲突（collision）。协调各结点如何使用共享信道的规则，就是多路访问协议，也称媒体访问控制（MAC）协议。

对于速率为$R$的广播信道，理想的多路访问协议应当做到：只有一个结点要发送时，它能以速率$R$发送；有$M$个结点要发送时，每个结点的平均速率为$R/M$；协议是分散的，没有会导致整个网络瘫痪的特殊结点；协议简单、实现成本低。

多路访问协议大体可以分为三类：信道划分协议、随机访问协议和轮流协议。

共享介质型网络

共享介质型网络顾名思义就是多个设备共同使用同一个通信介质的网络，这是一种半双工的设计。半双工指的是数据可以在一个信道上的两个方向上相互传输，但是不能同时传输。

共享介质型网络的类型主要有以太网（Ethernet）和光纤分布式数据接口。

既然多个设备会共同使用一个信道，那么就可能存在多个数据传输到同一个介质上导致的数据争用问题。为此，共享介质型网络有争用和令牌传递（token-passing protocol）两种介质访问控制方式。

信道划分协议

信道划分协议事先把信道“切”成若干份，每个结点独占其中一份，因此永远不会发生冲突：

信道划分在负载很重时效率很高，但在负载很轻时浪费严重，这正是随机访问协议要解决的问题。

随机访问协议

在随机访问协议中，结点总是以信道的全部速率$R$发送。一旦发生冲突，各结点分别等待一个随机时间后重传，随机性使它们很可能不会再次撞在一起。

ALOHA与时隙ALOHA

时隙ALOHA把时间分成长度等于一个帧时间的时隙，结点只在时隙开始时发送；如果发生冲突，就在之后的每个时隙中以概率$p$重传。设有$N$个活跃结点，一个时隙成功当且仅当恰好有一个结点发送：

也就是说，结点很多时最多只有约37%的时隙在传送有用的数据。纯ALOHA不分时隙，一帧会与前后各一个帧时间内发送的任何帧冲突，最大效率只有$1/(2e) \approx 0.18$。

争用

争用是发生在载波侦听多路访问（CSMA, Carrier Sense Multiple Access）上的数据访问方式。在这种访问方式下，网络中各个介质会采用先到先得的方式占用载波信道发送数据。如果多个介质同时发送帧，就势必会产生冲突，继而导致通信性能的下降和网络拥堵。

假设A想要给C发送数据，那么A会在确认周围没有其它介质要给C发送数据后，把数据发给C。在这个过程中，A会给信道上的每个介质都发送数据，每个介质在接收到A的数据后，会从A的报文中解析出MAC地址。如果这个数据不是发给自己的，就会丢弃这条数据。

在CSMA中，介质首先会监控载波信道上是否有数据存在，如果没有就会发送数据；如果有，则会等一段时间再发送。

带冲突检测的CSMA（CSMA/CD）

先听后说并不能消除冲突：信号在总线上传播需要时间，远处的结点在信号到达之前仍会认为信道空闲。CSMA/CD在此基础上增加了“边说边听”：结点在发送的同时检测信道，一旦发现冲突就立即停止发送，并发出一个短的阻塞信号（jam）通知所有结点，然后随机退避一段时间再重试。这样，冲突的帧不会被完整地发送出去，浪费的信道时间大大减少。

设$d_{prop}$为信号在两个最远结点之间的最大传播时延，$d_{trans}$为发送一个最长帧的时间，CSMA/CD的效率可以近似为：

传播时延越小、帧越长，效率就越接近1。

轮流协议

随机访问协议在负载轻时表现很好，但负载重时冲突频繁。轮流协议让结点按某种顺序轮流发送，常见的有两种：

• 轮询（polling）：由一个主结点依次询问每个结点是否有数据要发送。它消除了冲突，但引入了轮询时延，而且主结点一旦故障，整个信道都会停止工作。
• 令牌传递：一个称为令牌（token）的特殊帧在结点之间按固定顺序传递，令牌环就是典型的例子。

令牌环

令牌环顾名思义就是有一个令牌，以环为一圈进行令牌传输，只有获得令牌的介质才能够传输数据。

这种方式有两个优点：

1. 持有令牌的介质才能够传输数据，这样能够保证不会有报文冲突情况。
2. 每个介质都有平等获取令牌的机会，这样保证了即使网络拥堵也不会导致性能下降。

令牌环也有代价：即使只有一个结点要发送，它也必须等令牌转到自己；令牌一旦因差错而丢失，或者持有令牌的结点崩溃，就需要专门的恢复机制（例如由监控站重新产生令牌）。