Doctoral Thesis Proposal - Anup Agarwal

— 12:30pm

Location:
In Person and Virtual - ET - Reddy Conference Room, Gates Hillman 4405 and Zoom

Speaker:
ANUP AGARWAL, Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://www.cs.cmu.edu/~anupa/

Designing Network Control Algorithms with Performance Guarantees

Control algorithms, such as those used in congestion control (CC) and adaptive-bitrate (ABR) streaming, make critical decisions that influence performance, user experience, and revenue in networked applications. Despite their importance, these algorithms are often developed through heuristics and intuition, leading to implicit assumptions about network environments and a lack of formal guarantees about their performance. The result is anywhere from silent to embarrassing performance degradation (e.g., the recent Netflix livestream of Paul vs Tyson).

In this proposed thesis, we design tools (both mathematical and computational) that make formal performance guarantees possible. Network control algorithms often operate in partially observable environments, e.g., they do not explicitly know the network topology, routing, link capacities, or what other flows they share the network with. The mathematical tools allow us to reason about what information algorithms may infer from their partial observations. The computational tools build on these mathematical tools to semi-automate the design of control algorithms, using techniques from program synthesis, and game theory. By combining our tools with techniques in network calculus and formal methods, we precisely state performance objectives and environment assumptions, enabling us to construct proofs about the performance of the designed control algorithms.

Through this work, we design new CC algorithms that provide performance bounds on networks where existing algorithms struggle to guarantee even 1% utilization. Our systematic methodology also led us to discover and prove new fundamental tradeoffs in congestion control, including a tradeoff between loss and convergence time on networks with jitter and short buffers, and a tradeoff between fairness and robustness vs. latency and generality of CC algorithms.

The majority of the completed work deals with single-agent congestion control. In the proposed work, we extend our tools to reason about multi-agent control environments and ABR algorithms. 

Thesis Committee

Srinivasan Seshan (Chair)
Vyas Sekar
Justine Sherry
Philip Brighten Godfrey (University of Illinois Urbana-Champaign)


Additional Information

In Person and Zoom Participation.  See announcement.

Event Website:
https://csd.cmu.edu/calendar/doctoral-thesis-proposal-anup-agarwal