Data center network architecture is driven by the economics of reach. Although electrical interconnect remains the most cost-effective solution for short-reach communication, its reach has shrunk considerably as signalling rates have increased, and is set to shrink further. Correspondingly, the crossover point between electrical and optical links continues to move to shorter distances as well. At the same time, silicon photonics technology is enabling integration of optical I/O with analog and digital electronics within the same package, drastically reducing the cost differential between optical I/O and electrical I/O. The coincidence of these two trends is set to cause a “perfect storm” in datacenter network architecture that will invalidate existing assumptions and require re-evaluation of prevalent architectural best practices. We first review how reach has shaped datacenter networks, introduce the requisite technology platform that enables in-package optics, and discuss the potentially disruptive implications this has on datacenter network architecture. We show how in-package optics gives rise to a repartitioning of chassis switch architecture to reduce cost and power, overcomes the reach limitation of DAC cables and backplane traces in favor of direct fiber connectivity, and enables much greater topological freedom.

Deadlock avoidance mechanisms for lossless lowdistance networks typically increase the order of virtual channel (VC) index with each hop. This restricts the number of buffer resources depending on the routing mechanism and limits performance due to an inefficient use. Dynamic buffer organizations increase implementation complexity and only provide small gains in this context because a significant amount of buffering needs to be allocated statically to avoid congestion. We introduce FlexVC, a simple buffer management mechanism which permits a more flexible use of VCs. It combines statically partitioned buffers, opportunistic routing and a relaxed distancebased deadlock avoidance policy. FlexVC mitigates Head-of-Line blocking and reduces up to 50% the memory requirements. Simulation results in a Dragonfly network show congestion reduction and up to 37.8% throughput improvement, outperforming more complex dynamic approaches. FlexVC merges different flows of traffic in the same buffers, which in some cases makes more difficult to identify the traffic pattern in order to support nonminimal adaptive routing. An alternative denoted FlexVCminCred improves congestion sensing for adaptive routing by tracking separately packets routed minimally and nonminimally, rising throughput up to 20.4% with 25% savings in buffer area.

Summary The Graph500 benchmark attempts to steer the design of High‐Performance Computing systems to maximize the performance under memory‐constricted application workloads. A realistic simulation of such benchmarks for architectural research is challenging due to size and detail limitations. By contrast, synthetic traffic workloads constitute one of the least resource‐consuming methods to evaluate the performance. In this work, we provide a simulation tool for network architects that need to evaluate the suitability of their interconnect for BigData applications. Our development is a low computation‐ and memory‐demanding synthetic traffic model that emulates the behavior of the Graph500 communications and is publicly available in an open‐source network simulator. The characterization of network traffic is inferred from a profile of several executions of the benchmark with different input parameters. We verify the validity of the equations in our model against an execution of the benchmark with a different set of parameters. Furthermore, we identify the impact of the node computation capabilities and network characteristics in the execution time of the model in a Dragonfly network.

In today's datacenters handling big data and for exascale computers of tomorrow, there is a pressing need for high-radix switches to economically and efficiently unify the computing and storage resources that are dispersed across multiple racks. In this paper, we present SCOC, a switch architecture suitable for economical IC implementation that can efficiently replace crossbars for high-radix switch nodes. SCOC is a multi-stage bufferless network with O(N2/m) cost, where m is a design parameter, practically ranging between 4-16. We identify and resolve more than five fairness violations that are pertinent to hierarchical scheduling. Effectively, from a performance perspective, SCOC is indistinguishable from efficient flat crossbars. Computer simulations show that it competes well or even outperforms flat crossbars and hierarchical switches. We report data from our ASIC implementation at 32 nm of a SCOC 136×136 switch, with shallow buffers, connecting 25 Gb/s links. In this first incarnation, SCOC is used at the spines of a server-rack, fat-tree network. Internally, it runs at 9.9 Tb/s, thus offering a speedup of 1.45 ×, and provides a fall-through latency of just 61 ns.

