路由算法

路由算法

路由算法用来在特定的拓扑中找到一条或多条从源至目标节点的路径。维序算法(dimension order routing)以确定的维顺序路由，在Mesh结构中不需要虚拟通道就可以实现无死锁路由[4]。它实现简单，但性能差，特别在业务负载不均匀，交换结构规模较大时更为突出。自适应路由算法通过寻找空闲通道的方法来平衡负载，增加整个结构吞吐量。文献[5]提出了无死锁的部分自适应的最短路径路由算法(planar adaptive algorithm，PAR)：对任意规模的Mesh结构都只需3个虚拟通道就可解决死锁，该算法具有一定的自适应特性。如果该算法应用在Torus中，由于Torus结构较Mesh结构在每维最远节点对间存在环路，所以还需提供一倍的虚拟通道来防止死锁。

文献[6]提供了一种自适应路由算法的构造方法。是对阻塞的分组提供额外逃逸通道。在分组出现阻塞后采用该通道，同时在逃逸通道所构成的网络中采用一定资源限制防止死锁。比PAR进一步增加了自适应特性。

Star_channel算法最多用5个虚拟通道来防止死锁[7]。具有完全自适应性的最短路径算法，即路由算法可应用从源节点s到目标节点d的所有最短路径。
本文提到的三种算法都是动态自适应的，根据网络的状态来改变路由。还有一种是与网络状态无关的路由算法，如下所述。

文献[8]算法通过随机选择象限和中间节点的方法来平衡负载。RLB算法在此作了进一步改进[9]，能够保证在同一维上的负载平衡。由于与结构状态无关，此算法可采用源路由表方法来实现。在数据交换结构中源路由表技术更适合。路由算法简化了中间节点及更高处理速度的实现，提高了整个结构吞吐量。而且使用源路由表时，改变路由设置简单，只需更新源节点上的路由表。
本文所述的算法都是通过对资源的限制来防止死锁，充分利用物理链路带宽，平衡各个物理链路上的负载，但是对于节点上的缓存资源利用率不高。采用死锁恢复的策略可以解决这个问题。

直接互连结构在数据交换中的应用分析