Smart Car Parks (SCPs) based on Wireless Sensor Networks (WSNs) are one of the most interesting Internet of Things applications. This paper addresses the deployment optimization problem of two-tiered WSNs dedicated to fire monitoring in SCPs. Networks deployed inside the SCP consist of three types of nodes: Sensor Nodes (SNs) which cover the spots within the parking area, Relay Nodes (RNs) which forward alert messages generated by SNs, and the Sink node which is connected to the outside world (e.g, firefighters), through a high bandwidth connection. We propose an algorithm based on chaos theory and Whale Optimization Algorithm (WOA), which minimizes simultaneously the deployed number of SNs, RNs, and network diameter while ensuring coverage and connectivity. To evaluate the effectiveness of our proposal, we have conducted extensive tests. The results show that the Chaos WOA (CWOA) outperforms the original WOA in terms of solution quality and computation time and by comparison with an exact method, CWOA provides results very close to the optimal in terms of fitness value and is efficient in terms of computational time when the problem becomes more complex.

The exponential growth of the Internet-of-Things (IoT) technology paradigm has resulted in new applications and on-line services. Smart car park is one interesting example among others that can take advantage of applications based on wireless sensor networks (WSNs) Which constitute the core of IoT. This paper focuses on the deployment optimization problem of WSNs dedicated to the fire detection in a smart car park. In such networks, the nodes are classified into two categories: Sensor Nodes (SNs) deployed within the smart car park for targets coverage and Relay Nodes (RNs) whose task is to relay alert messages generated by the sensor nodes up to the sink node. In this study, we propose a Multi-Objective Binary Integer Linear Programming (MOBILP) which minimizes simultaneously the number of sensor nodes, relay nodes and the maximum distance from sensor nodes to the sink node, while ensuring coverage and connectivity. We have conducted extensive tests in order to evaluate the performance of our proposal. The results demonstrate that the MOBILP outperforms the existing approaches in terms of quality of solutions compared to a sequential deployment method, which consists to deploy SNs then RNs, and in terms of the ability to find other efficient solutions compared to a simultaneous deployment method using a mono-objective function, which consists to deploy SNs and RNs simultaneously.

Privacy preservation in wireless sensor networks has drawn considerable attention from research community during last few years. Emergence of single-owner, multi-user commercial sensor networks along with hostile and uncontrollable environment of such networks, makes the security issue in such networks of a great importance. This paper concentrates on token-based privacy preservation schemes. A possible attack on such schemes has been introduced. Two different approaches has been utilized to mitigate the attack. We present mathematical models for it's effects and overheads. The results have been verified using extensive simulations.

Grid-based networks (or grids for short), such as meshes and tori, have been the underlying topology for many multicomputers, and have been extensively studied in the past as a graph topology. In this paper, we investigate some topological properties of grids without boundary wrap-around (meshes) and with boundary wrap-around (tori). In particular, we study the problem of finding the number of nodes located at/within a given distance from a given node (surface area/volume) in the network and derive some expressions for computing such a number. Furthermore, we provide similar expressions that improve on previous results already reported in the literature for some special cases of grids, notably hypercubes and k-ary n-cubes. We also show some applications of the derived expressions in analytical performance modelling of some grid-based networks under uniform and hotspot traffic loads.

The increasing number of collective communication-based services with a mass interest and the parallel increasing demand for service quality are paving the way toward end-to-end QoS guarantees. Although many multicast algorithms in interconnection networks have been widely reported in the literature, most of them handle the multicast communication within limited performance metrics, i.e., either delay/latency or throughput. In contrast, this study investigates the multicast communication within a group of QoS constrains, namely latency, jitter, throughput, and additional traffic caused. In this paper, we present the Qualified Groups (QGs) as a novel path-based multicast algorithm for interconnection networks. To the best of our knowledge, the QG is the first multicast algorithm that considers the multicast latency at both the network and node levels across different traffic scenarios in interconnection networks. Our analysis shows that the proposed multicast algorithm exhibits superior performance characteristics over other well-known path-based multicast algorithms under different operating conditions. In addition, our results show that the QG can significantly improve the parallelism of the multicast communication.

The k-ary n-cube which has an n-dimensional grid structure with k nodes in each dimension has been a popular topology for interconnection networks. Analytical models for k-ary n-cubes have been widely reported under the assumptions that the message destinations are uniformly distributed over all network nodes and the message arrivals follow a non-bursty Poisson process. Recent studies have convincingly demonstrated that the traffic pattern in interconnection networks reveals the bursty nature in the both spatial domain (i.e., non-uniform distribution of message destinations) and temporal domain (i.e., bursty message arrival process). With the aim of capturing the characteristics of the realistic traffic pattern and obtaining a comprehensive understanding of the performance behaviour of interconnection networks, this paper presents a new analytical model for k-ary n-cubes in the presence of spatio-temporal bursty traffic. The accuracy of the model is validated through extensive simulation experiments of an actual system.

Wireless sensor networks (WSNs) are usually missioned to gather critical information in hostile and adversarial environments, which make them susceptible to compromise and revelation. Therefore, establishing secure communication in such networks is of great importance necessitating utilization of efficient key distribution schemes. In order to address such methods, several works using probabilistic, deterministic and hybrid approaches have been introduced in past few years. In this paper, we study the connectivity of key-distribution mechanisms in secured topologies of wireless sensor networks. We explore the effect of the radio range on the connectivity of the network and provide a lower bound on the radio range under which the cover time of the underlying topology decreases significantly. We also deduce that any broadcasting algorithm in such a network is performing only by a factor O(nß), where ß ¿ (0,1), worse than broadcasting algorithms in unsecured topologies. Our numerical results and simulation experiments validates the correctness and efficiency of our analysis.

