YINS/EE Seminar

“A Mathematical Theory of QoS: Flows, Incremental Paths and Optimal Greedy Algorithms”

Speaker: Jordi Ros-Giralt
Reservoir Labs, Inc., New York 

Abstract: In this talk we introduce a mathematical theory of QoS, a newly developed theoretical framework that reveals new insights about the topological properties of data networks. The theory tackles several problems related to networks, flows and quality of service (QoS) that have either being elusive or unaddressed. As an initial contribution, we provide the first mathematically formal definition of the concept of elephant flow and a first greedy algorithm to identify all elephant flows in networks that target max-min fairness such as those running TCP’s congestion control. Unlike existing approaches which have measured the size of a flow based on a variety of metrics such as rate, byte counts, duration or jitter, we show that a precise mathematical description of the concept of flow size depends on the topological structure of the network and a utility function characterizing the QoS delivered by the network. The theory shows that all existing solutions to the problem of elephant flow detection are implicitly assuming a single bottleneck-link topology-thus not reflecting the true nature of real networks-and introduces a first polynomial algorithm to resolve the general multi-bottleneck problem. The theory however stands general in that it provides a fresh new look to the problem of network QoS optimization. In traditional network optimization, the topology is assumed static, and the objective is to find optimal routes (routing problem) and optimal flow transmission rates (congestion control problem). The proposed theory of QoS generalizes this view by allowing also to identify modifications in the topological structure of a network (the feasible set) that lead to better QoS performance. To put the theory to the test, we apply it to resolve the max-min/max-flow rate allocation problem. While max-min has been a preferred objective in modern congestion control protocols, it is well-known that such criterion can be suboptimal in terms of the max-flow objective-a measure of global network welfare regardless of fairness. The theory provides a framework to study the topological changes that need to be applied onto a network in order to maximally increase the total flow rate while maintaining fairness, providing new insights to operators in the design of modern data networks.

Speaker bio: Jordi Ros-Giralt, Ph.D.  is a computer scientist with expertise in Network Optimization and High-Performance Computing. In his Ph.D. thesis Jordi formulated and resolved the problem of lexicographic optimization for distributed networks, providing a theory and a suite of practical distributed protocols for unicast, multicast, multipath and discrete networks. Subsequently he worked on the problems of high speed packet processing and IP convergence, inventing a seamless IP mobility protocol and an ad hoc, unmanned VoIP distributed system for mobile virtual network operators (MVNO). Jordi has been active both in academia and in the corporate world where he has helped to found several start ups. He is the main developer and founder of the platform Labdoo.org that brings educational laptops to more than 1000 schools around the world. Jordi is the 2017 Alan Turing Award for Social Impact from the Computer Science Association of Catalonia. He received his Ph.D. in computer science and MBA from the University of California, and a B.Sc. in Telecommunications Engineering from BarcelonaTech. Jordi works at Reservoir Labs developing next generation network analysis and traffic engineering technologies.

Hosted by: Professor Leandros Tassiulas

.