Dragonfly topologies are one of the most promising interconnect designs for enabling large, potentially exascale compute systems, particularly those envisioned to accommodate workloads that are sensitive to system diameter and end-to-end latency. They are cost-effective designs with a very low diameter and close to optimal performance for workloads which induce a balanced load across the network. However, these benefits are balanced by a reduced path diversity, which leaves Dragonflies vulnerable to certain adversarial traffic patterns. The performance of such workloads can be significantly improved using indirect routing approaches. However, the indirect routing approach that is most commonly used today exhibits in turn significant vulnerability to a subset of these traffic patterns for reasons that have not been, up to now entirely, understood. In exploring this vulnerability, we manage to provide a theoretical justification, based on inherent properties of the Dragonfly topology, of why performance degrades. Furthermore, we manage to isolate what specifically in the structure of a traffic pattern makes it a worst case in this context, and thus we are able to characterize the precise workload subset that will experience poor performance. By building upon the understanding of the interaction that causes sub-optimal behavior, we then show how simple changes to either the routing strategy or the process to node assignment can bring performance back close to ideal levels. Finally, we not only provide a theoretical justification for our performance models, but also validate them via comprehensive simulation-based studies of systems with up to 16,512 nodes.

Adaptive routing is an efficient congestion avoidance mechanism for modern Data enter and HPC networks. Congestion detection traditionally relies on the occupancy of the router queues. However, this approach can hinder performance due to coarse-grain measurements with small buffers, and potential routing oscillations with large buffers. We introduce an alternative mechanism, labelled Contention-Based Adaptive Routing. Our mechanism adapts routing based on an estimation of "network contention", the simultaneity of traffic flows contending for a network port. Our system employs a set of counters which track the demand for each output port. This exploits path diversity thanks to earlier detection of adversarial traffic patterns, and decouples buffer size and queue occupancy from contention detection. We evaluate our mechanism in a Dragonfly network. Our evaluations show this mechanism achieves optimal latency under uniform traffic and similar to best previous routing mechanisms under adversarial patterns, with immediate adaptation to traffic pattern changes.

Interference of nearby jobs has been recently identified as the dominant reason for the high performance variability of parallel applications running on High Performance Computing (HPC) systems. Typically, HPC systems are dynamic with multiple jobs coming and leaving in an unpredictable fashion, sharing simultaneously the system interconnection network. In such environment contention for network resources is causing random stalls in the progress of application execution degrading application and system performance overall. Eliminating job interactions in their neighbourhoods is key for guaranteeing performance predictability of applications. In this paper we are proposing the concept of quiet neighbourhoods that significantly reduce job interactions. Quiet neighbourhoods are created by the system resource manager in two phases. First, multiple virtual network blocks are defined on the top of the physical network resources based on typical workload distributions. Second, newly arriving jobs are allocated in these virtual blocks based on their size.

HPC network topology design is currently shifting from high-performance, higher-cost Fat-Trees to more cost-effective architectures. Three diameter-two designs, the Slim Fly, Multi-Layer Full-Mesh, and Two-Level Orthogonal Fat-Tree excel in this, exhibiting a cost per endpoint of only 2 links and 3 router ports with lower end-to-end latency and higher scalability than traditional networks of the same total cost. However, other than for the Slim Fly, there is currently no clear understanding of the performance and routing of these emerging topologies. For each network, we discuss minimal, indirect random, and adaptive routing algorithms along with deadlock-avoidance mechanisms. Using these, we evaluate the performance of a series of representative workloads, from global uniform and worst-case traffic to the all-to-all and near-neighbor exchange patterns prevalent in HPC applications. We show that while all three topologies have similar performance, OFTs scale to twice as many endpoints at the same cost as the others.

