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

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

项目编号： No.61300230

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 杨裔

作者单位： 兰州大学

项目金额： 24万元

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

中文关键词： 自适应路由；容错路由；短期路由负荷预测；二维／多维网格网络；无线多跳网络

英文摘要： 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.

英文关键词： self-adapted routing；fault tolerant routing；short-term routing load forecasting；2d/nd mesh；wireless mesh network