Mesh网络容错广播路由算法的概率分析

One-to-all or broadcast communication is one of the most important communication patterns and occurs in many important applications in parallel computing. This paper proposes a fault tolerant, local-irdormation-based, and distributed broadcast routing algorithm based on the concept of k-submesh-cormectivity in all-port mesh networks.The paper analyzes the fault tolerance of the algorithm in terms of node failure probability. Suppose that every nodehas independent failure probability, and deduce the success probability of the broadcast routing, which successfully routes a message from a source node to all non-faulty nodes in the networks. The paper strictly proves that the broadcast routing algorithm with the success probability of 99％ to route among all non-faulty nodes on mesh networks with forty thousand nodes, in case that the node failure probability is controlled within 0.12％ Simulation results show that the algorithm is practically efficient and effective, and the time steps of the algorithm are very closeto the optimum.     

交换超立方体网络容错路由研究

为了研究交换超立方体网络容错路由问题,引入了相邻结点集合类的概念,提出了相邻结点集的求解公式。对于满足任意子连通性条件的交换超立方体网络,给出了基于相邻结点集合类的自适应容错路由算法及算法的步长上界。仿真实验结果表明算法是有效的。     

点对点网络容错路由算法的概率分析

基于网络中结点错误概率 ,提出一种新的概率分析方法 ,对网络中点对点的路由算法的容错性概率、路径长度、算法复杂性进行严格的推导 .以超立方体网络为分析的网络拓扑 ,提出在其上的一个路由算法 .分析表明 :在所有实际规模的超立方体网络中 (其结点数可以高达十亿个 ) ,在相当大的结点出错概率 (可高达 8% )的情况下 ,路由算法可达到 99.9%的成功概率     

超立方体网络下的自适应容错路由研究*

针对超立方体结构的多处理机系统出现故障的问题,对容错超立方体网络的局部连通性进行了研究。根据局部连通性的特点定义了相邻节点集合类的概念,提出并证明了求解两类相邻节点集合的公式。给出了满足任意子连通性条件的超立方体网络的自适应容错路由算法。该算法是分布式和基于局部信息的,可以预防死锁。仿真实验的结果表明算法是高效的,且构建的路径长度接近于最优路径长度。     

局部k-子立方连通的超立方网络中的广播容错算法

基于局部k-子立方体连通性的概念,提出了在局部k-子立方连通的超立方体中的,“播路由算法该算法是分布的、基于局部信息的,在容错性上有了很大的提高,能在线性时间内构造超立方体H1中接近最优的路径。     

故障超立方体网络中的高效容错路由算法研究

对超立方体网络中具有大量节点和链路故障模式进行了研究,提出了两类"子连通性"即k-维子连通性和任意子连通性的概念;基于两类子连通性概念,分别给出了两个满足该两类子连通性条件的超立方体网络的分布式容错路由算法.证明了已有的两类局部连通性概念中的条件"错误节点数小于正确节点数"是不必要的.提出的两个子连通性概念是两类局部连通性概念的最大扩展,可以在更大程度上保证整个超立方体网络的全局连通性,是已有的两类局部连通性概念的一种完全扩展.     

网络容错路由算法概率分析的一种新的方法

该文提出了一种新的概率分析方法来研究在给定结点错误概率的情况下超立方体网络强容错路由算法的容错性的概率。针对文中提出的基于新的局部连通性网络容错模型的高效的强容错路由算法犤1犦,该文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达4.7%的错误结点而具有99%的概率确保找到正确结点组成的路径,而如果结点的错误概率不超过0.1%,则所有实际规模的超立方体网络能够具有99.9%的概率确保找到正确结点组成的路径。该算法的时间性能是最优的,且该算法构造的路径的长度不超过源结点和目的结点之间海明距离的两倍加上一个很小的常数。     

三维Mesh网络容错路由算法及其概率分析

基于三维Mesh网络中k-Mesh子网连通的概念提出一个简单的基于局部信息和分布式的容错路由算法,并对其容错性进行概率分析．假设每个结点具有独立的出错概率,推导出路由算法成功返回由正确结点组成的路径的概率,结果表明即使三维Mesh网络上非常简单的路由算法也有相当高的成功概率．算法的时间复杂性是线性的,所构造的路由路径长度非常接近两点间的最优路径长度．另外,基于k-Mesh子网容错模型提出的容错路由算法是基于局部信息的和分布式的,因而具有很好的实际意义．     

具有不连通子立方体的超立方体中广播路由

基于扩展的局部k—维子立方体连通的超立方体网络Hn,提出了超立方体网络Hn中新的广播容错路由算法。算法分析表明,基于扩展局部k—维子立方体连通的广播路由算法比基于局部k-子立方连通的广播路由算法提高了超立方体网络的容错性和通用性。     

Torus网络中容错路由算法的设计与概率分析

基于k-Torus子网的概念提出了一个简单的Torus网络容错路由算法。假设结点出错相互独立,计算出路由算法成功路由的概率。对于几十万个结点以上的Torus网络,提出的路由算法构造通路的概率可达99%,且所提出的路由算法具有线性的特点。     

A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges

