An official website of the United States government
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.
more »
« less
Hop-constrained oblivious routing
We prove the existence of an oblivious routing scheme that is poly(logn)-competitive in terms of (congestion + dilation), thus resolving a well-known question in oblivious routing. Concretely, consider an undirected network and a set of packets each with its own source and destination. The objective is to choose a path for each packet, from its source to its destination, so as to minimize (congestion + dilation), defined as follows: The dilation is the maximum path hop-length, and the congestion is the maximum number of paths that include any single edge. The routing scheme obliviously and randomly selects a path for each packet independent of (the existence of) the other packets. Despite this obliviousness, the selected paths have (congestion + dilation) within a poly(logn) factor of the best possible value. More precisely, for any integer hop-bound h, this oblivious routing scheme selects paths of length at most h · poly(logn) and is poly(logn)-competitive in terms of congestion in comparison to the best possible congestion achievable via paths of length at most h hops. These paths can be sampled in polynomial time. This result can be viewed as an analogue of the celebrated oblivious routing results of R'acke [FOCS 2002, STOC 2008], which are O(logn)-competitive in terms of congestion, but are not competitive in terms of dilation.
more »
« less
- PAR ID:
- 10271618
- Date Published:
- Journal Name:
- Symposium on Theory of Computing (STOC)
- Page Range / eLocation ID:
- 1208 to 1220
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)The Jellyfish network has recently been proposed as an alternative to the fat-tree network for data centers and high-performance computing clusters. Jellyfish uses a random regular graph as its switch-level topology and has shown to be more cost-effective than fat-trees. Effective routing on Jellyfish is challenging. It is known that shortest path routing and equal cost multi-path routing (ECMP) do not work well on Jellyfish. Existing schemes use variations of k-shortest path routing (KSP). In this work, we study two routing components for Jellyfish: path selection that decides the paths to route traffic, and routing mechanisms that decide which path to be used for each packet. We show that the performance of the existing KSP can be significantly improved by incorporating two heuristics, randomization and edge-disjointness. We evaluate a range of routing mechanisms, including traffic oblivious and traffic adaptive schemes, and identify an adaptive routing scheme with noticeably higher performance than others.more » « less
-
Routing solutions for multi-hop underwater wireless sensor networks suffer significant performance degradation as they fail to adapt to the overwhelming dynamics of underwater environments. To respond to this challenge, we propose a new data forwarding scheme where relay selection swiftly adapts to the varying conditions of the underwater channel. Our protocol, termed CARMA for Channel-aware Reinforcement learning-based Multi-path Adaptive routing, adaptively switches between single-path and multi-path routing guided by a distributed reinforcement learning framework that jointly optimizes route-long energy consumption and packet delivery ratio. We compare the performance of CARMA with that of three other routing solutions, namely, CARP, QELAR and EFlood, through SUNSET-based simulations and experiments at sea. Our results show that CARMA obtains a packet delivery ratio that is up to 40% higher than that of all other protocols. CARMA also delivers packets significantly faster than CARP, QELAR and EFlood, while keeping network energy consumption at bay.more » « less
-
A Mobile Ad-hoc Network (MANET) is a collection of nodes that communicate with each other wirelessly without any central support or conventional structure. The transmission of data packets over wireless channels in MANETs helps to maintain communication. Ad-hoc On-Demand Distance Vector Routing is a reactive routing protocol associated with MANET which creates a route to destination by broadcasting route request packets through the entire network. A link failure in this type of protocol causes the source to flood the network with these Route Request packets that leads to congestion in the network and performance degradation. This paper proposes an Efficient Multipath AODV routing algorithm that determines if a node in a network is relaying or is silent in the process of route discovery to send data packets from the source to destination. Simulation results show the proposed routing algorithm controls congestion and enhances performance in the network as not all network nodes have to participate in the route discovery for a particular source-destination pair.more » « less
-
Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We address multicommodity buy-at-bulk network design in the nonuniform setting. Existing poly-logarithmic approximations are based on the junction tree approach [Chekuri et al., 2010; Guy Kortsarz and Zeev Nutov, 2011]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [Chekuri et al., 2010]. The rounding is based on recent results in hop-constrained oblivious routing [Ghaffari et al., 2021], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buy-at-bulk network design is based on an LP-based reduction to h-hop constrained network design for which we obtain LP-based bicriteria approximation algorithms. We also consider a fault-tolerant version of h-hop constrained network design where one wants to design a low-cost network to guarantee short paths between a given set of source-sink pairs even when k-1 edges can fail. This model has been considered in network design [Luis Gouveia and Markus Leitner, 2017; Gouveia et al., 2018; Arslan et al., 2020] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the single-source setting for any fixed k. We build upon the single-source algorithm and the junction-tree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3406325.3451098
