The network topology of modern parallel computing systems is inherently heterogeneous, with a variety of latency and bandwidth values. Moreover, contention for the bandwidth can exist on different levels when many processes communicate with each other. Many-pair, point-to-point MP communication is thus characterized by heterogeneity and contention, even on a cluster of homogeneous multicore CPU nodes. To get a detailed understanding of the individual communication cost per MPI process, we propose a new modeling methodology that incorporates both heterogeneity and contention. First, we improve the standard max-rate model to better quantify the actually achievable bandwidth depending on the number of MPI processes in competition. Then, we make a further extension that more detailedly models the bandwidth contention when the competing MPI processes have different numbers of neighbors, with also non-uniform message sizes. Thereafter, we include more flexibility by considering interactions between intra-socket and inter-socket messaging. Through a series of experiments done on different processor architectures, we show that the new heterogeneous and contention-constrained performance models can adequately explain the individual communication cost associated with each MPI process. The largest test of realistic point-to-point MPI communication involves 8,192 processes and in total 2,744,632 simultaneous messages over 64 dual-socket AMD Epyc Rome compute nodes connected by InfiniBand, for which the overall prediction accuracy achieved is 8 4%.

Interconnection networks are the communication backbone of modern high-performance computing systems and an optimised interconnection network is crucial for the performance and utilisation of the system as a whole. One element of the interconnection network is the routing algorithm, which directly influences how we are able to utilise the physical network topology. InfiniBand is one of the most common network architectures used in high-performance computing and traditionally it only supported static routing. For multi-path networks such as Fat-trees, static routing is inefficient because it cannot balance traffic in real-time nor utilise multiple paths efficiently under adversarial traffic. This again potentially leads to unnecessary contention and an underutilised network, which has led to numerous proposals on how to avoid this by using adaptive routing. Adaptive routing has recently been introduced in InfiniBand and in this paper we evaluate to what extent the expected benefits of adaptive routing is true for InfiniBand. Through a set of experiments on HDR InfiniBand equipment we describe the basic behaviour of adaptive routing in InfiniBand, its benefits in Fat tree topologies and the unfortunate side effects related to unfairness that adaptive routing in general might introduce, including such phenomena as the reverse parking lot problem and congestion spreading.

This work introduces a class of network performance models designed to capture variations in network quality on diverse timescales. By explicitly modeling how quality changes over time, the proposed models enable computation of performance metrics that are beyond the scope of steady-state methods such as Markov chains. We use the quality attenuation (ΔQ) metric to quantify network quality, and ΔQ generative models specify how quality attenuation varies over time. Variation over time is modeled using a finite state machine with timed state transitions. We show how the models can be used to shed light on practical problems by presenting novel results for the problem of buffer sizing. In addition to the buffer sizing results, this work presents the ΔQ generative model structure and the basic algorithms needed to work with the models.

WiFi is one of the most widely deployed networking technologies, and understanding WiFi performance is therefore of great importance. The WiFi MAC layer sometimes introduces significant and variable delays. No existing models of the WiFi protocol describe WiFi performance in terms of complete latency distributions. In this work, we present a novel model of WiFi performance. We explicitly define our model in terms of the latency introduced at each step in the protocol state machine, and the model produces complete latency distributions. We validate the model by comparing its outputs to previous modeling work and real-world measurements. Finally, we use our results to quantify the latency distribution of WiFi as a function of the duration of transmit opportunities and the number of stations competing for the channel. Quantifying this relation represents a significant improvement in our understanding of WiFi performance that would not be possible with existing models.

WiFi is a crucial part of internet infrastructure. Performance issues are common in WiFi networks, but well-tested solutions exist for some known problems. In this work, we look for evidence of known WiFi issues in chipsets commonly found in consumer WiFi routers. We document serious performance problems in most of the tested WiFi chipsets and point to existing solutions for the detected problems. The prevalence of these problems has implications for network management, network research, and for users and creators of performance-sensitive network applications running over WiFi. To our knowledge, this is the most comprehensive documentation of these issues to date.

Summary To meet the demands of communication‐intensive workloads in the cloud, virtual machines (VMs) should utilize low overhead network communication paradigms. In general, such paradigms enable VMs to directly communicate with the hardware by means of a passthrough technology like Single‐Root I/O Virtualization (SR‐IOV). However, when passthrough‐based virtualization is coupled with lossless interconnection networks, live migrations introduce scalability challenges due to the substantial network reconfiguration overhead. With these challenges in mind, we proposed a virtual switch (vSwitch) SR‐IOV architecture for InfiniBand in our previous work titled “Towards the InfiniBand SR‐IOV vSwitch Architecture”. In this paper, we first suggest solutions to rectify the space‐domain scalability issues that are present in vSwitch‐enabled subnets as a result of the VMs using dedicated layer‐two addresses. Then, we discuss routing strategies for virtualized environments using vSwitches and present a routing algorithm for Fat‐Trees. We also present a reconfiguration method that minimizes imposed reconfiguration overhead on Fat‐Trees. We perform an extensive evaluation of our prototype algorithms, and as vSwitch‐enabled hardware does not yet exist, we deduce from empirical observations by emulating vSwitches with existing hardware, as well as large‐scale simulations. Our results show significant reduction in the reconfiguration times as route recalculations can be eliminated, and for certain scenarios, the number of reconfiguration subnet management packets sent to switches is reduced from several hundred thousand down to a single one without degrading the routing quality.

Mobile edge computing (MEC) is an emergent architecture where cloud computing services are extended to the edge of networks leveraging mobile base stations. As a promising edge technology, it can be applied to mobile, wireless, and wireline scenarios, using software and hardware platforms, located at the network edge in the vicinity of end-users. MEC provides seamless integration of multiple application service providers and vendors toward mobile subscribers, enterprises, and other vertical segments. It is an important component in the 5G architecture which supports variety of innovative applications and services where ultralow latency is required. This paper is aimed to present a comprehensive survey of relevant research and technological developments in the area of MEC. It provides the definition of MEC, its advantages, architectures, and application areas; where we in particular highlight related research and future directions. Finally, security and privacy issues and related existing solutions are also discussed.

