多计算机系统中的互连网络为处理器之间相互通信提供了一种有效的机制,是决定系统性能的重要因素之一。在互连网络中,节点间的通信由路由算法实现。路由算法决定了一条消息或报文到达目的节点所经过的路径。当代并行机的互连网络一般都采用虫孔交换作为网络互连的机制。而虫孔交换路由算法很容易产生死锁现象,导致消息不能到达目的节点,通信无法完成。这些都是设计路由算法时必须考虑的问题。局部扭曲立方体是一种新型的互连网络拓扑结构。作为超立方体的一种变体,其直径大约只有超立方体的一半左右。一个局部扭曲立方体可由两个低一维的子立方体根据一定规则连边得到。对于这种结构的路由算法,目前尚没有进行详细研究。本文的主要工作就是基于局部扭曲立方体进行的。本文首先介绍了互连网络拓扑结构中路由器模型和各种交换技术,接着介绍了现有的单播和多播路由算法和其中的无死锁路由理论。然后,在对局部扭曲立方体结构进行了详细介绍。本文对局部扭曲立方体路由算法的主要研究工作如下:在单播方面,本文提出了四种算法。首先是一种基于转弯模型的单播最短自适应路由算法。该算法利用将物理通道分成两条虚通道进而形成两个不相交的虚拟网络,将不同的点对之间的路由限定在某一个虚拟网络中,从而有效地避免了死锁的产生。在此基础上,利用局部扭曲立方体的特点,本算法对局部的子立方体采用了P-cube路由,使其能在局部子立方体中自适应路由。接下来,在保证无死锁的条件下,通过提高通道的利用率,提出了一种更具自适应性的路由算法。本文提出来的第三种算法针对死锁产生的特点,牺牲了一部分最短路由,不需要采用虚通道。虽然这种算法中路由不一定是最短的,但它在局部的子立方体中能最大限度地进行P-cube路由,自适应性有了明显提高。最后,本文还首次提出了一种基于路径的单播自适应算法,对局部扭曲立方体进行编号,依照编号来确定路由路径。它同样被证明是无死锁的。在多播路由算法研究方面,本文首先给出了局部扭曲立方体的广播树算法。只适合支持SAF和VCT交换技术的网络,当与虫孔路由结合时,很容易产生死锁。然后本文设计了一种基于单播的多播链算法,通过将多播目的节点集分成类,分别在两个子立方体上采用类似于超立方体的链算法,成功实现了在局部扭曲立方体上的多播。最后,对这个算法的性能进行了简单的分析。