We consider two flow control schemes for best effort traffic in on-chip architectures, which can be deemed as the solutions to the boundary extremes of a class of utility maximization problem. At one extreme, we consider the so-called rate-sum flow control scheme, which aims at improving the performance of the underlying system by roughly maximizing throughput while satisfying capacity constraints. At the other extreme, we deem the max-min flow control, whose concern is to maintain max-min fairness in rate allocation by fairly sacrificing the throughput. We then elaborate our argument through a weighting mechanism in order to achieve a balance between the orthogonal goals of performance and fairness. Moreover, we investigate the implementation facets of the presented flow control schemes in on-chip architectures. Finally, we validate the proposed flow control schemes and the subsequent arguments through extensive simulation experiments.

Broadcasting in MANETs is a fundamental data dissemination mechanism, with important applications, e.g., route query process in many routing protocols, address resolution and diffusing information to the whole network. Broadcasting in MANETs has traditionally been based on flooding, which overwhelm the network with large number of rebroadcast packets. Fixed counter-based flooding has been one of the earliest suggested approaches to overcome blind-flooding or the ldquobroadcast storm problemrdquo. As the topological characteristics of mobile networks varies instantly, the need of an adapted counter-based broadcast emerge. This research argues that neighbouring information could be used to better estimate the counter-based threshold value at a given node. Additionally results of extensive simulation experiments performed in order to determine the minimum and maximum number of neighbours for a given node is shown. This is done based on locally available information and without requiring any assistance of distance measurements or exact location determination devices.

The development of peer to peer overlay networks applications has attracted an immense interest from the research community in recent years. Several challenging issues have to be resolved in order to provide accessible, efficient and scalable inter-peer communication. Achieving resilience so as to reduce the disconnection probability, is among the most demanding issues to provide a robust and omnipresent service to peer to peer applications. This paper attempts to address this issue, by proposing a graph-theoretic model using the well-known star interconnection network with sub-logarithmic degree characteristics, which not only facilitate scalability problem, but also achieves maximum connectivity compared to the other existing graph-based methods. The simulation results confirm that the proposed solution attains a higher degree of resiliency compared to other existing topologies.

Conventional on-demand route discovery for ad hoc routing protocols extensively use simple flooding, which could potentially lead to high channel contention, causing redundant retransmissions and thus excessive packet collisions in the network. This phenomenon has been shown to greatly increase the network communication overhead and end to end delay. This paper proposes a new probabilistic counter-based method that can significantly reduce the number of RREQ packets transmitted during route discovery operation. Our simulation results reveal that equipping AODV routing protocol with the proposed probabilistic counter-based route discovery method can result in significant performance improvements in terms of routing overhead, MAC collisions and end-to-end delay while still achieving a good throughput.

The applications running on Networks on-Chip (NoC) typically have to meet a minimum performance requirements to perform successfully. Employing differentiated services is a widely used approach to support QoS (Quality of Service) by relatively prioritizing traffic in the networks employing connection-less communication mechanisms. In this paper we present an analytical evaluation of the average message latency for wormhole-routed interconnect architectures exploiting a traffic prioritization mechanism to achieve differentiated services-based QoS. To verify the validity of the model we apply the method to the Spidergon NoC and compare the model against the results obtained from a discrete-event simulator developed using OMNET.

Sensor nodes are usually deployed in adversarial environments in which they are subject to compromise and revelation of critical information rendering the entire network useless. Therefore, secure communication of wireless sensor networks (WSNs) necessitates utilization of efficient key distribution schemes. Over the past few years, several works using probabilistic, deterministic and hybrid methods have been conducted to address key distribution among sensor nodes. In this paper we propose a novel method to deterministically distribute key-chains throughout a WSN utilizing expander graphs based on the Zig-Zag graph product. Given a set of constraints such as network size, amount of storage, radio range and key-chain length, we are able to efficiently construct a resilient yet scalable key distribution graph. The main advantage of the obtained method is providing a more user-adjustable and predictable framework compared to the previously proposed approaches. Simulation results demonstrate the efficiency of our proposed scheme and its general applicability to different network paradigms with diverse requirements.

Pipelined circuit switching which combines the advantages of both circuit switching and wormhole switching is an efficient method for reconciling the conflicting demands of communication performance and fault-tolerance in interconnection networks of multi-computers. The arrival process and destination distribution of messages generated by real-world parallel applications can markedly affect the performance of communication networks. This paper presents an analytical performance model to calculate the message latency in hypercube interconnection networks with pipelined circuit switching in the presence of bursty and correlated traffic coupled with hot-spot message destinations. The accuracy of the analytical model is validated through extensive simulation experiments.

The performance of the existing non-contiguous processor allocation strategies has been traditionally carried out by means of simulation based on a stochastic workload model to generate a stream of incoming jobs. To validate the performance of the existing algorithms, there has been a need to evaluate the algorithms' performance based on a real workload trace. In this paper, we evaluate the performance of several well-known processor allocation and job scheduling strategies based on a real workload trace and compare the results against those obtained from using a stochastic workload. Our results reveal that the conclusions reached on the relative performance merits of the allocation strategies when a real workload trace is used are in general compatible with those obtained when a stochastic workload is used.

