Möbius–deBruijn: The product of Möbius cube and deBruijn digraph

Möbius cube and deBruijn digraph have been proved to be two of the most popular interconnection architectures, due to their desirable properties. Some of the attractive properties of one, however, are not found in the other. The Möbius–deBruijn architecture, proposed in this paper, is the product of Möbius cube and deBruijn digraph, which is a combination of the two architectures. It employs the Möbius cube as a unit cluster and connects many such clusters by means of given number of parallel deBruijn digraphs. Consequently, the Möbius–deBruijn provides some of the desirable properties of both the architectures, such as the flexibility in terms of embedding of parallel algorithms, the high level of fault-tolerant, and the efficient inter-cluster communication. The proposed architecture also possesses the logarithmic diameter, the optimal connectivity, and the simple routing mechanism amenable to network faults. The methodology to construct the Möbius–deBruijn can apply to the product of deBruijn digraph and other hypercube-like networks, and also applies to the product of Kautz digraph and hypercube-like networks.     

A regular scalable fault tolerant interconnection network for distributed processing

Bounded degree networks like deBruijn graphs or wrapped butterfly networks are very important from VLSI implementation point of view as well as for applications where the computing nodes in the interconnection networks can have only a fixed number of I/O ports. One basic drawback of these networks is that they cannot provide a desired level of fault tolerance because of the bounded degree of the nodes. On the other hand, networks like hypercube (where degree of a node grows with the size of a network) can provide the desired fault tolerance but the design of a node becomes problematic for large networks. In their attempt to combine the best of the both worlds, authors in [IEEE Transactions on Parallel and Distributed Systems 4(9) (1993) 962] proposed hyper-deBruijn (HD) networks that have many additional features of logarithmic diameter, partitionability, embedding, etc. But, HD networks are not regular, are not optimally fault tolerant and the optimal routing is relatively complex. Our purpose in the present paper is to extend the concepts used in the above-mentioned reference to propose a new family of scalable network graphs that retain all the good features of HD networks and at the same time are regular and maximally fault tolerant; the optimal point to point routing algorithm is significantly simpler than that of the HD networks. We have developed some new interesting results on wrapped butterfly networks in the process.     

Folded Petersen cube networks: new competitors for the hypercubes

We introduce and analyze a new interconnection topology, called the k-dimensional folded Petersen (FP_k) network, which is constructed by iteratively applying the Cartesian product operation on the well-known Petersen graph. Since the number of nodes in FP_k is restricted to a power of ten, for better scalability we propose a generalization, the folded Petersen cube network FPQ_n,k =Q_n×FP_k, which is a product of the n-dimensional binary hypercube (Q_n) and FP_k. The FPQ_n,k topology provides regularity, node- and edge-symmetry, optimal connectivity (and therefore maximal fault-tolerance), logarithmic diameter, modularity, and permits simple self-routing and broadcasting algorithms. With the same node-degree and connectivity, FPQ _n,k has smaller diameter and accommodates more nodes than Q _n+3k, and its packing density is higher compared to several other product networks. This paper also emphasizes the versatility of the folded Petersen cube networks as a multicomputer interconnection topology by providing embeddings of many computationally important structures such as rings, multi-dimensional meshes, hypercubes, complete binary trees, tree machines, meshes of trees, and pyramids. The dilation and edge-congestion of all such embeddings are at most two     

Reliable overlay multicast trees for private Internet broadcasting with multiple sessions

With rapid advances of computing technologies and high speed networks, various high volume multimedia services have become popular in the Internet. Private Internet broadcasting is a typical way to support these services and overlay multicast technology is known to be a promising solution to support this method. In an overlay multicast network, members are dynamically joining or leaving their multicast group. To reduce frequent updates of multicast members and provide a reliable multicast route, overlay multicast trees are investigated. The problem is formulated as a binary integer programming which maximizes the minimum link reliability for all multicast sessions. Tabu search heuristic is developed with repeated intensification and diversification. Robust computational result is obtained that is comparable to the optimal solution and applicable in real time.     

On the Dynamic Initialization of Parallel Computers

The incremental and dynamic construction of interconnection networks from smaller components often leaves the fundamental problem of assigning addresses to processors to be contended with at power-up time. The problem is fundamental, for virtually all parallel algorithms known to the authors assume that the processors know their global coordinates within the newly created entity. We refer to this problem as the initialization problem. Rather surprisingly, the initialization problem has not received much attention in the literature. Our main contribution is to present parallel algorithms for the initialization problem on a number of network topologies, including complete binary trees, meshes of trees, pyramids, linear arrays, rings, meshes, tori, higher dimensional meshes and tori, hypercubes, butterflies, linear arrays with a global bus, rings with a global bus and meshes with multiple broadcasting, under various assumptions about edge labels, leader existence, and a priori knowledge of the number of nodes in the network. With two exceptions, the proposed algorithms are optimal.     

Broadcasting on Incomplete WK-Recursive Networks

