Minimal fault diameter for highly resilient product networks

We present a number of results related to the fault tolerance of Cartesian product networks. We start by presenting a method for building containers (i.e., sets of node-disjoint paths) between any two nodes of a product network based on given containers for the factor networks. Then, we show that the best achievable fault diameter (i.e., diameter under maximum fault conditions), under reasonable network regularity and connectivity conditions, is equal to the fault-free diameter plus one. The concept of high fault resilience is then defined. We then prove that if each factor network is highly resilient, then their Cartesian product has minimal fault diameter. We derive from these results that Cartesian products of several popular networks are highly resilient and have minimal fault diameter equal to diameter plus one. These results spare future efforts that would be needed to individually determine the fault diameter of such networks as has been the practice with previously studied networks.     

Hamiltonicity of the WK-recursive network with and without faulty nodes

Recently, the WK-recursive network has received much attention due to its many favorable properties such as a high degree of scalability. By K(d,t), we denote the WK-recursive network of level t, each of whose basic modules is a d-node complete graph, where d>1 and t/spl ges/1. In this paper, we first show that K(d,t) is Hamiltonian-connected, where d/spl ges/4. A network is Hamiltonian-connected if it contains a Hamiltonian path between every two distinct nodes. In other words, a Hamiltonian-connected network can embed the longest linear array between any two distinct nodes with dilation, congestion, load, and expansion all equal to one. Then, we construct fault-free Hamiltonian cycles in K(d,t) with at most d-3 faulty nodes, where d/spl ges/4. Since the connectivity of K(d,t) is d-1, the result is optimal.     

Swapped (OTIS) Networks Built of Connected Basis Networks Are Maximally Fault Tolerant

An optical transpose interconnection system (OTIS) network with n^2 nodes is a two-level swapped architecture built of n copies of an n-node basis network that constitute its clusters. A simple rule for intercluster connectivity (node j in cluster i connected to node i in cluster j) leads to regularity, modularity, packageability, fault tolerance, and algorithmic efficiency of the resulting networks. We prove that an OTIS (swapped) network with a connected basis network possesses maximal fault tolerance, regardless of whether its basis network is maximally fault tolerant. We also show how the corresponding maximal number of node-disjoint paths between two nodes of a swapped network can be algorithmically constructed in a manner that is independent of the existence and construction of node-disjoint paths within its basis network. Our results are stronger than previously published results and they replace a number of proofs and constructions in the literature for specific basis networks. Additionally, we use our parallel path constructions to establish that the fault diameter and wide diameter of an OTIS network is no more than 4 units greater than its diameter.     

Designing a Fault-tolerant Fully-Chained Combining Switches Multi-stage Interconnection Network with Disjoint Paths

Multi-stage Interconnection Networks (MINs) are designed to achieve fault-tolerance and collision solving by providing a set of disjoint paths. Ching-Wen Chen and Chung-Ping Chung had proposed a fault-tolerant network called Combining Switches Multi-stage Interconnection Network (CSMIN) and an inaccurate algorithm that provided two correct disjoint paths only for some source-destination pairs. This paper provides a more comprehensive and accurate algorithm that always generate correct routing-tags for two disjoint paths for every source-destination pair in the CSMIN. The 1-fault tolerant CSMIN causes the two disjoint paths to have regular distances at each stage. Moreover, our algorithm backtracks a packet to the previous stage and takes the other disjoint path in the event of a fault or a collision in the network. Furthermore, to eliminate the backtracking penalties of CSMIN, we propose a new design called Fault-tolerant Fully-Chained Combining Switches Multi-stage Interconnection Network (FCSMIN). It has similar characteristics of 1-fault tolerance and two disjoint paths between any source-destination pair, but it can tolerate only one link or switch fault at each stage without backtracking. Our simulation and comparative analysis result shows that FCSMIN has added advantages of destination-tag routing, lower hardware costs, strong reroutability, lower preprocessing overhead, and higher fault-tolerance power in comparison to CSMIN.     

Improved upper and lower bounds on the optimization of mixed chordal ring networks