In this paper, we proposed a graph theoretic approach employing an algorithmic method to construct constant-degree graphs possessing not only provably minimum diameter, but also maximum connectivity with respect to other similar graphs.

Two strategies are used for the allocation of jobs to processors connected by mesh topologies: contiguous allocation and non-contiguous allocation. In noncontiguous allocation, a job request can be split into smaller parts that are allocated to non-adjacent free sub- meshes rather than always waiting until a single sub-mesh of the requested size and shape is available. Lifting the contiguity condition is expected to reduce processor fragmentation and increase system utilization. However, the distances traversed by messages can be long, and as a result the communication overhead, especially contention, is increased. The extra communication overhead depends on how the allocation request is partitioned and assigned to free sub-meshes. This paper presents a new noncontiguous allocation algorithm, referred to as greedy-available-busy-list (GABL for short), which can decrease the communication overhead among processors allocated to a given job. The simulation results show that the new strategy can reduce the communication overhead and substantially improve performance in terms of parameters such as job turnaround time and system utilization. Moreover, the results reveal that the shortest- service-demand-first (SSD) scheduling strategy is much better than the first-come-first-served (FCFS) scheduling strategy.

Networks on chip (NoC) emerged as a promising alternative to bus-based interconnect networks to handle the increasing communication requirements of the large systems on chip. Employing an appropriate topology for a NoC is of high importance mainly because it typically trade-offs between cross-cutting concerns such as performance and cost. The spidergon topology is a novel architecture which is proposed recently for NoC domain. The objective of the spidergon NoC has been addressing the need for a fixed and optimized topology to realize cost effective multi-processor SoC (MPSoC) development [7]. In this paper we analyze the traffic behavior in the spidergon scheme and present an analytical evaluation of the average message latency in the architecture. We prove the validity of the analysis by comparing the model against the results produced by a discrete- event simulator.

One of the key issues in the design of multiprocessors system-on-chip (MP-SoCs), multicomputers, and peer-to-peer networks is the development of an efficient communication network to provide high throughput and low latency and its ability to survive beyond the failure of individual components. Generally, the faulty components may be coalesced into fault regions, which are classified into convex and concave shapes. In this paper, we propose a mathematical solution for counting the number of common fault patterns in a 2-D mesh interconnect network including both convex (I-shape, II-shape, square-shape) and concave (L-shape, U- shape, T-shape, +-shape, H-shape) regions. The results presented in this paper which have been validated through simulation experiments can play a key role when studying, particularly, the performance analysis of fault-tolerant routing algorithms and measure of a network fault-tolerance expressed as the probability of a disconnection.

The use of adaptively-routed wormhole switched k-ary n-cubes has been motivated by the high path diversity provided by the rich topology of this family of interconnection networks. Due to its insensitivity to message destination, adaptive wormhole switching has been an attractive design alternative not only in networks suggested for contemporary multicomputers but also in the new Network-on-Chip and System-on-Chip architectures. Although analytical performance models for wormhole switched networks have been widely reported in the literature over the past two decades, the majority of these models have unrealistically assumed negligible buffering capacity at each switching element of the network. This paper proposes the first analytical model to assess the performance of adaptively-routed wormhole-switched k-ary n-cubes with finite size buffers. The new model can also accounts for the use of any number of virtual channels in order to further improve system performance. The model is validated by means of an event-driven simulator and experiments show close agreement between model predictions and simulator results.

The performance study of the existing noncontiguous processor allocation strategies has been traditionally carried out by means of simulation based on a stochastic workload model to generate a stream of incoming jobs that are submitted to and run on a given message passing parallel machine for a period of time. To validate the performance of the existing allocation algorithms, there has been need to evaluate the algorithms' performance based on a real workload trace. In this study, we evaluate the performance of several well-known processor allocation and job scheduling strategies based on a real workload trace and compare the results against those obtained from using a stochastic workload. Our results reveal that the conclusions reached on the relative performance merits of the allocation strategies when a real workload trace is used are in general compatible with those obtained when a stochastic workload is used.

The spidergon scheme is a commercial NoC (Network On-Chip) proposed recently to address the demand for a fixed and optimized topology to realize cost effective multi-processor SoC (MPSoC) development. The increasing diversity of the applications quality of service requirements may, however, inhibit employing a particular architecture for a wide range of applications, unless the performance it delivers is improved. A traditional approach to enhance the performance of the interconnect networks has been employing the virtual channels. In this paper, we present an analytical model to evaluate the performance of the Spidergon NoC and to study the effect of employing virtual channels. Results obtained through simulation experiments show that the model exhibits a good degree of accuracy in predicting average message latency under various working conditions.

One of the fundamental problems in parallel computing is how to efficiently perform routing in a faulty network each component of which fails with some probability. This paper presents a comparative performance study of ten prominent adaptive fault-tolerant routing algorithms in wormhole-switched 2D mesh interconnect networks. These networks carry a routing scheme suggested by Boppana and Chalasani as an instance of a fault-tolerant method. The suggested scheme is widely used in the literature to achieve high adaptivity and support inter-processor communications in parallel computer systems due to its ability to preserve both communication performance and fault-tolerant demands in these networks. The performance measures studied are the throughput, average message latency and average usage of virtual channels per node. Results obtained through simulation suggest two classes of presented routing schemes as high performance candidate in most faulty networks.

