Nearly optimal one-to-many parallel routing in star networks

Star networks were proposed recently as an attractive alternative to the well-known hypercube models for interconnection networks. Extensive research has been performed that shows that star networks are as versatile as hypercubes. This paper is an effort in the same direction. Based on the well-known paradigms, we study the one-to-many parallel routing problem on star networks and develop an improved routing algorithm that finds n-1 node-disjoint paths between one node and a set of other n-1 nodes in the n-star network. These parallel paths are proven of minimum length within a small additive constant, and the running time of our algorithm is bounded by O(n²). More specifically, given a node s and n-1 other nodes {t₁, t₂ , …, t_n-1} in the n-star network, our algorithm constructs n-1 node-disjoint paths P₁, P₂, …, P_n-1, where P_i is a path from s to t_j of length at most dist(s, t_j)+6 and dist(s, t _j) is the distance, i.e., the length of a shortest path, from s to t_j, for i=1, 2, …, n-1.The best bound on the path length by previously known algorithms for the same problem is 5(n-2)≈10Δ_n/3, where Δ_n=max{dist(s, t)} is the diameter of the n-star network     

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.     

Wirelength of 1-fault hamiltonian graphs into wheels and fans

In this paper we obtain a fundamental result to find the exact wirelength of 1-fault hamiltonian graphs into wheels and fans. Using this result we compute the exact wirelength of circulant graphs, generalized Petersen graphs, augmented cubes, crossed cubes, M?bius cubes, locally twisted cubes, twisted cubes, twisted n-cubes, generalized twisted cubes, hierarchical cubic networks, alternating group graphs, arrangement graphs and tori into wheels and fans. In addition, we find the exact wirelength of hypercubes, folded hypercubes, shuffle cubes, cube connected cycles, cyclic-cubes, wrapped butterfly networks and star graphs into fans.     

An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges

In this paper, we study fault-tolerant routing in bijective connection networks with restricted faulty edges. First, we prove that the probability that all the incident edges of an arbitrary node become faulty in an n-dimensional bijective connection network, denoted by X_n, is extremely low when n becomes sufficient large. Then, we give an O(n) algorithm to find a fault-free path of length at most n+3⌈log₂∣F∣⌉+1 between any two different nodes in X_n if each node of X_n has at least one fault-free incident edge and the number of faulty edges is not more than 2n−3. In fact, we also for the first time provide an upper bound of the fault diameter of all the bijective connection networks with the restricted faulty edges. Since the family of BC networks contains hypercubes, crossed cubes, Möbius cubes, etc., all the results are appropriate for these cubes.     

A new parallel and distributed shortest path algorithm forhierarchically clustered data networks

This paper presents new efficient shortest path algorithms to solve single origin shortest path problems (SOSP problems) and multiple origins shortest path problems (MOSP problems) for hierarchically clustered data networks. To solve an SOSP problem for a network with n nodes, the distributed version of our algorithm reaches the time complexity of O(log(n)), which is less than the time complexity of O(log ² (n)) achieved by the best existing algorithm. To solve an MOSP problem, our algorithm minimizes the needed computation resources, including computation processors and communication links for the computation of each shortest path so that we can achieve massive parallelization. The time complexity of our algorithm for an MOSP problem is O(m log(n)), which is much less than the time complexity of O(M log² (0)) of the best previous algorithm. Here, M is the number of the shortest paths to be computed and m is a positive number related to the network topology and the distribution of the nodes incurring communications, m is usually much smaller than M. Our experiment shows that m is almost a constant when the network size increases. Accordingly, our algorithm is significantly faster than the best previous algorithms to solve MOSP problems for large data networks     

A fast parallel algorithm for routing unicast assignments in Benesnetworks

This paper presents a new parallel algorithm for routing unicast (one-to-one) assignments in Benes networks. Parallel routing algorithms for such networks were reported earlier, but these algorithms were designed primarily to route permutation assignments. The routing algorithm presented in this paper removes this restriction without an increase in the order of routing cost or routing time. We realize this new routing algorithm on two different topologies. The algorithm routes a unicast assignment involving O(k) pairs of inputs and outputs in O(lg ² k+lg n) time on a completely connected network of n processors and in O(lg⁴ k+lg² k lg n) time on an extended shuffle-exchange network of n processors. Using O(n lg n) professors, the same algorithm can be pipelined to route α unicast assignments each involving O(k) pairs of inputs and outputs, in O(lg² k+lg n+(α-1) lg k) time on a completely connected network and in O(lg⁴ k+lg² k lg n+(α-1)(lg ³ k+lg k lg n)) time on the extended shuffle-exchange network. These yield an average routing time of O(lg k) in the first case, and O(lg³ k+1g k lg n) in the second case, for all α⩾lg n. These complexities indicate that the algorithm given in this paper is as fast as Nassimi and Sahni's algorithm for unicast assignments, and with pipelining, it is faster than the same algorithm at least by a factor of O(lg n) on both topologies. Furthermore, for sparse assignments, i.e., when k=O(1), it is the first algorithm which has an average routing time of O(1g n) on a topology with O(n) links     

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     

