Efficient routing in Dragonfly networks has proven to be challenging. Studies have shown that the current state-of-the-art Universal Globally Adaptive Routing (UGAL) for the Dragonfly network makes sub-optimal routing decisions in some situations when the decisions are made using local information. The advent of Software-Defined Networking (SDN) offers new opportunities for optimizing UGAL routing by providing a global network view. In this work, we study the potential of leveraging SDN technology to improve UGAL routing on Dragonfly networks. In particular, we develop techniques that utilize the global flow information available to an SDN network to improve the latency estimation and path selection in UGAL, which leads to better routing performance. We performed extensive simulation with synthetic traffic and application workloads, and concluded that by incorporating the global flow information in SDN, the performance of UGAL can be significantly improved.

New frontiers in simulation-based teacher training have been unveiled with the advancement of artificial intelligence (AI). Integrating AI into virtual student agents increases the accessibility and affordability of teacher training simulations, but little is known about how preservice teachers interact with AI-powered student agents. This study analyzed the discourse behavior of 15 preservice teachers who undertook simulation-based training with AI-powered student agents. Using a framework of ambitious science teaching, we conducted a pattern analysis of teacher and student talk moves, looking for evidence of academically productive discourse. Comparisons are made with patterns found in real classrooms with professionally trained science teachers. Results indicated that preservice teachers generated academically productive discourse with AI-powered students by using ambitious talk moves. The pattern analysis also revealed coachable moments where preservice teachers succumbed to cycles of unproductive discourse. This study highlights the utility of analyzing classroom discourse to understand human-AI communication in simulation-based teacher training.

The Dragonfly networks have been adopted in the current supercomputers, and will be deployed in future generation supercomputers and data centers. Effective routing on Dragonfly is challenging. Universal Globally Adaptive Load-balanced routing (UGAL) is the state-of-the-art routing algorithm for Dragonfly. For each packet, UGAL selects either a minimal path or a non-minimal path based on their estimated latencies. Practical UGAL makes routing decisions with local information, deriving the estimated latency for each path from the local queue occupancy and path hop count information. In this work, we develop techniques to improve the accuracy of the latency estimation for UGAL with local information, which results in more effective routing decisions. In particular, our schemes are able to proactively mitigate the potential network congestion with imbalanced network traffic. Extensive simulation experiments using synthetic traffic patterns and application workloads demonstrate that our enhanced UGAL schemes significantly improve the routing performance for many common traffic conditions.

We study the performance of software-based secure communication infrastructure for HPC Message Passing Interface (MPI) applications in container clusters. Specifically, extensive experiments are performed using micro-and application benchmarks to evaluate the encrypted MPI communication performance. Container built-in encrypted communication schemes including Docker Swarm and Kubernetes Antrea and Calico, as well as CryptMPI, a secure MPI library, are evaluated and compared. Our results confirm the findings in earlier studies that for some MPI applications, running in the container environment with unencrypted communication introduces only minor overheads over running on the bare metal system. However, when the communications are encrypted, all of the container built-in software-based encrypted communication mechanisms that we evaluated incur very large overheads in all of our experiments for both micro-benchmarks and application benchmarks. On the other hand, CryptMPI, which encrypts and decrypts messages in the MPI library, achieves much higher performance than the container built-in encryption schemes.

The Florida State University (FSU) Computer Science Integrated with Mathematics in Middle Schools (CSIMMS) project explores the feasibility and effectiveness of integrating Computer Science (CS) into middle school general mathematics courses. Through Design Based Research, we developed and tested 13 teaching modules that integrate CS concepts into general middle school mathematics courses, grades 6, 7, and 8, beginning in 2017. In this paper, we discuss our experience with integrating computer science into middle school mathematics and report our preliminary findings.

Compute nodes on high performance computing (HPC) platforms are increasingly equipped with multiple GPUs. This results in increased computational capacity per node, and reduction in the total number of nodes or endpoints in the system. This trend changes the computation and communication balance in comparison to pre-GPU era HPC platforms, which warrants a new study of hardware architectural parameters. In this work, we leverage the end-to-end system simulation capabilities of TraceR-CODES and study the impact of several hardware design parameters on the performance of realistic HPC workloads. We focus on three crucial hardware parameters: (1) number of GPUs per node, (2) network link bandwidth, and (3) network interface controller (NIC) scheduling policies, in the context of two popular network topologies – fat-tree and dragonfly.

We consider the encrypted all-reduce operation on multi-core clusters. We derive performance bounds for the encrypted all-reduce operation and develop efficient algorithms that are theoretically optimal in that they asymptotically achieve the performance bounds. We empirically evaluate our encrypted all-reduce algorithms on production clusters. The results show that with the right algorithm, encryption can be incorporated in the all-reduce operation on large messages without significant overheads on modern multi-core clusters whose compute node has a large number of cores.

As more High-Performance Computing (HPC) applications that process sensitive data are moving to run on the public cloud, there is a need for the cloud infrastructure to provide privacy and integrity support. In this work, we investigate how to add encryption to all-gather to protect internode communication. This task is challenging since encryption is often more expensive than communication in contemporary HPC systems. We derive performance bounds for encrypted allgather, and develop new algorithms that meet the theoretical lower bounds. Our empirical evaluation on production systems demonstrates that the new algorithms achieve substantially better performance than the naive approach.