Clouds offer flexible and economically attractive compute and storage solutions for enterprises. However, the effectiveness of cloud computing for high-performance computing (HPC) systems still remains questionable. When clouds are deployed on lossless interconnection networks, like InfiniBand (IB), challenges related to load-balancing, low-overhead virtualization, and performance isolation hinder full potential utilization of the underlying interconnect. Moreover, cloud data centers incorporate a highly dynamic environment rendering static network reconfigurations, typically used in IB systems, infeasible. In this paper, we present a framework for a self-adaptive network architecture for HPC clouds based on lossless interconnection networks, demonstrated by means of our implemented IB prototype. Our solution, based on a feedback control and optimization loop, enables the lossless HPC network to dynamically adapt to the varying traffic patterns, current resource availability, workload distributions, and also in accordance with the service provider-defined policies. Furthermore, we present IBAdapt, a simplified ruled-based language for the service providers to specify adaptation strategies used by the framework. Our developed self-adaptive IB network prototype is demonstrated using state-of-the-art industry software. The results obtained on a test cluster demonstrate the feasibility and effectiveness of the framework when it comes to improving Quality-of-Service compliance in HPC clouds.

Summary Exascale computing systems are being built with thousands of nodes. The high number of components of these systems significantly increases the probability of failure. A key component for them is the interconnection network. If failures occur in the interconnection network, they may isolate a large fraction of the machine. For this reason, an efficient fault‐tolerant mechanism is needed to keep the system interconnected, even in the presence of faults. A recently proposed topology for these large systems is the hybridk‐aryn‐directs‐indirect family that provides optimal performance and connectivity at a reduced hardware cost. This paper presents a fault‐tolerant routing methodology for thek‐aryn‐directs‐indirect topology that degrades performance gracefully in presence of faults and tolerates a large number of faults without disabling any healthy computing node. In order to tolerate network failures, the methodology uses a simple mechanism. For any source‐destination pair, if necessary, packets are forwarded to the destination node through a set of intermediate nodes (without being ejected from the network) with the aim of circumventing faults. The evaluation results shows that the proposed methodology tolerates a large number of faults. For instance, it is able to tolerate more than 99.5% of fault combinations when there are 10 faults in a 3‐D network with 1000 nodes using only 1 intermediate node and more than 99.98% if 2 intermediate nodes are used. Furthermore, the methodology offers a gracious performance degradation. As an example, performance degrades only by 1% for a 2‐D network with 1024 nodes and 1% faulty links.

In battery-powered Cognitive Machine-to-Machine\nCommunications (CM2M), the energy consumption, opportunis-\ntic data access capacity and interference to the licensed system\nneed to be optimized simultaneously. We consider this as joint\ncooperative spectrum sensing and power allocation, and model\nthis as a constraint multiobjective optimization problem of three\nobjectives. Our model helps to find a Pareto optimal variable\nset of sensing duration, detection threshold and transmission\npower for each individual sensor in cooperative spectrum sensing.\nThe evaluation of our model shows that energy consumption,\nopportunistic data capacity and interference are optimized\nsimultaneously while keeping the total cooperative spectrum\nsensing error lower than a predefined threshold. Pareto optimal\nresults show that better energy efficiency [bits/joule] makes lower\nharmful interference to the primary system.

Reconfiguration of high performance lossless interconnection networks is a cumbersome and time-consuming task. For that reason reconfiguration in large networks are typically limited to situations where it is absolutely necessary, for instance when severe faults occur. On the contrary, due to the shared and dynamic nature of modern cloud infrastructures, performance-driven reconfigurations are necessary to ensure efficient utilization of resources. In this work we present a scheme that allows for fast reconfigurations by limiting the task to subparts of the network that can benefit from a local reconfiguration. Moreover, our method is able to use different routing algorithms for different sub-parts within the same subnet. We also present a Fat-Tree routing algorithm that reconfigures a network given a user-provided node ordering. Hardware experiments and large scale simulation results show that we are able to significantly reduce reconfiguration times from 50% to as much as 98.7% for very large topologies, while improving performance.

In large InfiniBand subnets the Subnet Manager (SM) is a potential bottleneck. When an InfiniBand subnet grows in size, the number of paths between hosts increases polynomials and the SM may not be able to serve the network in a timely manner when many concurrent path resolution requests are received. This scalability challenge is further amplified in a dynamic virtualized cloud environment. When a Virtual Machine (VM) with InfiniBand interconnect live migrates, the VM addresses change. These address changes result in additional load to the SM as communicating peers send Subnet Administration (SA) path record queries to the SM to resolve new path characteristics. In this paper we benchmark OpenSM to empirically demonstrate the SM scalability problems. Then we show that our novel SA Path Record Query caching scheme significantly reduces the load towards the SM. In particular, we show by using the Reliable Datagram Socket protocol that only a single initial SA path query is needed per communicating peer, independent of any subsequent (re)connection attempts.

InfiniBand (IB) is a widely used network interconnect for modern high-performance computing systems. In large IB fabrics, isolation of nodes is provided through partitioning. The routing algorithm, however, is unaware of these partitions in the network, Traffic flows belonging to different partitions might share links inside the network fabric. This sharing of intermediate links creates interference, which is particularly critical to avoid in multi-tenant environments like a cloud. In such systems, each tenant should experience predictable network performance, unaffected by the workload of other tenants. In addition, using current routing schemes, routes crossing partition boundaries are considered when distributing routes onto links in the network, despite the fact that these routes will never be used. The result is degraded load-balancing. In this paper, we present a novel partition-aware fat-tree routing algorithm, pFTree. The pFTree algorithm utilizes several mechanisms to provide network-wide isolation of partitions belonging to different tenant groups. Given the available network resources, pFTree starts by isolating partitions at the physical link level, and then moves on to utilize virtual lanes, if needed. Our experiments and simulations show that pFTree is able to significantly reduce the affect of inter-partition interference without any additional functional overhead. Furthermore, pFTree also provides improved load-balancing over the de facto standard IB fat-tree routing algorithm.

