摘要
矩形无效块模型可以用来解决网格下的容错路由问题 ,最小连接块 (MCC)模型是它的一个改良模型 .本文在MCC基础上 ,建立MCC重叠图 ,当发现不存在曼哈顿路径的时候 ,给出一套算法 ,来计算出一条避免无效块的尽可能短的路径 .模拟试验表明 ,通过这种算法找到的路径 ,与最短路径相差很小 .比起花费更多的时间去找寻最短路径 。
Rectangular fault block model is designated to solve the problem of fault-tolerant route in mesh and was improved as Minimal-Connected-Component (MCC) model. Based on MCC, we construct an overlapping graph and give a set of algorithm according to the graph to work out the route as short as possible to avoid the appearance of fault block when Manhattan route does not exist. The simulated test shows that the route found by the algorithm mentioned above is nearly the shortest one. Hence compared to other methods costing much more time, this new heuristic fault-tolerant algorithm is of no doubt a better method in finding the shortest route.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2004年第2期318-322,共5页
Acta Electronica Sinica
基金
国家自然科学基金项目 (No.60 0 730 2 9)
国家 973项目 (No .2 0 0 2CB31 2 0 0 2 )
教育部高校青年教师奖资助计划
关键词
自适应路由
矩形无效块模型
容错性
网格
Algorithms
Computer simulation
Fault tolerant computer systems
Heuristic methods
Mathematical models
Routers