Conventional on-demand route discovery methods in mobile ad hoc networks (MANET) employ blind flooding, where a mobile node blindly rebroadcasts received Route Request (RREQ) packets until a route to a particular destination is established. This can potentially lead to high channel contention, causing redundant retransmissions and thus excessive packet collisions in the network. Such a phenomenon induces what is known as broadcast storm problem, which has been shown to greatly increase the network communication overhead and end-to-end delay. In this paper, we show that the deleterious impact of such a problem can be reduced if measures are taken during the dissemination of RREQ packets. We propose two new probabilistic methods for on-demand route discovery, that is simple to implement and can significantly reduce the overhead involved in the dissemination of RREQs. Our analysis reveals that equipping AODV with probabilistic route discovery can result in significant performance improvements on all the standard metrics.

Traffic loads have a significant impact on the performance of routing algorithms. Many analytical models for adaptive routing in interconnection networks have been reported. However, most existing studies are based on the assumption that the arrivals of traffic follow a non-bursty Poisson process and the message destinations are uniformly distributed over the network. With the aim of obtaining a deep understanding of network performance under more realistic working conditions, this study develops an analytical performance model for adaptive-routed hypercubic networks under hot-spot and batch arrival traffic. This model adopts the Compound Poisson Process (CPP) to capture the properties of the batch arrival traffic. Extensive simulation experiments are conducted to validate the accuracy of the analytical model.

In this paper, we propose a flow-level simulator called FSIM (Fluid-based SIMulator) for performance evaluation of large-scale networks, and verify its effectiveness using our FSIM implementation. The notable features of our flow-level simulator FSIM are its accuracy and fast simulation execution compared with conventional flow-level simulators. For improving simulation accuracy, our flow-level simulator FSIM utilizes accurate fluid-flow models. For accelerating simulation execution speed, our flow-level simulator FSIM adopts an adaptive numerical computation algorithm for ordinary differential equations. Another notable feature of our flow-level simulator FSIM is its compatibility with the existing network performance analysis tool. In this paper, through several experiments using our FSIM implementation, we evaluate the effectiveness of our flow-level simulator FSIM in terms of simulation speed, accuracy and memory consumption. Consequently, we show that our flow-level simulator FSIM outperforms a conventional flow-level simulator; i.e., it realizes approximately 100% faster simulation with higher accuracy and less memory consumption than a conventional flow-level simulator.

Appropriate use of a probabilistic broadcasting method in MANETs can decrease the number of rebroadcasts, and as a result reduce the opportunity of contention and collision among neighbouring nodes. In this paper we evaluate the performance of Adjusted Probabilistic flooding by comparing it to "simple" flooding as used with the Ad Hoc on Demand Distance Vector (AODV) routing protocol as well as a fixed probabilistic approach. The results reveal that the Adjusted Probabilistic flooding exhibits superior performance in terms of both reachability and saved rebroadcasts.

Interconnect networks employing wormhole-switching play a critical role in shared memory multiprocessor systems-on-chip (MPSoC) designs, multicomputer systems and system area networks. Virtual channels greatly improve the performance of wormhole-switched networks because they reduce blocking by acting as "bypass" lanes for non-blocked messages. Capturing the effects of virtual channel multiplexing has always been a crucial issue for any analytical model proposed for wormhole-switched networks. Dally has developed a model to investigate the behaviour of this multiplexing which have been widely employed in the subsequent analytical models of most routing algorithms suggested in the literature. It is indispensable to modify Daily's model in order to evaluate the performance of channel multiplexing in more general networks where restrictions such as timing constraints of input arrivals and finite buffer size of queues are common. In this paper we consider timing constraints of input arrivals to investigate the virtual channel multiplexing problem inherent in most current networks. The analysis that we propose is completely general and therefore can be used with any interconnect networks employing virtual channels. The validity of the proposed equations has been verified through simulation experiments under different working conditions

Many analytical performance models for k-ary n-cube networks have been reported in the literature. However, the inherent asymmetry of the mesh topology (k-ary n-cubes without wraparounds) renders derivation of an analytical model for this class of networks more challenging. As a consequence, very few analytical models have been proposed for wormhole routed 2-D mesh networks, and there has been to the best of our knowledge, no analytical performance model proposed for n-D mesh networks. To address this shortcoming, this paper proposes the first analytical performance model for n-D mesh networks employing fully adaptive wormhole routing. Simulation results show that this model is able to predict message latency with a good degree of accuracy, thus providing designers and researchers with a useful tool for the study and analysis of performance issues in mesh-based multicomputer systems

A major issue in modelling the performance merits of interconnection network is dealing with virtual channels. Some analytical models chose not to deal with this issue at all i.e. one virtual channel per physical channel. More sophisticated models, however, relayed on a method proposed by Dally to capture the effect of arranging the physical channel into many virtual channels. In this study, we investigate the accuracy of Dally's method and propose an alternative approach to deal with virtual channels in analytical performance modelling. The new method is validated via simulation experiments and results reveal its accuracy under different traffic conditions