To meet the demands of the Exascale era and facilitate Big Data analytics in the cloud while maintaining flexibility, cloud providers will have to offer efficient virtualized High Performance Computing clusters in a pay-as-you-go model. As a consequence, high performance network interconnect solutions, like InfiniBand (IB), will be beneficial. Currently, the only way to provide IB connectivity on Virtual Machines (VMs) is by utilizing direct device assignment. At the same time to be scalable, Single-Root I/O Virtualization (SR-IOV) is used. However, the current SR-IOV model employed by IB adapters is a Shared Port implementation with limited flexibility, as it does not allow transparent virtualization and live-migration of VMs. In this paper, we explore an alternative SR-IOV model for IB, the virtual switch (vSwitch), and propose and analyze two vSwitch implementations with different scalability characteristics. Furthermore, as network reconfiguration time is critical to make live-migration a practical option, we accompany our proposed architecture with a scalable and topology agnostic dynamic reconfiguration method, implemented and tested using OpenSM. Our results show that we are able to significantly reduce the reconfiguration time as route recalculations are no longer needed, and in large IB subnets, for certain scenarios, the number of reconfiguration subnet management packets (SMPs) sent is reduced from several hundred thousand down to a single one.

As the size of high-performance computing systems grows, the number of events requiring a network reconfiguration, as well as the complexity of each reconfiguration, is likely to increase. In large systems, the probability of component failure is high. At the same time, with more network components, ensuring high utilization of network resources becomes challenging. Reconfiguration in interconnection networks, like InfiniBand (IB), typically involves computation and distribution of a new set of routes in order to maintain connectivity and performance. In general, current routing algorithms do not consider the existing routes in a network when calculating new ones. Such configuration-oblivious routing might result in substantial modifications to the existing paths, and the reconfiguration becomes costly as it potentially involves a large number of source-destination pairs. In this paper, we propose a novel routing algorithm for IB based fat-tree topologies, SlimUpdate. SlimUpdate employs techniques to preserve existing forwarding entries in switches to ensure a minimal routing update, without any performance penalty, and with minimal computational overhead. We present an implementation of SlimUpdate in OpenSM, and compare it with the current de facto fat-tree routing algorithm. Our experiments and simulations show a decrease of up to 80% in the number of total path modifications when using SlimUpdate routing, while achieving similar or even better performance than the fat-tree routing in most reconfiguration scenarios.

Infini Band (IB) has become a popular network interconnect for high performance computing (HPC) systems. Many of the large IB-based HPC systems use some variant of the fat-tree topology to take advantage of the useful properties fat-trees offer. The fat-tree routing algorithm is one of the most efficient deterministic routing algorithms for fat-tree topologies. The algorithm ensures that the number of routes assigned to each link are balanced across the fabric. However, one problem with its load-balancing technique is that it assumes uniform traffic distribution in the network. When routes towards nodes that mainly consume large amount of data are assigned to share links in the fabric while alternative links are underutilized, sub-optimal network throughput is obtained. Also, as the fat tree algorithm routes nodes according to the indexing order, the performance may differ for two systems cabled in the exact same way. In this paper, we propose wFatTree, a novel fat-tree routing algorithm, which considers node traffic characteristics to balance load across the network links more evenly, and with predictable network performance. Our experiments and simulations show an improvement of up to 60% in total network throughput on large fat-tree installations when using wFatTree routing. Furthermore, wFatTree can also be used to prioritize traffic flowing towards the critical nodes in the network.

Interconnection networks are key components in high-performance computing (HPC) systems, their performance having a strong influence on the overall system one. However, at high load, congestion and its negative effects (e.g., Head-of-line blocking) threaten the performance of the network, and so the one of the entire system. Congestion control (CC) is crucial to ensure an efficient utilization of the interconnection network during congestion situations. As one major trend is to reduce the effective wiring in interconnection networks to reduce cost and power consumption, the network will operate very close to its capacity. Thus, congestion control becomes essential. Existing CC techniques can be divided into two general approaches. One is to throttle traffic injection at the sources that contribute to congestion, and the other is to isolate the congested traffic in specially designated resources. However, both approaches have different, but non-overlapping weaknesses: injection throttling techniques have a slow reaction against congestion, while isolating traffic in special resources may lead the system to run out of those resources. In this paper we propose EcoCC, a new Efficient and Cost-Effective CC technique, that combines injection throttling and congested-flow isolation to minimize their respective drawbacks and maximize overall system performance. This new strategy is suitable for current commercial switch architectures, where it could be implemented without requiring significant complexity. Experimental results, using simulations under synthetic and real trace-based traffic patterns, show that this technique improves by up to 55 percent over some of the most successful congestion control techniques.

At the core of an efficient chip multiprocessors (CMP) is support for unicast and multicast routing, low implementation costs, and the ability to isolate concurrent applications with maximum utilization of the CMP. We present an efficient logic-based unicast and multicast routing algorithm that guarantees isolation of local application traffic within any near-convex region on the chip, and the algorithms to recognize supported partitions and configure the cores accordingly. Evaluations show that the routing algorithm has a 57% more compact implementation than a recent multicast solution with the same coverage, and it achieves 5% higher throughput with 13% lower latency.

Networks-on-chip (NoCs) are key components in many-core chip designs. Dynamic power-awareness is a new challenge present in NoCs that must be efficiently handled by the routing functionality as it introduces irregularities in the commonly used 2-D meshes. In this article, we propose a logic-based routing algorithm, iFDOR, oriented towards dynamic powering down one region within every application partition on the chip through dynamic rerouting, with low implementation costs. Results show that we can successfully shutdown an arbitrary rectangular region within an application partition without significant impact on network performance.

