Routing schemes for multiple random broadcasts in arbitrary networktopologies

We consider the problem where packets are generated at each node of a network according to a Poisson process with rate λ, and each of them has to be broadcast to all the other nodes. The network topology is assumed to be an arbitrary bidirectional graph. We derive upper bounds on the maximum achievable broadcast throughput, and lower bounds on the average time required to complete a broadcast. These bounds apply to any network topology, independently of the scheme used to perform the broadcasts. We also propose two dynamic broadcasting schemes, called the indirect and the direct broadcasting scheme, that can be used in a general topology, and we evaluate analytically their throughput and average delay. The throughput achieved by the proposed schemes is equal to the maximum possible, if a half-duplex link model is assumed, and is at least equal to one half of the maximum possible, if a full-duplex model is assumed. The average delay of both schemes is of the order of the diameter of the trees used to perform the broadcasts. The analytical results obtained do not use any approximating assumptions     

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     

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.     

Broadcasting schemes for hypercubes with background traffic

Optimal broadcasting schemes for interconnection networks (INs) are most essential for the efficient interprocess communication amongst parallel computers. In this paper two novel broadcasting schemes are proposed for hypercube computers with bursty background traffic and a single-port mode of message passing communication. The schemes utilize a maximum entropy (ME) based queue-by-queue decomposition algorithm for arbitrary queueing network models (QNMs) [D.D. Kouvatsos, I. Awan, Perform. Eval. 51 (2003) 191] and are based on binomial trees and graph theoretic concepts. It is shown that the overall cost of the one-to-all broadcasting scheme is given by max{ω₁,ω₂,…,ω_2ⁿ/2}, where ω_i, i=1,2,…,2ⁿ/2 is the total weight at each leaf node of the binomial tree and n is the degree of the hypercube. Moreover, the upper bound of the total cost of the neighbourhood broadcasting scheme is determined by ∑_i=1^Fmax{ω_i}, where F is an upper bound of the number of steps and is equal to 1.33⌈log₂(n−1)⌉+1. Evidence based on empirical studies indicates the suitability of the schemes for achieving optimal broadcasting costs.     

An effective routing algorithm in incomplete hypercubes

An incomplete hypercube appears interesting and practical because of its relaxed restriction on the system size and possession of salient properties of complete hypercubes. The performance of incomplete hypercubes can be improved considerably by reducing communication time, which can be achieved by forwarding messages through two parallel paths between a pair of nodes. This paper presents a simple and effective two-parallel-paths routing algorithm for incomplete hypercubes which takes advantage of the flexibility provided by incomplete hypercubes, and yet prevents traffic congestion and deadlock. Simulation results indicate that the mean latency for sending large sized messages is reduced and the degree of reduction becomes larger when the system load grows. This significant reduction in latency could translate to a respectable performance improvement. This algorithm can also tolerate one fault in the system by sending duplicate copies of messages through two parallel paths with little increase in the mean latency under light-traffic load.     

Near-optimal message routing and broadcasting in faulty hypercubes

A distributed routing algorithm for faulty hypercubes is described. This algorithm uses a directed depth-first approach to find a path between the sender and receiver of a message whenever at least one non-faulty path exists. We show that, when an arbitrary number of elements of the hypercube can be faulty, the algorithm always routes messages using fewer than 2N hops, whereN is the number of nodes in the hypercube. This performance is shown to be within a factor of two of the optimal worst-case routing efficiency. Through foult simulations, we show that, even when up to half of the elements in the cube are faulty, complete the analysis, we prove that our algorithm is deadlock-free. Finally, we present two extensions of the algorithm. The first uses local storage to reduce the overhead of the algorithm while the second allows reliable broadcasting in the presence of an arbitrary number of faults.Supported in part by the National Science Foundation under Grant CCR-9010547.Supported in part by the National Science Foundation Instrumentation Grant CDA-8820627.     

k-pairwise disjoint paths routing in perfect hierarchical hypercubes