Node-pancyclicity and edge-pancyclicity of crossed cubes

Crossed cubes are important variants of the hypercubes. It has been proven that crossed cubes have attractive properties in Hamiltonian connectivity and pancyclicity. In this paper, we study two stronger features of crossed cubes. We prove that the n-dimensional crossed cube is not only node-pancyclic but also edge-pancyclic for n?2. We also show that the similar property holds for hypercubes.     

Unicast in hypercubes with large number of faulty nodes

Unicast in computer/communication networks is a one-to-one communication between a source node s and a destination node t. We propose three algorithms which find a nonfaulty routing path between s and t for unicast in the hypercube with a large number of faulty nodes. Given the n-dimensional hypercube H_n and a set F of faulty nodes, node uϵ H_n is called k-safe if u has at least k nonfaulty neighbors. The H_n is called k-safe if every node of H_n is k-safe. It has been known that for 0⩽k⩽n/2, a k-safe H_n is connected if |F|⩽2^k(n-k)-1. Our first algorithm finds a nonfaulty path of length at most d(s,t)+4 in O(n) time for unicast between 1-safe s and t in the H_n with |F|⩽2n-3, where d(s,t) is the distance between s and t. The second algorithm finds a nonfaulty path of length at most d(s,t)+6 in O(n) time for unicast in the 2-safe H_n with |F|⩽4n-9. The third algorithm finds a nonfaulty path of length at most d(s,t)+O(k²) in time O(|F|+n) for unicast in the k-safe H_n with |F|⩽2^k(n-k)-1 (0⩽k⩽n/2). The time complexities of the algorithms are optimal. We show that in the worst case, the length of the nonfaulty path between s and t in a k-safe H_n with |F|⩽2^k(n-k)-1 is at least d(s,t)+2(k+1) for 0⩽k⩽n/2. This implies that the path lengths found by the algorithms for unicast in the 1-safe and 2-safe hypercubes are optimal     

Diagnosability of the Mobius cubes

The recently introduced interconnection networks, the Mobius cubes, are hypercube variants that have some better properties than hypercubes. The n-dimensional Mobius cube M_n is a regular graph with 2ⁿ nodes and n2^n-1 edges. The diameter of M_n is about one half that of the n-dimensional hypercube Q _n and the average number of steps between nodes for M_n is about two-thirds of the average for Q_n, and 1-M_n has dynamic performance superior to that of Q_n. Of course, the symmetry of M_n is not superior to that of Q_n, i.e., Q_n is both node symmetric and edge symmetric , whereas M_n is, in general, neither node symmetric (n⩾4) nor edge symmetric (n⩾3). In this paper, we study the diagnosability of M_n. We use two diagnosis strategies, both based on the so-called PMC diagnostic model-the precise (one-step) diagnosis strategy proposed by Preparata et al. (1967) and the pessimistic diagnosis strategy proposed by Friedman (1975). We show that the diagnosability of M_n is the same as that of Q_n , i.e., M_n is n-diagnosable under the precise diagnosis strategy and (2n-2)/(2n-2)-diagnosable under the pessimistic diagnosis strategy     

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.     

Hot-potato algorithms for permutation routing

We develop a methodology for the design of hot-potato algorithms for routing permutations. The basic idea is to convert existing store-and-forward routing algorithms to hot-potato algorithms. Using it, we obtain the following complexity bounds for permutation routing: n×n Mesh: 7n+o(n) steps; 2ⁿ hypercube: O(n²) steps; n×n Torus: 4n+o(n) steps. The algorithm for the two-dimensional grid is the first to be both deterministic and asymptotically optimal. The algorithm for the 2ⁿ-nodes Boolean cube is the first deterministic algorithm that achieves a complexity of o(2ⁿ) steps     

A routing-table-based adaptive and minimal routing scheme on network-on-chip architectures

