曹入辉，梁家荣，王新阳，豆秋丽

（广西大学计算机与电子信息学院，广西 南宁 530004）

1 引言

互连网络的拓扑结构是计算机科学中的一个重要研究分支，人们已提出了多种互连网络，其中超立方体网络是极具吸引力的网络模型之一。超立方体网络具有正规性、对称性、可靠性、强容错性、可嵌入性、直径短和网络通信能力的可扩展性等优点［1～3］，然而对于n 维的超立方体，在n 值较大时，也就是网络中的节点数很大时，过多的边数使得超立方体网络的实现和扩展很困难，开销和性能提高的对比越来越大。为了保持超立方体网络的优点，同时避开因边数增大给网络的实现和扩展等方面带来的困难，人们转而研究超立方体网络的变种。其中，交换超立方网就是超立方体网络的一个重要变种，它具有非常灵活的结构，可以根据需要很容易地在原有基础上进行扩展；此外，它在和其他超立方体网络的变体比较时有自己独特的优势，即交换超立方网可以作为P2P 环境中的一种逻辑拓扑结构［4］，因此相信交换超立网将会成为未来并行计算机系统中一个重要的应用网络模型。

死锁问题一直是并行计算机系统互连网络路由算法研究中的关键问题，死锁是指系统在某一时刻存在若干信息因彼此等待网络信道资源而永远无法达到终点的情形。在避免死锁的路由算法设计中，可采取以下两种算法：第一种为确定性路由算法，确定性路由算法是指在两个主机之间确定单一的路径；……