关键词: 星形网络, 容错性, 路由算法, 概率分析

Abstract: In the paper，the node-to-node fault-tolerance parallel routing problem of star network with faulty nodes is studied.A new node-to-node parallel routing algorithm with certain fault-tolerance ability is proposed.The new algorithm is strictly proved to be correct.The time complexity of new algorithm is discussed and the length of paths found by new algorithm is analyzed.The fault-tolerance probability of new algorithm is strictly analyzed by probabilistic analysis approach and its limitation range is calculated respectively.

Key words: star network, fault tolerance, routing algorithm, probability analysis