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

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

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

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/toms, 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.