The Dragonfly network organizes routers into groups, with connectivity within each group provided by local links and connectivity between groups provided by global links. The specification of Dragonfly leaves many options for arranging global links. In this work, we study global link arrangement for practical Dragonfly topologies where (1) there are multiple global links connecting each pair of groups, and (2) the global link bandwidth is similar to the local link bandwidth. We found that existing global link arrangement schemes such as the absolute, relative and circulant-based arrangements do not specify an important component in global connectivity for practical Dragonfly, which we call per-router arrangement. Per-router arrangement determines how the global links from each individual router are connected. We integrate per-router arrangement into existing schemes, develop a unified algorithm to compute a large class of global link arrangements for practical Dragonfly, and carry out an extensive simulation study to evaluate different global link arrangement schemes. Our results indicate that the existing understanding of the global link arrangement does not apply to practical Dragonfly: contradict to the existing understanding that global link arrangement does not make significant difference in performance when global links have similar bandwidth as local links, per-router arrangement significantly impacts the network performance of practical Dragonfly. We identify the schemes that yield high performance for practical Dragonfly.

As High Performance Computing (HPC) applications with data security requirements are increasingly moving to execute in the public cloud, there is a demand that the cloud infrastructure for HPC should support privacy and integrity. Incorporating privacy and integrity mechanisms in the communication infrastructure of today's public cloud is challenging because recent advances in the networking infrastructure in data centers have shifted the communication bottleneck from the network links to the network end points and because encryption is computationally intensive. In this work, we consider incorporating encryption to support privacy and integrity in the Message Passing Interface (MPI) library, which is widely used in HPC applications. We empirically study four contemporary cryptographic libraries, OpenSSL, BoringSSL, Libsodium, and CryptoPP using micro-benchmarks and NAS parallel benchmarks to evaluate their overheads for encrypting MPI messages on two different networking technologies, 10Gbps Ethernet and 40Gbps InfiniBand. The results indicate that (1) the performance differs drastically across cryptographic libraries, and (2) effectively supporting privacy and integrity in MPI communications on high speed data center networks is challenging-even with the most efficient cryptographic library, encryption can still introduce very significant overheads in some scenarios such as a single MPI communication operation on InfiniBand, but (3) the overall overhead may not be prohibitive for practical uses since there can be multiple concurrent communications.

The Dragonfly network has been deployed in the current generation supercomputers and will be used in the next generation supercomputers. The Universal Globally Adaptive Load-balance routing (UGAL) is the state-of-the-art routing scheme for Dragonfly. In this work, we show that the performance of the conventional UGAL can be further improved on many practical Dragonfly networks, especially the ones with a small number of groups, by customizing the paths used in UGAL for each topology. We develop a scheme to compute the custom sets of paths for each topology and compare the performance of our topology-custom UGAL routing (T-UGAL) with conventional UGAL. Our evaluation with different UGAL variations and different topologies demonstrates that by customizing the routes, T-UGAL offers significant improvements over UGAL on many practical Dragonfly networks in terms of both latency when the network is under low load and throughput when the network is under high load.

The recent interconnect topology designs for High Performance Computing (HPC) systems have followed two directions, one characterized by low diameter and the other by high path diversity. The low diameter design focuses on building large networks with small diameters, guaranteeing one short path between each pair of nodes. Examples include Slim Fly and Dragonfly. The high path diversity design takes into account not only other topological metrics such as diameter but also path diversity between pairs of nodes. Examples include fat-tree, Random Regular Graph (RRG) and Generalized De Bruin Graph (GDBG). Topologies designed from these two approaches have distinct features and require very different routing schemes to exploit the network capacity. In this work, we study the performance-related topological features of representative topologies of the two design approaches, including Slim Fly, Dragonfly, RRG, and GDBG, and compare HPC application performance on these topologies with a set of routing schemes. The study uncovers new knowledge about the topologies designed by these two approaches. Findings of the study include (1) the load balance routing technique designed for low diameter topologies, known as the Universal Globally Adaptive Load-balanced routing (UGAL), can be effectively adapted for the high path diversity topologies, and (2) high path diversity topologies in general achieve higher performance than low diameter topologies for networks built by a similar number of the same type of switches.

The Slim Fly topology has recently been proposed for the future generation supercomputers. It has small diameter and relies on the Universal Globally Adaptive Load-balanced (UGAL) routing, which adapts the routes between minimal (MIN) routing and Valiant Load-Balancing (VLB) routing to exploit the network capacity. In this work, we show that the current Slim Fly is not load-balanced for both MIN routing and VLB routing, in that certain links in the network have a significantly higher probability to carry traffic than others. As such, hot spots are more likely to form on such links. We propose two approaches to address this problem and to make Slim Fly load-balanced: (1) modifying the topology by selectively increasing the bandwidth of the potential hot-spot links so that the original routing becomes load-balanced, and (2) modifying the routing scheme by using a weighted VLB routing to distribute the traffic in a more load balanced fashion than the original VLB routing on the original Slim Fly. The results of our performance analysis and simulation demonstrate that both approaches result in more effective Slim Fly than its current form.

High Performance Computing (HPC) applications and systems are often studied through modeling and simulation at various granularities. As the size of HPC systems and applications and the cost of high fidelity simulation continue to grow, a good understanding of the trade-offs of the complexity and accuracy of HPC application modeling and simulation schemes can help balance the competing goals of accuracy and time. In this work, we investigate the complexity and accuracy trade-off using an MPI application modeling tool and an MPI application simulation tool. The performance and accuracy results of modeling and simulation of a large spectrum of HPC applications on three supercomputers are measured and compared. The results show that although modeling is often one to two orders of magnitude faster than simulation, it achieves within 5% of predicted application time in comparison to simulation for 85% of cases in our data set. We further enhance the modeling tool with a statistical model to predict whether simulation can yield significantly different results than modeling. The enhanced tool achieves a very high successful prediction rate of 93.2% on our dataset and is thus effective in determining whether modeling or simulation should be used.