Hierarchical hypercubes (HHC), also known as cube-connected cubes, have been introduced in the literature as an interconnection network for massively parallel systems. Effectively, they can connect a large number of nodes while retaining a small diameter and a low degree compared to a hypercube of the same size. Especially (2 ^m +m)-dimensional hierarchical hypercubes ( $\mathit {HHC}_{2^{m}+m}$ ), called perfect HHCs, are popular as they are symmetrical, which is a critical property when designing routing algorithms. In this paper, we describe an algorithm finding, in an $\mathit{HHC}_{2^{m}+m}$ , mutually node-disjoint paths connecting k=?(m+1)/2? pairs of distinct nodes. This problem is known as the k-pairwise disjoint-path routing problem and is one of the important routing problems when dealing with interconnection networks. In an $\mathit{HHC}_{2^{m}+m}$ , our algorithm finds paths of lengths at most 2 ^m+1+m(2 ^m+1+1)+4 in O(2^5m ) time, where 2 ^m+1 is the diameter of an $\mathit{HHC}_{2^{m}+m}$ . Also, we have shown through an experiment that, in practice, the lengths of the generated paths are significantly lower than the worst-case theoretical estimations.     

Routing multiple paths in hypercubes

We present new techniques for mapping computations onto hypercubes. Our methods speed up classical implementations of grid and tree communications by a factor of (n), wheren is the number of hypercube dimensions. The speedups are asymptotically the best possible.We obtain these speedups by mapping each edge of the guest graph onto short, edge-disjoint paths in the hypercube such that the maximum congestion on any hypercube edge isO(1). These multiple-path embeddings can be used to reduce communication time for large grid-based scientific computations, to increase tolerance to link faults, and for fast routing of large messages.We also develop a general technique for deriving multiple-path embeddings from multiple-copy embeddings. Multiple-copy embeddings are one-to-one maps of independent copies of the guest graph within the hypercube. We present an efficient multiple-copy embedding of the cube-connected-cycles network within the hypercube. This embedding is used to derive efficient multiple-path embeddings of trees and butterfly networks in hypercubes.This research was supported by NSF/DARRA Grant CCR-8908285, NSF Grant CCR-8807426, and AFOSR Grant 89-0382.     

Minimal fully adaptive wormhole routing on hypercubes

Wormhole routing is an advanced switching technique used in new generation multicomputers. Since such a machine may suffer serious performance degradation under heavy or uneven traffic load, an adaptive routing method is particularly called upon. In minimal fully adaptive routing, the paths between any source and destination pair to be used are exactly all the shortest paths. We propose in this paper a minimal fully adaptive routing algorithm for n-dimensional hypercube with (n+1)/2 virtual channels per physical channel.     

Interval routing schemes

In this paper the problem of routing messages along shortest paths in a distributed network without using complete routing tables is considered. In particular, the complexity of deriving minimum (in terms of number of intervals) interval routing schemes is analyzed under different requirements. For all the cases considered NP-hardness proofs are given, while some approximability results are provided. Moreover, relations among the different cases considered are studied.This work was supported by the EEC ESPRIT II Basic Research Action Program under Contract No. 7141 Algorithms and Complexity II, by the EEC Human Capital and Mobility MAP project, and by the Italian MURST 40% project Algoritmi, Modelli di Calcolo e Strutture Informative.     

Universal routing schemes

Summary.  In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all n-node networks. In [31], Peleg and Upfal showed that one cannot implement a universal routing scheme with less than a total of Ω(n ^1+1/(2s+4)) memory bits for any given stretch factor s≧1. We improve this bound for stretch factors s, 1≦s<2, by proving that any near-shortest path universal routing scheme uses a total of Ω(n ²) memory bits in the worst-case. This result is obtained by counting the minimum number of routing functions necessary to route on all n-node networks. Moreover, and more fundamentally, we give a tight bound of Θ(n log n) bits for the local minimum memory requirement of universal routing scheme of stretch factors s, 1≦s<2. More precisely, for any fixed constant ɛ, 0<ɛ<1, there exists a n-node network G on which at least Ω(n ^ɛ) routers require Θ(n log n) bits each to code any routing function on G of stretch factor <2. This means that, whatever you choose the routing scheme, there exists a network on which one cannot compress locally the routing information better than routing tables do. Received: August 1995 / Accepted: August 1996     

Efficient communication primitives on hypercubes

We give practical algorithms, complexity analysis and implementation for one-to-all broadcasting, all-to-all personalized communication and matrix transpose (with two-dimensional partitioning of the matrix) on hypercubes. We assume the following communication characteristics: circuit-switched, e-cube routing and one-port communication model. For one-to-all broadcasting, we give an algorithm that combines the well-known recursive doubling algorithm[1] and the algorithm based on edgedisjoint spanning trees[2]. The measured times of the combined algorithm are always superior to those of the edge-disjoint spanning tree algorithm and outperform the recursive doubling algorithm. For all-to-all personalized communication we propose a hybrid algorithm that combines the well-known recursive doubling algorithm[3,4] and the recently proposed direct-route algorithm[5,6] Our hybrid algorithm balances between data transfer time and start-up time of these two algorithms, and its communication complexity is estimated to be better than the two previous algorithms for a range of machine parameters. For matrix transpose with two-dimensional partitioning of the matrix, we relate a two-phase algorithm to the previous result in Reference 7. The algorithm is predicted to be better than the recursive transpose algorithm[8] by n nearest-neighbor communications[4]. It takes advantage of circuit-switched routing and is congestion-free within each phase. We also suggest a way of storing the matrix such that the transpose operation can be realized in one phase without congestion.     