Single Root I/O Virtualization (SR-IOV) is a promising I/O virtualization approach for achieving high performance in the virtualization over InfiniBand (IB) network. One challenge is related to the hardware address assignment for each virtual IB device. There are two schemes for the hardware address assignment, static assignment and dynamic assignment. Static assignment always preserves the hardware address of a virtual IB device that is attached to a VM, but the dynamic assignment does not. A drawback, however, using static assignment is that its communication will be disconnected after VM migration. In this paper, we point out the problem related to SR-IOV over IB that breaks the network connections after VM migration when the static assignment is deployed. Then, we propose a signalling mechanism that can maintain the network connectivity after VM migration. The performance evaluation using an experimental test bed shows that the proposed signalling mechanism does not increase the service downtime during hot migration. We also optimize the signalling method, where the same event can only be forwarded to a physical server once regardless of the hosted VMs, to reduce the management message overhead from O(n*m) to O(n).

In a loss less interconnection network, network congestion needs to be detected and resolved to ensure high performance and good utilization of network resources at high network load. If no countermeasure is taken, congestion at a node in the network will stimulate the growth of a congestion tree that not only affects contributors to congestion, but also other traffic flows in the network. Left untouched, the congestion tree will block traffic flows, lead to underutilization of network resources and result in a severe drop in network performance. The InfiniBand standard specifies a congestion control (CC) mechanism to detect and resolve congestion before a congestion tree is able to grow and, by that, hamper the network performance. The InfiniBand CC mechanism includes a rich set of parameters that can be tuned in order to achieve effective CC. Even though it has been shown that the CC mechanism, properly tuned, is able to improve both throughput and fairness in an interconnection network, it has been questioned whether the mechanism is fast enough to keep up with dynamic network traffic, and if a given set of parameter values for a topology is robust when it comes to different traffic patterns, or if the parameters need to be tuned depending on the applications in use. In this paper we address both these questions. Using the three-stage fat-tree topology from the Sun Data center InfiniBand Switch 648 as a basis, and a simulator tuned against CC capable InfiniBand hardware, we conduct a systematic study of the efficiency of the InfiniBand CC mechanism as the network traffic becomes increasingly more dynamic. Our studies show that the InfiniBand CC, even when using a single set of parameter values, performs very well as the traffic patterns becomes increasingly more dynamic, outperforming a network without CC in all cases. Our results show throughput increases varying from a few percent, to a seventeen-fold increase.

Most standard cluster interconnect technologies are flexible with respect to network topology. This has spawned a substantial amount of research on topology-agnostic routing algorithms, which make no assumption about the network structure, thus providing the flexibility needed to route on irregular networks. Actually, such an irregularity should be often interpreted as minor modifications of some regular interconnection pattern, such as those induced by faults. In fact, topology-agnostic routing algorithms are also becoming increasingly useful for networks on chip (NoCs), where faults may make the preferred 2D mesh topology irregular. Existing topology-agnostic routing algorithms were developed for varying purposes, giving them different and not always comparable properties. Details are scattered among many papers, each with distinct conditions, making comparison difficult. This paper presents a comprehensive overview of the known topology-agnostic routing algorithms. We classify these algorithms by their most important properties, and evaluate them consistently. This provides significant insight into the algorithms and their appropriateness for different on- and off-chip environments.

In loss less interconnection networks such as InfiniBand, congestion control (CC) can be an effective mechanism to achieve high performance and good utilization of network resources. The InfiniBand standard describes CC functionality for detecting and resolving congestion, but the design decisions on how to implement this functionallity is left to the hardware designer. One must be cautious when making these design decisions not to introduce fairness problems, as our study shows. In this paper we study the relationship between congestion control, switch arbitration, and fairness. Specifically, we look at fairness among different traffic flows arriving at a hot spot switch on different input ports, as CC is turned on. In addition we study the fairness among traffic flows at a switch where some flows are exclusive users of their input ports while other flows are sharing an input port (the parking lot problem). Our results show that the implementation of congestion control in a switch is vulnerable to unfairness if care is not taken. In detail, we found that a threshold hysteresis of more than one MTU is needed to resolve arbitration unfairness. Furthermore, to fully solve the parking lot problem, proper configuration of the CC parameters are required.

Existing congestion control mechanisms in interconnects can be divided into two general approaches. One is to throttle traffic injection at the sources that contribute to congestion, and the other is to isolate the congested traffic in specially designated resources. These two approaches have different, but non-overlapping weaknesses. In this paper we present in detail a method that combines injection throttling and congested-flow isolation. Through simulation studies we first demonstrate the respective flaws of the injection throttling and of flow isolation. Thereafter we show that our combined method extracts the best of both approaches in the sense that it gives fast reaction to congestion, it is scalable and it has good fairness properties with respect to the congested flows.

It is a well known fact that multiple virtual lanes can improve performance in interconnection networks, but this knowledge has had little impact on real clusters. Currently, a large number of clusters using InfiniBand is based on fat-tree topologies that can be routed deadlock-free using only one virtual lane. Consequently, all the remaining virtual lanes are left unused. In this paper we suggest an enhancement to the fat-tree algorithm that utilizes virtual lanes to improve performance when hot-spots are present. Even though the bisection bandwidth in a fat-tree is constant, hot-spots are still possible and they will degrade performance for flows not contributing to them due to head-of-line blocking. Such a situation may be alleviated through adaptive routing or congestion control, however, these methods are not yet readily available in InfiniBand technology. To remedy this problem, we have implemented an enhanced fat-tree algorithm in OpenSM that distributes traffic across all available virtual lanes without any configuration needed. We evaluated the performance of the algorithm on a small cluster and did a large-scale evaluation through simulations. In a congested environment, results show that we are able to achieve throughput increases up to 38% on a small cluster and from 221% to 757% depending on the hot-spot scenario for a 648-port simulated cluster.

