路由算法主要分为两大类：确定路由算法和自适应路由算法。确定路由算法通常是基于某种固定的规则或者网络拓扑结构来寻找路径。这种算法在实现上相对简单，但是可能会在网络负载不均匀或者网络规模较大的情况下表现出较差的性能。自适应路由算法则可以根据网络的实际运行状态动态地调整路径选择，以平衡网络负载，提高整个网络的吞吐量。
例如，文献[5]中提出的PAR算法，就是一个自适应的路由算法。它能够在Mesh网络中，通过使用三个虚拟通道来防止死锁，同时具有一定的自适应特性。如果将这个算法应用到Torus网络中，由于Torus网络的结构特点，可能需要使用更多的虚拟通道来防止死锁。
另一种自适应路由算法是在文献[6]中提出的，它为阻塞的分组提供了额外的逃逸通道。当网络中的分组出现阻塞时，可以使用这个逃逸通道来避免死锁。这种方法在一定程度上增加了网络的自适应特性。
还有一种被称为Star_channel的路由算法，它最多使用五个虚拟通道来防止死锁。这种算法具有完全的自适应性，可以应用到从源节点到目标节点的所有最短路径。
除了自适应路由算法，还有一种与网络状态无关的路由算法。这种算法不依赖于网络的当前状态，例如文献[8]中提出的算法，它通过随机选择象限和中间节点的方法来平衡网络负载。RLB算法在这个基础上进行了改进，能够保证在同一维上的负载平衡。
总的来说，路由算法在数据交换结构中起着至关重要的作用。它不仅需要根据网络的当前状态来动态地调整路径选择，还需要通过资源的限制来防止死锁，充分利用物理链路带宽，平衡各个物理链路上的负载。同时，它也需要尽可能地提高节点上的缓存资源利用率，以实现更高效的数据交换。
路由算法
路由算法用来在特定的拓扑中找到一条或多条从源至目标节点的路径。维序算法(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]，能够保证在同一维上的负载平衡。由于与结构状态无关，此算法可采用源路由表方法来实现。在数据交换结构中源路由表技术更适合。路由算法简化了中间节点及更高处理速度的实现，提高了整个结构吞吐量。而且使用源路由表时，改变路由设置简单，只需更新源节点上的路由表。
本文所述的算法都是通过对资源的限制来防止死锁，充分利用物理链路带宽，平衡各个物理链路上的负载，但是对于节点上的缓存资源利用率不高。采用死锁恢复的策略可以解决这个问题。
直接互连结构在数据交换中的应用分析
