Routing permutations on baseline networks with node-disjoint paths

Permutation is a frequently-used communication pattern in parallel and distributed computing systems and telecommunication networks. Node-disjoint routing has important applications in guided wave optical interconnects where the optical "crosstalk" between messages passing the same switch should be avoided. In this paper, we consider routing arbitrary permutations on an optical baseline network (or reverse baseline network) with node-disjoint paths. We first prove the equivalence between the set of admissible permutations (or semipermutations) of a baseline network and that of its reverse network based on a step-by-step permutation routing. We then show that an arbitrary permutation can be realized in a baseline network (or a reverse baseline network) with node-disjoint paths in four passes, which beats the existing results [M. Vaez et al., (2000)], [G. Maier et al., (2001)] that a permutation can be realized in an n /spl times/ n banyan network with node-disjoint paths in O(n/sup 1/2/) passes. This represents the currently best-known result for the number of passes required for routing an arbitrary permutation with node-disjoint paths in unique-path multistage networks. Unlike other unique path MINs (such as omega networks or banyan networks), only baseline networks have been found to possess such four-pass routing property. We present routing algorithms in both self-routing style and central-controlled style. Different from the recent work in [Y. Yang et al., (2003)], which also gave a four-pass node-disjoint routing algorithm for permutations, the new algorithm is efficient in transmission time for messages of any length, while the algorithm in [Y. Yang et al., (2003)] can work efficiently only for long messages. Comparisons with previous results demonstrate that routing in a baseline network proposed in this paper could be a better choice for routing permutations due to its lowest hardware cost and near-optimal transmission time.     

Hypercube sandwich approach to conferencing

This paper presents a novel cascaded conference network that provides distributed processing and signal transmission among members of disjoint sets of generic send/receive devices called conferees. It assumes an online request model in which idle groups of conferees may request the formation of a conference interconnection. Once a conference is established, all conferees remain connected until the entire conference is dissolved. The Hypercube Sandwich Network (HSN) consists of two components. A bidirectional permutation network is used for routing purposes to and from a hypercube of special processing elements for the purpose of conference formation. The HSN achieves strictly nonblocking performance for N conferees using O(Nlog N) processing elements, and this is shown to be tight to within a log ^1/4 N factor. Previous constructions required a quadratic number of processing elements for strictly nonblocking performance or could only provide wide-sense nonblocking conferencing. If the stronger requirement is made that the communication delay is logarithmic in the conference size, a simple algorithm is presented for wide-sense nonblocking conferencing in an HSN with O(N log N) processing elements.An earlier version of this paper was presented at the 1995 International Conference on Parallel Processing Techniques and Applications.     

Nonblocking k-fold multicast networks

Multicast communication involves transmitting information from a single source to multiple destinations and is a requirement in high-performance networks. Current trends in networking applications indicate an increasing demand in future networks for multicast capability. Many multicast applications require not only multicast capability, but also predictable communication performance such as guaranteed multicast latency and bandwidth. In this paper, we present a design for a nonblocking k-fold multicast network, in which any destination node can be involved in up to k simultaneous multicast connections in a nonblocking manner. We also develop an efficient routing algorithm for the network. As can be seen, a k-fold multicast network has significantly lower network cost than that of k copies of ordinary 1-fold multicast networks and is a cost effective choice for supporting arbitrary multicast communication.     

2-Dilated flattened butterfly: A nonblocking switching topology for high-radix networks

High-performance computing is highly dependent on the communication network connecting the nodes. In this paper, we propose a 2-Dilated flattened butterfly (2DFB) network which provides non-blocking performance for relatively low cost overhead. We study the topological properties of the proposed 2DFB network and compare it with different nonblocking switching topologies. We observe that a dilation factor of two is sufficient to obtain nonblocking property for a flattened butterfly structure irrespective of its size or dimension. Dilating each link in a flattened butterfly causes an increase in cost. Therefore, we modeled the implementation cost of a 2DFB network and compared it with other popular nonblocking networks. We observe that the cost of a 2DFB is less than other nonblocking networks, while at the same time providing reduced latency because of its reduced diameter and hop count. We also propose a procedure to develop a conflict-free static routing schedule as well as an adaptive load balanced routing scheme (ALDFB) for 2DFB networks. Finally, we also describe the hardware implementation of a 2DFB network using the NetFPGA as the switching element and verify the nonblocking behavior of a 2DFB. We also show that the 2DFB topology can be used to build high speed switching systems with reduced cost.     

点对点并行路由算法及容错性概率分析