The Random regular graph (RRG) has recently been proposed as an interconnect topology for future large scale data centers and HPC clusters. An RRG is a special case of directed regular graph (DRG) where each link is unidirectional and all nodes have the same number of incoming and outgoing links. In this work, we establish bounds for DRGs on diameter, average k-shortest path length, and a load balancing property with k-shortest path routing, and use these bounds to evaluate RRGs. The results indicate that an RRG with k-shortest path routing is not ideal in terms of diameter and load balancing. We further consider the Generalized De Bruijn Graph (GDBG), a deterministic DRG, and prove that for most network configurations, a GDBG is near optimal in terms of diameter, average k-shortest path length, and load balancing with a k-shortest path routing scheme. Finally, we use modeling and simulation to exploit the strengths and weaknesses of RRGs for different traffic conditions by comparing RRGs with GDBGs.

Max-min fairness is often used in the performance modeling of interconnection networks. Existing methods to compute max-min fair rates for multi-commodity flows have high complexity and are computationally infeasible for large networks. In this work, we show that by considering topological features, this problem can be solved efficiently for the fat-tree topology that is widely used in data centers and high performance compute clusters. Several efficient new algorithms are developed for this problem, including a parallel algorithm that can take advantage of multi-core and shared-memory architectures. Using these algorithms, we demonstrate that it is possible to find the max-min fair rate allocation for multi-commodity flows in fat-tree networks that support tens of thousands of nodes. We evaluate the run-time performance of the proposed algorithms and show improvement in orders of magnitude over the previously best known method. We further demonstrate a new application of max-min fair rate allocation that is only computationally feasible using our new algorithms.

The OpenFlow-style Software Defined Networking (SDN) technology has shown promising performance in data centers and campus networks; and the HPC community is significantly interested in adopting the SDN technology. However, while OpenFlow-style SDN allows dynamic per-flow resource management using a global network view, it does not support adaptive routing, which is widely used in HPC systems. This gives rise to the question whether SDN can achieve the performance that HPC systems expect with adaptive routing. In this work, we investigate possible methods to apply the SDN technology on the current generation HPC interconnects with the Dragonfly topology, and compare the performance of SDN with that of adaptive routing. Our results indicate that adaptive routing results in higher performance than SDN when both have similar resource allocation for a given traffic condition. However, SDN can use the global network view to compete with adaptive routing by allocating network resources more effectively.

Random regular graph (RRG) has recently been proposed as an interconnect topology for future large scale data centers and HPC clusters. While various studies have been performed, this topology is still not well understood. RRG is a special case of directed regular graph (DRG) where each link is unidirectional and all nodes have the same number of incoming and outgoing links. In this work, we establish bounds for DRG on diameter, average k-shortest path length, and a load balancing property with k-shortest path routing, and use these bounds to evaluate RRG. The results indicate that RRG with k-shortest path routing is not ideal in terms of diameter and load balancing. We further consider the Generalized De Bruijn Graph (GDBG), a deterministic DRG, and prove that for most network configurations, GDBG is near optimal in terms of diameter, average k-shortest path length, and load balancing with a k-shortest path routing scheme. Finally, we explore the strengths and weaknesses of RRG for different traffic conditions by comparing RRG with GDBG.

We present a novel trace-based analysis tool that rapidly classifies an MPI application as bandwidth-bound, latency-bound, load-imbalance-bound, or computation-bound for different interconnection networks. The tool uses an extension of Lamport's logical clock to track application progress in the trace replay. Ithas two unique features. First, it predicts application performance for many latency and bandwidth parameters from a single replay of the trace. Second, it infers the performance characteristics of an application and classifies the application using the predicted performance trend for a range of network configurations instead of using the predicted performance for a particular network configuration. We describe the techniques used in the tool and its design and implementation, and report our performance study of the tool and our experience with classifying nine applications and mini-apps from the DOE Design Forward project as well as the NAS Parallel Benchmarks.

InfiniBand is the de facto networking technology for commodity HPC clusters and has been widely deployed. However, most production large-scale InfiniBand clusters use simple routing schemes such as the destination-mod-k routing to route traffic, which may result in degraded communication performance. In this work, we investigate using the OpenFlow-style Software-Defined Networking (SDN) technology to overcome the routing deficiency in InfiniBand. We design an enhanced InfiniBand with OpenFlow-style SDN capability and demonstrate a use case that illustrates how the SDN capability can be exploited in HPC clusters to improve the system and application performance. Finally, we quantify the potential benefits of InfiniBand with OpenFlow-style SDN capability in balancing the network load by simulating job traces from production HPC clusters. The results indicate that InfiniBand with SDN capability can achieve much better network load balancing than traditional InfiniBand for HPC clusters.

Max-min fairness is often used in the performance modeling of interconnection networks. Existing methods to compute max-min fair rates for multi-commodity flows have high complexity and are computationally infeasible for large networks. In this work, we show that by considering topological features, this problem can be solved efficiently for the fat-tree topology that is widely used in data centers and high performance computing clusters. Using two new algorithms that we developed, we demonstrate it is possible to find the max-min fair rate allocation for multi-commodity flows in fat-tree networks that support tens of thousands of nodes. We evaluate the run-time performance of the proposed algorithms and demonstrate an application.

Traditionally, interconnect performance is either characterized by simple topological parameters such as bisection bandwidth or studied through simulation that gives detailed performance information for the scenarios simulated. Neither of these approaches provides a good performance overview for extreme-scale interconnects. The topological parameters are not directly related to application level communication performance while the simulation complexity limits the number of scenarios that can be investigated. In this work, we propose a new performance metric, called LANL-FSU Throughput Indices (LFTI), for characterizing the throughput performance of interconnect designs. LFTI combines the simplicity of topological parameters and the accuracy of simulation: like topological parameters, LFTI can be derived from interconnect specification, at the same time, it directly reflects the application level communication performance. Moreover, in cases when the theoretical throughput for each communication pattern can be modeled efficiently for an interconnect, LFTI for the interconnect can be computed efficiently. These features potentially allow LFTI to be used for rapid and comprehensive evaluation and comparison of extreme-scale interconnect designs. We demonstrate the effectiveness of LFTI by using it to evaluate and explore the design space of a number of large-scale interconnect designs.