The star graph was introduced as an attractive alternative to the well-known hypercube and its properties have been well studied in the past. Most of these studies have focused on topological properties and algorithmic aspects of this network. Although several analytical models have been proposed in the literature for different interconnection networks, none of them have dealt with star graphs. This paper proposes the first analytical model to predict message latency in wormhole-switched star interconnection networks with fully adaptive routing. The analysis focuses on a fully adaptive routing algorithm which has shown to be the most effective for star graphs. The results obtained from simulation experiments confirm that the proposed model exhibits a good accuracy under different operating conditions

Massively parallel computing systems are being built with hundreds or thousands of components such as nodes, links, memories, and connectors. The failure of a component in such systems will not only reduce the computational power but also alter the network's topology. The software-based fault-tolerant routing algorithm is a popular routing to achieve fault-tolerance capability in networks. This algorithm is initially proposed only for two dimensional networks (Suh et al., 2000). Since, higher dimensional networks have been widely employed in many contemporary massively parallel systems; this paper proposes an approach to extend this routing scheme to these indispensable higher dimensional networks. Deadlock and livelock freedom and the performance of presented algorithm, have been investigated for networks with different dimensionality and various fault regions. Furthermore, performance results have been presented through simulation experiments

A number of measurement studies have convincingly demonstrated that network traffic can exhibit a noticeable self-similar nature, which has a considerable impact on queuing performance. However, many routing protocols developed for MANETs over the past few years have been primarily designed and analyzed under the assumptions of either CBR or Poisson traffic models, which are inherently unable to capture traffic self-similarity. It is crucial to re-examine the performance properties of MANETs in the context of more realistic traffic models before practical implementation show their potential performance limitations. In an effort towards this end, this paper evaluates the performance of three well-known and widely investigated MANET routing protocols, notably DSR, AODV and OLSR, in the presence of the bursty self-similar traffic. Different performance aspects are investigated including, delivery ratio, routing overhead, throughput and end-to-end delay. Our simulation results indicate that DSR routing protocol performs well with bursty traffic models compared to AODV and OLSR in terms of delivery ratio, throughput and end-to-end delay. On the other hand, OLSR performed poorly in the presence of self-similar traffic at high mobility especially in terms of data packet delivery ratio, routing overhead and delay. As for AODV routing protocol, the results show an average performance, yet a remarkably low and stable end-to-end delay

Summary form only given. The efficiency of a large-scale multicomputer is critically dependent on the performance of its underlying interconnection network. Dimension-ordered routing has been employed to transmit messages in multicomputer networks, as it requires a simple deadlock-avoidance algorithm, resulting in an efficient router implementation. The performance of this routing algorithm has been widely analysed under the assumption of the traditional Poisson arrival process, which is inherently unable to model traffic self-similarity revealed by many real-world applications. In an effort towards providing cost-effective tools that help investigating network performance under more realistic traffic loads, we propose an analytical model for dimension-ordered routing in k-ary n-cube networks when subjected to self-similar traffic. As the service time, blocking probability and waiting time experienced by a message vary from a dimension to another with dimension-ordered routing, the design of this model poses greater challenges. The model validity is demonstrated by performance results obtained from simulation experiments.

A number of recent research studies have explored ways to improve TCP throughput in IEEE 802.11 mobile ad hoc networks. In particular, hidden terminal effects caused by interference have been shown to degrade TCP performance and have been dealt with, in previous work, by restricting the maximum congestion window size. We have pursued an alternative approach and have developed a TCP variant which adjusts the sending rate increase to achieve competitive goodput for TCP connections. In this paper, we demonstrate that a slower sending rate increase during the congestion avoidance phase of TCP leads to improved performance for TCP Reno while eliminating the negative effects inherent in restricting the maximum congestion window size. A performance comparison against existing solutions under various mobility conditions is also included.

Abstract Many studies have revealed that the traffic generated by multimedia applications exhibits a high degree of burstiness and possesses strong correlation in the number of message arrivals between adjacent time intervals, which can significantly affect network performance. This paper proposes a new analytical performance model for circuit‐switched k‐ary n‐cubes with correlated traffic pattern. Compared to the models presented in the previous studies, this model is more realistic due to its ability to capture the effects of using virtual channels at a source node by taking into account the splitting of correlated traffic. Moreover, a closed‐form expression for computing the probability of virtual channel occupancy is given. The validity of the present model is demonstrated by comparing analytical results against those obtained through simulation experiments of the actual system. Copyright © 2004 John Wiley & Sons, Ltd.

Abstract Several studies have examined the relative performance merits of the torus and hypercube taking into account the channel bandwidth constraints imposed by implementation technology. While the torus has been shown to outperform the hypercube under the constant wiring density constraint, the opposite conclusion has been reached when the constant pin‐out constraint is considered. However, these studies have assumed a pure uniform traffic pattern and deterministic routing. The ‘uniform traffic’ assumption is not always justifiable in practice as there are many real‐world parallel applications that exhibit non‐uniform traffic patterns, which can create unbalanced traffic such as hotspots in the network. This paper re‐examines the performance merits of the torus and hypercube in the presence of hotspot traffic. The comparative analysis is based on fully adaptive routing as this has been gaining popularity in recent practical multicomputers. Moreover, it uses a new cost model that takes into account the implementation cost of the network and its routers. The results reveal that for moderate and large system sizes, lower dimensionalk‐aryn‐cubes (e.g. 2D torus) always outperform their higher dimensional counterparts even under the pin‐out constraint. Copyright © 2004 John Wiley & Sons, Ltd.