用概率性分析方法,研究了在结点错误概率性分布的情形下,超立方体网络的点对点并行路由算法,并对算法的容错性概率、路径长度、算法复杂性进行了严格的推导。提出的算法是基于任意给定两个正确结点可以找出n条不相交的路径。分析了算法保证一条或多条路径同时联通的概率达到99.99%时结点的错误概率上界,同时考虑了两点间的海明距离变化,得出了较好的理论结论与计算结果。方法为研究超立方体网络容错性与并行路由算法提供了一种新的途径与新的考虑角度,具有更一般与更接近实际的意义。     

Using the dual path property of omega networks to obtainconflict-free message routing

A strategy for dealing with communication conflicts that occur in omega networks is presented. The strategy operates by implementing the dual path property of omega networks, which allows the source and destination processors to reverse roles for some of the messages that are being transmitted. For certain message patterns, such a reversal produces a modified message pattern for which the network routes are disjoint. For a circuit switching mode in which the network links and switches are bidirectional, the disjoint set of routes for modified message pattern can be used to achieve conflict-free message transmission for the original message pattern. This strategy is investigated, and an efficient algorithm to determine whether it can be successfully applied to a given message pattern is presented     

Parallel routing algorithms for nonblocking electronic and photonic switching networks

We study the connection capacity of a class of rearrangeable nonblocking (RNB) and strictly nonblocking (SNB) networks with/without crosstalk-free constraint, model their routing problems as weak or strong edge-colorings of bipartite graphs, and propose efficient routing algorithms for these networks using parallel processing techniques. This class of networks includes networks constructed from banyan networks by horizontal concatenation of extra stages and/or vertical stacking of multiple planes. We present a parallel algorithm that runs in O(lg/sup 2/ N) time for the RNB networks of complexities ranging from O(N lg N) to O(N/sup 1.5/ lg N) crosspoints and parallel algorithms that run in O(min{d* lg N, /spl radic/N}) time for the SNB networks of O(N/sup 1.5/ lg N) crosspoints, using a completely connected multiprocessor system of N processing elements. Our algorithms can be translated into algorithms with an O(lg N lg lg N) slowdown factor for the class of N-processor hypercubic networks, whose structures are no more complex than a single plane in the RNB and SNB networks considered.     

An optimal inherently stabilizing routing algorithm for star P2P overlay networks

Star graphs possess many desirable properties such as scalable node degrees and diameters, which are essential to facilitate reduced routing table sizes and low maximum path length for routing in large P2P networks. In addition, because a large number of disjoint paths are available and each data/replica in an n‐star can be placed in an (n − 1)‐star, load balancing and alleviation of network bottlenecks can be implemented in star P2P overlay networks. Therefore, star networks have been proposed as viable alternatives to existing overlay topologies for large P2P networks. In this paper, we propose an optimal stabilizing and inherently stabilizing algorithm for routing messages over all disjoint paths between two peers in a star P2P overlay network. The algorithm is optimal in terms of its time complexity in rounds and the length of the longest path traversed by the messages, and fault tolerant due to being stabilizing and inherently stabilizing, allowing the system to withstand transient faults. The algorithm can be used to increase network reliability and survivability in P2P networks. In addition, the usage of all disjoint paths to route messages between two peers leads to increased network bandwidth while distributing the communication overhead across the network and eliminating network bottlenecks in P2P networks. Copyright © 2016 John Wiley & Sons, Ltd.     

On the design of hypermesh interconnection networks for multicomputers

Topology, routing algorithm, and router structure are among the most important factors that greatly influence network performance. This paper assesses the interaction of these elements on two related but distinct types of multicomputer networks, the binary n-cube (or cube) and the hypermesh. The analysis will show that the topological properties of the hypermesh confer an important advantage over the cube that makes the former a promising option for use in high-performance multicomputers. The hypermesh can use simple routing algorithms and cheap routers with little performance penalty. The cube, on the other hand, is constrained to the use of a specific routing algorithm and complex routers to take advantage of its rich connectivity.     

Binary Cube Emulation of Butterfly Networks Encoded by Gray Code

We present algorithms for binary cube networks that emulate butterfly network computations on binary-reflected Gray-coded data in the same time complexity as that required for binary-coded data. The code conversion required for the emulation with binary-reflected Gray-coded data is either performed in local memories or through concurrent exchanges. The emulation of a butterfly network with one or two rows mapped to each binary cube node requires n communication cycles on an n-cube. For more than two rows per node, one additional communication cycle is required for every pair of rows, with concurrent communication on all channels of every node. The encoding upon completion can be either binary, or binary-reflected Gray code, or any combination thereof, without affecting the communication complexity.     