The wide deployment of virtualization in datacenters catalyzes the emergence of virtual traffic that delivers the network demands between the physical network and the virtual machines hosting clients' services. Virtual traffic presents new opportunities for reducing physical network demands, as well as challenges of increasing management complexity. Given the plethora of prior art on virtualization technologies in datacenters, surprisingly little is still known about such virtual traffic, and its dependence on the physical network and virtual machines. This paper provides a multi-faceted analysis of the patterns and impacts of multiplexing the virtual traffic onto the physical network, particularly from the perspective of the network edge. We use a large collection of field data from production datacenters hosting a large number of diversified services from multiple enterprise tenants. Our first focus is on uncovering the temporal and spatial characteristics of the virtual and physical traffic, i.e., network demand growth and communication patterns, with special attention paid to the traffic of migrating virtual machines. The second focus is on characterizing the effect of network multiplexing in terms of communication locality, traffic load heterogeneity, and the dependency on CPU processing power at the edges of the network. Last but not least, we conduct a mirroring analysis on service QoS, defined by the service unavailability induced by network related issues, e.g., loads. We qualitatively and quantitatively discuss the implications and opportunities that virtual traffic presents for network capacity planning of virtualized networks and datacenters.

Converged Enhanced Ethernet (CEE) is a crucial step in embracing storage, cluster, and high-performance computing fabrics under a common network. However, the adoption of lossless CEE in virtualized clusters is hindered by the lack of network hypervisor software that addresses the major issues of losslessness, i.e., head-of-line blocking and saturation trees. Our objective is to design a hypervisor that prevents miscon-figured or malicious virtual machines from filling the lossless network with stalled packets, thus compromising tenant isolation. Furthermore, we observe that current hypervisors perform compulsory isolation, management, and mobility functions, but introduce new bottlenecks on the data-path. By taking advantage of the lossless fabric, we deconstruct the existing virtualized networking stack into its core functions and consolidate them into zFabric, an efficient hypervisor that meets our aforementioned goals. To demonstrate zFabric's benefits, we evaluate a prototype implementation on a datacenter testbed. Besides resolving head-of-line blocking, zFabric improves throughputs for long flows by up to 56%, lowers CPU utilization by up to 63%, and shortens completion times by up to 7x for partition-aggregate queries when compared with current virtualized TCP stacks.

Dragonflies are recent network designs that are one of the most promising topologies for the Exascale effort due to their scalability and cost. While being able to achieve very high throughput under random uniform all-to-all traffic, this type of network can experience significant performance degradation for other common high performance computing workloads such as stencil (multi-dimensional nearest neighbor) patterns. Often, the lack of peak performance is caused by an insufficient understanding of the interaction between the workload and the network, and an insufficient understanding of how application specific task-to-node mapping strategies can serve as optimization vehicles.

Performance-optimized datacenter networks aim to handle more efficiently the growing East-West intra-cluster traffic of BigData applications. The demanding latency constraints and traffic patterns of these applications expose the inherent bottlenecks of the often oversubscribed datacenter network topologies, favoring in stead the full-bisectional bandwidth fat-trees. And yet their topological benefits may remain unrealized in practical deployments, if such fabrics use single path or flow-level (ECMP hashing) multipath routing. Here we model in detail on Layer 2 the routing performance of modern fat-tree networks using stochastic permutations of bursty traffic. We first analytically simplify and then validate by accurate simulation models that the throughputs for ‘static’ d-mod-k and for ECMP-like multipath routing are 63% and 47%, respectively. We also find that ECMP routing results in a wide spread of link loads under random permutation traffic, which manifests as a 3x throughput reduction for 30% of the flows. Furthermore, ECMP can lead to collisions of mouse and elephant flows, often increasing the flow completion time (FCT) of delay-sensitive flows by a factor of 10. In contrast, packet-based multipath outperforms all the others in this study.

The articles i nthis special issue focus on switching and routing applications for scalable and energy efficient networking.

The personalized all-to-all collective exchange is one of the most challenging communication patterns in HPC applications in terms of performance and scalability. In the context of the fat tree family of interconnection networks, widely used in current HPC systems and datacenters, we show that there is potential for optimizing this traffic pattern by deriving a tight theoretical lower bound for the bandwidth needed in the network to support such communication in a non-contending way. Current state of the art methods require up to twice as much bisection bandwidth as this theoretical minimum. We propose a set of optimized exchanges that use exactly the minimum amount of resources and exhibit close to ideal performance. This enables cost-effective networks, i.e., with as little as half the bisection bandwidth required by current state of the art methods, to exhibit quasi optimal performance under all-to-all traffic. In addition to supporting our claims by mathematical proofs, we include simulation results that confirm their correctness in practical system configurations.