Many recent studies have convincingly demonstrated that network traffic exhibits a noticeable self-similar nature, which has a considerable impact on queuing performance. However, the networks used in current multicomputers have been primarily designed and analyzed under the assumption of the traditional Poisson arrival process, which is inherently unable to capture traffic self-similarity. Consequently, it is crucial to reexamine the performance properties of multicomputer networks in the context of more realistic traffic models before practical implementations show their potential faults. In an effort toward this end, we propose the first analytical model for wormhole-switched k-ary n-cubes in the presence of self-similar traffic. Simulation experiments demonstrate that the proposed model exhibits a good degree of accuracy for various system sizes and under different operating conditions. The analytical model is then used to investigate the implications of traffic self-similarity on network performance. We reveal that the network suffers considerable performance degradation when subjected to self-similar traffic, stressing the great need for improving network performance to ensure efficient support for this type of traffic.

Abstract A number of recent research studies have explored ways to improve TCP throughput in mobile ad hoc networks by improving its interaction with the IEEE 802.11 medium access control (MAC) layer. In particular, the hidden terminal effects caused by interference can impact TCP performance dramatically and have been dealt with in the past by restricting the maximum sending window size. We have developed a TCP variant, which instead, adjusts the sending rate increase to achieve competitive goodput for TCP connections. Extensive simulation experiments indicate that a slower sending rate increase during the congestion avoidance phase of TCP leads to improved performance for TCP Reno while eliminating the negative effects inherent in restricting the maximum sending window size. This work discusses the applicability of our TCP oriented solution to the hidden terminal effect, includes a performance comparison against existing solutions and discusses its performance merits under various mobility conditions. Copyright © 2004 John Wiley & Sons, Ltd.

Analytical models are cost-effective and versatile tools for evaluating system performance under different design alternatives. This study presents an analytical performance model for pipelined circuit switching (PCS) in binary n-cube networks in the presence of bursty traffic, which is modeled by a switched Poisson process (SPP). The validity of the model is demonstrated by comparing analytical results to those obtained through simulation experiments of the actual system. This model and that proposed by Min et al. for wormhole switching (WS) are then used to investigate the relative performance merits of PCS and WS under bursty traffic.

The properties of self-similar traffic have strong effects on queueing performance. It has been suggested that many existing computer and communication systems need to be reevaluated in the presence of this new type of traffic. To this end, this paper proposes an analytical performance model for adaptive wormhole routing in torus interconnection networks under self-similar traffic. The bursty characteristic of traffic over multiple time scales is captured by the superposition of a number of two-state Markov-modulated poisson processes (MMPPs). Simulation experiments demonstrate that the proposed model exhibits a good degree of accuracy for various system sizes and under different operating conditions. The analytical model is then used to investigate the impact of the important parameter of traffic self-similarity on network performance.

Many broadcast algorithms have been proposed for the mesh over the past decade. However, most of these algorithms do not exhibit good scalability properties as the network size increases. As a consequence, most existing broadcast algorithms cannot support real-world parallel applications that require large-scale system sizes due to their high computational demands. Motivated by these observations, this study proposes a new adaptive broadcast algorithm for the mesh. The unique feature of our algorithm is that it handles broadcast operations with a fixed number of message passing steps irrespective of the network size. Our algorithm is based on the coded path routing, which has been proposed in (Al-Dubai and Ould-Khaous, 2001). Results from extensive comparative analysis reveal that the proposed algorithm exhibits superior performance characteristics over those of the well-known Recursive Doubling and Extending Dominating Node algorithms.

This paper describes the new fault-tolerant routing algorithm for k-ary n-cubes using the concept of "probability vectors" and conducts an extensive performance analysis for the new algorithm. To compute these vectors, a node determines first its faulty set, which represents the set of all its neighbouring nodes that are faulty or unreachable due to faulty links. Each node then calculates a probability vector, where the l/sup th/ element represents the probability that a destination node at distance l cannot be reached through a minimal path due to a fault node or link. The probability vectors are used by all the nodes to achieve an efficient fault-tolerant routing in the network. The extensive performance analysis conducted in this study reveals that the proposed algorithm exhibits good fault-tolerance properties in terms of the achieved average routing distances.

Many recent studies on a wide range of networks by means of high quality, high time-resolution measurements have indicated that traffic burstiness and correlations among inter-arrival intervals are present over many time scales, which can be modelled using the long-range dependent (LRD) process. A LRD process is characterised by a hyperbolically decaying correlation function. However, interconnection networks used in current multicomputers have been mainly designed and analysed under the assumption that traffic follows the traditional short-range dependent process (e.g., the Poisson arrival process). In an effort to reevaluate network performance, this paper presents a new analytical model for circuit-switched interconnection networks under LRD traffic. Simulation experiments reveal that the model exhibits a good degree of accuracy under various operating conditions.

Most existing broadcast algorithms proposed for the mesh do not scale well with the network size. Furthermore, they have been mainly based on deterministic routing, which cannot exploit the alternative paths provided by mesh topology to reduce communication latency. Motivated by these observations, this paper introduces a new adaptive broadcast algorithm for the mesh. The unique feature of our algorithm is its ability to handle broadcast operations with only two message-passing steps irrespective of the network size. Results from extensive comparative analysis reveal that the proposed algorithm exhibits superior performance characteristics over those of the well-known recursive doubling and extending dominating node algorithms.

