Journal of Interconnection Networks

Network-on-chip multicore architectures with a large number of processing elements are becoming a reality with the recent developments in technology. In these modern systems the processing elements are interconnected with regular network-on-chip (NoC) topologies such as meshes and trees. In this paper we propose a parallel Gauss-Seidel (GS) iterative algorithm for solving large systems of linear equations on a torus NoC architecture. The proposed parallel algorithm is O(Nn²/k²) time complexity for solving a system with matrix of order n on a k × k torus NoC architecture with N iterations assuming n and N are large compared to k (i.e. for large linear systems that require a large number of iterations). We show that under these conditions the proposed parallel GS algorithm has near optimal speedup.

The node-to-set parallel routing problem for a k-connected network Γ is as follows: given a node s and k other nodes {t₁, t₂, … , t_k} in Γ, find k node-disjoint paths connecting s and t_i, for 1 ≤ i ≤ k. From the viewpoint of applications in synthesizing fast and resilient collective communication operations, it is desirable to make the parallel paths as short as possible. Building such paths is a nontrivial problem for a general network. Optical transpose interconnection system (OTIS, also known as swapped) networks, a class of hierarchical structures built of n identical n-node factor networks, are known to be maximally fault-tolerant for any connected factor network, implying that they have maximal connectivity. We propose a general algorithm for the node-to-set parallel routing problem in OTIS/swapped networks that yields paths of length no greater than D + 4 in O(Δ² + Δf(n)) time, where D and Δ represent the diameter and degree of the OTIS network and O(f(n)) is the time complexity of a shortest-path routing algorithm for the n-node factor network. Our node-to-set routing algorithm is shown to have optimal time complexity for certain OTIS networks of practical interest, including OTIS-Mesh and OTIS-Hypercube.

In the last few years peer-to-peer (P2P) systems have gained ground for multipoint video content distribution over IP networks. P2P technologies give new opportunities to define an efficient multimedia streaming application, but at the same time they involve a set of technical challenges and issues due to the best-effort service offered by the underlying Internet, and its dynamic and heterogeneous nature. Stringent requirements in terms of end-to-end delay for real-time applications motivates the choice of a tree-structured topology against other topologies that have been introduced in the last research works, but mainly aimed at non-real-time services like video on demand and live streaming. The target of this paper is to present a platform for multipoint multimedia transmission based on a tree overlay network with jitter control and to show through experiments on real environment that our platform performs better than a traditional tree overlay network system in terms of PSNR, frame loss and playout frozen time.

Graph embedding has been known as a powerful tool for implementation of parallel algorithms and simulation of interconnection networks. In this paper, we introduce a technique to obtain a lower bound for the dilation of an embedding. Moreover, we give algorithms for embedding variants of hypercubes with dilation 2 proving that the lower bound obtained is sharp. Further, we compute the exact wirelength of embedding folded hypercubes and augmented cubes into hypercubes.

In this article, the concept of cycle connectivity of a weighted graph is discussed. Cycle connectivity of partial trees, cycles and precisely weighted graphs are obtained. Also the concepts of cyclic cutnode and cyclic bridge in weighted graphs are introduced and a condition for a precisely weighted graph to possess a cyclic cutnode is obtained.

Reducing interference is one of the main challenges in wireless communication. How to minimize interference through network topology control in wireless sensor networks is a well-known open algorithmic problem. In this paper, we answer the question of how to minimize the average interference when a node is receiving a message. We adopt the protocol interference model, which defines the interference range of a node to be a constant times larger than its transmission range. We study the problem for nodes arbitrarily deployed in one-dimensional (1D) and two-dimensional (2D) regions respectively. For 1D networks, we propose a fast polynomial-time exact algorithm that can compute the minimum average interference. For 2D networks, we give a proof that the maximum interference can be bounded while minimizing the average interference. The bound is only related to the distances between nodes but not the network size. Based on the bound, we propose the first exact algorithm to compute the minimum average interference in 2D networks. Optimal topologies with the minimum average interference can be constructed through traceback in both 1D and 2D networks.