局部扭曲立方体广播容错路由算法

A Broadcast Routing Algorithm on Locally Twisted Cubes

基于局部扭曲立方体的优良特性,利用立方体分割的思想,设计一种广播容错路由算法。通过证明,若源节点为安全节点,算法产生的广播树是最优的;若源节点为非安全节点(故障节点数小于n),广播能够在n+1步内完成。

As a new kind of variants of the well - known hypercubes, a class of graphs known as the locally twisted cubes （LTQs） has recently been proposed as candidates for the topology of interconnection network. While retaining some nice properties of a hypercube. This thesis addresses how to route messages in a faulty n - dimensional LTQ. A fault - tolerant broadcast algorithm is developed based on the concept of divisional hypercube. Theoretical analysis shows that an optimal broadcast tree can be formed when the source node is safe, and a broadcast requires at most n ＋ 1 steps when the source is unsafe and there are no more than n failing nodes.