We propose a novel design for RDMA-based small message channels that significantly improves the MVAPICH design. First, we develop a technique that eliminates persistent buffer association, a scheme used in MVAPICH that not only results in significant memory requirement, but also imposes restrictions in memory management. Building upon this technique, we propose a novel shared RDMA-based small message channel design that allows MPI processes on the same SMP node to share small message channels, which greatly reduces the number of small message channels needed for an MPI program on clusters with SMP nodes. Our techniques considerably improve the scalability and reduce memory requirement in comparison to MVAPICH, allowing RDMA-based small message channels to be used by a much larger number of MPI processes. The experimental results demonstrate that our techniques achieve the improvements without adding noticeable overheads or sacrificing the performance benefits of RDMA in practice.

The jellyfish topology where switches are connected using a random graph has recently been proposed for large scale data-center networks. It has been shown to offer higher bisection bandwidth and better permutation throughput than the corresponding fat-tree topology with a similar cost. In this work, we propose a new routing scheme for jellyfish that out-performs existing schemes by more effectively exploiting the path diversity, and comprehensively compare the performance of jellyfish and fat-tree topologies with HPC workloads. The results indicate that both jellyfish and fat-tree topologies offer comparable high performance for HPC workloads on systems that can be realized by 3-level fat-trees using the current technology and the corresponding jellyfish topologies with similar costs. Fat-trees are more effective for smaller systems while jellyfish is more scalable.

Folded-Clos networks, also referred to as fat-trees, have been widely used as interconnects in large scale high performance computing clusters. The switching capability of such interconnects in computer communication environments, however, is not well understood. In particular, the concept of nonblocking interconnects, which is often used by system vendors, has only been studied in the telephone communication environment with the assumption of a centralized controller. Such "nonblocking'' networks do not support nonblocking communications in computer communication environments where the network control is distributed. This paper theoretically analyzes the conditions for folded-Clos networks to achieve nonblocking communications in computer communication environments with various routing schemes including deterministic routing and adaptive routing, and establishes nonblocking conditions.

Optimizing Message Passing Interface (MPI) point-to-point communication for large messages is of paramount importance since most communications in MPI applications are performed by such operations. Remote Direct Memory Access (RDMA) allows one-sided data transfer and provides great flexibility in the design of efficient communication protocols for large messages. However, achieving high performance on RDMA-enabled clusters is still challenging due to the complexity both in communication protocols and in protocol invocation scenarios. In this work, we investigate a profile-driven compiled-assisted protocol customization approach for efficient communication on RDMA-enabled clusters. We analyze existing protocols and show that they are not ideal in many situations. By leveraging the RDMA capability, we develop a set of protocols that can provide near-optimal performance for all protocol invocation scenarios, which allows protocol customization to achieve near-optimal performance when the appropriate protocol is used for each communication. Finally, we evaluate the potential benefits of protocol customization using micro-benchmarks and application benchmarks. The results demonstrate that the proposed protocols can out-perform traditional rendezvous protocols to a large degree in many situations and that protocol customization can significantly improve MPI communication performance.

Message Passing Interface (MPI) point-to-point communications are usually realized with two protocols, the eager protocol for small messages and the rendezvous protocol for medium and large sized messages. Traditional sender-initiated rendezvous protocols are sub-optimal in many situations. In this work, we propose to refine the rendezvous protocol for medium and large messages on RDMA-enabled clusters with three protocols that are customized for different situations, a hybrid protocol for medium sized messages when the sender arrives early, a sender-initiated protocol for large messages when the sender arrives early, and a receiver-initiated protocol when the receiver arrives early. In comparison to traditional sender-initiated rendezvous protocols, the proposed scheme reduces unnecessary synchronizations, decreases the number of control messages that are in the critical path of communications, and improves the communication progress, which results in a significantly better communication-computation overlap capability. We present and analyze these protocols, and describe how these protocols and the eager protocol can be seamlessly integrated in one system without introducing an excessive number of control messages. We have implemented the proposed scheme for InfiniBand clusters. The experimental results demonstrate the effectiveness of the proposed technique.

Round robin based packet schedulers generally have a low complexity and provide long-term fairness. The main limitation of such schemes is that they do not support short-term fairness. In this paper, we propose a new low complexity round robin scheduler, called Fair Round Robin (FRR), that overcomes this limitation. FRR has similar complexity and long-term fairness properties as the stratified round robin scheduler, a recently proposed scheme that arguably provides the best quality-of-service properties among all existing round robin based low complexity packet schedulers. FRR offers better short-term fairness than stratified round robin and other existing round robin schedulers.

To realize a path in an InfiniBand network, an address, known as local identifier (LID) in the InfiniBand specification, must be assigned to the destination of the path and used in the forwarding tables of intermediate switches to direct the traffic following the path. Hence, routing in InfiniBand has two components: (1) computing all paths, and (2) assigning LIDs to destinations and using them in intermediate switches to realize the paths. We refer to the task of computing paths as path computation and the task of assigning LIDs as LID assignment. This paper focuses on the LID assignment component, whose major issue is to minimize the number of LIDs required to support a given set of paths. We prove that the problem of realizing a given set of paths with a minimum number of LIDs is NP-complete, develop an integer linear programming formulation for this problem, design a number of heuristics that are effective and efficient in practical cases, and evaluate the performance of the heuristics through simulation. The experimental results indicate that the performance of our best performing heuristic is very close to optimal.

