计算机网络中的无冲突协议

几乎所有的碰撞都可以被避免。CSMA/CD不过，这种情况仍然可能在争用期间发生。在争用期间发生冲突的话，会严重影响系统的性能。这种情况通常发生在电缆长度较长而数据包的长度较短的情况下。随着光纤网络的应用越来越广泛，这个问题变得更加严重了。接下来，我们将讨论一些能够解决争用期间冲突问题的协议。

• 位图协议
• 二进制倒计时
• 有限关注协议
• 自适应树形路径协议

纯正的Aloha技术，以及CSMA和CSMA/CD机制基于竞争的协议：

• 尝试一下，如果发生碰撞的话，再重试一次。
• 无法保证其性能表现
• 如果网络负载过高，会发生什么情况呢？

无碰撞协议：

• 支付持续性的运营成本，以实现性能保障。
• 在网络负载较高的情况下，这种方式非常有用。

位图协议：
位图协议是一种无冲突的通信协议。在位图协议中，每个争用周期恰好包含N个时隙。如果某个站点需要发送数据，那么它会在对应的时隙中发送一个1比特的信号。例如，如果站点2有数据要发送，那么它就会在第二个时隙中发送一个1比特的信号。

一般来说，Station 1会通过将1位数据插入到第1个槽位中来表明自己有要传输的数据。这样，每个站点都清楚哪个站点想要进行传输。因为大家都已经确定了下一个要传输的站点，所以不会发生冲突的情况。这种以“谁先传输”来决定传输顺序的协议被称为“预约协议”。

为了分析该协议的性能，我们将以“竞争位时隙”为单位来衡量时间。一个数据帧由d个时间单位组成。在低负载情况下，由于没有数据帧的传输，比特位图会一直重复出现。在高负载情况下，所有站点都有数据需要发送，因此N位竞争周期会被分配到N个时隙中，这样每个时隙中的开销就只有1位而已。

一般来说，编号较高的站点需要等待半扫描时间后才能开始传输数据；而编号较低的站点则需要在等待半扫描时间之后，再继续传输数据。具体来说，编号较低的站点平均需要等待1.5个N个比特的时间才能开始传输数据。
 

2. 二进制倒计时：
二进制倒计时协议被用来克服每个二进制站点需要额外1位比特的开销问题。在二进制倒计时中，使用的是二进制站点地址。希望使用该通道的站点会将其地址以二进制比特串的形式发送出去，且起始位为最高位。所有地址的长度都是相同的。下面，我们将通过示例来说明二进制倒计时的工作原理。

在这种方法中，会同时读取不同的站点地址，从而确定传输的优先级。 如果这些站点0001、1001、1100、1011都试图抢占这个传输通道的话…… 所有电台在最初播放时，都会广播出它们最重要的地址位，这些地址位分别对应于0、1、1、1。 最重要的几位二进制位会被一起读取。 站点0001看到另一个站点地址中的第1个MSB后，得知有一个编号更高的站点正在争夺该频道。因此，它选择放弃当前轮次的竞争。

另外三个站点，即1001、1100和1011，继续传输数据。下一个比特值为1的站点是1100。因此，1011和1001这两个站点因为其第二个比特值为0而停止传输。之后，1100这个站点开始传输数据，随后又开始了下一个传输周期。

3. 有限关注协议：

• 基于碰撞的协议（如纯ALOHA协议、带时隙的ALOHA协议以及CSMA/CD协议）在网络负载较低的情况下表现良好。
• 当负载较高时，无冲突的协议（如位图、二进制倒计时等）是非常合适的选择。
• 那么，将它们各自的优点结合起来会怎么样呢：

1. 在轻负载情况下，其行为类似于ALOHA协议。
2. 在负载较重的情况下，其行为类似于位图方案。

4. 自适应树形路径协议：

• 将整个组中的用户进行划分，从而限制每个时隙内的竞争程度。
• 在较小的负载下，每个人都可以尝试每个时间段来享受这种感觉。
• 在重负荷的情况下，每个插槽只能有一个设备能够尝试接入。
• 我们该如何做到这一点呢？

1. 将每个站点都视为二叉树的叶子节点。
2. 在成功传输之后，第一个时间段内，所有电台/设备都可以进行通信。
   可以尝试在根节点之下找到那个插槽。
3. 如果没有冲突的话，那就没问题了。
4. 否则，如果发生冲突的话，那么只有处于子树下的节点才会尝试进行下一次搜索。（深度优先搜索）

槽位0C*、E*、F*、H*（节点0下的所有节点都可以尝试发送数据）。存在冲突。
Slot-1C*（节点1下的所有节点都可以尝试），C发送。
槽2E*、F*、H*（所有位于节点2下方的节点都可以尝试进行冲突处理）
Slot-3E*、F*（节点5下的所有节点都可以尝试发送数据），存在冲突
Slot-4E*（E下的所有节点都可以尝试），E发送
槽5F*（F下的所有节点都可以尝试），F发送
槽6H*（节点6下的所有节点都可以尝试发送数据），H开始发送数据。