A Mathematical Framework for the Detection of Elephant Flows



Publication Source: Extended Mathematical Report

How large is a network flow? Traditionally this question has been addressed by using metrics such as the number of bytes, the transmission rate or the duration of a flow. We reason that a formal mathematical definition of flow size should account for the impact a flow has on the performance of a network: flows that have the largest impact, should have the largest size. In this paper we present a theory of flow ordering that reveals the connection between the abstract concept of flow size and the QoS properties of a network. The theory is generalized to accommodate for the case of partial information, allowing us to model real computer network scenarios such as those found in involuntary lossy environments or voluntary packet sampling protocols (e.g., sFlow). We explore one application of this theory to address the problem of elephant flow detection at very high speed rates. The algorithm uses the information theoretic properties of the problem to help reduce the computational cost by a factor of one thousand.
Article

Report of the 2014 Runtime Systems Summit



Publication Source: U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research (ASCR)

This report summarized runtime system challenges for exascale computing, that follow from the fundamental challenges for exascale systems. Some of the key exascale challenges that pertain to runtime systems include parallelism, energy efficiency, memory hierarchies, data movement, heterogeneous processors and memories, resilience, performance variability, dynamic resource allocation, performance portability, and interoperability with legacy code. In addition to summarizing these challenges, the report also outlined different approaches to addressing these significant challenges that have been pursued by research projects in the DOE-sponsored X-Stack and OS/R programs. It also included a chapter on deployment opportunities for vendors and government labs to build on the research results from these projects.
Article

Report of the 2014 Programming Models & Environments Summit



Publication Source: U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research (ASCR)

Programming models and environments play the essential roles in high performance computing of enabling the conception, design, implementation and execution of science and engineering application codes. This report presents the topics discussed and results from the 2014 DOE Office of Science Advanced Scientific Computing Research (ASCR) Programming Models & Environments Summit, and subsequent discussions among the summit participants and contributors to topics in this report.
Article

Polyhedral Compilation for Energy Efficiency



Publication Source: 2016 IEEE High Performance Extreme Computing Conference (HPEC '16), Waltham, MA, USA.

In the last decade, the scope of software optimizations expanded to encompass energy consumption on top of the classical runtime minimization objective. In that context, several optimizations have been developed to improve the software energy efficiency. However, these optimizations commonly rely on long profiling steps and are often implemented as unstable runtime systems, which limits their applicability. We propose in this paper a new energy model and two associated energy optimizations that can be performed at compilation time, without having to profile the compiled programs. The model predicts the energy consumption of programs at compilation time using the precise software representation available in the polyhedral model. The energy model is then used at the core of two compiler optimizations to generate more efficient programs. The model and the two optimizations have been implemented in the R-Stream compiler.
Article

High-Performance Algorithms and Data Structures to Catch Elephant Flows



Publication Source: 2016 IEEE High Performance Extreme Computing Conference (HPEC '16), Waltham, MA, USA.

In high-speed networks, it is important to detect the presence of large flows—also known as elephant flows— because of their adverse effects on delay-sensitive flows. If detected on a timely fashion, network operators can apply active policies such as flow redirection or traffic shaping to ensure the overall quality of service of the network is preserved. Towards this objective, we develop a high-performance data structure and algorithm to address the problem of detecting large flows at very high-speed rates. Our solution leverages the concept of optimal sampling rate under partial information to avoid the need for processing every single packet on the network. With this strategy, we present a prototype of a high-performance network sensor capable of processing traffic rates at 100Gbps and detect the largest flows with high accuracy.
Article

1 2 3 13