The WK-recursive networks, which were originally proposed by Vecchia and Sanges, have suffered from a rigorous restriction on the number of nodes. Like other incomplete networks, the incomplete WK-recursive networks have been proposed to relieve this restriction. In this paper, broadcasting on the incomplete WK-recursive networks is discussed. The proposed broadcasting algorithm is optimal with respect to message complexity. Besides, extensive experiments are made to evaluate its performance. Experimental results show that (1) the heights of the broadcasting trees do not exceed the diameters, (2) a high percentage of the nodes can receive the message from the source node via the shortest paths, (3) for those nonshortest transmission paths, the deviations are small, and (4) a high percentage of the broadcasting trees are of minimum height.     

DESIGN OF A PARALLEL INTERCONNECT BASED ON COMMUNICATION PATTERN CONSIDERATIONS

An interconnects versatility is usually described by its ability to support a variety of algorithmic patterns based on the physical or logical embeddings within its topology that match the desired algorithmic patterns. However, most such embeddings are available on u discrete basis, though a particular algorithm may require a variety of embeddings during different phases of its operation. To provide for such varying embedded topology needs, we propose a simple and VLSI realizable interconnect structure, termed as a Union Graph (UG), which combines two discrete interconnects, with very individual and distinctive capabilities, through a union operation. We present the union of the binary deBruijn graph (BDG) and a Torus to demonstrate the effectiveness of this approach. The focus is on providing practical usability of the network for algorithmic support rather than on graph properties. We highlight the importance of communication aspects of different execution phases in designing an algo-rithmically specialized interconnect. A set of examples are used to demonstrate the UG's versatility for algorithmic support.     

Binary search networks: A new method for key searching

A novel method for key searching, binary search networks, is proposed, and its search, insertion, and deletion algorithms are presented. A binary search network is an extension of a binary search tree which is widely used as a practical key search method.Some properties of binary search networks are discussed, and the optimization problem of minimizing a search cost is remarked upon. The advantages and disadvantages of binary search networks relative to binary search trees are also discussed.     

二进制递归网络的连通性

二进制递归网络是超立方体的一类特殊变体,它具有很多良好的网络特性。网络的连通性是衡量网络结构通信能力的一个重要性能,虽然到目前为止已知的一些二进制递归网 络的连通性都已被研究过,但这些研究只是针对个体进行的,并不能代表所有二进制递归网络的连通特性。本文通过证明任何一个二进制递归网络中的每对顶点之间只能存在在”条顶点不交路,得到了整个二进制递归网络的点和边连通度皆为”的重要结论。     

Independent spanning trees on even networks

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and bandwidth. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. In this paper, we give an algorithm to construct ISTs on even networks, and show that these ISTs are optimal for height and path lengths, and each path in the ISTs has length at most the length of the shortest path+4 in the even network.     

Hyperbolic trees for efficient routing computation

Complex system theory is increasingly applied to develop control protocols for distributed computational and networking resources. The paper deals with the important subproblem of finding complex connected structures having excellent navigability properties using limited computational resources. Recently, the two-dimensional hyperbolic space turned out to be an efficient geometry for generative models of complex networks. The networks generated using the hyperbolic metric space share their basic structural properties (like small diameter or scale-free degree distribution) with several real networks. In the paper, a new model is proposed for generating navigation trees for complex networks embedded in the two-dimensional hyperbolic plane. The generative model is not based on known hyperbolic network models: the trees are not inferred from the existing links of any network; they are generated from scratch instead and based purely on the hyperbolic coordinates of nodes. We show that these hyperbolic trees have scale-free degree distributions and are present to a large extent both in synthetic hyperbolic complex networks and real ones (Internet autonomous system topology, US flight network) embedded in the hyperbolic plane. As the main result, we show that routing on the generated hyperbolic trees is optimal in terms of total memory usage of forwarding tables.

     

Streets of Byzantium: Network Architectures for Fast Reliable Broadcasts

A site broadcasting its local value to all other sites ina fault-prone environment is a fundamental paradigm in constructing reliable distributed systems. Time complexity lower bounds and network connectivity requirements for reliable broadcast protocols in point-to-point communication networks are well known. In this paper, we consider the reliable broadcast problem in distributed systems with broadcast networks (for example, Ethernets) as the basic communication architecture. We show how properties of such network architectures can be used to effectively restrict the externally visible behavior of faulty processors. We use these techniques to derive simple protocols that implement reliable broadcast in only two rounds, independent of the failure upper bounds.     

Topological properties of OTIS-networks

We conduct a general study of the topological properties of optical transpose interconnection systems (OTIS). We first obtain their basic topological metrics of size, degree, shortest distance and diameter, and then we obtain results related to the recursive structure and efficient embedding of meshes, cubes, spanning trees and cycles. We also present minimal one-to-one routing and optimal broadcasting algorithms, and we show how to construct node-disjoint paths between any two nodes of an OTIS network. Recent studies have addressed only particular members of the general class of OTIS networks. In this paper, we present unified tools for obtaining the topological properties of an arbitrary OTIS network based on the properties of the corresponding factor network     

Products of networks with logarithmic diameter and fixed degree

