路由算法决定数据包从网络中的源路由器到目标路由器所遵循的路径。设计路由算法时要重点考虑的一个方面是避免死锁。转弯限制路由 是一种用于mesh拓扑系列的路由算法，它通过限制算法中允许的下一方向来避免死锁，同时确定网络中从源节点到目标节点的路由。
产生死锁的原因
死锁（如图 1 所示）是由于缓冲区或链接等网络资源饱和而无法进一步传输数据包的情况。死锁的主要原因是网络中信道的循环获取。 例如，考虑网络中有四个信道。四个数据包已经填满了这四个信道的输入缓冲区，需要转发到下一个信道。现在假设所有这些通道的输出缓冲区也充满了需要传输到下一个信道的数据包。如果这四个信道形成一个循环，则无法继续传输数据包，因为所有通道的输出缓冲区和输入缓冲区都已满。这称为循环获取信道，会导致死锁。
死锁的解决方法
死锁可以被预防、避免、检测和解除。 就延迟和资源而言，检测和打破网络中的死锁是昂贵的。因此，简单且低成本的解决方案是使用防止循环获取信道的路由技术来避免死锁。
转弯限制路由背后的逻辑
轮流限制路由背后的逻辑源自一个关键特性。当且仅当所有四个可能的顺时针（或逆时针）旋转都已发生时，才可能出现循环获取信道的现象。这意味着可以通过至少禁止顺时针转动之一和逆时针转动之一来避免死锁。图 2 显示了非限制路由算法中所有可能的顺时针和逆时针转弯。
转弯限制路线示例
可以通过在路由算法中禁止四个可能的顺时针转弯中的至少一个和四个可能的逆时针转弯中的至少一个来获得转弯限制路由。这意味着至少有 16 (4x4) （如图 5 所示）如果当前方向为北（y轴正方向），则不能转向任何其他方向。这意味着如果在寻找路径时需要，应最后选择北方向。
负优先路由
负优先路由
例如，考虑下面的图 7。假设有多个路由器，F1、F2 等，它们将数据包传输到一个拥挤但低成本的链路，从源路由器 S 到目标路由器 D。实施转弯限制路由意味着现在可能会一些有从馈线路由器到路由器 S 的转弯被限制。这些馈线路由器可能必须使用更长的路径才能到达目的地 D，从而在一定程度上缓解从 S 到 D 的链路拥塞。
- 基于策略的路由
- 死锁
- 启发式算法
参考
评论 (0)