Abstract: Seeking paths algorithm constitutes the primary factor influencing the communication performance of interconnection networks and the performance of massive parallel processors systems，so solutions for seeking paths problems of star network as one of the best alternatives to hypercube become very important.Under the conditional fault tolerant model，rules used for seeking paths are researched，and a fault-tolerance seeking paths algorithm based on adaptive rules is proposed.The correctness and the fault tolerance are analyzed.The simulation experiment confirms that the algorithm has very high success probability.Under the situation of edge failing independently，the communication reliability between two terminals in star networks is analyzed，and its lower bound limited is derived and confirmed.

Key words: star interconnection network, adaptivity, fault-tolerance seeking paths algorithm, fault-tolerance probability

摘要： 大规模并行处理机系统中寻径算法对互连网络的通信性能和系统性能起着至关重要的作用，而star互连网络作为超立方体网络的最好替代之一，其寻径问题的解决变得非常重要。在有条件的容错模型基础上，对寻径时的规则进行了研究，提出了一种基于自适应规则的容错寻径算法。对算法的正确性以及容错性进行了分析。经仿真实验证明了该算法具有较高的成功概率。在边失效独立的情况下，对star网络终端对间通信可靠性进行了分析，推导出了其约束下界，并给予了证明。

关键词: star互连网络, 自适应, 容错寻径算法, 容错性概率