This paper develops and studies a traffic-aware inter-domain routing (TIDR) protocol, which drastically improves the stability of the BGP-based inter-domain routing system. TIDR is designed based on two important Internet properties-the Internet access non-uniformity and the prevalence of transient failures. In TIDR, a network prefix is classified at an AS as either significant or insignificant from the viewpoint of a neighboring AS, depending on the amount of traffic exchanged between the prefix and the neighbor (including transit traffic). While BGP updates of significant prefixes are propagated with a higher priority, the propagation of updates of insignificant prefixes is aggressively slowed down. In particular, TIDR tries to localize the effect of transient failures on insignificant prefixes instead of propagating it onto the whole Internet. Importantly, TIDR will not create traffic black-holes due to the localization of transient failures. In this paper we present the design of TIDR and perform simulation experiments to study the performance of TIDR. Our simulation results show that TIDR can greatly improve the stability of BGP and also outperforms other existing schemes including Ghost Flushing and EPIC.

We present an MPI topology discovery tool for homogeneous Ethernet switched clusters. Unlike existing Ethernet topology discovery methods that rely on simple network management protocol (SNMP) queries to obtain the topology information, our tool infers the topology from end-to- end measurements. The tool works on clusters connected by managed and/or unmanaged Ethernet switches, and does not require any special privilege. We discuss the theoretical foundation of the tool, present the algorithms used, and report our evaluation of the tool.

A message passing interface (MPI) collective operation such as broadcast involves multiple processes. The process arrival pattern denotes the timing when each process arrives at a collective operation. It can have a profound impact on the performance since it decides the time when each process can start participating in the operation. In this paper, we investigate the broadcast operation with different process arrival patterns. We analyze commonly used broadcast algorithms and show that they cannot guarantee high performance for different process arrival patterns. We develop two process arrival pattern aware algorithms for broadcasting large messages. The performance of proposed algorithms is theoretically within a constant factor of the optimal for any given process arrival pattern. Our experimental evaluation confirms the analytical results: existing broadcast algorithms cannot achieve high performance for many process arrival patterns while the proposed algorithms are robust and efficient across different process arrival patterns.

The distributed denial-of-service (DDoS) attack is a serious threat to the legitimate use of the Internet. Prevention mechanisms are thwarted by the ability of attackers to forge or spoof the source addresses in IP packets. By employing IP spoofing, attackers can evade detection and put a substantial burden on the destination network for policing attack packets. In this paper, we propose an interdomain packet filter (IDPF) architecture that can mitigate the level of IP spoofing on the Internet. A key feature of our scheme is that it does not require global routing information. IDPFs are constructed from the information implicit in border gateway protocol (BGP) route updates and are deployed in network border routers. We establish the conditions under which the IDPF framework correctly works in that it does not discard packets with valid source addresses. Based on extensive simulation studies, we show that, even with partial deployment on the Internet, IDPFs can proactively limit the spoofing capability of attackers. In addition, they can help localize the origin of an attack packet to a small number of candidate networks.

Abstract — To realize a path in an InfiniBand network, an address, known as Local IDentifier (LID) in the InfiniBand specification, must be assigned to the destination of the path and used in the forwarding tables of intermediate switches to direct the traffic following the path. Hence, routing in InfiniBand has two components: (1) computing all paths, and (2) assigning LIDs to destinations and using them in intermediate switches to realize the paths. We refer to the task of computing paths as path computation and the task of assigning LIDs as LID assignment. This paper focuses on the LID assignment component, whose major issue is to minimize the number of LIDs required to support a given set of paths. We prove that the problem of realizing a given set of paths with a minimum number of LIDs is NPcomplete, develop an integer linear programming formulation for this problem, design a number of heuristics that are effective and efficient in practical cases, and evaluate the performance of the heuristics through simulation. The experimental results indicate that the performance of our best performing heuristic is very close to optimal. We further demonstrate that by separating path computation from LID assignment and using the schemes that are known to achieve good performance for path computation and LID assignment separately, more effective routing schemes than existing ones can be developed. Index Terms — InfiniBand, LID Assignment, NP-Complete I.

By analyzing a two-month trace of more than 25 million emails received at a large US university campus network, of which more than 18 million are spam messages, we characterize the spammer behavior at both the mail server and the network levels. We also correlate the arrivals of spam with the BGP route updates to study the network reachability properties of spammers. Among others, our significant findings are: (a) the majority of spammers (93% of spam only mail servers and 58% of spam only networks) send only a small number of spam messages (no more than 10); (b) the vast majority of both spam messages (91.7%) and spam only mail servers (91%) are from mixed networks that send both spam and non-spam messages; (c) the majority of both spam messages (68%) and spam mail servers (74%) are from a few regions of the IP address space (top 20 "/8" address spaces); (d) a large portion of spammers (81% of spam only mail servers and 27% of spam only networks) send spam only within a short period of time (no longer than one day out of the two months); and (e) network prefixes for a non-negligible portion of spam only networks (6%) are only visible for a short period of time (within 7 days), coinciding with the spam arrivals from these networks. We discuss the implications of the findings for the current anti-spam efforts, and more importantly, for the design of future email delivery architectures.

Process arrival pattern, which denotes the timing when different processes arrive at an MPI collective operation, can have a significant impact on the performance of the operation. In this work, we characterize the process arrival patterns in a set of MPI programs on two common cluster platforms, use a micro-benchmark to study the process arrival patterns in MPI programs with balanced loads, and investigate the impacts of the process arrival pattern on collective algorithms. Our results show that (1) the differences between the times when different processes arrive at a collective operation are usually sufficiently large to affect the performance; (2) application developers in general cannot effectively control the process arrival patterns in their MPI programs in cluster environments: balancing loads at the application level does not balance the process arrival patterns; and (3) the performance of the collective communication algorithms is sensitive to process arrival patterns. These results indicate that the process arrival pattern is an important factor that must be taken into consideration in developing and optimizing MPI collective routines. We propose a scheme that achieves high performance with different process arrival patterns, and demonstrate that by explicitly considering process arrival pattern, more efficient MPI collective routines than the current ones can be obtained.

