Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFatPaths: Routing in Supercomputers and Data Centers when Shortest Paths Fall Short
144
0
0.0
(
0
)
Added by
Maciej Besta
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We introduce FatPaths: a simple, generic, and robust routing architecture that enables state-of-the-art low-diameter topologies such as Slim Fly to achieve unprecedented performance. FatPaths targets Ethernet stacks in both HPC supercomputers as well as cloud data centers and clusters. FatPaths exposes and exploits the rich (fat) diversity of both minimal and non-minimal paths for high-performance multi-pathing. Moreover, FatPaths uses a redesigned purified transport layer that removes virtually all TCP performance issues (e.g., the slow start), and incorporates flowlet switching, a technique used to prevent packet reordering in TCP networks, to enable very simple and effective load balancing. Our design enables recent low-diameter topologies to outperform powerful Clos designs, achieving 15% higher net throughput at 2x lower latency for comparable cost. FatPaths will significantly accelerate Ethernet clusters that form more than 50% of the Top500 list and it may become a standard routing scheme for modern topologies.
rate research
Read More
In 1903, noted puzzle-maker Henry Dudeney published The Spider and the Fly puzzle, which asks for the shortest path along the surfaces of a square prism between two points (source and target) located on the square faces, and surprisingly showed that the shortest path traverses five faces. Dudeneys source and target points had very symmetrical locations; in this article, we allow the source and target points to be anywhere in the interior of opposite faces, but now require the square prism to be a cube. In this context, we find that, depending on source and target locations, a shortest path can traverse either three or four faces, and we investigate the conditions that lead to four-face solutions and estimate the probability of getting a four-face shortest path. We utilize a combination of numerical calculations, elementary geometry, and transformations we call corner moves of cube unfolding diagrams,
With the growth of demands for quasi-instantaneous communication services such as real-time video streaming, cloud gaming, and industry 4.0 applications, multi-constraint Traffic Engineering (TE) becomes increasingly important. While legacy TE management planes have proven laborious to deploy, Segment Routing (SR) drastically eases the deployment of TE paths and thus became the most appropriate technology for many operators. The flexibility of SR sparked demands in ways to compute more elaborate paths. In particular, there exists a clear need in computing and deploying Delay-Constrained Least-Cost paths (DCLC) for real-time applications requiring both low delay and high bandwidth routes. However, most current DCLC solutions are heuristics not specifically tailored for SR. In this work, we leverage both inherent limitations in the accuracy of delay measurements and an operational constraint added by SR. We include these characteristics in the design of BEST2COP, an exact but efficient ECMP-aware algorithm that natively solves DCLC in SR domains. Through an extensive performance evaluation, we first show that BEST2COP scales well even in large random networks. In real networks having up to thousands of destinations, our algorithm returns all DCLC solutions encoded as SR paths in way less than a second.
Physarum Polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s0 and s1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s0 - s1 path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by the biologists and can be seen as an example of a natural algorithm, that is, an algorithm developed by evolution over millions of years.
The power consumption of enormous network devices in data centers has emerged as a big concern to data center operators. Despite many traffic-engineering-based solutions, very little attention has been paid on performance-guaranteed energy saving schemes. In this paper, we propose a novel energy-saving model for data center networks by scheduling and routing deadline-constrained flows where the transmission of every flow has to be accomplished before a rigorous deadline, being the most critical requirement in production data center networks. Based on speed scaling and power-down energy saving strategies for network devices, we aim to explore the most energy efficient way of scheduling and routing flows on the network, as well as determining the transmission speed for every flow. We consider two genera
In this paper, we consider the IoT data discovery problem in very large and growing scale networks. Specifically, we investigate in depth the routing table summarization techniques to support effective and space-efficient IoT data discovery routing. Novel summarization algorithms, including alphabetical based, hash based, and meaning based summarization and their corresponding coding schemes are proposed. The issue of potentially misleading routing due to summarization is also investigated. Subsequently, we analyze the strategy of when to summarize in order to balance the tradeoff between the routing table compression rate and the chance of causing misleading routing. For experimental study, we have collected 100K IoT data streams from various IoT databases as the input dataset. Experimental results show that our summarization solution can reduce the routing table size by 20 to 30 folds with 2-5% increase in latency when compared with similar peer-to-peer discovery routing algorithms without summarization. Also, our approach outperforms DHT based approaches by 2 to 6 folds in terms of latency and traffic.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