Recently, Chen, Hwang and Liu [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16] introduced the mixed chordal ring network as a topology for interconnection networks. In particular, they showed that the amount of hardware and the network structure of the mixed chordal ring network are very comparable to the (directed) double-loop network, yet the mixed chordal ring network can achieve a better diameter than the double-loop network. More precisely, the mixed chordal ring network can achieve diameter about as compared to for the (directed) double-loop network, where N is the number of nodes in the network. One of the most important questions in interconnection networks is, for a given number of nodes, how to find an optimal network (a network with the smallest diameter) and give the construction of such a network. Chen et al. [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16] gave upper and lower bounds for such an optimization problem on the mixed chordal ring network. In this paper, we improve the upper and lower bounds as and , respectively. In addition, we correct some deficient contexts in [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16].     

The twisted crossed cube

The topology of interconnection networks plays an important role in the performance of parallel and distributed computing systems. In this paper, we propose a new interconnection network called twisted crossed cube (TCQ_n) and investigate its basic network properties in terms of the regularity, connectivity, fault tolerance, recursiveness, hamiltonicity and ability to simulate other architectures, and so on. Then, we develop an effective routing algorithm Route (u, v) for TCQ_n that takes no more than d(u, v) + 1 steps for any two nodes (u, v) to communicate with each other, and the routing process shows that the diameter, wide diameter, and fault‐tolerant diameter of TCQ_n are about half of the corresponding diameters of the equivalent hypercube with the same dimension. In the end, by combining TCQ_n with crossed cube (CQ_n), we propose a preferable dynamic network structure, that is, the dynamic crossed cube, which has the same network diameter as TCQ_n/CQ_n and better properties in other respects, for example, its connection complexity is half of that of TCQ_n/CQ_n when the network scale is large enough, and the number of its average routing steps is also much smaller than that in TCQ_n/CQ_n. Copyright © 2015 John Wiley & Sons, Ltd.     

A practical interconnection network RP(k) and its routing algorithms

Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-al     

基于局部故障块三维mesh/torus网的容错路由

当系统包含很少的故障点时．mesh/torus网整个系统就有可能是不可靠的．该文采用扩展的局部可靠性信息来指导三维mesh／torus网的容错路由．扩展的局部可靠性信息在每个平面内部对无故障节点分类，所以系统中的故障块也是在不同的平面上构成的，而不是基于整个系统．很多基于整个系统不可靠的节点在二维的平面中都会变成可靠的节点．不管是在可靠的系统内，甚或不可靠的系统内，扩展的局部可靠性信息都能有效地指导容错路由．不同于以往的方法，作者的方法不会将任何无故障节点设置为无效节点．所有的故障块都是在平面内构成的，而不是基于整个系统；在一个平面内．任何包含在故障块里的无故障节点仍然可作为出发点或者目标点，这样将大大提高系统的计算能力和性能．模拟结果表明该文方法大大优于已有的方法．     

Optimal path embedding in crossed cubes

The crossed cube is an important variant of the hypercube. The n-dimensional crossed cube has only about half diameter, wide diameter, and fault diameter of those of the n-dimensional hypercube. Embeddings of trees, cycles, shortest paths, and Hamiltonian paths in crossed cubes have been studied in literature. Little work has been done on the embedding of paths except shortest paths, and Hamiltonian paths in crossed cubes. In this paper, we study optimal embedding of paths of different lengths between any two nodes in crossed cubes. We prove that paths of all lengths between [(n+1)/2] and 2/sup n/-1 can be embedded between any two distinct nodes with a dilation of 1 in the n-dimensional crossed cube. The embedding of paths is optimal in the sense that the dilation of the embedding is 1. We also prove that [(n+1)/2]+1 is the shortest possible length that can be embedded between arbitrary two distinct nodes with dilation 1 in the n-dimensional crossed cube.     

Circuit-switched broadcasting in torus and mesh networks

We consider the problem of broadcasting on torus and mesh networks using circuit-switched, half-duplex, and link-bound communication. In this paper, we obtain an optimal broadcasting algorithm that uses pd time steps for a d-dimensional torus with (2d+1)^p nodes in each side of the torus. Using this algorithm, we show that a broadcasting on a d-dimensional mesh with the same size can be done in pd+p+d-1 time steps     