Transient chaotic neural network-based disjoint multipath routing for mobile ad-hoc networks

Due to mobility of wireless hosts, routing in mobile ad-hoc networks (MANETs) is a challenging task. Multipath routing is employed to provide reliable communication, load balancing, and improving quality of service of MANETs. Multiple paths are selected to be node-disjoint or link-disjoint to improve transmission reliability. However, selecting an optimal disjoint multipath set is an NP-complete problem. Neural networks are powerful tools for a wide variety of combinatorial optimization problems. In this study, a transient chaotic neural network (TCNN) is presented as multipath routing algorithm in MANETs. Each node in the network can be equipped with a neural network, and all the network nodes can be trained and used to obtain optimal or sub-optimal high reliable disjoint paths. This algorithm can find both node-disjoint and link-disjoint paths with no extra overhead. The simulation results show that the proposed method can find the high reliable disjoint path set in MANETs. In this paper, the performance of the proposed algorithm is compared to the shortest path algorithm, disjoint path set selection protocol algorithm, and Hopfield neural network (HNN)-based model. Experimental results show that the disjoint path set reliability of the proposed algorithm is up to 4.5 times more than the shortest path reliability. Also, the proposed algorithm has better performance in both reliability and the number of paths and shows up to 56% improvement in path set reliability and up to 20% improvement in the number of paths in the path set. The proposed TCNN-based algorithm also selects more reliable paths as compared to HNN-based algorithm in less number of iterations.     

Efficient nonblocking switching networks for interprocessorcommunications in multiprocessor systems

The performance of a multiprocessor system depends heavily on its ability to provide conflict free paths among its processors. In this paper, we explore the possibility of using a nonblocking network with O(N log N) edges (crosspoints) to interconnect the processors of an N processor system, We combine Bassalygo and Pinsker's implicit design of strictly nonblocking networks with an explicit construction of expanders to obtain a strictly nonblocking network with -765.18N+352.8N log N edges and 2+log(N/5) depth. We present an efficient parallel algorithm for routing connection requests on this network and implement it on three parallel processor topologies. The implementation on a parallel processor whose processing elements are interconnected as in the Bassalygo-Pinsker network requires O(N log N) processing elements, O(N log N) interprocessor links and it takes O(log N) steps to route any single connection request where each step involves a small number (≈72) of bit-level operations. A contracted or folded version of the same implementation reduces the processing element count to O(N) without increasing the link count or the routing time. Finally, we establish that the same algorithm takes O(log³ N) steps on a perfect shuffle processor with O(N) processing elements. These results improve the crosspoint, depth and routing time complexities of the previously reported strictly nonblocking networks     

交叉立方体在两种策略下的可诊断性

互连网络可诊断性度的高低是衡量这种网络性能优劣的重要标志二交叉立方体是近年提出的一类互连网络，它有一些比超立方体更好的性质．本文用PMC模型证明了n维交叉立方体Dn在精确策略和悲观策略下分别是n-可诊断的和（2n－2）／（2n－2）一可诊断的，从而证明民在这两种策略下的可诊断性度与n维超立体的相同．另外，本文在证明Dn是n-可诊断的同时，还得到了Dn中任何两顶点之间的n条互不相交的路径，它们可作为容错远路的依据．     

Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements

A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k distinct source-sink pairs in which each vertex of G is covered by a path. We deal with the graph G/sub 0/ /spl oplus/ G/sub 1/ obtained from connecting two graphs G/sub 0/ and G/sub 1/ with n vertices each by n pairwise nonadjacent edges joining vertices in G/sub 0/ and vertices in G/sub 1/. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G/sub 0/ /spl oplus/ G/sub 1/ connecting two lower dimensional networks G/sub 0/ and G/sub 1/. In the presence of faulty vertices and/or edges, we investigate many-to-many disjoint path coverability of G/sub 0/ /spl oplus/ G/sub 1/ and (G/sub 0/ /spl oplus/ G/sub 1/) /spl oplus/ (G/sub 2/ /spl oplus/ G/sub 3/ ), provided some conditions on the Hamiltonicity and disjoint path coverability of each graph G/sub i/ are satisfied, 0 /spl les/ i /spl les/ 3. We apply our main results to recursive circulant G(2/sup m/, 4) and a subclass of hypercube-like interconnection networks, called restricted HL-graphs. The subclasses includes twisted cubes, crossed cubes, multiply twisted cubes, Mobius cubes, Mcubes, and generalized twisted cubes. We show that all these networks of degree m with f or less faulty elements have a many-to-many k-DPC joining any k distinct source-sink pairs for any k /spl ges/ 1 and f /spl ges/ 0 such that f+2k /spl les/ m - 1.     

