Proactive congestion control
Abstract/Contents
- Abstract
- Most congestion control algorithms rely on a reactive control system that detects congestion and then marches carefully toward a desired operating point (e.g., by modifying the window size or picking a rate). These algorithms often take hundreds of RTTs to converge—an increasing problem in networks with short-lived flows. Motivated by the need for fast congestion control, this thesis focuses on a different class of congestion control algorithms, called proactive explicit rate-control (PERC) algorithms, which decouple the rate calculation from congestion signals in the network. The switches and NICs exchange control messages to run a distributed algorithm to pick explicit rates for each flow. PERC algorithms proactively schedule flows to be sent at certain explicit rates. They take as input the set of flows and the network link speeds and topology, but not a congestion signal. As a result, they converge faster and their convergence time depends only on fundamental "dependency chains, " essentially couplings between links that carry common flows, that are a property of the traffic matrix and the network topology. We argue that congestion control should converge in a time limited only by fundamental dependency chains. Our main contribution is s-PERC: a new practical distributed proactive scheduling algorithm. It is the first PERC algorithm to provably converge in bounded time without requiring per-flow state or network synchronization. It converges to the exact max-min fair allocation in 6N rounds (where N is the number of links in the longest dependency chain). In simulation and on a P4-programmed FPGA hardware test bed, s-PERC converges an order of magnitude faster than reactive schemes such as TCP, DCTCP, and RCP. Long flows complete in close to the ideal time, while while short-lived flows are prioritized, making it relevant for data centers and wide-area networks (WANs).
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2019; ©2019 |
| Publication date | 2019; 2019 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Jose, Lavanya |
|---|---|
| Degree supervisor | McKeown, Nick |
| Thesis advisor | McKeown, Nick |
| Thesis advisor | Alizadeh, Mohammad, (Professor) |
| Thesis advisor | Katti, Sachin |
| Degree committee member | Alizadeh, Mohammad, (Professor) |
| Degree committee member | Katti, Sachin |
| Associated with | Stanford University, Computer Science Department. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Lavanya Jose. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2019. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2019 by Lavanya Jose
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...