无死锁的包交换

在计算机网络中，死锁是最严重的系统故障之一。所谓死锁，指的是数据包陷入循环状态，无论采取何种处理措施，它们都永远无法到达目的地。必须及时发现并妥善处理死锁问题，以避免系统崩溃。

我们今天所使用的大多数网络都是分组交换网络。在这种网络中，消息被分解成多个数据包，然后这些数据包会被从源点传输到目的地。

存储转发式死锁：

这就是那种被广泛讨论的死锁现象。在这种情况下，中间节点会收到来自不同目的地的数据包，这些数据包需要被存储在本地缓冲区中，然后根据路由表将它们转发给下一个节点。但由于本地缓冲区的容量是有限的，这就导致了死锁的发生。.

例如：a、b、c、d 是四个节点。所有节点的缓冲区大小都是4。假设节点‘a’通过节点‘b’向节点‘d’发送数据包，而节点‘d’也通过节点‘c’向节点‘a’发送数据包。

解决方案：现在，要到达节点‘d’，所有来自‘b’的数据包都必须被传输到‘c’。同样地，要到达节点‘a’，所有来自‘c’的数据包也必须被传输到‘b’。不过，这些节点中没有任何一个节点的缓冲区是空的。

解决存储转发死锁的假设条件：

解决这个问题的过程中，有一些假设需要被满足，具体如下：

模型：该网络可以被看作是一个图G = (V, E)，其中V表示处理器集合，E表示通信链接的集合。每个节点都拥有B个缓冲区，而k则代表在G中，某个数据包所经过的最长路径的长度。

移动：我们将分布式计算视为一系列动作的集合。也就是说，环境中发生某些事情后，各个节点会对此作出相应的反应。

1. 生成/创造这是一个负责创建或接收新数据包的节点。该节点被认为是该数据包的发送源。
2. 转发：该数据包会被转发到新节点上，因为新节点的路由路径上的缓冲区是空的。
3. 消费：当数据包到达目的地后，它就会从缓冲区中被移除。

分组交换的要求：

1. 一种控制器算法，能够允许网络中的各种移动操作。
2. 在目的地，始终允许消耗一包商品。
3. 在所有缓冲区都为空的情况下，仍然可以生成数据包。
4. 该控制器仅使用本地信息来进行操作。
5. 如果某个控制器能够防止网络陷入死锁状态，那么就可以说该控制器是“无死锁的”。

解决存储转发死锁的方法：

为了解决这一僵局，我们有两种解决方案：

1. 结构化缓冲池
2. 非结构化缓冲池

结构化缓冲池：

使用结构化缓冲池的方法，可以为某个节点和某个数据包指定一个特定的缓冲区。如果生成或接收到了该数据包，那么必须使用该指定的缓冲区来存储该数据包。如果该缓冲区已被占用，那么该数据包就无法被接受。

缓冲图（Buffer Graph）：这是一种结构化的解决方案，用于解决僵局问题。它实际上是一种虚拟的有向图，该图是基于网络中的缓冲区来定义的。

1. 缓冲图没有有向环，也就是说，它是不存在有向环的。
2. 对于每一个路由路径来说，缓冲图中必须存在一条与之对应的路径。

【注意：数据包的传输路径是由路由算法决定的。而缓冲区管理策略则决定了数据包将在下一个节点中存储在哪个缓冲区里。】

2. 缓冲图控制器：

• 只有当节点中的缓冲区为空时，才允许生成数据包。
• 只有当下一个节点中有空闲的缓冲区时，才允许数据包的转发。

根据这套规则，可以避免僵局的发生，同时还能有效防止数据包的丢失。

缺点：存储缓冲区的使用受到限制。

非结构化缓冲池：

在使用非结构化缓冲池的方法中，所有的缓冲区都是平等的。该方法只是规定是否应该接受某个数据包，而并不决定该数据包应该被放置在哪个缓冲池中。

前馈计数控制器（FC）：这是一种非结构化的解决方案。对于某个数据包p来说，假设sp表示到达目的地的跳数，而fu表示节点中可用的缓冲区数量。那么，如果sp < fu，则控制器会接受这个数据包p。
如果B表示节点中可用的空闲缓冲区的最大数量，而k则表示到达目标位置所需的跳转次数上限，那么当B大于K时，就一定能够避免陷入死锁状态。
从上述内容可以看出，Forward计数控制器是一种不会陷入死锁的控制器。

2. 转发状态控制器(FS)：接收端需要更多关于数据包的信息。例如，如果空闲缓冲区b的数量少于数据包到达目的地的路径长度，那么就需要将Forward State Controller视为一种不会导致死锁的控制器。

3. 后退计数控制器（BC）：这是一种“转发计数控制器”的变体。当数据包从源节点传输到目标节点时，只有当该数据包的缓冲区中至少包含一些有效的数据时，它才可以被接受。也就是说，对于某个数据包p来说，假设tp表示数据包从源节点出发后经过的跳数，那么控制器会在满足tp>k-fu的情况下才接受该数据包。
通过应用这种方法，可以防止网络中的死锁现象。因此，所谓的“反向计数控制器”实际上就是一种能够避免死锁的控制器。

4. 后退状态控制器（BS）：与前向状态控制器类似，在反向状态控制器中，我们可以利用接收节点中数据包的更多信息来做出决策。

FC、BC、FS、BS之间的关系：

1. FC ⊂ FS，即
2. BC ⊂ BS
3. BC ⊂ FC
4. BS ⊂ FS

其他一些常见的死锁情况包括：

后代陷入僵局/后代无法继续繁衍这种情况可能发生在网络中，当一个数据包p能够生成另一个数据包q时。这种情况下，就违反了“网络始终允许转发和消耗数据包”这一假设。为了避免这种死锁现象，可以在缓冲图中使用多个层次结构来避免这种情况。

2. 复制与释放的死锁问题这种情况可能发生在源端持有数据包的副本时，直到从目标端收到对数据包的确认之后，才释放该副本。为了避免这种死锁现象，可以采用两种扩展的缓冲图原理来解决问题。

3. 节奏陷入僵局这种情况可能发生在网络中存在节点且内部存储有限的情况下。这些节点可能会拒绝处理新的消息，直到有新的消息被生成为止。为了避免这种死锁现象，可以将“和平数据包”与“延迟响应”区分开来。

4. 重新组装时出现死锁现象这种情况可能出现在那些需要将大消息分割成较小的数据包进行传输的网络中。在这样的网络中，只有当消息中的所有数据包都到达目的地之后，才能从网络中移除任何一个数据包。为了避免这种重新组装过程中的死锁现象，可以分别使用不同的缓冲区来负责数据包的转发和重新组装工作。