宋冠军，韩江雪

（1.华北计算技术研究所，北京100083；2.清华大学 软件学院，北京100084）

0 引 言

对于互联网络而言，她主要由下述4个部分组成：路由算法、流控技术、交换技术和拓扑结构。在上述四部分中，核心部分是路由算法。也就是说，影响性能的关键的因素在于如何给某一拓扑网络设计适合的路由算法，让其在进行消息传递时花费相对较少的时间。

当前已经有很多用于构造机群系统的交换式高速互联网，其中Myinet，Autonet，等都是已经成熟的几个。这些网络，一般采用不规则的拓扑结构和虫孔路由交换技术。然而由于不规则网络拓扑结构的复杂性和不可控性，网络中出现环路即通信重叠的可能性大大增加，进而网络中更加容易出现死锁现象。

Sancho，等［1］提出了一种基于深度优先搜索的多棵树路由算法，从而降低了传统breadthfirst路由算法的路由表数量，它的启发式up／down生成算法，大大提高了路由的效率。Puente，等［2］提出了一种基于不规则网络以伪哈密顿周期为基础的自适应路由机制，明显削减了传统的up＊／down＊路由算法的额外开销，有效地避免死锁的出现，但也同时造成了路由路径的增长。A.Jouraku的文章［3］提出的一种自适应路由算法，使数据包分布的尽可能均衡。Levitin，Karpovsky，和 Mustafa［4］中提出的新算法通过保证最小的路由回路被禁止以消除思索和维护图的连通性。

因此，如何提高系统性能并避免死锁，是本论文主要讨论与解决的问题，也是本研究的核心贡献所在。up＊／down＊路由现在已被广泛使用，在包括上文提及的多篇论文［5－11］中分别对NOWs系统路由进行了不同角度的阐述，但是这些路由方法存在很多问题，比如自适应性差，根节点的瓶颈等问题。……