Adding virtual channels to wormhole-routed networks greatly improves performance because they reduce blocking by acting as "bypass" lanes for non-blocked messages. Although several analytical models have been proposed in the literature for k-ary n-cubes with deterministic routing, most of them have not included the effects of virtual channel multiplexing on network performance. This paper proposes a new and simple analytical model to compute message latency in k-ary n-cubes with an arbitrary number of virtual channels. Results from simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various network sizes and under different operating conditions. The proposed model is then used to investigate the relative performance merits of two different organisations of virtual channels.

The k-ary n-cube has been used as the underlying topology for most practical multicomputers, and has been extensively studied in the past. We investigate some properties of this network. In particular, we study the problem of finding the number of nodes located i hops away from a given node (surface area) and the number of nodes located within i hops away from a given node (volume) in both the unidirectional and bidirectional k-ary n-cube, and have derived exact expressions calculating these numbers. These results are very useful when studying, for example, the spanning tree structure of the k-ary n-cube and the problem of resource placement in this network.

Several recent studies have revealed that deadlocks occur very infrequently in the network, especially when enough routing freedom is provided. Routing algorithms based on deadlock avoidance reserve some virtual channels or routing options to specifically deal with deadlocks, and as a result they are not utilized most of the time. Routing algorithms based on deadlock recovery allow messages to use all available virtual channels to cross the network, and efficiently handle infrequently occurred deadlocks. This paper describes a new analytical model of a true fully adaptive routing (TFAR) algorithm with software-based deadlock recovery in k-ary n-cubes. Results obtained through simulation experiments confirm that the model predicts message latency with a good degree of accuracy under different working conditions.

Several analytical models have been proposed in the literature for wormhole-routed multicomputers. However, all these models have been discussed in the context of unicast communication and there has been comparatively little activity in the area of analytical modelling of collective communication algorithms like broadcast. This paper presents an analytical model for predicting latency of broadcast messages in wormhole-routed hypercubes. Results obtained through simulation experiments show that the model exhibits a good degree of accuracy in predicting broadcast latency under different working conditions.

Many recent studies have revealed that the traffic generated by multimedia applications exhibits a high degree of burstiness and possesses strong correlation in the number of message arrivals between adjacent time intervals, which can significantly affect network performance. However all existing performance models for multicomputer networks have assumed the Poisson arrival process, which has been shown on many occasions to be unable to capture the nature of multimedia traffic. This paper proposes the first analytical model for wormhole switching in k-ary n-cube networks under multimedia traffic based on the well-known correlated Markov-modulated Poisson process (MMPP). Results obtained from simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various network sizes and under different operating conditions.

This paper describes a new fault-tolerant routing algorithm for the hypercube, using the concept of probability vectors. To compute these vectors, a node first determines its faulty set, which represents the set of all its neighbouring nodes that are faulty or unreachable due to faulty nodes or links. Each node then calculates a probability vector, where the $k$th element represents the probability that a destination node at distance $k$ cannot be reached through a minimal path due to a faulty node or link. The probability vectors are used by all the nodes to achieve an efficient fault-tolerant routing in the network. A performance comparison with the recently proposed safety-vectors algorithm, through extensive simulation, shows that the new algorithm exhibits superior performance in terms of routing distances and percentage of reachability.

Several analytical models of fully adaptive routing have recently been proposed for wormhole-routed k-ary n-cubes under the uniform traffic pattern. However, there has been hardly any model reported yet that deals with other important nonuniform traffic patterns, such as hot-spots. As a result, most studies have resorted to simulation when evaluating the performance merits of adaptive routing. In an effort to fill this gap, this paper describes the first analytical model of fully adaptive routing in k-ary n-cubes in the presence of hot-spot traffic. Results from simulation show close agreement with those predicted by the model.

Analytical models of fully adaptive routing for common wormhole-routed networks (e.g., hypercubes) under the uniform traffic pattern have recently been reported in the literature. However, many studies have revealed that the performance advantages of adaptive routing over deterministic routing is more noticeable when the traffic is nonuniform due to, for example, the existence of hot spots in the network. This paper proposes a new queueing model of fully adaptive routing in the hypercube in the presence of hot spot traffic. The analysis focuses on Duato's algorithm, but can easily be applied to other fully adaptive routing algorithms. Results from simulation experiments are presented to validate the model.

Several analytical models of deterministic routing in wormhole-routed k-ary n-cubes have already been reported in the literature. The performance characteristics of most fully-adaptive routing algorithms have often been analyzed by means of simulation and there is hardly any analytical model proposed for calculating message latency in wormhole-routed k-ary n-cubes using adaptive routing. The paper proposes an accurate analytical model to predict the message latency in wormhole-routed k-ary n-cubes with fully adaptive routing. The proposed model is general in that it exhibits a good degree of accuracy for various network configurations and under different operating conditions.

Several analytical models of fully adaptive routing in wormhole-routed k-ary n-cubes under the uniform traffic pattern have recently been proposed in the literature. Although the uniform reference model has been widely used in the past, it is not always true in practice as there are many applications that exhibit non-uniform traffic patterns. There has not been so far any study that describes an analytical model of fully adaptive routing under permutation traffic patterns. This paper describes a new analytical model of fully adaptive routing in k-ary n-cubes in the presence of non-uniform traffic generated by matrix-transpose permutations, which is an important communication operation found in many matrix computation problems. Results obtained through simulation experiments confirm that the model predicts message latency with a reasonable degree of accuracy under different working conditions.

