跳转到内容

转弯限制路由

编辑链接
维基百科，自由的百科全书

路由算法决定数据包从网络中的源路由器到目标路由器所遵循的路径。设计路由算法时要重点考虑的一个方面是避免死锁。转弯限制路由[1] [2]是一种用于mesh拓扑系列的路由算法，它通过限制算法中允许的下一方向来避免死锁，同时确定网络中从源节点到目标节点的路由。

图 1：图中显示了输入和输出缓冲区都已满的四个信道。输出缓冲区中的所有数据包都将被转发到下一个信道。但是由于它们的输入缓冲区已满，因此无法进行转发。结果，不能再移动任何数据包。这就产生了死锁。

产生死锁的原因

死锁（如图 1 所示）是由于缓冲区或链接等网络资源饱和而无法进一步传输数据包的情况。死锁[3]的主要原因是网络中信道的循环获取。 [4]例如，考虑网络中有四个信道。四个数据包已经填满了这四个信道的输入缓冲区，需要转发到下一个信道。现在假设所有这些通道的输出缓冲区也充满了需要传输到下一个信道的数据包。如果这四个信道形成一个循环，则无法继续传输数据包，因为所有通道的输出缓冲区和输入缓冲区都已满。这称为循环获取信道，会导致死锁。

死锁的解决方法

死锁可以被预防、避免、检测和解除。 [5]就延迟和资源而言，检测和打破网络中的死锁是昂贵的。因此，简单且低成本的解决方案是使用防止循环获取信道的路由技术来避免死锁。 [6]

图 2：网络路线中所有可能的转弯 - 顺时针和逆时针。

转弯限制路由背后的逻辑

轮流限制路由背后的逻辑源自一个关键特性。当且仅当所有四个可能的顺时针（或逆时针）旋转都已发生时，才可能出现循环获取信道的现象。这意味着可以通过至少禁止顺时针转动之一和逆时针转动之一来避免死锁。图 2 显示了非限制路由算法中所有可能的顺时针和逆时针转弯。

图 3：XY 路由

转弯限制路线示例

可以通过在路由算法中禁止四个可能的顺时针转弯中的至少一个和四个可能的逆时针转弯中的至少一个来获得转弯限制路由。这意味着至少有 16 (4x4) [5]种可能的转弯限制路由技术，因为总共有 4 个顺时针转弯和 4 个逆时针转弯可供选择。下面列出了其中一些技术。

图 4：西向优先路由
图 5：北最后路由
图 6：负优先路由

XY 路由

XY 路由 [5] （如图 3 所示）限制了从 y 轴到 x 轴的所有转向。这避免了并不一定需要的两个逆时针和两个顺时针转向。因为它限制了允许的转弯方向，我们可以把它作为转弯限制路由的示例。

西优先路由

西优先路由[2] [5] （如图 4 所示）限制所有转向西方向（x轴负方向）的转弯。这意味着如果在寻找路径时需要，应首先选择西向。

北最后路由

北最后路由 [2] [7] （如图 5 所示）如果当前方向为北（y轴正方向），则不能转向任何其他方向。这意味着如果在寻找路径时需要，应最后选择北方向。

负优先路由

负优先路由 [2] [7] （如图6所示）禁止在上一方向为正时转向负方向。西被认为是X维度的负方向，南被认为是Y维度的负方向。这意味着在进行任何其他转弯之前，应在其中一个负方向上有越点。

转弯限制路由的优点

  • 与死锁检测和解除技术相比，避免死锁的实现成本更低。
  • 转弯限制提供从一个节点到另一个节点的最短路径以及非最小长度路径作为备用，这允许绕过拥塞或故障链路进行路由。 [8]

例如，考虑下面的图 7。假设有多个路由器，F1、F2 等，它们将数据包传输到一个拥挤但低成本的链路，从源路由器 S 到目标路由器 D。实施转弯限制路由意味着现在可能会一些有从馈线路由器到路由器 S 的转弯被限制。这些馈线路由器可能必须使用更长的路径才能到达目的地 D，从而在一定程度上缓解从 S 到 D 的链路拥塞。

图 7：相互连接的四台路由器 F1、F2、S 和 D 的拓扑结构。转向限制可以在一定程度上缓解链路 SD 上的拥塞。

参考

  1. ^ Solihin, Yan. fundamentals of parallel computer architecture. solihin books. 2016: 390–392. ISBN 9780984163007. 
  2. ^ 2.0 2.1 2.2 2.3 CHRISTOPHER J. GLASS AND LIONEL M. NI. The Turn Model for Adaptive Routing (PDF). Michigan State University. [2023-04-14]. （原始内容 (PDF)存档于2016-12-03）. 
  3. ^ Solihin, Yan. fundamentals of parallel computer architecture. solihin books. 2016: 388–389. ISBN 9780984163007. 
  4. ^ Coulouris, George. Distributed Systems Concepts and Design. Pearson. 2012. ISBN 978-0-273-76059-7. 
  5. ^ 5.0 5.1 5.2 5.3 Solihin, Yan. fundamentals of parallel computer architecture. solihin books. 2016: 390. ISBN 9780984163007. 
  6. ^ Havender, James W. Avoiding deadlock in multitasking systems. IBM Systems Journal. 1968, 7 (2): 74–84 [2023-04-14]. doi:10.1147/sj.72.0074. （原始内容存档于2012-02-24）. 
  7. ^ 7.0 7.1 Solihin, Yan. Fundamentals of parallel computer architecture. Solihin books. 2016: 390–391. ISBN 9780984163007. 
  8. ^ Solihin, Yan. fundamentals of parallel computer architecture. solihin books. 2016: 392. 
检索自“https://zh.wikipedia.org/w/index.php?title=转弯限制路由&oldid=82626332”