死锁恢复的多维交换结构容错路由算法

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

死锁恢复的多维交换结构容错路由算法

许都, 宋雷, 王宏

文章导航 > 电子科技大学学报 > 2008 > 37(6): 844-847,854

许都, 宋雷, 王宏. 死锁恢复的多维交换结构容错路由算法[J]. 电子科技大学学报, 2008, 37(6): 844-847,854.

引用本文:

许都, 宋雷, 王宏. 死锁恢复的多维交换结构容错路由算法[J]. 电子科技大学学报, 2008, 37(6): 844-847,854.

XU Du, SONG Lei, WANG Hong. Deadlock Recovery-Based Fault Tolerant Routing Algorithm for Multi-Dimensional Switching Fabric[J]. Journal of University of Electronic Science and Technology of China, 2008, 37(6): 844-847,854.

Citation:

XU Du, SONG Lei, WANG Hong. Deadlock Recovery-Based Fault Tolerant Routing Algorithm for Multi-Dimensional Switching Fabric[J]. Journal of University of Electronic Science and Technology of China, 2008, 37(6): 844-847,854.

死锁恢复的多维交换结构容错路由算法

1.
电子科技大学宽带光纤传输与通信网技术教育部重点实验室成都 610054

基金项目:

国家自然科学基金(60372011)

作者简介:
许都(1968-),男,副教授,主要从事通信网络理论及应用方面的研究.

中图分类号: TP302.8

Deadlock Recovery-Based Fault Tolerant Routing Algorithm for Multi-Dimensional Switching Fabric

1.
Key Laboratory of Ministry of Education for Broadband Optical Fiber Transmission and Communication Networks,University of Electronics Science and Technology of China Chengdu 610054

摘要: 在高性能路由器中采用多维交换结构是解决可扩展性的一种方法。在实现这种交换结构时,随着节点数目的增多,交换结构出现故障的概率也随之增加。该文在mesh/torus结构上提出了一种基于死锁恢复策略的容错路由算法MMAR。基于各非故障节点周围链路的状态,MMAR能容错任意形状的故障模型且所需虚拟通道数少。通过在凹形区域表面节点中设置该凹形区域内节点位置信息表,该算法能避免消息进入与其目的节点无关的凹形区域以使绕道路径最短。该文给出了在256个节点的二维torus中的仿真结果,验证了算法的有效性。
- 死锁恢复 /
- 故障模型 /
- 容错路由算法 /
- 多维交换结构
Abstract: Scalable switching fabrics can be used to implement high performance routers by employing multi-dimensional switching fabrics. But the fault probability of switching fabric also increases with the increase of components. A novel fault-tolerant algorithm on the mesh/torus, named as minimal misrouted adaptive routing (MMAR), is proposed based on deadlock recovery mechanism. According to the status of links around each fault-free node, MMAR can accommodate arbitrary shaped fault models using minimal number of virtual channels. When encountering concave fault models, through setting the position tables for the nodes within the concave regions at the surface nodes of each concave region, MMAR can minimize the length of the misrouted paths by avoiding routing the message into the irrespective holes. Performance results of a simulation on torus with 256 nodes are also given.
- deadlock recovery /
- fault model /
- fault-tolerant routing algorithm /
- multi-dimensional switching fabric