The personalized all-to-all collective exchange is one of the most challenging communication patterns in HPC applications in terms of performance and scalability. We present a framework for the design of optimized collective patterns for generic hierarchical topologies. Our proposal can be applied, among others, to two types of topologies of great importance today: (i) the family of extended generalized fat tree networks (including k-ary n-trees and their variations) which are extensively used today in both HPC and commercial data centers, and (ii) direct low-diameter scalable hierarchical architectures such as the recently proposed dragonfly networks. We argue that exchange patterns that are congruent with the underlying structure of the network have inherent advantages compared to patterns that are oblivious to this structure. However, the current commonly used hierarchical pattern, the XOR exchange, has limited applicability, because it requires that the number of communicating nodes equals an integral power of two, making it suitable only for few tree designs and unsuitable for any dragonfly network. We propose several new, generic, universally applicable approaches to perform such exchanges in a hierarchical fashion that outperform current state of the art approaches. We support our claims by means of both mathematical proofs and simulation results that show that we can achieve an improvement of almost two-fold in dragonflies, and a twoto three-fold improvement in fat tree networks in cases where the XOR exchange cannot be applied.

The scalability of many datacenter applications is largely dependent on the networking infrastructure. Several studies addressed the network traffic characteristics from the perspective of network equipment, i.e., collecting and analyzing traffic data from routers, switches, or other network aggregation points. However, little is known about how traffic is directly generated by the servers. In this paper, we conduct an empirical study to characterize datacenter traffic from a server-centric perspective. We analyze data from more than 30,000 servers, located across more than 50 production datacenters, over a two-year time span. Our evaluation encompasses traffic statistics as well as network resources, based on short-term snapshots and long-term evolution of the collected metrics. In particular, we characterize the temporal and spatial characteristics of incoming and outgoing traffic volumes across servers, in packets as well as bytes per second. Our analysis provides a baseline for datacenter network modeling and workload model calibration.

Datacenter networking is currently dominated by two major trends. One aims toward lossless, flat layer-2 fabrics based on Converged Enhanced Ethernet or InfiniBand, with benefits in efficiency and performance. The other targets flexibility based on Software Defined Networking, which enables Overlay Virtual Networking. Although clearly complementary, these trends also exhibit some conflicts: In contrast to physical fabrics, which avoid packet drops by means of flow control, practically all current virtual networks are lossy. We quantify these losses for several common combinations of hypervisors and virtual switches, and show their detrimental effect on application performance. Moreover, we propose a zero-loss Overlay Virtual Network (zOVN) designed to reduce the query and flow completion time of latency-sensitive datacenter applications. We describe its architecture and detail the design of its key component, the zVALE lossless virtual switch. As proof of concept, we implemented a zOVN prototype and benchmark it with Partition-Aggregate in two testbeds, achieving an up to 15-fold reduction of the mean completion time with three widespread TCP versions. For larger-scale validation and deeper introspection into zOVN, we developed an OMNeT++ model for accurate cross-layer simulations of a virtualized datacenter, which confirm the validity of our results.

In the context of eXtended Generalized Fat Tree (XGFT) topologies, widely used in HPC and datacenter network designs, we propose a generic method, based on Integer Linear Programming (ILP), to efficiently determine optimal routes for arbitrary workloads. We propose a novel approach that combines ILP with dynamic programming, effectively reducing the time to solution. Specifically, we divide the network into smaller subdomains optimized using a custom ILP formulation that ensures global optimality of local solutions. Local solutions are then combined into an optimal global solution using dynamic programming. Finally, we demonstrate through a series of extensive benchmarks that our approach scales in practice to networks interconnecting several thousands of nodes, using a single-threaded, freely available linear programming solver on commodity hardware, with the potential for higher scalability by means of commercial, parallel solvers.

