Contracting Wide-area Network Topologies to Solve Flow Problems Quickly

on YouTube ↗13m

" summary

NCFlow contracts the WAN into clusters and replaces the full multi-commodity LP with a tiny aggregated inter-cluster flow plus parallel per-cluster subproblems, contracts the WAN into clusters, bundles inter-cluster demands into single aggregated edges, selects one inter-cluster link per cluster pair and iteratively shuffles assignments to avoid conflicts. On Azure and public topologies it reaches a median 98% of optimal total flow while running 8x faster and using 6x fewer FIB entries (maximum speedups up to 1300x) and can recompute after failures in ~10 ms.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 0:29Traffic Engineering
3. 1:28Slow Traffic Engineering
4. 3:50Clustering
5. 6:14Solving per cluster
6. 8:11Solution
7. 9:55Recap
8. 10:27Results

" related talks

• 14mOneWAN Traffic Engineering: Unifying Inter-Datacenter and Internet BackbonesUmesh Krishnaswamy · Networking @Scale Fall 2022
• 21mTransparent and Flexible Network Management for Big Data Processing in the CloudAnupam Das, Cristian Lumezanu, Yueping Zhang, Vishal Singh, Guofei Jiang, Curtis Yu · HotCloud '13
• 15mMitigating Scalability Walls of RDMA-based Container NetworksEnnan Zhai, Tianyin Xu, Wei Liu, Feng Qian, Yunhao Liu, Yu Guan, Kun Qian, Zhenhua Li, Lanlan Xi, Shuhong Zhu, Hongfei Xu, Chao Qin · NSDI '25
• 17mNetHint: White-Box Networking for Multi-Tenant Data CentersWei Zhang, Ion Stoica, Jingrong Chen, Danyang Zhuo, Hong Zhang, Liang Luo, Jeffrey Chase · 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22)
• 16mOneWAN is better than two: Unifying a split WAN architectureUmesh Krishnaswamy, Nikolaj Bjørner, Erica Lan, Rachee Singh, Himanshu Raj, Srikanth Kandula, Paul Mattes, Paul-Andre C Bissonnette, Zahira Nasrin, Sonal Kothari, Prabhakar Reddy, John Abeln, Luis Irun-Briz, Jamie Gaudette · NSDI 2023
• 16mOptimizing Network Provisioning through CooperationRanjita Bhagwan, Yogesh Bansal, Harsha Sharma, Parth Thakkar, Sagar Bharadwaj, Venkata N. Padmanabhan, Vijay Kumar, Kathleen Voelbel · 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22)
• 17mTopoOpt: Co-optimizing Network Topology and Parallelization Strategy for Distributed...Ying Zhang, Zhihao Jia, Manya Ghobadi, Dheevatsa Mudigere, Weiyang Wang, Moein Khazraee, Zhizhen Zhong, Anthony Kewitsch · NSDI 2023
• 21mTowards An Application Objective-Aware Network InterfaceBrighten Godfrey, Sangeetha Abdu Jyothi, Sayed Hadi Hashemi, Roy Campbell · HotCloud '20