摘要
Mesh网络是较早研究的且现在仍然是最为重要的、最有吸引力的网络模型之一。因其结构、规则简单及良好的可扩展性,易于VLSI(超大规模集成电路)的实现,网格(Mesh)网络不仅成为了许多理论研究的基础模型,而且也是许多大型多处理器并行计算机系统所采用的拓扑结构。给出了两种故障情形下的最短路由算法:1)当Mesh的行数大于等于3且列数大于等于3、出现一个矩形故障区域时,给出了任意两个无故障结点间的最短路由算法,并且计算出了路径长度;2)当Mesh的行数≥3且列数≥3、某个结点及其k跳以内的邻居结点出现故障时,给出了任意两个无故障结点间的最短路由算法,并且计算出了路径长度。
Mesh network is studied early and it is still one of the most important and attractive network models at present.Because of its simple,regular and scalable structure,and it is useful for the implementation of VLSI(Very Large Scale Integrated Circuit),Mesh network has not only become the basic model of many theoretical studies,but also the topology structure of many large multiprocessor and parallel computer systems.A mesh with mrows and ncolumns is denoted by Mm,n.In this paper,we gave the shortest routing algorithm under two different kinds of faulty area.1)We gave a routing algorithm to find the shortest path between any two fault-free nodes in Mm,n with m≥3and n≥3,and calculated the length of the path obtained by the algorithm when there is a rectangular faulty region.2)We gave a routing algorithm to find the shortest path between any two fault-free nodes in Mm,n with m≥3and n≥3,and calculated the length of the path given by the algorithm when there exists such a situation that a node and its k-hop neighbours are faulty.
出处
《计算机科学》
CSCD
北大核心
2017年第S1期252-257,共6页
Computer Science
基金
软件新技术与产业化协同创新中心
国家自然科学基金项目(61572340)资助
关键词
最短路由算法
容错路由算法
网格网络
Shortest routing algorithm
Fault-tolerant routing algorithm
Mesh network
