Narrow Results

Several existing studies have revealed that pipelined circuit switching (or PCS for short) can provide superior performance characteristics over wormhole switching. This paper proposes a new analytical model for PCS in high-radix high-dimensional k-ary n-cubes augmented with virtual channel support. The model uses Random Walk Theory to analyse the backtracking actions of the message header during the path set-up phase, and M/G/1 queueing systems to compute the mean waiting time that a message experiences at a source node before entering the network. Results from simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various network sizes and under different operating conditions.

Through simulation, we studied the performance of three adaptive “wormhole” routing strategies, and compared them with static routing. Since adaptive routing is susceptible to deadlock, an abort-and-retry strategy was used to prevent it from arising. The impact of packetization of long messages and buffering at message destinations were also studied. Results are presented and analyzed for a variety of hardware configurations and traffic conditions. The combination of adaptive routing, abort-and-retry, and buffering at the destination is shown to achieve excellent performance for modest cost.

The adaptive routing approach has been expected as a promising way to improve network performance by utilizing available network bandwidth. Previous adaptive routing strategies in wormhole-routed multicomputer networks restrict the routing of messages by the routing algorithm to prevent deadlock. This results in low degree of adaptivity and low utilization of physical or virtual channels. In this paper, we examine the possibility of performing restriction-free adaptive routing in wormhole-routed networks as an approach to further improving the performance of these networks. A new flow control policy, called message cutting-in, is proposed, and two adaptive routing strategies are presented. Freedom of communication deadlock is achieved by the proposed flow control policy. The proposed adaptive routing strategies do not restrict routing and maximally utilize the physical and virtual channels. Simulation results show that the restriction-free adaptive routing approach is promising from the fact that it has the lowest latency and highest throughput depending on the number of virtual channels per physical channel and patterns of message traffic.

A number of analytical models for predicting message latency in k-ary n-cubes have recently been reported in the literature. Most of these models, however, have been discussed for adaptive routing algorithms based on deadlock avoidance, e.g. Duato's routing. Several research studies have empirically demonstrated that routing algorithms based on deadlock recovery offer maximal adaptivity that can result in considerable improvement in network performance. Disha is an example of a true fully adaptive routing algorithm that uses minimal hardware to implement a simple and efficient progressive method to recover from potential deadlocks. This paper proposes a new analytical model of Disha in wormhole-routed k-ary n-cubes. Simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various networks sizes and under different traffic conditions.

In previous papers, we have developed the theoretical background for the design of deadlock-free adaptive routing algorithms for store-and-forward and wormhole networks. Some definitions and theorems have been proposed, developing conditions to verify that an adaptive algorithm is deadlock-free, even when there are cyclic dependencies between channels. Also, two design methodologies have been proposed.

In this paper, we propose a partial order between channels as well as an equivalence relation. This relation splits the set of channels into equivalence classes. Then, we extend our previous theory by considering equivalence classes (channel classes) instead of channels. This extension drastically simplifies the verification of deadlock freedom for adaptive routing algorithms with cyclic dependencies between channels. Finally, we present an example.

Multicast communication refers to the delivery of the same message from one source node to an arbitrary number of destination nodes. Two multicast wormhole routing methods have been presented in [13] for multicomputers with 2D-mesh and hypercube topologies. Also, a theory for the design of deadlock-free adaptive routing algorithms for wormhole networks has been proposed in [7, 8]. This theory supplies the sufficient conditions for an adaptive routing algorithm to be deadlock-free, even when there are cyclic dependencies between channels.

This paper analyses the additional channel dependencies produced by multicast routing algorithms on wormhole networks. Then, the theory proposed in [7, 8] is extended by considering them. As an example, the multicast routing algorithms presented in [13] are extended, taking advantage of the alternative paths offered by the network.

The performance of the communication network of a massively parallel processor depends, among other parameters, on the network topology, the message flow control and the routing mechanisms. This paper analyses the gains in average message latency and maximum sustained throughput that can be achieved using an adaptive routing strategy instead of an oblivious one. Two different bidimensional topologies have been studied, mesh and torus, using cut-through message flow control. First, we have simulated an ideal case in which there is no limit to the temporary storage capacity of the routing node. Then, a more realistic design, that implies the implementation of a deadlock avoidance technique, is analysed. To assure deadlock-free routing, the network is split into several virtual networks. Results show that adaptive routing is not a good election with this kind of networks. The torus topology shows potentially better results than the mesh. In any case, a different deadlock avoidance technique should be implemented if these potential gains are to be exploited.

Fault-tolerant systems aim at providing continuous operations in the presence of faults. Multicomputers rely on an interconnection network between processors to support the message-passing mechanism. Therefore, the reliability of the interconnection network is very important for the reliability of the whole system.

This paper analyses the effective redundancy available in a wormhole network by combining connectivity and deadlock freedom. Redundancy is defined at the channel level, giving a sufficient condition for a channel to be redundant and computing the set of redundant channels. The redundancy level of the network is also defined, proposing a theorem that supplies a lower bound for it. Finally, a fault-tolerant routing algorithm based on the former theory is proposed.

Although using table to implement routing algorithm has some advantages in network-on-chip (NoC), the router queries the routing table whenever a packet is to be forwarded. The querying time significantly increases the packet delay even if some methods have been proposed to shorten the table size. In mesh-based NoC, statistics shows that two neighbor routers have the same routing options for over 50% packets, on average. In this paper, we propose a technique to let packets pass through some routers without querying the routing table. Consequently, the time to query the routing table is significantly decreased. Simulation results show that this leads up to 16% decrease of average packet delay.

High reliability against undesirable effects is one of the key objectives in the design for Network-on-Chip (NoC). As a result, designing reliable and efficient routing method is highly desirable. This paper presents a novel turn model called NMad-y using one and two virtual channels along the $X$- and $Y$-dimensions, respectively, and Adaptive and Fault-tolerant Routing Method (AFRM) which is designed based on the NMad-y turn model. AFRM can effectively tolerate multiple faulty routers and links in more complicated faulty situations by the link status of neighbor routers within two hops. AFRM is able to impose the reliability of network without losing the performance of network. Simulation results show that AFRM achieves better saturation throughput (0.83% on average) than a state-of-the-art fault-tolerant routing method and maintains high reliability of more than 97.43% on average.

Focusing on finding a pre-specified basis path in a network, this research formulates a two-stage stochastic optimization model for the least expected time shortest path problem, in which random scenario-based time-invariant link travel times are utilized to capture the uncertainty of the realworld traffic network. In this model, the first stage aims to find a basis path for the trip over all the scenarios, and the second stage intends to generate the remainder path adaptively when the realizations of random link travel times are updated after a pre-specified time threshold. The GAMS optimization software is introduced to find the optimal solution of the proposed model. The numerical experiments demonstrate the performance of the proposed approaches.

This paper compares the reliability performance of five adaptive and two fixed routing algorithms in the context of a simplified military wireless network. The network is abstracted as a circuit switched network where the connectivity can change. The five algorithms are shown to differ widely in their sensitivity to the gain parameter, transient behavior and response to increasing load or lost trunk capacity. All the adaptive algorithms had a higher transient call blocking ratio under general overload conditions than an optimized fixed algorithm where the originating switch retains supervision of the call. This is consistent with the philosophy of network design that adaptive routing is most valuable when the network configuration is not fully known or when local overloads exist but additional capacity is available elsewhere. These results are applicable to commercial as well as military wireless systems. Interference on a wireless connection can lead to changes in network topology, or a local overload may exist at a congested node, creating the conditions where adaptive routing algorithms are useful.