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 sub-parts 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.

InfiniBand (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.

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.

Efficient CMP utilisation requires virtualisation. This forces multiple applications to contend for the same network resources and memory bandwidth. In this paper we study the cause and effect of network congestion with respect to traffic local to the applications, and traffic caused by memory access. This reveals that applications close to the memory controller suffer because of congestion caused by memory controller traffic from other applications. We present a simple mechanism to reduce head-of-line blocking in the switches, which efficiently reduces network congestion, increases network performance, and evens out the performance differences between the CMP applications.

End-point hotspots can cause major slowdowns in interconnection networks due to head-of-line blocking and congestion. Therefore, avoiding congestion is important to ensure high performance for the network traffic. It is especially important in situations where permanent congestion, which results in permanent slowdown, can occur. Permanent congestion occurs when traffic has been moved away from a failed link, when multiple jobs run on the same system, and compete for network resources, or when a system is not balanced for the application that runs on it. In this paper we suggest a mechanism for dynamic allocation of virtual lanes and live optimisation of the distribution of flows between the allocated virtual lanes. The purpose is to alleviate the negative effect of permanent congestion by separating network flows into slow lane and fast lane traffic. Flows destined for an end-point hot-spot is placed in the slow lane and all other flows are placed in the fast lane. Consequently, the flows in the fast lane are unaffected by the head-of-line blocking created by the hot-spot traffic. We demonstrate the feasbility of this approach using a modified version of OFED and OpenSM with fat-tree routing on a small InfiniBand cluster. Our experiments show an increase in throughput ranging from 150% to 468% compared to the conventional fat-tree algorithm in OFED.

Many-core chip design requires flexible routing solutions for the interconnect to handle faults, provide performance partitions, and react to dynamic changes in processing requirements and power/heat distribution. We have developed a logic based rerouting mechanism suitable for tolerating dynamic powering down of regions within the application partition on the chip. This mechanism is combined with the logic based FDOR routing algorithm to create a powerful routing algorithm with low implementation cost. This allows for higher system utilisation through enabling more efficient power management as well as supporting many irregular mesh topologies through flexible virtualisation. Results show that powering down a single switch results in an 8% throughput reduction in the worst case for the evaluated topology.

Admission and power control schemes play important roles in deploying cognitive radio technology to cellular networks. In this paper, we propose a method to calculate the power scale factor, introduce two pre-admission control schemes, and reformulate the problem as a multidimensional knapsack problem. In addition, we propose a novel admission and power control scheme called JAPC-MKP. Simulation results show that our proposed JAPC-MKP can very closely approach the optimal results from the optimization software MOSEK, and greatly outperform the existing schemes in most cases.

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 on one link 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.

Ethernet is about to enter the domain of data center and high performance computing by introducing several performance optimizations that will close the performance and functionality gap between Ethernet and its fiercest competitioner InfiniBand. Through the Data Center Bridging Task Group the IEEE is about to expand the 802.1 standard with four new supplements that will both close the performance gap and make the converged network a reality. In a converged network all applications use a single physical infrastructure, e.g. Ethernet or InfiniBand. This is ideal for the next generation of data centers that are now emerging. In this paper we discuss the architectural challenges faced by Ethernet in order to improve performance and make the converged network a reality, and we present the Ethernet enhancements currently being standardized by the IEEE.

Femtocell is envisioned as a highly promising solution to tackle the communications in the indoor environments, which has been a very challenging problem for mobile network operators. Currently, the spectrum allocated to femtocells is from the same licensed spectrum of macrocells, and the same mobile network operator. In this case, the capacity of femtocell networks may be largely limited due to the finite number of licensed spectrum bands and also the interference with other femtocells and macrocells. In this paper, we propose a radically new communications paradigm by incorporating cognitive radio in femtocell networks (COGFEM). In COGFEM, the cognitive radio enabled femtocells are able to access licensed spectrum bands not only from macrocells but also from other licensed systems (e.g. TV systems). Thus, the co-channel interference in femtocells can be greatly reduced and the network capacity can be significantly improved. We formulate a joint channel allocation and power control problem in COGFEM, and present two intelligent algorithms for efficient spectrum sharing in COGFEM. Results indicate that COGFEM is able to achieve much higher capacity than the femtocell networks which does not employ agile spectrum access.

The expected increase in number of cores on a single chip leads to the necessity of high-performance on chip interconnects (NoC). Furthermore, in order to fully utilize the abundance of cores, the chip is expected to support a number of applications running on the chip simultaneously. It is therefore necessary to partition the chip to support numerous applications without any risk of interference between them. The success of this depends on the flexibility of the underlying routing algorithm. This paper presents a flexible routing algorithm based on dimension ordered routing, which supports a large variety of irregular (2-D and 3-D) mesh topologies. The algorithm provides high efficiency at very low additional complexity, as is confirmed by experimental results.

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 which enables packets to reach their intended destinations amid the changes. Efficient reconfiguration methods are desired that 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 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%, 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.

In cognitive radio cellular networks (CogCell), the Secondary Users (SUs) can be admitted to the Base Station (BS) provided that the interference caused by SUs to the Primary Users (PUs) is no higher than the pre-defined threshold. In addition, different SUs may require different Quality of Service (QoS) and hence make different payment based on the provided QoS level. In this paper, we investigate the maximally achievable revenue obtained from SUs subjected to the interference constraints on PUs and QoS requirements of SUs. To solve the identified issue, we introduce the revenue efficiency factor and propose an efficient Joint Admission and Power Control scheme using a Minimal Revenue Efficiency Removal algorithm (JAPC-MRER). With comparison to the other two schemes JAPC-MSRA and JAPC-Random, our strategy is able to achieve much higher revenue with guaranteed interference requirements and QoS demands. In addition, the proposed scheme is evaluated with the effects of the key parameters, i.e. the number of PUs, the number of SUs and the interference threshold.

As the end of Moores-law is on the horizon, power becomes a limiting factor to the continuous increases in performance gains for single-core processors. Processor engineers have shifted to the multicore paradigm and many-core processors are reality. Within the context of these multi-core, 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 metric 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 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. The implementation of routing algorithms for NoC is a key design parameter in order to achieve an effective virtualization of the chip that should also support broadcast within the virtualized context. The intention behind this paper is for it to serve 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.

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 non-saturation 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.

In this paper we embed an efficient topology agnostic routing algorithm with fault tolerance capabilities into back-pressured Ethernet technology. This makes it possible to use off-the-shelf equipment to build cost-effective systems with an efficient use of all network components. This stands in contrast to the inefficient use of network resources (links) supported by the Spanning Tree Protocol (STP). The Segment-Based Routing Algorithm (SR) is a deterministic routing algorithm that achieves high performance without the use of virtual channels. Furthermore, it is topology agnostic, meaning it can handle any topology and 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 compared to the conventional Ethernet routing algorithm, the STP, and other topology agnostic routing algorithms such as Up*/Down* and Tree-based Turn-prohibition, which both are applicable to Ethernet.

Mobile WiMAX is a promising wireless technology approaching market deployment. Much discussion concentrate on whether mobile WiMAX will reach a tipping point and become 4G or not. As a pre-mobile WiMAX system is being delivered, we decided to set up a real life field trial and perform the most important measurements over the system setup. The system was delivered with 4th order diversity. In this paper we analyze physical system performance based on field trial measurements, especially at locations with non line of sight conditions in urban areas. We investigate the gain with 2nd and 4th order base station diversity and derive analytical expressions. The system path loss is plotted and found to approach the Cost-231 Hata model for urban areas. Throughput is also measured and analyzed. Sub-channelization in the uplink points out to be an important feature for enhanced coverage.

An increasing amount of current and emerging 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.

This paper investigates rate configuration of the Expedited Forwarding (EF) class of Differentiated Services (DiffServ) when used with 802.11e EDCA. The rate configuration problem is presented, and several approaches are tested and evaluated in order to solve the problem. Results reveal that the contention window makes rate configuration very hard for the highest priority class (AC\_VO) in 802.11e EDCA. Our evaluations show that 802.11e EDCA is not able to conform to DiffServ's EF PHB specifications.

A recent trend in interconnection network technologies is the inclusion of various mechanisms to support a variety of Quality of Service concepts. This has been necessitated by an increasing number of application areas that require some level of performance guarantees from the network for parts of its traffic. In this paper we describe and compare the capabilities and support for Quality of Service of the three most important interconnection network technology standards of today. Equalities between the technologies are explained and differences are clarified.

The way conventional Ethernet is used today differs in two aspects from how dedicated system area networks are used. Firstly, dedicated system area networks are lossless and only drop frames when bit errors occur, while conventional Ethernet drop frames whenever congestion occur. Secondly, these networks are either deadlock free or use mechanisms which avoids deadlock situations, while still using all available links. Ethernet avoids deadlocks by using a spanning tree protocol which turns any topology into a tree. A drawback of this approach is that we are left with a lot of unused links and thus wasting resources. In this paper we describe how to obtain a lossless deadlock free network with the best possible performance, while adhering to the current Ethernet standard and using off-the-shelf Ethernet equipment. We achieve this by introducing flow control in all network nodes and by taking control over the routing algorithm. Also, we use TCP to illustrate the effect of flow control on higher layer protocols. Through simulations we verify the following tree improvements. Firstly, the activation of flow control turns Ethernet into a lossless network. Secondly, taking control over the routing algorithm allows us to build any topology without the limitations of the spanning tree protocol. And thirdly, an overall improvement in throughput is achieved by combining these enhancements.

Interconnection networks play a key role in the fault tolerance of massively parallel computers, since faults may isolate a large fraction of the machine containing many healthy nodes. In this paper, we present a methodology to design fully adaptive fault-tolerant routing algorithms for direct interconnection networks that can be applied to different regular topologies. The methodology is mainly based on the selection of an intermediate node (if needed) for each source-destination pair. Packets are adaptively routed to the intermediate node and, from this node, they are adaptively forwarded to their destination. This methodology requires only one additional virtual channel, even for tori. Evaluation results show that the methodology is 7-fault tolerant, and for up to 14 faults, more than 99% of the combinations are tolerated, also without significantly degrading performance in the presence of faults.

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.

Previous work on Quality of Service in Cut-through networks shows that resource reservation mechanisms are only effective below the saturation point. Admission control in these networks will therefore need to keep network utilization below the saturation point, while still utilising the network resources to the maximum extent possible. In this paper we propose and evaluate three admission control schemes. Two of these use a centralised bandwidth broker, while the third is a distributed measurement based approach. We combine these admission control schemes with a DiffServ based QoS scheme for virtual cut-through networks to achieve class based bandwidth and latency guarantees. Our simulations show that the measurement based approach favoured in the Internet communities performs poorly in cut-through networks. Furthermore it demonstrates that detailed knowledge on link utilization improves performance significantly.

The article covers methods for service discovery in multi hop Bluetooth ad hoc networks, so called scatternets. A service discovery algorithm is presented that can be used to extend the Bluetooth Service Discovery Protocol to the scatternet without the use of broadcast messages. Extensive simulation results are presented showing that significant reductions in the number of messages sent are achieved compared to using a broadcast approach. Avoiding network flooding and reducing the number of messages is important as many Bluetooth devices have limited power sources and therefore benefit from keeping links idle in power saving modes.