3元n立方网络的2阶超连通性

为了度量以3元n立方网络为底层拓扑结构的并行与分布式系统的连通性,通过构造其2阶超割的方法,计算出当n不小于2时,3元n立方网络的2阶超连通度是6n-7。证明了对于以3元n立方网络为底层拓扑结构的并行与分布式计算机系统,当有不超过6n-8个节点发生故障且每个连通分支至少还有3个健康的节点时,该并行与分布式系统的任意两个节点之间仍然有一条无故障的通信线路。     

Routing and wavelength assignment for 3-ary n-cube communication patterns in linear array optical networks for n communication rounds

k-ary n-cubes are a class of communication patterns that are employed by a number of typical parallel algorithms. This paper addresses the implementation of parallel algorithms with bidirectional 3-ary n-cube communication patterns on a bidirectional linear array WDM optical networks when the information is transmitted one dimension after another. By giving an embedding scheme ?, we prove the optimal number of wavelengths under ? and design a routing and wavelength assignment strategy of it.     

Fault-tolerant wormhole routing for hypercube networks

We present an adaptive fault-tolerant wormhole routing algorithm for hypercubes by using 3 virtual networks. The routing algorithm can tolerate at least n−1 faulty nodes and can route a message via a path of length no more than the shortest path plus four. Previous algorithms which achieve the same fault tolerant ability need 5 virtual networks. Simulation results are also given in this paper.     

Strong Menger connectivity with conditional faults on the class of hypercube-like networks

In this paper, we study the Menger property on a class of hypercube-like networks. We show that in all n-dimensional hypercube-like networks with n−2 vertices removed, every pair of unremoved vertices u and v are connected by min{deg(u),deg(v)} vertex-disjoint paths, where deg(u) and deg(v) are the remaining degree of vertices u and v, respectively. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, all hypercube-like networks still have the strong Menger property, even if there are up to 2n−5 vertex faults.     

3元◢n◣立方体网络的◢t/k◣可诊断度研究

可诊断度是评估多处理器系统可靠性的一个关键指标.t/k诊断策略通过允许至多k个无故障处理器被误诊为故障处理器,从而极大提高了系统的可诊断度.与t可诊断度和t1/t1可诊断度相比,t/k可诊断度可以更好地反映实际系统的故障模式.3元n立方是一种性质优良并且应用广泛的网络拓扑,在许多分布式多处理器的构建中被用做底层网络.根据一些引理以及确定系统为t/k可诊断的充分条件,研究得出当n≥3及0≤k≤n,3元n立方是tk,n/k-可诊断的,其中tk,n=2(k+1)n-(k+1)(k+2).这个结果显示,在选择恰当的k值时,3元n立方的t/k可诊断度tk,n远大于其t可诊断度2n和t1/t1可诊断度4n-3.     

单向k-元n-立方体网络

单向[k]-元[n]-立方体是指具有单向边的[k]-元[n]-立方体互连网络拓扑。当网络包含的顶点数目较大时,比起传统的双向[k]-元[n]-立方体,单向?[k]-元[n]-立方体对通信硬件复杂性的要求更低一些。提出了[k]-元[n]-立方体的一个定向,使得定向后的单向[k]-元[n]-立方体[UQkn]有一些良好的性质。证明了[UQkn]是正则的,极大弧连通的,具有迭代结构的且[UQkn]的直径是小的。此外,提出了一个简单的多项式时间路由算法。     

A fault-tolerant wormhole routing scheme for torus networks with nonconvex faults

In this paper, we present a fault-tolerant routing algorithm for torus networks by using only 4 virtual channels. The proposed algorithm is based on the solid fault model, which includes rectangular faults and many practical nonconvex faults. Previous works need at least 6 virtual channels to achieve the same fault-tolerant ability.     

Characterization of spatial fault patterns in interconnection networks

Parallel computers, such as multiprocessors system-on-chip (Mp-SoCs), multicomputers and cluster computers, are consisting of hundreds or thousands multiple processing units and components (such as routers, channels and connectors) connected via some interconnection network that collectively may undergo high failure rates. Therefore, these systems are required to be equipped with fault-tolerant mechanisms to ensure that the system will keep running in a degraded mode. Normally, the faulty components are coalesced into fault regions, which are classified into two major categories: convex and concave regions. In this paper, we propose the first solution to calculate the probability of occurrences of common fault patterns in torus and mesh interconnection networks which includes both convex (-shaped, □-shaped) and concave (L-shaped, T-shaped, +-shaped, H-shaped) regions. These results play a key role when studying, particularly, the performance analysis of routing algorithms proposed for interconnection networks under faulty conditions.     