Fat trees are a very common communication architecture in current large-scale parallel computers. The probability of failure in these systems increases with the number of components. We present a routing method for deterministically and adaptively routed fat trees, applicable to both distributed and source routing, that is able to handle several concurrent faults and that transparently returns to the original routing strategy once the faulty components have recovered. The method is local and dynamic, completely masking the fault from the rest of the system. It only requires a small extra functionality in the switches to handle rerouting packets around a fault. The method guarantees connectedness and deadlock and livelock freedom for up to k -1 benign simultaneous switch and/or link faults where k is half the number of ports in the switches. Our simulation experiments show a graceful degradation of performance as more faults occur. Furthermore, we demonstrate that for most fault combinations, our method will even be able to handle significantly more faults beyond the k -1 limit with high probability.

Rerouting around faulty components and migration of jobs both require reconfiguration of data structures in the Queue Pairs residing in the hosts on an InfiniBand cluster. In this paper we report an implementation of dynamic reconfiguration of such host side data-structures. Our implementation preserves the Queue Pairs, and lets the application run without being interrupted. With this implementation, we demonstrate a complete solution to fault tolerance in an InfiniBand network, where dynamic network reconfiguration to a topology-agnostic routing function is used to avoid malfunctioning components. This solution is in principle able to let applications run uninterruptedly on the cluster, as long as the topology is physically connected. Through measurements on our test-cluster we show that the increased cost of our method in setup latency is negligible, and that there is only a minor reduction in throughput during reconfiguration.

The fat-tree topology has become a popular choice for InfiniBand fabrics due to its inherent deadlock freedom, fault-tolerance and full bisection bandwidth. InfiniBand is used by more than 40% of the systems on the latest Top 500 list, and many of these systems are based on a fat-tree topology. However, the current InfiniBand fat-tree routing algorithm suffers from flaws that reduce its scalability and flexibility. Counter-intuitively, the achievable throughput per node deteriorates both when the number of nodes in a tree decreases or when the node distribution among leaves is nonuniform. In this paper, we identify the weaknesses of the current enhanced fat-tree routing algorithm in Open Fabrics Enterprise Distribution and we propose extensions to it that alleviate all performance problems related to node distribution. The new algorithm is implemented in OpenSM for real world evaluation and for future contribution to the Open Fabrics community. We demonstrate that our solution allows to achieve a predictable high throughput regardless of the number of nodes and their distribution. Furthermore, the simulations show that our extensions improve throughput up to 30% depending on topology size and node distribution.

In lossless interconnection networks congestion control (CC) can be an effective mechanism to achieve high performance and good utilization of network resources. Without CC, congestion in one node may grow into a congestion tree that can degrade the performance severely. This degradation can affect not only contributors to the congestion, but also throttles innocent traffic flows in the network. The InfiniBand standard describes CC functionality for detecting and resolving congestion. The InfiniBand CC concept is rich in the way that it specifies a set of parameters that can be tuned in order to achieve effective CC. There is, however, limited experience with the InfiniBand CC mechanism. To the best of our knowledge, only a few simulation studies exist. Recently, InfiniBand CC has been implemented in hardware, and in this paper we present the first experiences with such equipment. We show that the implemented InfiniBand CC mechanism effectively resolves congestion and improves fairness by solving the parking lot problem, if the CC parameters are appropriately set. By conducting extensive testing on a selection of the CC parameters, we have explored the parameter space and found a subset of parameter values that leads to efficient CC for our test scenarios. Furthermore, we show that the InfiniBand CC increases the performance of the well known HPC Challenge benchmark in a congested network.

Abstract In cognitive radio (CR) networks, medium access control (MAC) protocols play an important role to exploit the spectrum opportunities, manage the interference to primary users (PUs), and coordinate the spectrum access amongst secondary users (SUs). In this paper, we first introduce the challenges in the design and implementation of CR MAC protocols. Then, we make a comprehensive survey of the state‐of‐the‐art CR MAC protocols and categorize them on the basis of spectrum sharing modes, i.e., overlay and underlay modes. We also introduce some other classification metrics such as architecture (centralized or distributed), sharing behaviors (cooperative or non‐cooperative), and access modes (contention based or contention free). Through the study, we find out that most CR MAC protocols are designed for the overlay mode. The CR MAC protocols in underlay mode could yield higher spectrum utilization efficiency with the cost of more complicated power and admission control schemes. The centralized CR MAC protocols are more suitable to do spectrum sensing using quiet period of whole network, while the distributed CR MAC protocols are more flexible to deploy. We identify several future directions, such as more practical CR MAC protocols for underlay mode, MAC protocols considering security, MAC protocols considering heterogeneous coexistence, etc. Copyright © 2009 John Wiley & Sons, Ltd.

An increasing number of research efforts on wireless sensor networks (WSNs) are now considering dynamic environments with heterogeneous sensor devices. Most of this research considers data, control, and management issues separately and not clearly within a common architecture. This paper presents our development of an architecture, namely DCM-Arch, to address these issues together. The architectureconsists of three-planes of functionalities (in the verticaldimension): 1) data, 2) control, and 3) management; and four-tiers of network infrastructures (in the horizontal dimension): 1) routing and network infrastructure, 2) logical network infrastructure, 3) adaptation middleware, and 4) component-based software application. The data plane handles the information storage, reduction, and dissemination in WSNs. The control plane deals with the lightweight sensor adaptation and reconfiguration middleware to cope with the dynamic changes of the environment. Finally, the management plane provides the context management functions, e.g. for collaboration and reasoning, to allow sensors, coordinators, and sinks to make good decisions about adaptation and reconfiguration. While the vertical dimension describes the functionalities of DCM-Arch, its four-tiers provide the required facilities to achieve those functionalities.

There is a large body of work addressing information storage, reduction, and dissemination in Wireless Sensor Networks (WSNs), but there seems to be no contribution giving a survey of this literature. In this paper we take on such a challenge and review previous WSN research and further presents a framework that we use for classifying the different proposed approaches and techniques. The framework is structured into 3 tiers: (1) routing and network infrastructure, (2) logical network infrastructure, and (3) information storage and processing. The paper, however, mainly focuses on tier-2 and tier-3. We also discuss future visions and challenges within the WSN community.

