自适应路由算法优于确定性路由算法

Adaptive Routing Algorithm Excel in Deterministic Routing Algorithm

在研究并行计算机系统的容错时 ,自适应路由算法是一个极为重要的研究课题 .它是在网络结点出错时 ,算法通过可选择的路径进行路由 .在每个结点具有独立的出错概率的模型下 ,研究 Mesh网络上自适应路由算法和确定性路算法的性能 .本文提出的技术使得我们能严格地推导出路由算法的成功的概率 ,从而能分析和比较算法的性能 .研究结果表明自适应路由算法具有明显的优势 :一方面确定性路算法需要全局错误信息而变得高效性 ,另一方面自适应路由算法对于结点出错和网络规模具有更好的健壮性而具有更高的成功概率 .

In the research of fault tolerant parallel computer systems, adaptive routing algorithm is a very important subject. It routes through alternative paths in presence of faulty network nodes. This paper studied the performance of mesh network adaptive routing algorithm and deterministic routing algorithm under the model in which each network node has independent failure probability. Developed a new techniques that enable us to derive formally proven success probability for the two routing schemes and compare and analyze their performance. The formal study shows that adaptive routing algorithm has the clear advantage over deterministic routing algorithm. On the one hand, deterministic routing algorithm requires no global knowledge of network faults and is more efficient, on the other hand adaptive routing algorithm have higher success probability and are more robust to node failure probability and to network size.