星型网络的3-限制边连通性

星型互连网络是并行与分布式处理领域中最流行的互连网络之一,它以n维星图作为拓扑结构。k-限制边连通度是衡量网络的可靠性的参数之一。一般来说,一个网络的k-限制边连通度越大,其连通性就越好。研究了星型互连网络的k限制边连通度;证明了当n≥3时,n维星型互连网络的3-限制连通度为3n－7。     

The super connectivity of exchanged hypercubes

The exchanged hypercube EH(s,t) where s?1 and t?1 are two positive integers, proposed by Loh et al. [The exchanged hypercube, IEEE Transactions on Parallel and Distributed Systems 16 (9) (2005) 866-874], is obtained by systematically removing links from a binary hypercube Qn. This paper determines that the super connectivity and the super edge-connectivity of EH(s,t) are 2s where s?t. That is, for s?t, at least 2s vertices (resp. 2s edges) of EH(s,t) are removed to get a disconnected graph that contains no isolated vertex.     

The super connectivity of augmented cubes

The augmented cube AQn, proposed by Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2) (2002) 71-84], is a (2n−1)-regular (2n−1)-connected graph (n≠3). This paper determines that the super connectivity of AQn is 4n−8 for n?6 and the super edge-connectivity is 4n−4 for n?5. That is, for n?6 (respectively, n?5), at least 4n−8 vertices (respectively, 4n−4 edges) of AQn are removed to get a disconnected graph that contains no isolated vertices. When the augmented cube is used to model the topological structure of a large-scale parallel processing system, these results can provide more accurate measurements for reliability and fault tolerance of the system.     

Super connectivity of Kronecker products of graphs

Let G₁ and G₂ be two connected graphs. The Kronecker product G₁×G₂ has vertex set V(G₁×G₂)=V(G₁)×V(G₂) and the edge set . In this paper, we show that if G is a bipartite graph with κ(G)=δ(G), then G×Kn(n?3) is super-κ.     

Ad Hoc网络连通度的研究

连通度是Ad Hoc网络的根本属性。保持网络的连通性对于提高网络的吞吐量至关重要。目前的研究主要以概率论方法为理论基础,讨论节点临界的传输范围以及节点的平均度在什么情况下,保持Ad Hoc网络的k连通。首先对Ad Hoc网络连通度目前的研究进展进行了综述,其次在引入能量模型的基础上,对Ad Hoc网络的连通度进行了仿真,基于仿真结果指出了相关文献的不足之处,最后对将来的研究方向进行了展望。     

Conditional connectivity of Cayley graphs generated by transposition trees

Given a graph G and a non-negative integer h, the Rh-(edge)connectivity of G is the minimum cardinality of a set of (edges)vertices of G, if any, whose deletion disconnects G, and every remaining component has minimum degree at least h. Similarly, given a non-negative integer g, the g-(edge)extraconnectivity of G is the minimum cardinality of a set of (edges)vertices of G, if any, whose deletion disconnects G, and every remaining component has more than g vertices. In this paper, we determine R₂-(edge)connectivity and 2-extra(edge)connectivity of Cayley graphs generated by transposition trees.     

超立方体网络的3路结构连通度及子结构连通度

针对以超立方体网络为蓝本的多处理机系统的可靠性和容错能力的精准度量问题，结合多处理机系统遭受计算机病毒攻击时常常发生结构性故障的特点，研究了n维超立方体网络的结构连通性和子结构连通性评价问题。首先，使用构造n维超立方体网络的3路结构割的方法得到其3路结构连通度的一个上界；然后，使用构造n维超立方体网络的3路子结构集的等价变换或约简变换的方法，得到其3路结构子连通度的一个下界；最后，利用任意网络的3路结构连通度不小于3路子结构连通度的性质，证实了超立方体网络的3路结构连通度和子结构连通度均为该超立方体网络维数的一半。这一结果表明，在3路结构故障模型下，破坏敌方以超立方体网络为底层拓扑的多处理系统至少需要攻击该系统中维数一半的3路结构或子结构。     

Hamiltonian properties of twisted hypercube-like networks with more faulty elements

Twisted hypercube-like networks (THLNs) are a large class of network topologies, which subsume some well-known hypercube variants. This paper is concerned with the longest cycle in an n-dimensional (n-D) THLN with up to 2n−9 faulty elements. Let G be an n-D THLN, n≥7. Let F be a subset of V(G)?E(G), |F|≤2n−9. We prove that G−F contains a Hamiltonian cycle if δ(G−F)≥2, and G−F contains a near Hamiltonian cycle if δ(G−F)≤1. Our work extends some previously known results.