We consider efficient implementations of the all-reduce operation with large data sizes on tree topologies. We prove a tight lower bound of the amount of data that must be transmitted to carry out the all-reduce operation and use it to derive the lower bound for the communication time of this operation. We develop a topology specific algorithm that is bandwidth efficient in that (1) the amount of data sent/received by each process is minimum for this operation; and (2) the communications do not incur network contention on the tree topology. With the proposed algorithm, the all-reduce operation can be realized on the tree topology as efficiently as on any other topology when the data size is sufficiently large. The proposed algorithm can be applied to several contemporary cluster environments, including high-end clusters of workstations with SMP and/or multi-core nodes and low-end Ethernet switched clusters. We evaluate the algorithm on various clusters of workstations, including a Myrinet cluster with dual-processor SMP nodes, an InfiniBand cluster with two dual-core processors SMP nodes, and an Ethernet switched cluster with single processor nodes. The results show that the routines implemented based on the proposed algorithm significantly outperform the native MPI_Allreduce and other recently developed algorithms for high-end SMP clusters when the data size is sufficiently large.

Fat-tree based system area networks have been widely adopted in high performance computing clusters. In such systems, the routing is often deterministic and the traffic demand is usually uncertain and changing. In this paper, we study routing performance on fat-tree based system area networks with deterministic routing under the assumption that the traffic demand is uncertain. The performance of a routing algorithm under uncertain traffic demands is characterized by the oblivious performance ratio that bounds the relative performance of the routing algorithm and the optimal routing algorithm for any given traffic demand. We consider both single path routing where the traffic between each source-destination pair follows one path, and multi-path routing where multiple paths can be used for the traffic between a source-destination pair. We derive lower bounds of the oblivious performance ratio of any single path routing scheme for fat-tree topologies and develop single path oblivious routing schemes that achieve the optimal oblivious performance ratio for commonly used fat-tree topologies. These oblivious routing schemes provide the best performance guarantees among all single path routing algorithms under uncertain traffic demands. For multi-path routing, we show that it is possible to obtain a scheme that is optimal for any traffic demand (an oblivious performance ratio of 1) on the fat-tree topology. These results quantitatively demonstrate that single path routing cannot guarantee high routing performance while multi-path routing is very effective in balancing network loads on the fat-tree topology.

We develop a message scheduling scheme for efficiently realizing all-to-all personalized communication (AAPC) on Ethernet switched clusters with one or more switches. To avoid network contention and achieve high performance, the message scheduling scheme partitions AAPC into phases such that 1) there is no network contention within each phase and 2) the number of phases is minimum. Thus, realizing AAPC with the contention-free phases computed by the message scheduling algorithm can potentially achieve the minimum communication completion time. In practice, phased AAPC schemes must introduce synchronizations to separate messages in different phases. We investigate various synchronization mechanisms and various methods for incorporating synchronizations into the AAPC phases. Experimental results show that the message scheduling-based AAPC implementations with proper synchronization consistently achieve high performance on clusters with many different network topologies when the message size is large

Message Passing Interface (MPI) collective communication routines are widely used in parallel applications. In order for a collective communication routine to achieve high performance for different applications on different platforms, it must be adaptable to both the system architecture and the application workload. Current MPI implementations do not support such software adaptability and are not able to achieve high performance on many platforms. In this paper, we present STAR-MPI (Self Tuned Adaptive Routines for MPI collective operations), a set of MPI collective communication routines that are capable of adapting to system architecture and application workload. For each operation, STAR-MPI maintains a set of communication algorithms that can potentially be efficient at different situations. As an application executes, a STAR-MPI routine applies the Automatic Empirical Optimization of Software (AEOS) technique at run time to dynamically select the best performing algorithm for the application on the platform. We describe the techniques used in STAR-MPI, analyze STAR-MPI overheads, and evaluate the performance of STAR-MPI with applications and benchmarks. The results of our study indicate that STAR-MPI is robust and efficient. It is able to and efficient algorithms with reasonable overheads, and it out-performs traditional MPI implementations to a large degree in many cases.

We consider unicast-based pipelined broadcast schemes for clusters connected by multiple Ethernet switches. By splitting a large broadcast message into segments and broadcasting the segments in a pipelined fashion, pipelined broadcast may achieve very high performance. We develop algorithms for computing various contention-free broadcast trees on Ethernet switched clusters that are suitable for pipelined broadcast, and evaluate the schemes through experimentation. The conclusions drawn from our theoretical and experimental study include the following. First, pipelined broadcast can be more effective than other common broadcast schemes including the ones used in the latest versions of MPICH and LAM/MPI when the message size is sufficiently large. Second, contention-free broadcast trees are essential for pipelined broadcast to achieve high performance. Finally, while it is difficult to determine the optimal message segment size for pipelined broadcast, finding one size that gives good performance is relatively easy.

An MPI collective operation involves multiple processes that may arrive at the operation at different times. We call such arrival timing the process arrival pattern. The process arrival pattern can significantly affect the performance of a collective operation since it decides the time when each process starts participating in the operation. We characterize the process arrival pattern in a set of MPI programs on two common cluster platforms, study it in a micro-benchmark with balanced loads, and evaluate its impacts on some collective communication algorithms. The results indicate that application developers cannot effectively control the process arrival patterns in cluster environments. Furthermore, the performance of communication algorithms is sensitive to process arrival patterns. Based on these observations, we conclude that, to develop MPI collective routines that can achieve high performance for practical applications in cluster environments, MPI developers must take the process arrival pattern into consideration.