In this paper, we present a routing algorithm that combines the shortest path routing and adaptive routing schemes for NoCs. In specific, routing follows the shortest path to ensure low latency and low energy consumption. This routing scheme requires routing information be stored in a series of routing tables created at the routers along the routing path from the source to the destination. To reduce the exploration space and timing cost for selecting the routing path, a routing list and routing table for each node are created off-line. Routing table is updated on-line to reflect the dynamic change of the network status to avoid network congestion. To alleviate the high hardware implementation cost associated with the routing tables, a method to help reduce the size of the routing tables is also introduced. Compared to the existing routing algorithms, the experimental results have confirmed that the proposed algorithm has better performance in terms of routing latency and power consumption.     

基于拥塞控制的无线传感器网络数据汇集树生成算法

针对无线传感器网络数据汇集应用中, 由于数据流量大, 相邻路径之间容易发生串扰、信道竞争和冲突, 造成拥塞问题, 提出了基于拥塞控制的无线传感器网络数据汇集树生成算法(Data gather tree algorithm based on congestion control, DGT-CC). DGT-CC算法通过层次发现、邻居发现、启发式搜索和流量均衡策略构造一棵最短路径最小拥塞权值树. 理论分析证明DGT-CC算法收敛, 并能够构造一棵最短路径最小拥塞权值树, 仿真实验表明DGT-CC算法在丢包率、网络吞吐量和时延方面都较普通的最短路径树具有更好的性能.     

一个针对洗牌交换网的最优路由算法

洗牌交换网是最流行的互连网之一,然而,它的缺点之一便是最短路由算法,最短路由算法,通常也称为最优路由算法,能保证报文在任意一对结点之间沿着最短路径传送。针对包含2^n个结点的洗牌交换网,文中给出了一个O（n^2)时间复杂度的最短路由算法。该算法还可以很容易地适用于立方体连接圈（CCC）,且所得到的算法比已有的CCC路由算法要简单得多。     

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.     

The spined cube: A new hypercube variant with smaller diameter

Bijective connection graphs (in brief, BC graphs) are a family of hypercube variants, which contains hypercubes, twisted cubes, crossed cubes, Möbius cubes, locally twisted cubes, etc. It was proved that the smallest diameter of all the known n-dimensional bijective connection graphs (BC graphs) is , given a fixed dimension n. An important question about the smallest diameter among all the BC graphs is: Does there exist a BC graph whose diameter is less than the known BC graphs such as crossed cubes, twisted cubes, Möbius cubes, etc., with the same dimension? This paper answers this question. In this paper, we find that there exists a kind of BC graphs called spined cubes and we prove that the n-dimensional spined cube has the diameter ⌈n/3⌉+3 for any integer n with n?14. It is the first time in literature that a hypercube variant with such a small diameter is presented.     

Efficient algorithms for globally optimal trajectories

We present serial and parallel algorithms for solving a system of equations that arises from the discretization of the Hamilton-Jacobi equation associated to a trajectory optimization problem of the following type. A vehicle starts at a prespecified point x_o and follows a unit speed trajectory x(t) inside a region in ℛ^m until an unspecified time T that the region is exited. A trajectory minimizing a cost function of the form ∫₀^T r(x(t))dt+q(x(T)) is sought. The discretized Hamilton-Jacobi equation corresponding to this problem is usually solved using iterative methods. Nevertheless, assuming that the function r is positive, we are able to exploit the problem structure and develop one-pass algorithms for the discretized problem. The first algorithm resembles Dijkstra's shortest path algorithm and runs in time O(n log n), where n is the number of grid points. The second algorithm uses a somewhat different discretization and borrows some ideas from a variation of Dial's shortest path algorithm (1969) that we develop here; it runs in time O(n), which is the best possible, under some fairly mild assumptions. Finally, we show that the latter algorithm can be efficiently parallelized: for two-dimensional problems and with p processors, its running time becomes O(n/p), provided that p=O(√n/log n)     

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

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

Some permutation routing algorithms for low-dimensional hypercubes

Oblivious permutation routing in binary d-cubes has been well studied in the literature. In a permutation routing, each node initially contains a packet with a destination such that all the 2^d destinations are distinct. Kaklamanis et al. (Math. Syst. Theory 24 (1991) 223–232) used the decomposability of hypercubes into Hamiltonian circuits to give an asymptotically optimal routing algorithm. The notion of “destination graph” was first introduced by Borodin and Hopcroft to derive lower bounds on routing algorithms. This idea was recently used by Grammatikakis et al. (Proceedings of the Advancement in Parallel Computing, Elsevier, Amsterdam, 1993) to construct many–one routing algorithms for the binary 2-cube and 3-cube. In the present paper, further theoretical development is made along this line. It is then applied to obtain algorithms for binary d-cubes with d up to 12, which compare favorably with the above-mentioned “Hamiltonian circuit” algorithm. Some results on t-nary cubes with t3 are also obtained.