Computer architectures for high performance computing have traditionally been based on an assumption of one parallel application running alone on one machine. The current trend is, however, that huge computer installations offer compute power to a set of users or customers, each demanding only a subset of the available compute resources. This places new requirements on the architecture, in that it must support dynamic partitioning of the resources into several virtual servers as demand changes. We introduce a novel framework which supports flexible formation of such virtual servers while preventing interference between the communication of different virtual servers. This paper investigates the impacts of a shared interconnection network on applications running on virtual compute servers. We show that the interconnect performance supplied to each job is highly unpredictable, and that a job can experience a performance degradation of 97% when its traffic interferes with the traffic of concurrent jobs. With a minor reduction in the utilization of each processing node, this can be considerably improved through a combination of routing-containment in the interconnection network and a carefully designed resource allocation strategy.

Overlapping Reconfiguration is currently the most efficient method to reconfigure an interconnection network, but is only valid for systems that apply distributed routing. This paper proposes a solution which enables utilization of Overlapping Reconfiguration in a source routed environment. We demonstrate how a synchronized injection of tokens has a significant impact on the performance of the method. Furthermore, we propose and evaluate an optimization of the original algorithm that reduces (and in some cases even eliminates) performance issues caused by the token forwarding regime, such as increased latency and decreased throughput.

This paper addresses the problem of optimal cooperative spectrum sensing in a cognitive-enabled sensor network where cognitive sensors can cooperate in the sensing of the spectrum. Such sensor networks are assumed to be power resource constrained. With a given threshold for the accuracy of the spectrum detection, we find the optimal number of cognitive sensors participating in the cooperative spectrum sensing and the optimal sensing interval that minimize the total energy consumption of the cooperative sensing. First, the mathematical lower bound and upper bound for the number of cooperative cognitive sensors are found. Then the optimization problem to minimize the total energy consumed by a group of sensors is presented. Finally, an efficient approximate solution to the optimization problem is proposed. Numerical calculations validate the accuracy and the performance of the proposed scheme. The impact of the noise uncertainty, the choice of the energy detection threshold, and the spectrum bandwidth on the detection accuracy and the minimum total energy consumption is also studied.

Abstract In cognitive radio cellular networks (CogCell), the secondary users (SUs) are allowed to access the channels licensed to the primary users (PUs) including Primary Transmitters (PTs) and Primary Receivers (PRs), only if the interference to the PRs is less than the predefined threshold, and the quality of service (QoS) requirements of PTs are guaranteed. In addition, different SUs may require different levels of QoS, and pay differently depending on the provided QoS. The network operator achieves different secondary revenues by admitting SUs in different QoS levels. The problem we address in this paper is to maximize the total secondary revenue relative to the interference constraints on PRs, and QoS requirements for both PTs and SUs. We formulate this optimization problem, and propose a power control scheme for both PTs and SUs. Then, we introduce three solutions including an exact solution using dynamic programming, a greedy heuristic algorithm, and a minimal signal‐interference‐plus‐noise‐ratio (SINR) removal algorithm. Based on these algorithms, we propose three QoS aware admission and power control (QAPC) schemes, one optimal solution called QAPC‐dynamic, and two approximate solutions called QAPC‐greedy and QAPC‐minimal SINR removal algorithm (MSRA), respectively. Numerical results show that QAPC‐dynamic always achieves the highest secondary revenue while QAPC‐MSRA gives the lowest secondary revenue. Since the time complexity of QAPC‐dynamic is much higher than the other two schemes, QAPC‐greedy is recommended considering the trade‐off between the computation complexity and performance gain. Copyright © 2009 John Wiley & Sons, Ltd.

As the end of Moores-law is on the horizon, power becomes a limiting factor to continuous increases in performance gains for single-core processors. Processor engineers have shifted to the multicore paradigm and many-core processors are a reality. Within the context of these multi-core chips, three key metrics point themselves out as being of major importance, performance, fault-tolerance (including yield), and power consumption. A solution that optimizes all three of these metrics is challenging. As the number of cores increases the importance of the interconnection network-on-chip (NoC) grows as well, and chip designers should aim to optimize these three key metrics in the NoC context as well. In this paper we identify and discuss the main properties that a NoC must exhibit in order to enable such optimizations. In particular, we propose the use of virtualization techniques at the NoC level. AS a major finding, we identify the implementation of routing algorithms to become a key design parameter in order to achieve an effective virtualization of the chip should also supporting broadcast within the virtualized context. The intention behind this paper is for it to serve as a position paper on the topic of virtualization for NoC and the challenges that should be met at the routing layer in order to maximize performance, fault-tolerance and power consumption in multicore chips.

The manufacturing process of modern day processors is both costly and complex and there are many different factors that influence the quality of a chip when it comes off the production line. Typically, hundreds of chips are manufactured from a single silicon wafer and as we go deeper into the sub-micron era of microchip manufacturing, the potential for defects during production increases. The advent of multi-core computing may introduce problems related to connectivity and yield for high volume manufacturing (HVM). In this paper we explore potential benefits that fault tolerant routing provides within the NoC (network-on-chip) paradigm with a study of the relationship between connectivity and yield at the interconnect routing level. For dimension-order routing based mesh NoCs, we describe two methods that are logically straightforward to implement and that can be used to increase the yield of chips with interconnect router faults.

In a cognitive radio wireless network, each node can sense and opportunistically access the under-utilized spectrums in the primary system. Since the unoccupied spectrum is location-dependent and time-dependent, the available spectrums in each node are different. With this spectrum heterogeneity and different Quality-of-Service (QoS) requirement, different nodes may have different preferences in using a particular channel to communicate with its neighboring nodes. In this paper, we formulate this channel selection problem using a cooperative game theoretical approach such that the QoS requirement of each node is guaranteed and the network capacity is maximized. To further improve the performance, a learning negotiation mechanism is introduced. The key motivation is to derive new mixed strategies of the nodes with the reference to the historical profiles of all selected strategies in the past. Simulation results are presented to show the fast convergence of the game, the high efficiency of the learning mechanism, and the effect of mobility.