Software designers face many challenges when developing applications for embedded systems. One major challenge is meeting the conflicting constraints of speed, code size, and power consumption. Embedded application developers often resort to hand-coded assembly language to meet these constraints since traditional optimizing compiler technology is usually of little help in addressing this challenge. The results are software systems that are not portable, less robust, and more costly to develop and maintain. Another limitation is that compilers traditionally apply the optimizations to a program in a fixed order. However, it has long been known that a single ordering of optimization phases will not produce the best code for every application. In fact, the smallest unit of compilation in most compilers is typically a function and the programmer has no control over the code improvement process other than setting flags to enable or disable certain optimization phases. This paper describes a new code improvement paradigm implemented in a system called VISTA that can help achieve the cost/performance trade-offs that embedded applications demand. The VISTA system opens the code improvement process and gives the application programmer, when necessary, the ability to finely control it. VISTA also provides support for finding effective sequences of optimization phases. This support includes the ability to interactively get static and dynamic performance information, which can be used by the developer to steer the code improvement process. This performance information is also internally used by VISTA for automatically selecting the best optimization sequence from several attempted. One such feature is the use of a genetic algorithm to search for the most efficient sequence based on specified fitness criteria. We include a number of experimental results that evaluate the effectiveness of using a genetic algorithm in VISTA to find effective optimization phase sequences.

We develop an all-to-all broadcast scheme that achieves maximum bandwidth efficiency for clusters with tree topologies. Using our scheme for clusters with cut-through switches, any tree topology can support all-to-all broadcast as efficiently as a single switch connecting all machines when the message size is sufficiently large. Since a tree topology can be embedded in almost any connected network, it follows that efficient all-to-all broadcast can be achieved in almost all topologies, regular or irregular. To perform all-to-all broadcast efficiently on clusters with store-and-forward switches, the algorithm must minimize the communication path lengths in addition to maximizing bandwidth efficiency. This turns out to be a harder algorithmic problem. We develop schemes that give solutions to common cases for such systems. The performance of our algorithms is evaluated on Ethernet switched clusters with different topologies. The results confirm our theoretical finding. Furthermore, depending on the topology, our algorithms sometimes out-perform the topology-unaware algorithms used in MPI libraries, including MPICH and LAM/MPI, to a very large degree

All-to-all personalized communication (AAPC) is one of the most commonly used communication patterns in parallel applications. Developing an efficient AAPC routine is difficult since many system parameters can affect the performance of an AAPC algorithm. In this paper, we investigate an empirical approach for automatically generating efficient AAPC routines for Ethernet switched clusters. This approach applies when the application execution environment is decided, and it allows efficient customized AAPC routines to be created. Experimental results show that the empirical approach generates routines that consistently achieve high performance on clusters with different network topologies. In many cases, the automatically generated routines out-perform conventional AAPC implementations to a large degree.

In order for collective communication routines to achieve high performance on different platforms, they must be able to adapt to the system architecture and use different algorithms for different situations. Current Message Passing Interface (MPI) implementations, such as MPICH and LAM/MPI, are not fully adaptable to the system architecture and are not able to achieve high performance on many platforms. In this paper, we present a system that produces efficient MPI collective communication routines. By automatically generating topology specific routines and using an empirical approach to select the best implementations, our system adapts to a given platform and constructs routines that are customized for the platform. The experimental results show that the tuned routines consistently achieve high performance on clusters with different network topologies.

Conditional branches are expensive. Branches require a significant percentage of execution cycles since they occur frequently and cause pipeline flushes when mispredicted. In addition, branches result in forks in the control flow, which can prevent other code-improving transformations from being applied. In this paper we describe profile-based techniques for replacing the execution of a set of two or more branches with a single branch on a conventional scalar processor. These sets of branches can include tests of multiple variables. For instance, the test if (p1 != 0 && p2 != 0), which is testing for NULL pointers, can be replaced with if (p1 & p2 != 0). Program profiling is performed to target condition merging along frequently executed paths. The results show that eliminating branches by merging conditions can significantly reduce the number of conditional branches executed in non-numerical applications. Copyright © 2004 John Wiley & Sons, Ltd.

We study the quality-of-service (QoS) schemes that make routing decisions based on empirical resource availability probability information. These empirical probability based routing schemes offer better performance than the traditional schemes that make routing decisions based on resource availability information when the global network state information is imprecise. We investigate variations of empirical probability based QoS routing, present a number of schemes to explicitly maintain the resource availability probability information, and evaluate the performance of the routing schemes. We conclude that the performance of empirical probability based routing is insensitive to the frequency of probability information updates and that empirical probability based routing can achieve good performance without introducing excessive overheads.

No abstract available.

Compiled communication has recently been proposed to improve communication performance for clusters of workstations. The idea of compiled communication is to apply more aggressive optimizations to communications whose information is known at compile time. Existing MPI libraries do not support compiled communication. In this paper, we present an MPI prototype, CC--MPI, that supports compiled communication on Ethernet switched clusters. The unique feature of CC--MPI is that it allows the user to manage network resources such as multicast groups directly and to optimize communications based on the availability of the communication information. CC--MPI optimizes one--to--all, one--to--many, all--to--all, and many--to--many collective communication routines using the compiled communication technique. We describe the techniques used in CC--MPI and report its performance. The results show that communication performance of Ethernet switched clusters can be significantly improved through compiled communication.