In this paper, we consider the problem of a fault-free Hamiltonian cycle passing through prescribed edges in an n-dimensional hypercube Qn with some faulty edges. We obtain the following result: Let n?2, F⊂E(Qn), E₀⊂E(Qn)F with 1?|E₀|?2n−3, |F|<n−(⌊|E₀|/2⌋+1). If the subgraph induced by E₀ is a linear forest (i.e., pairwise vertex-disjoint paths), then in the graph Qn−F all edges of E₀ lie on a Hamiltonian cycle.     

Probabilistic analysis on mesh network fault tolerance

Mesh networks are among the most important interconnection network topologies for large multicomputer systems. Mesh networks perform poorly in tolerating faults in the view of worst-case analysis. On the other hand, such worst cases occur very rarely in realistic situations. In this paper, we study the fault tolerance of 2-D and 3-D mesh networks under a more realistic model in which each network node has an independent failure probability. We first observe that if the node failure probability is fixed, then the connectivity probability of these mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacture to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. We develop a novel technique to formally derive lower bounds on the connectivity probability for 2-D and 3-D mesh networks. Our study shows that these mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. For example, it is formally proved that as long as the node failure probability is bounded by 0.5%$0.5\%$, a 3-D mesh network of up to a million nodes remains connected with a probability larger than 99%$99\%$.     

Parallel routing algorithms for incomplete hypercube interconnection networks

Hypercube interconnection networks have been receiving considerable attention in the supercomputing environment. However, the number of processors must be exactly 2^r for an r-cube complete hypercube. This restriction severely limits its applicability. In this paper, we address three variant hypercube topologies with more flexibility in system sizes, the labelled hypercubes I_m^r, I_M^r, and I_A^r. Incomplete hypercube I_m^r consists of an r-cube and an m-cube complete hypercubes; I_m^r is composed of 2^r and Σ_{m ε M} 2^m nodes; I_Ar comes from an r-cube complete hypercube which operates in a degraded manner and allows that the missing nodes to be arbitrarily distributed. Specifically, we focus on the parallel paths routing algorithms for these three classes of incomplete hypercubes. Parallel paths between any given two nodes mean that these paths have the same source and destination nodes but with different intermediate nodes. Parallel communication is important as it will allow us to use the full bandwidth of the multiprocessors for the data transfer operation between any two nodes, and3these redundant paths can increase system fault-tolerance and communication reliability. With these parallel routing algorithms, one can use them as a criterion to design multiprocessor systems.     

Edge-fault-tolerant diameter and bipanconnectivity of hypercubes

Let n(?3) be a given integer and . And let Qn be an n-dimensional hypercube and F⊂E(Qn), such that every vertex of the graph Qn−F is incident with at least two edges. Assume x and y are any two vertices with Hamming distance H(x,y)=h. In this paper, we obtain the following results: (1) If h?2 and |F|?min{n+h−1,2n−5}, then in Qn−F there exists an xy-path of each length l∈Ωh+2, and the upper bound n+h−1 on |F| is sharp when 2?h?n−4, and the upper bound 2n−5 on |F| is sharp when n−4?h?n−1 and h=2. (2) If |F|?2n−5, then in Qn−F there exists an xy-path of each length l∈Ωs, where s=h if n−1?h?n, and s=h+2 if n−4?h?n−2 and h?2, and s=h+4 otherwise. Hence, the diameter of the graph Qn−F is n. Our results improve some previous results.     

The fastcube: a variation on hypercube topology with lower diameter

This paper presents a class of n-dimensional interconnection topologies with N=2ⁿ nodes which we refer to as n-fastcubes. The node degree of the n-fastcube is n and its diameter is ⌈(n+1)/2⌉, which is substantially smaller than that of the same size hypercube. Topological properties as well as several routing algorithms for fastcubes are developed. In addition, a new methodology for the design and analysis of fastcubes is employed. This methodology is based on modeling interconnection networks as finite state automata. The inputs to these particular automata are routing sequences. The routing and embedding algorithms developed in this paper produce routing sequences. The main characteristic of routing sequences is their node independence. A node independent routing sequence, p(H), produces a path between any pair of nodes with the Hamming distance of H. Thus, these sequences can be used, without modification, at any node to establish paths in a fastcube.     

Path partitions of hypercubes

A path partition of a graph G is a set of vertex-disjoint paths that cover all vertices of G. Given a set of pairs of distinct vertices of the n-dimensional hypercube Qn, is there a path partition of Qn such that ai and bi are endvertices of Pi? Caha and Koubek showed that for 6m?n, such a path partition exists if and only if the set P is balanced in the sense that it contains the same number of vertices from both classes of bipartition of Qn.In this paper we show that this result holds even for 2m−e<n, where e is the number of pairs of P that form edges of Qn. Moreover, our bound is optimal in the sense that for every n?3, there is a balanced set P in Qn such that 2m−e=n, but no path partition with endvertices prescribed by P exists.     

Embedding paths of variable lengths into hypercubes with conditional link-faults

Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q_n, in which every node is still incident to at least two fault-free links. Then we show that Q_n-F has a path of any odd (resp. even) length in the range from the distance to 2ⁿ-1 (resp. 2ⁿ-2) between two arbitrary nodes even if |F|=2n-5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults.