有节点故障的d进制n维方的圈嵌入

Cycles Embedding in d-Ary n-Dimensional Cube With Node Failures

关键词:  圈嵌入  超方  故障容错  互联网络  d进制

Key words:  cycle embedding  hypercube  fault-tolerant  interconnection network  d-ary

摘要:

互连网络的容错能力是并行计算中的一个关键问题，而d进制n维方（超方的一般形式）在计算机的互连网络中已得到广泛的应用。本文考虑有节点故障的d进制n维方的容错性。F是d进制n维方Q_n（d） 中的错误点集（n≥3）， 且|F|≤n-2，证明了Q_n（d）的每个无故障的边和无故障的点存在于长从4到dⁿ-2|F|的无故障偶圈中。而且，当d是奇数时，Q_n（d）的每个无故障的边和无故障的点存在于长为dⁿ-2|F|的无故障圈中。

Abstract:

The d-ary n-dimensional cube (the general form of hypercube) has been widely used as the interconnection network in parallel computers.The fault-tolerant capacity of an interconnection network is a critical issue in parallel computing.In this article, we consider the fault-tolerant capacity of the d-ary n-dimensional cube.Let F be a set of faulty vertices in Q_n(d) (n≥3) with |F|≤n-2, we prove that every fault-free edge and fault-free vertex (node) of Q_n(d) lies on a fault-free cycle of every even length from 4 to dⁿ-2|F|.Moreover, if d is an odd number, every fault-free edge and fault-free vertex (node) of Q_n(d) lies on a fault-free cycle of length dⁿ-2|F|.