Efficient optimization techniques for traffic engineering
Abstract/Contents
- Abstract
- Many enterprises today manage their Internet traffic on their wide-area networks (WANs) using software-defined traffic engineering to route traffic and allocate bandwidth optimally. This approach, however, scales poorly with network size; as the network grows, the algorithmic runtimes scale super-linearly, and they struggle to keep pace with changing traffic demands in the WAN. Simple heuristics can reduce the runtime but come at the expense of optimality: they lead to poor utilization and suboptimal performance. In this talk, we demonstrate how we can leverage clever partitioning strategies in the network to develop new, more scalable algorithms for traffic engineering that provide a better trade-off between runtime and optimality. We first present NCFlow, short for Network Contractions for Flow Problems. NCFlow uses a geographic partitioning strategy to modify the original problem and solve (1) a reduced problem on a contraction of the network, and (2) a set of sub-problems in parallel on disjoint clusters within the network. We also present POP, short for Partitioned Optimized Problems. Unlike NCFlow, POP uses a commodity-based partitioning strategy—it randomly splits the original traffic engineering problem into smaller, independent but identical sub-problems, solves them in parallel, and then coalesces the results into a single solution. We discuss the advantages and disadvantages of these two algorithms. Furthermore, we show that, on a large cloud provider's WAN traffic, as well as on publicly available WAN topologies, both NCFlow and POP nearly match the solution quality of currently deployed solutions, but are 11x faster in the median case, and up to 1,900x faster in the best case.
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 | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Abuzaid, Firas Maher |
|---|---|
| Degree supervisor | Bailis, Peter |
| Degree supervisor | Zaharia, Matei |
| Thesis advisor | Bailis, Peter |
| Thesis advisor | Zaharia, Matei |
| Thesis advisor | Prabhakar, Balaji, 1967- |
| Degree committee member | Prabhakar, Balaji, 1967- |
| Associated with | Stanford University, Computer Science Department |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Firas Abuzaid. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/nj221cf1818 |
Access conditions
- Copyright
- © 2022 by Firas Maher Abuzaid
- 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...