The paper first gives an overview of the required functions for providing Internet connectivity and mobility management for mobile ad-hoc networks (MANETs). Internet gateway selection is one of these functions. Since multiple Internet gateways might exist on the same MANET domain, a hybrid metric for Internet gateway selection is proposed as a replacement of the shortest hop-count metric. The hybrid metric provides load-balancing of intra/inter-MANET traffic. Simulation results show that ad-hoc routing protocols, using our proposed metric get better performance in terms of packet delivery ratio and transmission delay, at the cost of slightly increased signalling overhead.

Component failures and planned component replacements cause changes in the topology and routing paths supplied by the interconnection network of a parallel processor system over time. Such changes may require the network to be reconfigured such that the existing routing function is replaced by one that enables packets to reach their intended destinations amid the changes. Efficient reconfiguration methods are desired which allow the network to function uninterruptedly over the course of the reconfiguration process while remaining free from deadlocking behavior. In this paper, we propose, evaluate, and prove the deadlock freedom of a new network reconfiguration protocol that overlaps various phases of "static" reconfiguration processes traditionally used in commercial and research systems to provide performance efficiency on par with that of recently proposed "dynamic" reconfiguration processes but without their complexity. Simulation results show that the proposed Overlapping Static Reconfiguration protocol can reduce reconfiguration time by up to 50 percent, reduce packet latency by several orders of magnitude, reduce packet dropping by an order of magnitude, and provide unhalted packet injection as compared to traditional static reconfiguration while allowing network throughput similar to dynamic reconfiguration.

Ethernet's native routing algorithm, the spanning tree protocol, causes a major performance bottleneck when network connectivity increases. Since the spanning tree protocol avoids deadlocks and infinitely looping packets by turning any topology into a tree, it leaves a large portion of links unused and thus wastes bandwidth. In this paper we address this weakness by proposing a new routing algorithm that avoids disabling links and prohibiting turns, and that guarantees shortest path routing. Through the use oflayeredroutingwe show how to improve performance with respect to both the spanning tree protocol and a more recent proposal called tree-based turn-prohibition. The concept of layered routing is used to group virtual channels into network layers, and assign a limited set of source/destination address pairs to each layer. Extensive simulations show that we are able to increase throughput by a factor of more than 3.5 compared to the spanning tree protocol and a factor of 1.8 compared to tree-based turn-prohibition. Our concept relies on features introduced in IEEE standards 802.1Q, 802.1D and 802.3x, as well as changes currently discussed in IEEE task forces.

This paper presents a unique approach for a model-based admission control algorithm for the IEEE 802.11e enhanced distributed channel access (EDCA) standard. The analytical model used as the foundation for the algorithm covers both nonsaturation and saturation conditions. This allows us to keep the system out of saturation by monitoring several variables. Since the medium access delay represents the service time of the system, it is used as the threshold condition to ensure that the queuing delay is within reasonable bounds. The paper describes the admission control algorithm and several simulation results are presented and discussed.

Fixed WiMAX is being deployed worldwide, and the networks are increasing in size. Measurements have been performed, but the amount of measurements are few and do therefore not demonstrate performance in a real life deployment. We have performed extensive analyses of the physical performance in a fixed WiMAX deployment which has been operative for a year and where the amount of subscribers constantly increases. The analyses presented in this paper focus on received signal strength and signal to noise ratio. Based on the measured parameters, we present a Path Loss model for fixed WiMAX which will hopefully be of great reference value due to the amount of measurements presented. Finally, our Path Loss model is compared to other well known Path Loss models and is found to approach the free space loss model.

Ethernet is turning out to be a cost-effective solution for building cluster networks offering compatibility, simplicity, high bandwidth, scalability and a good performance-to-cost ratio. Nevertheless, Ethernet still makes inefficient use of network resources (links) and suffers from long failure recovery time due to the lack of a suitable routing algorithm. In this paper we embed an efficient routing algorithm into 802.3 Ethernet technology, making it possible to use off-the-shelf equipment to build high-performance and cost-effective Ethernet clusters, with an efficient use of link bandwidth and with fault tolerant capabilities. The algorithm, referred to as segment-based routing (SR), is a deterministic routing algorithm that achieves high performance without the need for virtual channels (not available in Ethernet). Moreover, SR is topology agnostic, meaning it can be applied to any topology, and tolerates any combination of faults derived from the original topology when combined with static reconfiguration. Through simulations we verify an overall improvement in throughput by a factor of 1.2 to 10.0 when compared to the conventional Ethernet routing algorithm, the spanning tree protocol (STP), and other topology agnostic routing algorithms such as Up*/Down* and tree-based turn-prohibition, the last one being recently proposed for Ethernet

Fault tolerance is critical for efficient utilisation of large computer systems. Dynamic fault tolerance allows the network to remain available through the occurance of faults as opposed to static fault tolerance which requires the network to be halted to reconfigure it. Although dynamic fault tolerance may lead to less efficient solutions than static fault tolerance, it allows for a much higher availability of the system. In this paper we devise a dynamic fault tolerant adaptive routing algorithm for the fat tree, a much used interconnect topology, which relies on misrouting around link faults. We show that we are guaranteed to tolerate any combination of less than (num_switch_ports)/2 link faults without the need for additional network resources for deadlock freedom. There is also a high probability of tolerating an even larger number of link faults. Simulation results show that network performance degrades very little when faults are dynamically tolerated

Computers get faster every year, but the demand for computing resources seems to grow at an even faster rate. Depending on the problem domain, this demand for more power can be satisfied by either, massively parallel computers, or clusters of computers. Common for both approaches is the dependence on high performance interconnect networks such as Myrinet, Infiniband, or 10 Gigabit Ethernet. While high throughput and low latency are key features of interconnection networks, the issue of fault-tolerance is now becoming increasingly important. As the number of network components grows so does the probability for failure, thus it becomes important to also consider the fault-tolerance mechanism of interconnection networks. The main challenge then lies in combining performance and fault-tolerance, while still keeping cost and complexity low. This paper proposes a new deterministic routing methodology for tori and meshes, which achieves high performance without the use of virtual channels. Furthermore, it is topology agnostic in nature, meaning it can handle any topology derived from any combination of faults when combined with static reconfiguration. The algorithm, referred to as segment-based routing (SR), works by partitioning a topology into subnets, and subnets into segments. This allows us to place bidirectional turn restrictions locally within a segment. As segments are independent, we gain the freedom to place turn restrictions within a segment independently from other segments. This results in a larger degree of freedom when placing turn restrictions compared to other routing strategies. In this paper a way to compute segment-based routing tables is presented and applied to meshes and tori. Evaluation results show that SR increases performance by a factor of 1.8 over FX and up*/down* routing