One of the prevalent trends in emerging large scale multi-tenant datacenters is network virtualization using overlays. Here we investigate application performance degradation in such an overlay applied to commodity 10 Gigabit Ethernet networks. We have adopted partition/aggregate as a representative commercial workload that today is deployed on bare metal servers and is notoriously sensitive to latency and TCP incast congestion. Using query completion time as the primary metric, we evaluate the degree to which a software-defined network (SDN) overlay impacts this application's behavior, the performance bounds of partition/aggregate with an SDN overlay, and whether active queue management (AQM) such as random early detection (RED) can benefit this environment. We introduce a generic SDN overlay framework, which we measure in hardware and simulate using a real TCP stack extracted from FreeBSD v9, running over a detailed Layer 2 commodity 10G Ethernet fabric network simulator. To further alleviate TCP incast congestion and support legacy congestion control, we propose an AQM translation scheme called v-RED. Finally, we report results concerning SDN's benefits in addressing TCP incast. Contrary to our expectations, we found that latency-sensitive applications do not necessarily suffer from performance degradation when deployed over SDN overlays.

Deadlock free routing techniques for torus topologies have been a subject of deep study in the field of HPC interconnects and many proposals exist in the literature. Practical deadlock avoidance techniques can be classified into two main categories, requiring either a segregation of traffic in non-cyclic virtual networks or some form of injection control. Simulating large high-dimension tori networks using application traffic is challenging. Most proposals use either large low-dimension tori, or synthetic traffic. Currently, tori of five and six dimensions are being used in actual supercomputers, such as the Fujitsu K Computer, which was ranked first in the Top 500 in two consecutive lists (June 2011 and November 2011). To our knowledge, there are no published papers comparing the performance implications of deadlock avoidance techniques for large high-dimension tori using traffic typical of parallel applications. We chose two well established deadlock-avoidance techniques in tori with dimension-order routing, dateline resource allocation and bubble injection restriction. The simulation tools had to be adapted to scale to simulate these large networks. In this paper we analyze network performance for tori of up to 6 dimensions comprising up to 4096 nodes when dealing with both synthetic and HPC-specific workloads.

Dragonfly networks have been recently proposed for the interconnection network of forthcoming exascale supercomputers. Relying on large-radix routers, they build a topology with low diameter and high throughput, divided into multiple groups of routers. While minimal routing is appropriate for uniform traffic patterns, adversarial traffic patterns can saturate inter-group links and degrade the obtained performance. Such traffic patterns occur in typical communication patterns used by many HPC applications, such as neighbor data exchanges in multi-dimensional space decompositions. Non-minimal traffic routing is employed to handle such cases. Adaptive policies have been designed to select between minimal and nonminimal routing to handle variable traffic patterns. However, previous papers have not taken into account the effect of saturation of intra-group (local) links. This paper studies how local link saturation can be common in these networks, and shows that it can largely reduce the performance. The solution to this problem is to use nonminimal paths that avoid those saturated local links. However, this extends the maximum path length, and since all previous routing proposals prevent deadlock by relying on an ascending order of virtual channels, it would imply unaffordable cost and complexity in the network routers. In this paper we introduce a novel routing/flow-control scheme that decouples the routing and the deadlock avoidance mechanisms. Our model does not impose any dependencies between virtual channels, allowing for on-the-fly (in-transit) adaptive routing of packets. To prevent deadlock we employ a deadlock-free escape sub network based on injection restriction. Simulations show that our model obtains lower latency, higher throughput, and faster adaptation to transient traffic, because it dynamically exploits a higher path diversity to avoid saturated links. Notably, our proposal consumes traffic bursts 43% faster than previous ones.

