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

摘要

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