Architectures and routing schemes for optical network-on-chips

As indicated in the latest version of ITRS roadmap, optical wiring is a viable interconnect technology for future SoC/SiC/SiP designs that can provide broad band data transfer rates unmatchable by the existing metal/low-k dielectric interconnects. In this paper, we present an interconnection architecture, referred as the wavelength routed optical network (WRON), suitable to build on-chip optical micro-networks. The routing scheme for WRON, using any two of the three routing parameters (the source node address, the destination node address, and the routing wavelength), is generalized in this paper. With WRON as the primitive platform, we further propose a new recursive architecture, the recursive wavelength routed optical network (RCWRON), and it serves as the basis of a redundant architecture, the redundant wavelength routed optical network (RDWRON). The routing schemes for RCWRON and RDWRON are also detailed in this paper.     

Using artificial intelligence in routing schemes for wireless networks

For the latest 10 years, many authors have focused their investigations in wireless sensor networks. Different researching issues have been extensively developed: power consumption, MAC protocols, self-organizing network algorithms, data-aggregation schemes, routing protocols, QoS management, etc. Due to the constraints on data processing and power consumption, the use of artificial intelligence has been historically discarded. However, in some special scenarios the features of neural networks are appropriate to develop complex tasks such as path discovery. In this paper, we explore the performance of two very well-known routing paradigms, directed diffusion and Energy-Aware Routing, and our routing algorithm, named SIR, which has the novelty of being based on the introduction of neural networks in every sensor node. Extensive simulations over our wireless sensor network simulator, OLIMPO, have been carried out to study the efficiency of the introduction of neural networks. A comparison of the results obtained with every routing protocol is analyzed. This paper attempts to encourage the use of artificial intelligence techniques in wireless sensor nodes.     

Efficient XML data placement schemes over multiple mobile wireless broadcast channels

The Journal of Supercomputing - Broadcasting is one of the basic ways to access XML data via mobile wireless networks. In these networks, XML data are disseminated over a wireless broadcast channel...     

Efficient schemes for broadcasting popular videos

We provide a formal framework for studying broadcasting schemes and design a family of schemes for broadcasting popular videos, the greedy disk-conserving broadcasting (GDB) family. We analyze the resource requirements for GDB, i.e., the number of server broadcast channels, the client storage space, and the client I/O bandwidth required by GDB. Our analysis shows that all of our proposed broadcasting schemes are within a small factor of the optimal scheme in terms of the server bandwidth requirement. Furthermore, GDB exhibits a tradeoff between any two of the three resources. We compare our scheme with a recently proposed broadcasting scheme, skyscraper broadcasting (SB). With GDB, we can reduce the client storage space by as much as 50% or the number of server channels by as much as 30% at the cost of a small additional increase in the amount of client I/O bandwidth. If we require the client I/O bandwidth of GDB to be identical to that of SB, GDB needs only 70% of the client storage space required by SB or one less server channel than SB does. In addition, we show that with small client I/O bandwidth, the resource requirements of GDB are close to the minimum achievable by any disk-conserving broadcasting scheme.     

Close to linear space routing schemes

Let \(G=(V,E)\) be an unweighted undirected graph with n vertices and m edges, and let \(k>2\) be an integer. We present a routing scheme with a poly-logarithmic header size, that given a source s and a destination t at distance \(\varDelta \) from s, routes a message from s to t on a path whose length is \(O(k\varDelta +m^{1/k})\). The total space used by our routing scheme is \(mn^{O(1/\sqrt{\log n})}\), which is almost linear in the number of edges of the graph. We present also a routing scheme with \(n^{O(1/\sqrt{\log n})}\) header size, and the same stretch (up to constant factors). In this routing scheme, the routing table of every \(v\in V\) is at most \(kn^{O(1/\sqrt{\log n})}deg(v)\), where deg(v) is the degree of v in G. Our results are obtained by combining a general technique of Bernstein (2009), that was presented in the context of dynamic graph algorithms, with several new ideas and observations.