Several analytical models of fully-adaptive routing have recently been proposed for wormhole-routed k-ary n-cubes under the uniform traffic pattern. However, there has been hardly any model reported yet that deals with other important non-uniform traffic patterns, such as hot spots. As a result, most studies have resorted to simulation when evaluating the performance merits of adaptive routing. This paper describes the first analytical model of fully-adaptive wormhole routing in k-ary n-cubes in the presence of hot spot traffic. Results from simulation show close agreement with those predicted by the model.

This paper introduces a parallel algorithm for computing an N=n!-point Lagrange interpolation on an n-star (n>2). It exploits several communication techniques on stars in a novel way which can be adapted for computing similar functions. The algorithm is optimal and consists of three phases: initialization, main and final. While there is no computation in the initialization phase, the main phase is composed of n!/2 steps, each consisting of four multiplications, four subtractions and one communication operation, and an additional step including one division and one multiplication. The final phase is carried out in (n-1) sub-phases each with O(log n) steps where each step takes three communications and one addition.

Several recent studies have revealed that pipelined circuit switching (PCS) can provide superior performance characteristics over wormhole routing. This paper proposes an original analytical model of PCS in k-ary n-cube networks augmented with virtual channel support. The model uses random walk theory to analyse the backtracking actions of the header flit during the path setup phase in PCS, and M/G/I queueing systems to compute the mean waiting time that a message experiences at a source before entering the network. Results from simulation experiments show close agreement to those predicted by the model.

Many analytical models of wormhole-routed networks have been proposed over the past few years. Most of these models, however, have been developed for unicast (or point-to-point) communication. There has been comparatively little activity in the area of analytical models of collective communication, such as broadcast. As a result, most existing studies have relied on simulation to evaluate the performance merits of collective communication algorithms. This paper presents a new analytical model for predicting broadcast latency in the hypercube. Results obtained through simulation experiments show that the model exhibits a good degree of accuracy in predicting message latency under different working conditions.

Several analytical models of adaptive routing in wormhole-routed networks, including hypercubes, under the uniform traffic pattern have recently been proposed in the literature. However, there has been hardly any model reported yet that deals with other important non-uniform traffic patterns exhibited by many parallel applications. As a result, most existing studies have resorted to simulation when evaluating the performance merits of adaptive routing under non-uniform traffic conditions. This paper describes a new analytical model of adaptive routing in the hypercube in the presence of non-uniform traffic generated by matrix-transpose permutations, which is used in many matrix computation problems. Results obtained through simulation experiments show that the model exhibits a good degree of accuracy in predicting message latency under different working conditions.

Low-dimensional k-ary n-cubes have been popular in recent multicomputers. These networks, however, suffer from high switching delays due to their high message distance. To overcome this problem, Dally has proposed a variation, called express k-ary n-cubes. with express channels that allow non-local messages to partially bypass clusters of nodes within a dimension. K-ary n-cubes are graph topologies where a channel connects exactly two nodes. This study argues that hypergraph topologies, where a channel connects any number of nodes, thus providing total bypasses within a dimension, represent potential candidates for future high-performance networks. It presents a comparative analysis, of a regular hypergraph, referred to as the distributed crossbar switch hypermesh (DCSH), and the express k-ary n-cube. The analysis considers channel bandwidth constraints which apply in different implementation technologies. The results conclude that the DCSH's total bypass strategy yields superior performance characteristics to the partial bypassing of its express cube counterpart.

Analytical models of deterministic routing in wormhole-routed k-ary n-cubes have widely been reported in the literature. Although many fully adaptive routing algorithms have been proposed to overcome the performance limitations of deterministic routing, there have been hardly any studies that describe analytical models for these algorithms. This paper proposes a new analytical model for obtaining latency measures in high-radix k-ary n-cubes with fully adaptive routing, based on Duato's algorithm (1998). The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.

Analytical models of deterministic routing in wormhole-routed k-ary n-cubes have widely been reported in the literature. Although many fully-adaptive routing algorithms have been proposed to overcome the performance limitations of deterministic routing, there has been hardly any study that describes analytical models for these algorithms. The paper proposes a queueing model for obtaining latency measures in wormhole-routed k-ary n-cubes with fully-adaptive routing, based on Duato's (1993) algorithm. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.

In a multicomputer network, the channel bandwidth is greatly constrained by implementation technology. Two important constraints have been identified in the literature, each appropriate for a particular technology: wiring density limits dominate in VLSI and pin-out in multiple-chip implementations. Most existing interconnection networks are categorized as either direct or indirect (multi-stage) topologies, the mesh and binary n-cube being examples of the former category, the omega and banyan networks of the latter. This paper argues that direct networks based on hypergraph topologies have characteristics which make them particularly appropriate for use in future high-performance parallel systems. The authors have recently introduced a regular multi-dimensional hypergraph network, called the Distributed Crossbar Switch Hypermesh (DCSH), which has topological properties that permit a relaxation of bandwidth constraints, and which has important topological and performance advantages over direct graph networks. This paper compares the DCSH to multi-stage networks, under both VLSI and multiple-chip technological constraints. The results suggest that in both cases, with a realistic model which includes routing delays through intermediate nodes, the DCSH exhibits superior performance across a wide range of traffic loads.