Journal of Interconnection Networks

Optical Burst and Packet Switching (OBS/OPS) are techniques designed to serve higher-layer packet-based communication protocols by allowing statistical multiplexing. Since OBS and OPS networks provide connectionless transport, they both suffer from contention, which occurs when multiple communications want to use simultaneously the same wavelength in a link. This paper proposes a Routing and Wavelength Assignment (RWA) strategy based on the concept of (rooted) collision-free digraph, which represents all paths assigned by the routing to those communications sharing a wavelength. Using the proposed RWA strategy, the contention problem can be successfully solved by using simple mechanisms based on adding a suitable additional delay to burst/packet transmissions. Here we define and characterize the routing-antipodal networks, in which we can define [n/2] pairs of arc-disjoint collision-free digraphs (with n being the number of nodes) that altogether include all arcs of the network. This implies that, using [n/2] wavelengths, we can achieve connectivity between any pair of nodes under the wavelength-continuity constraint. Solutions with fewer wavelengths are also feasible. In particular, if the routing-antipodal network has a trail that passes through all vertices at least once, one wavelength is enough to ensure connectivity between each pair of nodes. We also show that the line digraph technique provides us with a simple tool for obtaining proper collision-free digraphs. The proposed method works in either a synchronous or an asynchronous transmission environment. Also, the arriving and length burst/packet distributions can be of any type, provided that the maximum theoretical offered load is not exceeded.

The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the (ℓ, k)-routing problem, each node can send at most ℓ packets and receive at most k packets. Permutation routing is the particular case ℓ = k = 1. In the r-central routing problem, all nodes at distance at most r from a fixed node v want to send a packet to v.

In this article we study the permutation routing, the r-central routing and the general (ℓ, k)-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We use the store-and-forward Δ-port model, and we consider both full and half-duplex networks. We first survey the existing results in the literature about packet routing, with special emphasis on (ℓ, k)-routing on plane grids. Our main contributions are the following:

1. Tight permutation routing algorithms on full-duplex hexagonal grids, and half duplex triangular and hexagonal grids.

2. Tight r-central routing algorithms on triangular and hexagonal grids.

3. Tight (k, k)-routing algorithms on square, triangular and hexagonal grids.

4. Good approximation algorithms (in terms of running time) for (ℓ, k)-routing on square, triangular and hexagonal grids, together with new lower bounds on the running time of any algorithm using shortest path routing.

These algorithms are all completely distributed, i.e., can be implemented independently at each node. Finally, we also formulate the (ℓ, k)-routing problem as a WEIGHTED EDGE COLORING problem on bipartite graphs.

This paper deals with security of routing protocols of Mobile Ad hoc Networks (MANETs), and proposes a solution to immunize such protocols against packet dropping misbehavior. Most of the current secure protocols are vulnerable to packet dropping misbehavior, which can be exploited by selfish nodes and malicious ones as well. For example, simply by dropping RREQ (Route Request) packets a selfish node can exclude itself from routes and thereby avoid receiving data packets to forward. On the other hand, a malicious node can drop RERR (Route Error) packets to keep the use of failed routes, possibly resulting in a denial of service. To mitigate this vulnerability we propose a hybrid solution that secures routing protocols against the dropping of both directed and broadcast control packets, in which a different approach is adapted for each kind of packets. Dealing with control packets represents the main contribution in this manuscript, as all the current proposals in the context of selfish nodes only consider data packets. Our solution can be integrated with any source routing protocol. In this work it was implemented with one of the most secure protocols, namely ENDAIR. The resulting new extended secure protocol was assessed and analyzed through an extensive simulation study.

We consider the problem of load-balanced routing, where a dense network is modelled by a continuous square region, and origin-destination node pairs correspond to pairs of points in that region. The objective is to define a routing policy that assigns a continuous path to each origin-destination pair while minimizing the traffic, or load, passing through any single point. While the average load is minimized by straight-line routing, such a routing policy distributes the load non-uniformly, resulting in higher load near the center of the region. We consider one-turn rectilinear routing policies that divert traffic away from regions of heavier load, resulting in up to a 33% reduction in the maximum load while simultaneously increasing the path lengths by an average of less than 28%. Our policies are simple to implement, being both local and oblivious. We provide a lower bound that shows that no one-turn rectilinear routing policy can reduce the maximum load by more than 39% and we give a polynomial-time procedure for approximating the optimal randomized policy.

Optical burst switching (OBS) has attracted interest as a transport network architecture for the future optical Internet. However, many challenging issues have to be solved in order to pave the way for an effective implementation of OBS. Contention, which may occur when two or more bursts compete for the same wavelength on the same link, is a critical issue. This paper compares the basic and hybrid contention resolution strategies with respect to burst loss probability and end-to-end transfer delay. The simulation results show that hybrid techniques lead an effective reduction of the burst average loss rate compared to existing techniques. It is also observed that a significant differentiation with regard to burst loss has been achieved, when burst priorities are considered.

Several triple-loop networks have been recently proposed and their efficiency studied. However, the number of cases for which one of these networks exists is sparse. We extend these networks to larger classes to enhance their realizability. We also give a heuristic method to optimize the network parameters to increase their efficiency. Finally, we determine their wide diameters to understand their fault-tolerance performance.

In this paper, we propose a slightly different definition of the crossed cube. The interconnection network obtained form our new definition is exactly isomorphic to the one obtained from the original definition proposed by Efe. It is known that the crossed cube is not node symmetric. However, using our new definition, it reveals some relative symmetric properties of the crossed cube. We can take advantage of the symmetry to study the spanning connectivity of the crossed cube.

Networks on chip (NoC) emerged as a structured and scalable communication medium for development of future Systems-on-Chip (SoC). Due to its unique features in terms of scalability and ease of synthesis, the (rectangular) mesh topology is regarded as an appropriate candidate for on-chip network development. On the other hand, the Spidergon NoC has been proposed as an alternative topology to realize cost effective multi-processor SoC (MPSoC) development. This paper presents analytical models of the average message latency and network throughput for both rectangular mesh and the Spidergon NoC employing wormhole switching. For each model, the validity of the analysis is verified by comparing the analytical model against the results produced by a discrete event simulator. Using the developed models, we then compare these topologies from different perspectives including manufacturing issues, message latency and network throughput.