Network design aspects that influence cost and performance can be classified according to their distance from the applications, into issues concerning topology, switch technology, link technology, network adapter, and communication library. The network adapter has a privileged position to take decisions with more global information than any other component in the network. It receives feedback from the switches and requests from the communication libraries and applications. Also, compared to a network switch, an adapter has access to significantly more memory (host memory and on-chip memory) and memory bandwidth (which typically exceeds network bandwidth). The potential of the adapter to improve global network performance has not yet been fully exploited. In this work we show a series of noticeable performance improvements (of at least 10% to 15%) for medium-sized message exchanges in typical HPC communication patterns by optimizing message segmentation and packet injection policies, that can be implemented in an adapter's firmware inexpensively. We also show that implementing equivalent solutions in the switch (as opposed to the adapter) leads to only marginal performance improvements as the ones obtained by controlling the segmentation and injection policy at the adapter, while involving significantly more cost. In addition, enhancing the adapter will lead to less hardware complexity in the switches, thus reducing cost and energy consumption.

Based on a realistic, yet simple cost model, we compute the switch radix that minimizes the cost of a fat tree network to support a given number of end nodes. The cost model comprises two parameters indicating the relative cost of a crosspoint vs. a link, and the crosspoint-independent base cost of a switch. These parameters can be adapted to represent a given technology used to implement links and switches. Based on these inputs, the resulting model allows a quick evaluation of the switch radix that minimizes the overall cost of the network. We demonstrate that the optimum radix depends most strongly on the relative cost of a link, and turns out to be largely independent of the network size. Using a first-order cost bounds analysis based on current CMOS and link technology, our model indicates that the optimum switch radix for large fat trees is driven almost entirely by link cost and as a result lies in the range of hundreds of ports, rather than the tens of ports being offered today by most commercial switch products today.

Packet-switched networks are encountered at the heart of scalable network routers and high-performance computer (or data center) interconnects. As these networks scale to larger port counts, and their utilization increases, congestion management becomes indispensable. At the same time, technology constraints rule out monolithic bufferless switches with centralized schedulers, and impose buffered multi-stage switching fabrics with distributed control. These trends have for some time now called forth research and products [1, 2, 3, 4, 5], which applied the request-grant philosophy of bufferless crossbars to make buffered multi-stage switching fabrics practical and efficient. In such proactive schemes, saturation-tree congestion is avoided by having inputs inform outputs of their demand, and inject data only after receiving output permission (grants). The per output admission arbiters can be located in a central scheduling unit, as in [3] [2] [4], can be distributed across the edge switches of the fabric [4], or can be placed in the respective output adapters [1] [5]. Such schemes have been quite successful, especially because they can be combined conveniently with reorder/reassembly buffer management, as well as with end-to-end reliable-delivery schemes.

We consider low-complexity, all-optical multi-stage networks with distributed arbitration achieved through minimal per-node buffering. To enhance the saturation throughput of such networks while maintaining low latency at low loads, we examine a novel combination of deterministic (prescheduled) and speculative (eager) packet injections. Prescheduled injections are performed in a time-division-multiplexing (TDM) manner, whereas eager injections follow a packet multiplexing paradigm. Prescheduled injections aim at reducing contention in the fabric, and sustain network throughput when the load is high. Eager injections, on the other hand, ignore the TDM schedule, thus allowing low latency communication when contention is low. In our set of rules that govern the interaction between prescheduled and eager packets, eager packets can be intentionally dropped when they block the progress of prescheduled ones. At the same time a highly efficient end-to-end reliable delivery scheme, implemented at the host adapters, deals with random packet losses in the optical domain, and also recovers the dropped eager packets. Computer simulations demonstrate that our approach can render low-complexity networks, which are amenable to an all-optical implementation, attractive for use in computer interconnects.

A family of oblivious routing schemes for fat trees and their slimmed versions is presented in this work. First, two popular oblivious routing algorithms, which we refer to as S-mod-k and D-mod-k, are analyzed in detail. S-mod-k is the default routing algorithm given as an example in the first works formally describing fat tree networks. D-mod-k has been independently proposed and investigated by several authors, who conclude in their evaluations that it achieves better performance than a random or adaptive routing approach. First, we identify the reasons why these algorithms perform well. Using this insight we extend these algorithms, originally intended for full bisection networks, to slimmed networks. Based on the lessons learned we propose a new generalized family of algorithms that provides a better oblivious solution than the existing ones for this class of networks. Moreover, this family extends the previous work from k-ary n-trees to the more general class of extended generalized fat trees.

