并行计算机互连网络的拓扑结构一直是国际上的研究热点。人们已提出了多种互连网络拓扑结构，其中超立方体是最流行的互连网络拓扑结构之一而且已被广泛用于商业并行计算机系统。但它并不是各方面拓扑性质最好的互连网络，于是人们开展了对超立方体的一类变型，即交叉立方体及其性质的研究。研究表明，交叉立方体的某些性质优于超立方体，尤其是它的直径几乎是超立方体的一半，因此是一种值得人们研究并推广应用的互连网络拓扑结构。本文对交叉立方体网络的最短路径路由、并行路由、广播路由、无死锁路由、结点不相交路径长度以及交叉立方体环网络的嵌入问题展开了研究。本文的主要研究工作和贡献如下： (1)针对已有的交叉立方体网络最短路径路由算法只能将部分最短路径作为候选路径进行输出且不具有根据结点的繁忙程度进行选择路径能力的缺点，给出了结点各边可进行最短路径路由的充要条件，提出了一种可根据结点的繁忙程度进行择路时间复杂度为D(n2)的完全自适应最短路径路由算法，其中n为交叉立方体网络的维数。算法在进行路由的每一步，都从所有可进行最短路径路由的邻边中选择繁忙程度最低的计算机结点对应的边进行路由，因此是将全部最短路径作为候选路径，从而可输出任意一条最短路径。仿真实验结果验证了算法的有效性。 (2)对交叉立方体的顶点不相交路径进行了研究，证明了以下结论：在n维交叉立方体CQn中任意两顶点间存在n条顶点不相交的路径，并且满足①最短路径的长度=两顶点间的距离，②所有路径中最长路径的长度≤两顶点间的距离+4。这说明交叉立方体互连网络具有很好的并行通信性能和容错性能。同时提出了一种时间复杂度为O(n2)的n维交叉立方体网络并行路由算法，可输出源结点到目的结点的三条结点不相交路径P0，P1，P2，并且满足①|P0|=源结点到目的结点的距离，②|Pi|≤源结点到目的结点的距离+3(i=1，2)。 (3)在全端口虫洞模型下，利用递归方法将交叉立方体网络分解为互不相交的子交叉立方体网络，提出了n维交叉立方体网络的广播路由算法，其所需路由步数为O(n/log2(n+1))，在常数乘积因子范围内是优化的。仿真实验结果验证了算法的有效性。 (4)证明了在不使用虚通道的情况下n(n≥3)维交叉立方体网络中不存在无死锁的最短路径路由算法，通过将一个物理通道分成三个虚通道提出了一种时间复杂度为O(n)的无死锁最短路径虫洞路由算法。理论分析和仿真实验结果表明了算法的有效性。 (5)交叉立方体网络具有规模难以扩展(不易升级)的性质，而交叉立方体环网络可以有效克服升级困难的缺点。本文证明了交叉立方体环网络仍然保持了交叉立方体网络具有的哈密顿连通性和泛圈性。 本文通过对交叉立方体网络的路由算法和图嵌入问题的研究，提出了完全自适应最短路径路由算法、并行路由算法、广播路由算法以及无死锁路由算法，同时证明了交叉立方体环网络仍然保持了交叉立方体网络具有的哈密顿连通性和泛圈性，从而推动了交叉立方体网络的研究与应用。