k元n—立方体网络的死锁特征剖析

研究死锁形成几率随网络参数的变化规律 ,对于选择合适的寻径算法、改良网络设计方案都具有重要意义 .环形等多种网络都是 k元 n-立方体网络系列的拓扑同构体 .因此 ,k元 n-立方体网络死锁特征的研究结果具有一定的普遍适用性 .本文根据刻画死锁特征的死锁循环密度属性划分死锁类型 .利用死锁类型分析寻径适应性、物理通道、虚拟通道、缓冲区大小 ,消息长度以及缓冲区结构等参数对死锁形成几率的影响     

Summation and routing on a partitioned optical passive stars network with large group size

In a partitioned optical passive stars (POPS) network, n=dg processors are divided into g groups of d processors each, and such a POPS network is denoted by POPS(d,g). There is an optical passive star (OPS) coupler between every pair of groups. Hence, a POPS(d,g) requires g/sup 2/ couplers. It is likely that, in a practical system, the number of couplers will be less than the number of processors, i.e., d>/spl radic/n>g and the number of groups will be smaller than the number of processors in a group. Hence, it is important to design fast algorithms for basic operations on such POPS networks with large group size. We present fast algorithms for data sum, prefix sum, and permutation routing on a POPS(d,g) such that d>/spl radic/n>g. Our data sum and prefix sum algorithms improve upon the best known algorithms for these problems designed by Sahni (2000). Permutation routing can be solved on a POPS network by simulating a hypercube sorting algorithm. Our algorithm for permutation routing is more efficient compared to this simulated hypercube sorting algorithm.     

An introduction to the multistage cube family of interconnection networks

The interconnection network in large-scale parallel/distributed supercomputer systems is a crucial component. Three networks are overviewed here. Multistage cube networks represent an important family of networks, which includes the omega, n-cube, multistage shuffle-exchange, delta, baseline, SW-banyan, and Generalized Cube. This family has been used or proposed for use in such systems as staran, pasm, Ultracomputer, the BBN Butterfly, the IBM RP3, and data-flow machines. The multistage cube topology, distributed routing control, and ability to be partitioned into independent subnetworks are examined. The Extra Stage Cube (ESC), a single-fault-tolerant multistage cube network, is described. The structure, control, and partitionability of the ESC, and how it functions when multiple faults occur, are presented. The Dynamic Redundancy (DR) network, a fault-tolerant multistage cube network that supports the incorporation of spare processors for fault tolerance, is discussed. Its structure, control, and partitionability into single-fault-tolerant subnetworks are explained.This research was supported by the Air Force Office of Scientific Research under grant F49620-86-K-0006, the Rome Air Development Center under grant F30602-83-K-0119, and the Purdue Research Foundation David Ross Grant 1985/86 no. 0857.currently with the Supercomputing Research Center, 4380 Forbes Blvd., Lanham, MD 20706 (as of June 1, 1987).currently with Computer Science Department, University of Illinois, Urbana-Champaign, IL 61801.     

蓝牙分散网的多径不相交的路由算法

蓝牙的分散网是一种特殊的自组网．由于蓝牙设备的连接和通信的特性，传统自组网的路由协议不适于蓝牙网络．针对这个问题，提出了一种多径不相交(MPD)的路由算法．仿真结果表明，采用多条路径并行发送数据，提高了数据的投递率，减少了端到端之间的传输延迟，从而有效地减少了网络拥塞；避免了由于路由崩溃，造成系统瘫痪．     

二进制递归网络的连通性

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

Disjoint path properties of the data manipulator network family

A critical component of any parallel processing system is the interconnection network that provides communications among the system's processors and memories. The data manipulator (gamma) network family is an important class of multistage interconnection networks that is being studied by various researchers. One interesting property of the data manipulator network family is the existence of multiple paths through the network for most source/ destination pairs. The condition that must be present to have disjoint paths through the network for a given source/ destination pair is shown, where disjoint paths are multiple paths with no links in common. It is derived that the maximum number of disjoint paths for any source/destination pair is two and a method for finding the routing tags that specify these paths is given. For source/destination pairs that have disjoint paths, a single fault cannot prevent communication between that source/ destination pair. The effect of a fault in a given stage of the network on the number of source/destination pairs that can be connected is also discussed. All results are proven mathematically.