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

A Broadcast Routing Algorithm on Locally Twisted Cubes

作　　者：林玮[1] 李峻林[1] 唐良佐[1] 崔弈欣[1] 

机构地区：[1]武汉数字工程研究所,武汉430074

出　　处：《计算机与数字工程》2008年第8期1-4,49,共5页Computer & Digital Engineering

摘　　要：基于局部扭曲立方体的优良特性,利用立方体分割的思想,设计一种广播容错路由算法。通过证明,若源节点为安全节点,算法产生的广播树是最优的;若源节点为非安全节点(故障节点数小于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.

关 键 词：局部扭曲立方体 路由 容错路由 广播 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]