Intermittent Fault Diagnosability of Interconnection Networks

An interconnection network’s diagnosability is an important metric for measuring its self-diagnostic capability. Permanent fault and intermittent fault are two different fault models that exist in an interconnection network. In this paper, we focus on the problem pertaining to the diagnosability of interconnection networks in an intermittent fault situation. First, we study a class of interconnection networks called crisp three-cycle networks, in which the cn _in -number (the number of common vertices each pair of vertices share) is no more than one. Necessary and sufficient conditions are derived for the diagnosability of crisp three-cycle networks under the PMC (Preparata, Metze, and Chien) model. A simple check can show that many well-known interconnection networks are crisp three-cycle networks. Second, we prove that an interconnection network S is a t _i -fault diagnosable system without repair if and only if its minimum in-degree is greater than t _i under the BGM (Barsi, Grandoni, and Masetrini) model. Finally, we extend the necessary and sufficient conditions to determine whether an interconnection network S is t _i -fault diagnosable without repair under the MM (Maeng and Malek) model from the permanent fault situation to the intermittent fault situation.     

三维曲面多移动节点的传感器网络部署算法

目前大多数传感器网络部署研究主要集中在二维平面和三维全空间区域,然而,许多现实世界的应用领域是一个复杂的三维空间曲面,现有的覆盖方法不能取得较好的结果。本文研究三维空间曲面传感器网络部署方法,提出一种三维曲面多移动节点的传感器网络部署算法,采用静态节点和动态节点组成的混合传感器网络,由静态节点估算覆盖空洞的位置和面积,再通过移动节点对覆盖空洞进行依次修复。仿真结果表明,该算法的最终网络覆盖率达到了99%,比3DGA算法提高了6个百分点,比Delaunay算法提高了8.5个百分点,同时降低了网络整体能耗。     

Fault diameter of k-ary n-cube networks

We obtain the fault diameter of k-ary n-cube interconnection networks (also known as n-dimensional k-torus networks). We start by constructing a complete set of node-disjoint paths (i.e., as many paths as the degree) between any two nodes of a k-ary n-cube. Each of the obtained paths is of length zero, two, or four plus the minimum length except for one path in a special case (when the Hamming distance between the two nodes is one) where the increase over the minimum length may attain eight. These results improve those obtained by B. Bose et al. (1995) where the length of some of the paths has a variable increase (which can be arbitrarily large) over the minimum length. These results are then used to derive the fault diameter of the k-ary n-cube, which is shown to be Δ+1 where Δ is the fault free diameter     

具有大量错误结点的超立方体网络中并行路由算法