We investigate the compiler algorithms to support compiled communication in multiprocessor environments and study the benefits of compiled communication, assuming that the underlying network is an all-optical time-division-multiplexing (TDM) network. We present an experimental compiler, E-SUIF, that supports compiled communication for High Performance Fortran (HPF) like programs on all-optical TDM networks, and describe and evaluate the compiler algorithms used in E-SUIF. We further demonstrate the effectiveness of compiled communication on all-optical TDM networks by comparing the performance of compiled communication with that of a traditional communication method using a number of application programs.

Optical wavelength division multiplexing (WDM) rings are being deployed to support SONET/SDH self-healing rings. The cost of such a system is dominated by the SONET add/drop multiplexers (ADM). To minimize the system cost, algorithms must be developed to assign wavelengths to lightpaths in the system so that the number of ADM required is minimized. This problem of optimal wavelength assignment to minimize the number of SONET ADM is NP-hard. In this paper, we develop an integer linear programming (ILP) formation for this problem, propose a new wavelength assignment heuristic, and evaluate the existing and the newly proposed heuristic using the ILP formation. We conclude that the performance of the newly proposed heuristic is very close to optimal.

In large networks, maintaining precise global network state information is almost impossible. Many factors, including non-negligible propagation delay, infrequent link state update due to overhead concerns, link state update policy, resource reservation, and hierarchical topology aggregation, have impacts on the precision of the global network state information. To achieve efficient quality of service (QoS) routing, a practical routing algorithm must be able to make effective routing decisions in the presence of imprecise global network state information. In this paper, we compare five QoS routing algorithms that were proposed to tolerate imprecise global network state information, safety-based routing, randomized routing, multi-path routing, localized routing, and static multi-path routing. The performance of these routing algorithms are evaluated under two link state update policies, the timer based policy and the threshold based policy. The strengths and limitations of each scheme are identified.

Multiconstrained quality-of-service (QoS) routing deals with finding routes that satisfy multiple independent QoS constraints. This problem is NP-hard. Two heuristics, the limited granularity heuristic and the limited path heuristic, are investigated. Both heuristics extend the Bellman-Ford shortest path algorithm and solve general k-constrained QoS routing problems. Analytical and simulation studies are conducted to compare the time/space requirements of the heuristics and the effectiveness of the heuristics in finding paths that satisfy the QoS constraints. The major results of this paper are the following. For an N-nodes and E-edges network with k (a small constant) independent QoS constraints, the limited granularity heuristic must maintain a table of size O(|N|/sup k-1/) in each node to be effective, which results in a time complexity of O(|N|/sup k/|E|), while the limited path heuristic can achieve very high performance by maintaining O(|N|/sup 2/lg(|N|)) entries in each node. These results indicate that the limited path heuristic is relatively insensitive to the number of constraints and is superior to the limited granularity heuristic in solving k-constrained QoS routing problems when k>3.

In this paper, we study distributed path reservation protocols for multiplexed all-optical interconnection networks. The path reservation protocols negotiate the reservation and establishment of connections that arrive dynamically to the network. These protocols can be applied to both wavelength division multiplexing (WDM) and time division multiplexing (TDM) networks. Two classes of protocols are discussed: forward reservation protocols and backward reservation protocols. Simulations of multiplexed two-dimensional torus interconnection networks are used to evaluate and compare the performance of the protocols and to study the impact of system parameters, such as the multiplexing degree and the network size, speed, and load, on both network throughput and communication delay. The simulation results show that, in most cases, the backward reservation schemes provide better performance than their forward reservation counterparts.

We consider multihop communications on optical torus networks with time-division multiplexing where logical topologies are realized on top of the physical network to improve the communication performance. The logical topologies reduce the number of intermediate hops at the cost of a larger multiplexing degree. On the one hand, the larger multiplexing degree increases the packet communication time between hops. On the other hand, reducing the number of intermediate hops reduces the time spent at intermediate hops. We study the trade-off between the multiplexing degree and the number of intermediate hops. Specifically, we study four logical topologies ranging from the most dense logical all-to-all connections to the simplest logical torus topology on top of physical torus networks. We develop an analytical model that models the maximum throughput and the average packet delay of the multihop networks, verify the model through simulations, and study the performance and the impact of system parameters on the performance for these four topologies.

In this paper, we study distributed path reservation protocols for multiplexed all-optical interconnection networks. In such networks, a path for a connection is reserved such that transmitted data remains in the optical domain until it reaches its destination. The path reservation protocols negotiate the reservation and establishment of connections that arrive dynamically to the network. They can be applied to both wavelength division multiplexing (WDM) and time division multiplexing (TDM), which are two techniques that allow the large optical bandwidth to be shared among multiple connections. Two classes of protocols are discussed: forward reservation protocols and backward reservation protocols. Simulations of multiplexed 2-dimensional torus interconnection networks are used to evaluate and compare the performance of the protocols, and to study the impact of system parameters on both network throughput and communication delay. The simulation results show that the backward reservation schemes provide better performance than their forward reservation counterparts.

While all-optical networks offer large bandwidth for transferring data, the control mechanisms to dynamically establish all-optical paths incur large overhead. In this paper, we consider the problem of adapting all-optical multiplexed networks in multiprocessor or multicomputer environment by using compiled communication as an alternative to dynamic network control. In compiled communication, the network resources are managed statically and therefore, run time control overhead is eliminated. In addition, complex offline algorithms can be incorporated to manage the network resources more efficiently. We studied several off-line connection scheduling algorithms for optimizing the multiplexing degree required to satisfy communication requests. The performance of compiled communication for communication patterns that can be determined at compile time in application programs is evaluated and compared with dynamically controlled communication assuming a two-dimmension torus topology. Our results show that the compiled communication out-performs the dynamic communication to a large degree for these communication patterns. Since most of the communication patterns in parallel applications can be determined at compile time, we conclude that compiled communication is an effective mechanism for all-optical network in multiprocessor environments.