An increasing amount of interconnect technologies rely on source routing to forward packets through the network. It is therefore important to develop methods for fault tolerance that are well suited for source routed networks. Dynamic fault tolerance allows the network to remain available through the occurrence of faults, as opposed to static fault tolerance which requires the network to be halted to reconfigure it. Source routing readily supports the source node choosing a different path when a fault occurs, but using this approach, packets already in the network will be lost. Local dynamic fault tolerance, where the packet is routed around the fault locally, would prevent much of the traffic being lost during failures, but this is cumbersome to achieve in source routed networks since packets encountering a fault will need to follow a path different from that encoded in the packet header. In this paper we present a mechanism to achieve local dynamic fault tolerance in source routed fat trees, a topology that has widespread use in supercomputer systems, and compare it with endpoint dynamic fault tolerance. We also show that by combining the two approaches we achieve performance superior to any of the two individually

Massively parallel computing systems are being built with thousands of nodes. The interconnection network plays a key role for the performance of such systems. However, the high number of components significantly increases the probability of failure. Additionally, failures in the interconnection network may isolate a large fraction of the machine. It is therefore critical to provide an efficient fault-tolerant mechanism to keep the system running, even in the presence of faults. This paper presents a new fault-tolerant routing methodology that does not degrade performance in the absence of faults and tolerates a reasonably large number of faults without disabling any healthy node. In order to avoid faults, for some source-destination pairs, packets are first sent to an intermediate node and then from this node to the destination node. Fully adaptive routing is used along both subpaths. The methodology assumes a static fault model and the use of a checkpoint/restart mechanism. However, there are scenarios where the faults cannot be avoided solely by using an intermediate node. Thus, we also provide some extensions to the methodology. Specifically, we propose disabling adaptive routing and/or using misrouting on a per-packet basis. We also propose the use of more than one intermediate node for some paths. The proposed fault-tolerant routing methodology is extensively evaluated in terms of fault tolerance, complexity, and performance.

Through several giant evolutionary steps, Ethernet has become an almost ubiquitous technology for communication. Being versatile enough to be employed in new and various fields of application, it is now making inroads in factories. However, automated systems are different from many other applications of Ethernet,first and foremost because they require the network technology to deliver real-time performance. In the present study, a number of critical aspects of Ethernet, usually referred to as an Industrial Ethernet, are examined. More specifically, there is a focus on the application-to-application delay and jitter characteristics of such networks, when using Internet protocols such as UDP and TCP. It is demonstrated how important it is to take control of the latency in the station nodes, since the main communication delays occur inside the nodes, and different solutions are presented for controlling these delays. In particular, a priority-based protocol stack is assessed. The results show that real-time, Ethernet-based IP communication is now adequate even for demanding automated applications. In this paper, substation automation (power distribution) is used as an example of a demanding automation system.

Freedom from deadlock is a key issue in cut-through, wormhole, and store and forward networks, and such freedom is usually obtained through careful design of the routing algorithm. Most existing deadlock-free routing methods for irregular topologies do, however, impose severe limitations on the available routing paths. We present a method called layered routing, which gives rise to a series of routing algorithms, some of which perform considerably better than previous ones. Our method groups virtual channels into network layers and to each layer it assigns a limited set of source/destination address pairs. This separation of traffic yields a significant increase in routing efficiency. We show how the method can be used to improve the performance of irregular networks, both through load balancing and by guaranteeing shortest-path routing. The method is simple to implement, and its application does not require any features in the switches other than the existence of a modest number of virtual channels. The performance of the approach is evaluated through extensive experiments within three classes of technologies. These experiments reveal a need for virtual channels as well as an improvement in throughput for each technology class.

Current massively parallel computing systems are being built with thousands of nodes, which significantly affect the probability of failure. M. E. Gomex proposed a methodology to design fault-tolerant routing algorithms for direct interconnection networks. The methodology uses a simple mechanism: for some source-destination pairs, packets are first forwarded to an intermediate node, and later, from this node to the destination node. Minimal adaptive routing is used along both subpaths. For those cases where the methodology cannot find a suitable intermediate node, it combines the use of intermediate nodes with two additional mechanisms: disabling adaptive routing and using misrouting on a per-packet basis. While the combination of these three mechanisms tolerates a large number of faults, each one requires adding some hardware support in the network and also introduces some overhead. In this paper, we perform an in-depth detailed analysis of the impact of these mechanisms on network behaviour. We analyze the impact of the three mechanisms separately and combined. The ultimate goal of this paper is to obtain a suitable combination of mechanisms that is able to meet the trade-off between fault-tolerance degree, routing complexity, and performance.

In the automation world the intelligent electrical devices need to be accurately synchronized for time stamping of data and motion control. We discuss how to achieve precise time synchronization over switched Ethernet networks in a generic way. The addressed synchronization requirements relate to substation automation, which is associated with five levels of synchronization accuracy defined as the IEC 61850 classes T1 to T5. The paper challenges the hardest requirements and presents general solutions for IEC classes T4/T5 (4 /spl mu/s/1 /spl mu/s) and IEC class 3 (25 /spl mu/s) in multi-traffic LAN environments. The classes T4/T5 solution is based on an Ethernet switch from OnTime Networks, while the class T3 solution relies on standard Ethernet switches. Common for both solutions is that they adhere to a low-level time stamp implementation of the Simple Network Time Protocol.