什么是自适应路由？

在自适应路由中，中间节点可以考虑实际的网络状况，包括是否存在劣化或瓶颈，并据此决定将消息传输到哪个邻居。自适应路由方案根据输出通道的选择，可以是有利路由或错误路由。在有利路由中，只有已知可以保证更接近目的地的通道才是候选通道。

有利路由代表了一种保守的观点。错误路由协议依赖于乐观观点，并且可以使用有利和非有利通道来建立源和目的地之间的路径。乐观地选择非有利通道假设它将引导消息到一组空闲的有利通道，从而允许进一步向目的地前进。

有利协议的优点如下：

• 它们导致最短路径。
• 它们没有死锁。
• 它可以使其易于证明无死锁。

当网络中存在故障通道时，错误路由协议是有利的。在这种情况下，错误路由协议更有可能找到合适的路径。

自适应路由方案可以进一步细分为渐进式或回溯式协议。在渐进式路由中，消息不能在其已遵循的路径上向后移动。

相反，在回溯方案中，消息可以回溯并系统地探索源节点和目标节点之间所有可能的路径。消息头必须包含一些状态信息以避免重复搜索相同的路径，因此可以确保无死锁。

回溯方案也是无死锁的，因为它们不会阻塞持有资源。它可以防止重复搜索相同的路径，回溯协议在消息头（或探测）中存储历史信息。由于搜索空间可能非常大，尤其是在错误路由协议中，因此头变得太长，这会显着增加延迟时间。

在电路交换中，每个节点上的硬件支持可以显着减小报头大小。多计算机的每个节点上的每个通道都提供了一个历史位向量，该向量包含与节点上可用通道一样多的位。如果探测在通道 K 上进入节点，则历史位向量 K 的位包含有关相应输出通道的信息。如果已尝试输出通道，则相应的位为高，否则为低。每个节点上都使用一个额外的历史位向量来管理节点本身创建的探测。

如果中间节点没有空闲的有利通道，则有几种替代策略可供选择：

• 渐进式有利路由等待有利通道变为空闲。

• 渐进式错误路由协议尝试一个非有利的空闲通道。

• 回溯路由向后移动并从较早的节点重新开始。

Ginni

更新于： 2021-07-23

915 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习