As the Internet owes its scalability and stability to TCP, congestion control also plays a key role in the performance, efficiency, and stability of datacenters, as evidenced by the efforts to standardize congestion management (CM) for 10+ Gbps networks. The next step up from datacenters is CM for clouds. New solutions are necessary for clouds because, while the recent CM schemes have been tested on L2 reliable networks, they are limited by design to relatively small single domain datacenters. TCP, on the other hand, while scalable and continously evolving, was not designed for ¿s-latency lossless networks. To address this problem we first investigate whether path delay could serve as a reliable congestion measure for clouds spanning across multiple datacenters and heterogenous networks. A qualitative open loop analysis of two datacenter networks (10 Gb/s Ethernet and 12x Infiniband) yields positive results. We close the congestion control loop by adapting the delay observer to a re-designed AIMD controller whose base algorithm we extensively analyzed in IEEE 802.1Qau. However, despite the statistical correlation between congestion severity and delay, the low signal/noise ratio (l-2dB), and the congestion notification lag threaten the closed loop stability. Hence we design a combination of two original filters, called Dual-Edge KDS-CUSUM. After preliminary loop tuning in Matlab, simulation results in OMNeT++ bear out the trade-off between stability and dynamic response. The concept is validated on a cluster software implementation.

New static source routing algorithms for High Performance Computing (HPC) are presented in this work. The target parallel architectures are based on the commonly used fat-tree networks and their slimmed versions. The evaluation of such proposals and their comparison against currently used routing mechanisms have been driven by realistic traffic generated by HPC applications. Our experimental framework is based on the integration of two existing simulators, one replaying an MPI application and another simulating the network details. The resulting simulation platform has been fed with traces from real executions.

High-radix switches are desirable building blocks for large computer interconnection networks, because they are more suitable to convert chip I/O bandwidth into low latency and low cost than low-radix switches. Unfortunately, most existing switch architectures do not scale well to a large number of ports. For example, the complexity of the buffered crossbar architecture scales quadratically with the number of ports. Compounded with support for long round-trip times and many virtual channels, the overall buffer requirements limit the feasibility of such switches to modest port counts. Compromising on the buffer sizing leads to a drastic increase in latency and reduction in throughput, as long as traditional credit flow control is employed at the link level. We propose a novel link-level flow control protocol that enables high-performance scalable routers based on the increasingly popular buffered crossbar architecture to scale to higher port counts without sacrificing performance. By combining credited and speculative transmission, this scheme achieves reliable delivery, low latency, and high throughput, even with crosspoint buffers that are significantly smaller than the round-trip time.

The data vortex photonic packet-switching architecture features an all-optical transparent data path, highly distributed control, low latency, and a high degree of scalability. These characteristics make it attractive as a routing fabric in future photonic packet switches. We analyze the performance of the data vortex architecture as a function of its height and angle dimensions, H and A. The investigation is based on two performance measures: the average delay and the maximum throughput of the switch. We present an analytical model assuming uniform traffic and derive closed-form expressions for these measures. Our results obtained demonstrate that as H increases, the saturation throughput decreases and approaches2/9= 0.22 when A is small and H is large. Furthermore, for fixed switch size, the saturation throughput is maximized when A is minimal. We also present simulation results for the maximum throughput under uniform and nonuniform traffic, as well as for the mean number of hops and the mean input-queue packet delay as a function of input load, and address the issue of resequencing delay. The results obtained advocate that to support more ports, it is preferable to increase the height dimension and to keep the angle dimension as small as possible.