Analyzes some general properties of product networks that are pertinent to parallel architectures and then focuses on three case studies. These are products of complete binary trees, shuffle-exchange and de Bruijn networks. It is shown that all of these are powerful architectures for parallel computation, as evidenced by their ability to efficiently emulate numerous other architectures. In particular, r-dimensional grids and r-dimensional meshes of trees can be embedded efficiently in products of these graphs, i.e. either as a subgraph or with small constant dilation and congestion. In addition, the shuffle-exchange network can be embedded in an r-dimensional product of shuffle-exchange networks with dilation cost 2r and congestion cost 2. Similarly, the de Bruijn network can be embedded in an r-dimensional product of de Bruijn networks with dilation cost r and congestion cost 4. Moreover, it is well known that shuffle-exchange and de Bruijn graphs can emulate the hypercube with a small constant slowdown for “normal” algorithms. This means that their product versions can also emulate these hypercube algorithms with constant slowdown. Conclusions include a discussion of many open research areas     

Contention-based performance evaluation of multidimensional range search in peer-to-peer networks

Performance evaluation of peer-to-peer search techniques has hitherto been based on simple performance metrics, such as message hop counts and total network traffic, mostly disregarding the inherently concurrent nature of peer-to-peer networks, where contention may arise. This paper is concerned with quantifying the effects of contention in P2P networks, focusing on networks for multidimensional range search. We evaluate peer-to-peer networks derived from recently proposed works, introducing two novel metrics related to concurrency and contention, namely responsiveness and throughput. Our results highlight the impact of contention on these networks, and demonstrate that some studied networks do not scale in the presence of contention. Also, our results indicate that certain P2P network properties believed to be desirable (e.g. even data distribution or uniform peer access) may not be as critical as previously believed.     

The Hyperstar Interconnection Network

In this paper, a multiprocessor interconnection topology, the hyperstar, based on the Cartesian product of star graphs is studied. The basic properties of the hyperstar are discussed and proved. This includes reduced degree and diameter, hierarchical structure, vertex symmetry, optimal routing, and shortest path characterization. The hyperstar is shown to be a member of the Cayley class of symmetric graphs. Embeddings of hypercubes, star graphs, and meshes are discussed. An optimal one-to-all broadcasting algorithm is obtained and analyzed. Some results on fault tolerance, parallel paths, Hamiltonian cycles, and VLSI layouts are obtained. Furthermore, a comparative study between the hyperstar and seven related networks is conducted. The comparison is based on scalability, broadcasting cost, link requirements, cost/performance ratio, and other static parameters such as degree, diameter, and average diameter.     

A bandwidth latency tradeoff for broadcast and reduction

The “fractional tree” algorithm for broadcasting and reduction is introduced. Its communication pattern interpolates between two well known patterns—sequential pipeline and pipelined binary tree. The speedup over the best of these simple methods can approach two for large systems and messages of intermediate size. For networks which are not very densely connected the new algorithm seems to be the best known method for the important case that each processor has only a single (possibly bidirectional) channel into the communication network.     

Topological Properties of WK-Recursive Networks

The WK-recursive networks, which have been proposed by Vecchia and Sanges, offer high degree of regularity, scalability, and symmetry. They have also the properties of expansibility and equal degree. Many algorithmic results have been obtained for the WK-recursive networks, and a VLSI implementation of a 16-node WK-recursive network has been realized. In this paper, we investigate some topological properties of the WK-recursive networks, including container, wide diameter, and fault diameter.     

An optimal emulator and VLSI layout for complete binary trees

How complex does a graph need to be in order to emulate an arbitrary size complete binary tree with the same level of efficiency as would be obtained by a directed complete graph? In this paper, this question is answered by showing that any -node graph needs to have at least edges in order to perform this emulation. Subsequently, a graph is presented which meets this bound, and it is shown how to optimally embed an arbitrary size complete binary tree in the proposed graph. It is also shown how to optimally embed a node cycle in the proposed graph of nodes with unit dilation, unit congestion and uniform load of . Finally optimal VLSI layouts are presented for the proposed graph which require asymptotically same area as the corresponding layouts for complete binary trees. Received: 7 July 1994 / 28 May 1996     

Heuristic algorithms for designing self-repairing protection trees in mesh networks

Protection trees have been used in the past for restoring multicast and unicast traffic in networks in various failure scenarios. In this paper we focus on shared self-repairing trees for link protection in unicast mesh networks. Shared protection trees have been proposed as a relatively simple approach that is easy to reconfigure and could provide sub-second restoration times with sub-optimal redundancy requirement. The self-repairing nature of this class of protection trees may make them an attractive option for cases where dynamic changes in network topology or demand may occur. In this paper, we present heuristic algorithms to design a self-repairing protection tree for a given network. We study the restorability performance of shared trees and examine the limitations of such schemes in specific topologies, such as cases where long node chains exist. Using extensive simulations with thousands of randomly generated network graphs. We compare redundancy and average backup path length of shared protection trees with optimal tree designs and non-tree designs. We also apply our algorithms to the problem of designing the protection tree in a pre-designed fixed-capacity network, and study the performance of shared protection trees in this scenario under different network loads and link utilization levels.