On the Bottleneck Structure of Congestion-Controlled Networks
June 8, 2020
In this paper, we introduce the Theory of Bottleneck Ordering, a
mathematical framework that reveals the bottleneck structure of
data networks. This theoretical framework provides insights into
the inherent topological properties of a network at least in three
areas: (1) It identifies the regions of influence of each bottleneck; (2)
it reveals the order in which bottlenecks (and flows traversing them)
converge to their steady state transmission rates in distributed
congestion control algorithms; and (3) it provides key insights to
the design of optimized traffic engineering policies. We demonstrate
the efficacy of the proposed theory in TCP congestion-controlled
networks for two broad classes of algorithms: congestion-based
algorithms (BBR) and loss-based additive-increase/multiplicative-decrease
algorithms (Cubic and Reno). Among other results, our
network experiments show that: (1) Qualitatively, both classes of
congestion control algorithms behave as predicted by the bottleneck
structure of the network; (2) flows compete for bandwidth only
with other flows operating at the same bottleneck level; (3) BBR
flows achieve higher performance and fairness than Cubic and Reno
flows due to their ability to operate at the right bottleneck level;
(4) the bottleneck structure of a network is ever-changing and its
levels can be folded due to variations in the flows’ round trip times;
and (5) against conventional wisdom, low-hitter flows can have a
large impact to the overall performance of a network.
Google Scholar • Article
Uniform Random Sampling in Polyhedra
January 22, 2020
We propose a method for generating uniform samples among
a domain of integer points defined by a polyhedron in a multidimensional space. The method extends to domains defined
by parametric polyhedra, in which a subset of the variables
are symbolic. We motivate this work by a list of applications
for the method in computer science. The proposed method
relies on polyhedral ranking functions, as well as a recent
inversion method for them, named trahrhe expressions.
Google Scholar • Article
Systems and Methods for Minimizing Communications
December 3, 2019
A system for allocation of one or more data structures used in a program across a number of processing units takes into account a memory access pattern of the data structure, and the amount of total memory available for duplication across the several processing units. Using these parameters duplication factors are determined for the one or more data structures such that the cost of remote communication is minimized when the data structures are duplicated according to the respective duplication factors while allowing parallel execution of the program.
Google Scholar • Article
G2: A Network Optimization Framework for High-Precision Analysis of Bottleneck and Flow Performance
November 17, 2019
Congestion control algorithms for data networks have been the subject of intense research for the last three decades. While most of the work has focused around the characterization of a flow’s bottleneck link, understanding the interactions amongst links and the ripple effects that perturbations in a link can cause on the rest of the network has remained much less understood. The Theory of Bottleneck Ordering is a recently developed mathematical framework that reveals the bottleneck structure of a network and provides a model to understand such effects. In this paper we present G2, the first operational network optimization framework that utilizes this new theoretical framework to characterize with high-precision the performance of bottlenecks and flows. G2 generates an interactive graph structure that describes how perturbations in links and flows propagate, providing operators new optimization insights and traffic engineering recommendations to help improve network performance. We provide a description of the G2 implementation and a set of experiments using real TCP/IP code to demonstrate its operational efficacy.
This paper has not yet been published. If you would like to receive a copy once available, please contact us or check back here after the 2019 SuperComputing Conference. For more information on G2 technology, visit https://www.reservoir.com/research/tech/networking/.Systems and Methods for Efficient Targeting
November 5, 2019
A system for determining the physical path of an object can map several candidate paths to a suitable path space that can be explored using a convex optimization technique. The optimization technique may take advantage of the typical sparsity of the path space and can identify a likely physical path using a function of sensor observation as constraints. A track of an object can also be determined using a track model and a convex optimization technique.
Google Scholar • Article