本文讨论具有大量错误结点的超立方体网络中的并行路由算法。假定Hn是一个局部k-维子立方体连通用的n-维超立方体网络,本文提出的并行路由算法能够找出至少K=min（Dk(u),Dk(v）条并行路径,其中每一条路径的长度不超过（dH(Uk,Vk）＋3）2^k。该算法的时间复杂度为O（Kn2^k）。这里,Dk(u）和Dk(v）分别代表源结点u和目的结点v的正确的邻结点个数（不考虑u和v所在的k－维子立方体内部的邻结点）,dH(Uk,Vk）代表源结点u和目的结点v所在的两个k－维子立方体Uk和Vk之间的海明距离。本文还考察了了k=3的特殊情况,在k=3并且有分别不超过12．5％和25％的错误结点的情况下,该算法的时间复杂度为O（Kn）,并且每一条路径的路径长度分别在大约1．5和2倍源结点和目的结点之间的海明距离之内。该算法只要求结点知道其邻结点的状态,而无需知道整个网络信息,也就是说,该算法是基于局部信息的,因而该算法具有很强的实际意义。     

Gradient clock synchronization

We introduce the distributed gradientclock synchronization problem. As in traditional distributed clock synchronization, we consider a network of nodes equipped with hardware clocks with bounded drift. Nodes compute logical clock values based on their hardware clocks and message exchanges, and the goal is to synchronize the nodes' logical clocks as closely as possible, while satisfying certain validity conditions. The new feature of gradient clock synchronization GCS for short) is to require that the skew between any two nodesy' logical clocks be bounded by a nondecreasing function of the uncertainty in message delay (call this the distance) between the two nodes, and other network parameters. That is, we require nearby nodes to be closely synchronized, and allow faraway nodes to be more loosely synchronized. We contrast GCS with traditional clock synchronization, and discuss several practical motivations for GCS, mostly arising in sensor and ad-hoc networks. Our main result is that the worst case clock skew between two nodes at distance d or less from each other is Ω(d + , where D is the diameter of the network. This means that clock synchronization is not a localproperty, in the sense that the clock skew between two nodes depends not only on the distance between the nodes, but also on the size of the network. Our lower bound implies, for example, that the TDMA protocol with a fixed slot granularity will fail as the network grows, even if the maximum degree of each node stays constant.     

Generalized Diameters of the Mesh of Trees

The mesh of trees, which owns two favorable properties, small diameter and large bisection, is known as the fastest network when considered in terms of speed. In this paper we show that the wide diameter, fault diameter and Rabin number, which are three generalizations of diameter, of a two-dimensional 2ⁿ×2ⁿ mesh of trees are equal to 5n + 1.     

超级交叉立方体互连网络及其拓扑性质

交叉立方体是近年提出的超立方体的一种变种。由于它的许多优越性质（如直径、嵌入性等）,在并行处理领域越来越受到人们的重视。然而,像超立方体一样,它也有一个缺点,即要使交叉立方体升级,就必须成倍地增加其顶点个数。为了解决这一问题,本文将顶点个数的２的次幂的交叉立方体推广到具有任意个顶点的互连网络,提出了超级交叉立方体的定义,并证明它保持了交叉立方体在高速通度、对数级的直径和顶点度数等方面的优良性质,从     

Long-term attraction in higher order neural networks

Recent results on the memory storage capacity of higher order neural networks indicate a significant improvement compared to the limited capacity of the Hopfield model. However, such results have so far been obtained under the restriction that only a single iteration is allowed to converge. This paper presents a indirect convergence (long-term attraction) analysis of higher order neural networks. Our main result is that for any kappa(d)相似文献   

Efficient routing and sorting schemes for de Bruijn networks

We consider the problems of routing and sorting on a de Bruijn network. First, we show that any deterministic oblivious routing scheme for permutation routing on a d-ary de Bruijn network with N=dⁿ nodes, in the worst case, will take Ω(√N) steps under the single-port model. This improves the existing lower bounds provided d is not a constant. We also show that the lower bound is indeed a tight one. Second, we present a deterministic nonoblivious permutation routing algorithm which runs in O(d.n²) time on a d-ary de Bruijn network with N=dⁿ nodes. This algorithm is currently the fastest known nonoblivious deterministic routing algorithm for de Bruijn networks of arbitrary degree. Finally, we present an efficient general sorting algorithm for the de Bruijn networks of arbitrary degree. This algorithm is the best sorting algorithm known so far. It runs in O((log d).d.n²) time for directed de Bruijn network with dⁿ nodes, degree d, and diameter n. As a corollary, we show that on a binary de Bruijn network of Nnodes, our sorting scheme requires at most 2 log² Nsteps     

一种基于无效链路的分布式故障诊断一致性协议

故障诊断一致性(fault diagnosis agreement,FDA)是高可靠容错分布式系统的性能和完整性的重要保障.目前,大部分FDA协议还是只考虑单一故障组件的简单网络,而对于实际的分布式应用、故障节点和故障链路并存的系统假设更加有意义.但是,在此假设下,对恶意(拜占庭故障)组件的诊断是不可能满足FDA的.为此,首先提出了一种无效链路(invalid link)故障模型,可以更加准确地描述恶意组件的故障行为对系统的影响,有效提高故障诊断的覆盖率.在此模型基础上,提出了一个基于证据的故障诊断协议--PLFDA,可以同时对恶意节点和恶意链路进行检测和定位,并且能够满足故障诊断一致性要求.