[1]	郭志成, 刘影, 陈钰书, 唐明. 复杂网络上具有自适应行为的故障-恢复传播动力学研究 . 电子科技大学学报, 2024, 53(): 1-9. doi: 10.12178/1001-0548.2023080
[2]	张治中, 朱磊, 冯琳琳, 刘利兰. 基于多维属性的跨域虚拟网络映射算法 . 电子科技大学学报, 2019, 48(2): 174-181. doi: 10.3969/j.issn.1001-0548.2019.02.003
[3]	高媛, 杨成林. 基于复模型的模拟电路故障诊断 . 电子科技大学学报, 2017, 46(4): 540-546. doi: 10.3969/j.issn.1001-0548.2017.04.011
[4]	聂旭云, 杨炎, 刘梦娟, 秦志光. 基于节点能力模型的容迟网络路由算法 . 电子科技大学学报, 2013, 42(6): 905-910. doi: 10.3969/j.issn.1001-0548.2013.06.018
[5]	宋劲松, 周激流, 李振华, 张晓阳. 解决所有权死锁的一种数字水印算法 . 电子科技大学学报, 2011, 40(5): 787-790. doi: 10.3969/j.issn.1001-0548.2011.05.029
[6]	杨成林, 田书林, 龙兵. 模拟故障诊断中的容差处理方法研究 . 电子科技大学学报, 2011, 40(1): 47-52. doi: 10.3969/j.issn.1001-0548.2011.01.009
[7]	王俊芳, 张思东. 通用高速分组交换调度算法 . 电子科技大学学报, 2010, 39(1): 69-73. doi: 10.3969/j.issn.1001-0548.2010.01.017
[8]	姜书艳, 罗毅, 罗刚, 谢永乐. 电路级栅氧短路故障的动态电流测试分析 . 电子科技大学学报, 2010, 39(1): 61-64. doi: 10.3969/j.issn.1001-0548.2010.01.015
[9]	金军, 舒红平. 元胞自动机变换可恢复图像认证算法 . 电子科技大学学报, 2009, 38(6): 1026-1030. doi: 10.3969/j.issn.1001-0548.2009.06.028
[10]	荣健, 申金娥, 丁学科, 李芳, 邝爱华, 刘文鑫. 采用改进的退化模型恢复湍流降质图像 . 电子科技大学学报, 2008, 37(6): 890-892,950.
[11]	郭磊, 虞红芳, 李乐民. WDM网双故障的共享子通路保护算法 . 电子科技大学学报, 2005, 34(3): 289-292.
[12]	侯孟书, 卢显良, 周旭, 詹川. 非结构化P2P系统的路由算法 . 电子科技大学学报, 2005, 34(1): 105-108.
[13]	赵季红, 曲桦. 基于约束的GMPLS恢复算法 . 电子科技大学学报, 2005, 34(1): 101-104.
[14]	彭江艳, 袁玉波. 多维寿命分布模型 . 电子科技大学学报, 2005, 34(5): 706-708.
[15]	张兰, 徐红兵. 一种新的Iddq故障定位算法研究 . 电子科技大学学报, 2004, 33(2): 133-136.
[16]	许都, 朱旭东, 李乐民. 下一代可扩展交换机/路由器 . 电子科技大学学报, 2003, 32(3): 230-234.
[17]	宋欢, 李乐民, 王晟. OBS交换结构中FDLs和TWC的研究 . 电子科技大学学报, 2003, 32(3): 276-279.
[18]	罗俊, 李乐民, 许都. 测试交换结构性能的仿真信源实现 . 电子科技大学学报, 2003, 32(3): 285-288.
[19]	杨喜, 唐绍淑. 基于路径恢复的ATM/SDH网状网自愈结构 . 电子科技大学学报, 2000, 29(4): 422-428.
[20]	尹治本. 一种技术人员结构的评价模型及算法研究 . 电子科技大学学报, 1998, 27(3): 321-325.

WeChat

点击查看大图

计量

文章访问数: 3455
HTML全文浏览量: 123
PDF下载量: 71
被引次数: 0

死锁恢复的多维交换结构容错路由算法

1. 电子科技大学宽带光纤传输与通信网技术教育部重点实验室成都 610054

基金项目:

国家自然科学基金(60372011)

作者简介:
许都(1968-),男,副教授,主要从事通信网络理论及应用方面的研究.

收稿日期: 2007-05-29
修回日期: 2008-02-28
刊出日期: 2008-12-15

中图分类号: TP302.8

关键词:

摘要: 在高性能路由器中采用多维交换结构是解决可扩展性的一种方法。在实现这种交换结构时,随着节点数目的增多,交换结构出现故障的概率也随之增加。该文在mesh/torus结构上提出了一种基于死锁恢复策略的容错路由算法MMAR。基于各非故障节点周围链路的状态,MMAR能容错任意形状的故障模型且所需虚拟通道数少。通过在凹形区域表面节点中设置该凹形区域内节点位置信息表,该算法能避免消息进入与其目的节点无关的凹形区域以使绕道路径最短。该文给出了在256个节点的二维torus中的仿真结果,验证了算法的有效性。

English Abstract

许都, 宋雷, 王宏. 死锁恢复的多维交换结构容错路由算法[J]. 电子科技大学学报, 2008, 37(6): 844-847,854.

引用本文:

许都, 宋雷, 王宏. 死锁恢复的多维交换结构容错路由算法[J]. 电子科技大学学报, 2008, 37(6): 844-847,854.

XU Du, SONG Lei, WANG Hong. Deadlock Recovery-Based Fault Tolerant Routing Algorithm for Multi-Dimensional Switching Fabric[J]. Journal of University of Electronic Science and Technology of China, 2008, 37(6): 844-847,854.

Citation:

XU Du, SONG Lei, WANG Hong. Deadlock Recovery-Based Fault Tolerant Routing Algorithm for Multi-Dimensional Switching Fabric[J]. Journal of University of Electronic Science and Technology of China, 2008, 37(6): 844-847,854.

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

期刊在线

编辑办公

友情链接

电子科技大学

版权所有 © 《电子科技大学学报》编辑部

地址: 成都市建设北路二段四号电子科技大学主楼中350室电话: 028-83202308,83207559 Email: xuebao@uestc.edu.cn

本系统由北京仁和汇智信息技术有限公司开发