裂痕故障块:一种面向二维或多维网格网络拓扑的容错自适应路由机制的研究与应用

This project mainly focuses on the fault-tolerant routing for the 2D/ND mesh topology based networks. We propose the Cracky Rectangular Block (CRB) mechanism for fault-tolerant and CRB routing algorithms for optimal routing. The CRB could include as less as the fault nodes and fault links keeping rectangular, so routing could detour the CRB arriving to related destination. Unlike the traditional Block based routing mechanism, CRB builds internal spanning tree, so the routing could penetrate into or cross the CRB to get the destination. As a result, CRB could route to any node if and only if this node keeping connected with this network. This mechanism greatly improves the usability and robustness of parallel computers. For further applications, it can be easily using in Network on Chips， Multicore Computer Design and the Wireless Sensor Networks.

二维/多维网格(Mesh)网络一直是主流超级计算机采用的网络互联结构。近年来，随着电子元器件，集成技术以及无线通讯技术的飞速发展，其在片上网络、多核计算机和无线传感器网络等领域得到了新的应用。然而，传统的基于网格网络的容错自适应路由在应用于这些新领域的过程中开始受到一些瓶颈的制约：1. 当网络中超过15%的节点出现故障将会导致整个网络瘫痪，此问题严重降低了基于网格网络的片上网络和无线传感网的生命周期。2. 路由避免故障绕行导致的路径加长，此问题限制了其在片上网络和无线传感器网络中的实时应用。针对以上两个问题，本课题提出裂痕故障块容错机制及相应的自适应路由策略，在保证路由无死锁和无活锁的前提下，最大限度地提高网络节点的利用率和降低网络通信的延迟，实现网络的高容错，高鲁棒，零瘫痪，低延迟以及免维护等特性，大幅提高网格网络在新的应用领域中的可用性，可靠性，并在特殊应用中实现免维护。

本项目针对网格拓扑结构的网络进行容错自适应路由课题的研究，另外在研究过程中开展了带有短期路由负荷预测的路由方法研究，及其在新领域中的应用。主要解决以下问题:1. 当网络中超过15%的节点出现故障将会导致整个网络瘫痪，此问题严重降低了基于网格网络的片上网络和无线传感网的生命周期 。2. 路由避免故障绕行导致的路径加长，此问题限制了其在片上网络和无线传感器网络中的实时应用。针对以上两个问题，本课题完成了裂痕故障块容错机制及相应的自适应路由策略，在保证路由无死锁和无活锁的前提下，最大限度地提高网络节点的利用率和降低网络通信的延迟，实现网络的高容错，高鲁棒，零瘫痪，低延迟以及免维护等特性，大幅提高网格网络在新的应用领域中的可用性，可靠性，并在特殊应用中结合短期负荷预测，提高预测准确率，降低路由故障，提高路由效率，同时也完成了短期负荷预测的相关算法研究及其在新领域中的应用。本项目目前取得的成果为发表高水平论文10篇，其中SCI论文6篇，包括一区论文一篇，二区论文3篇，EI论文4篇，获得专利授权1项。另外完成了面向二维或多维网格拓扑结构的并行计算机裂痕故障块的构造模型，完成了面向二维或多维网格拓扑结构的并行计算机自适应消息优化路由机制，研制开发了面向二维网格网络拓扑的并行计算机节点消息转发中间件，并且在项目执行过程中完成了基于短期网络路由负荷预测的路由方法研究，并将该预测方法成功应用到了其他领域，取得了良好的效果。