We present a scheme to concurrently schedule unicast and multicast traffic in an input-queued switch. It aims at providing high performance under any mix of the two traffic types as well as at avoiding starvation of any connection. The key idea is to schedule the two traffic types independently and in parallel, and then arbitrate among them for access to the switching fabric. The unicast and multicast matchings are combined into a single integrated matching. Edges that are excluded from the integrated matching are guaranteed to receive service at a later time, thus balancing service ratios and preventing starvation. We use simulation to evaluate the performance of a system employing the proposed scheme and show that, despite its simplicity, it achieves the intended goals. We also design an enhanced remainder-service policy to achieve better integration and further improve performance.

We address the problem of how to exploit optics for ultrascale High Performance Computing interconnect fabrics. We show that for high port counts these fabrics require multistage topologies regardless of whether electronic or optical switch components are used. Also, per stage electronic buffers remain indispensable for maintaining throughput, lossless-ness and packet sequence. Although the notion of true all-optical packet switching is not yet viable, we show that appropriate use of optical switching technology offers power and scaling advantages that can be leveraged economically, and propose a hybrid opto-electronic HPC interconnect fabric architecture that combines the strength of electronics in processing and storing information with the strength of optics in switching and transporting high bandwidths. Using Semiconductor Optical Amplifier technology, we are building a prototype demonstrator switch that we believe solves all the technical challenges. Having reached this threshold now enables commercialization of this technology, which we are currently pursuing.

Heuristic, parallel, iterative matching algorithms for input-queued cell switches with virtual output queuing require O(log N) iterations to achieve good performance. If the hardware implementation of the number of iterations required is not feasible within the cell duration, the matching process can be pipelined to obtain a matching in every cell time slot. However, existing approaches incur a substantial latency penalty due to the way the pipelining is performed, which renders them unattractive in latency-sensitive applications such as parallel computer interconnects. We introduce a new class of pipelined matching algorithms that can be based on any existing iterative matching algorithm, makes the minimum latency independent of the pipeline depth, and is highly amenable to distributed implementation. Our simulation results confirm that specific instances of this class achieve significantly lower average latency throughout the load range than existing schemes do. We also propose an instantiation of the scheme that, in addition, significantly improves the performance with nonuniform traffic.

A buffered crossbar supporting P priorities and a flow control latency of RT packets between the input adapter and the crossbar requires a memory of order O(N/sup 2/*P*RT) packets in the crossbar to support any traffic pattern without blocking. We propose a new priority elevation mechanism that reduces the memory requirements to O(N/sup 2/*RT) for large values of RT. Our analysis shows that our mechanism has no drawback on the usual performance metrics and that it only introduces a small priority unfairness and worst-case blocking of less than RT packet times. We further show that an optimized system using a crosspoint memory of size 2RT has an unfairness of less than 0.02% affected packets at 95% loading with an average burst size of 30 packets.

We propose a systematic method to determine the lower bound for internal buffering of practical CIOQ (combined input-output queued) switching systems. We introduce a deterministic traffic scenario that stresses the global stability of finite output queues. We demonstrate its usefulness by dimensioning the buffer capacity of the CIOQ under such traffic patterns. Compliance with this property maximizes the performance achievable with finite buffers.

Traditional improvements in packet switch architecture are aimed at increasing switch performance in terms of utilization, fairness and QoS. This paper focuses on improving the architecture to achieve implementation feasibility of terabit aggregate data rates while maintaining such performance. Terabit class shared-memory switch chips are simple in concept but are a challenge to build due to the memory speed requirements and the complexity of wiring needed to connect these memories. Using a property of the combined shared memory and virtual output queuing switch architecture and a property of SRAMs, a new architecture is derived that enables construction of a terabit class switch fabric.

The problem of scheduling multicast traffic in packet switches is considered, and existing solutions based on purely input- or output-queued switches are reviewed. These are based exclusively on FIFO input queues, and are thus prone to head-of-line blocking. Furthermore, unicast and multicast traffic are typically queued and scheduled separately. A new, combined input- and output-queued approach is presented that (a) eliminates head-of-line blocking by applying virtual output queuing, and (b) handles unicast and multicast traffic in an integrated, fair way without sacrificing performance. Implementation as well as performance simulation results of the proposed architecture are presented to demonstrate its feasibility.