Guaranteeing Timeliness Via Prices...

on YouTube ↗25m

" summary

Claims a decentralized, provably optimal scheduler for low‑latency multi‑hop millimeter‑wave networks that meet hard end‑to‑end deadlines by maximizing weighted timely throughput under average per‑node concurrency (power) limits. Uses Lagrange multipliers to turn average constraints into per‑packet prices lambda and converts scheduling into small dynamic programs per packet with link success probabilities p_ij, reducing exponential state to a tractable linear program. Notes FCC release of 10.85 GHz (plus proposed 18 GHz), needs randomization and applies Whittle relaxation for peak limits, yielding asymptotically near‑optimal truncation.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 2:21Multi-hop network
3. 3:17Nodal constraints
4. 4:22Two challenges
5. 4:49Informational challenge of optimally scheduling a distributed system
6. 6:15Computational difficulty of determining optimal policy for scheduling entire network
7. 7:33Objective function
8. 10:32Decoupled packet level decision making
9. 12:26Optimal distributed solution
10. 13:21Need for randomization
11. 14:17One way to obtain prices
12. 14:53How can we exploit all this structure to determine the complete solution?
13. 16:06Exploit Solution Structure: Combine Single- Packet Transportation Problems of all Flows
14. 17:49Peak Power Constraint
15. 19:51Comparison with seminal work on Max Weight and Backpressure Policies
16. 20:38Example: Explicit solution
17. 21:20Example: Numerical Computation and Simulation Comparison

" related talks

• 16mGearbox: A Hierarchical Packet Scheduler for Approximate Weighted Fair QueuingPeixuan Gao, Anthony Dalleggio, Yang Xu, H. Jonathan Chao · 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22)
• 15mLaw: Towards Consistent Low Latency in 802.11 Home NetworksZili Meng, Yibin Shen · NSDI '26
• 17mTowards provably performant congestion controlRuben Martins, Anup Agarwal, Srinivasan Seshan, Venkat Arun, Devdeep Ray · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 34mDeterministic Networking for Real-Time Systems (Using TSN)Henrik Austad · Open Source Summit Europe + Embedded Linux Conference Europe 2017
• 50mThe Road Towards a Linux TSN InfrastructureJesus Sanchez-Palencia · Embedded Linux Conference + OpenIoT Summit North America 2018
• 16mTowards Optimal Rack-scale μs-level CPU Scheduling through In-Network Workload...Kai Chen, Hao Wang, Han Tian, Xudong Liao, Junxue Zhang, Guyue Liu, Xinchen Wan, Chaoliang Zeng, Mengyu Ma · USENIX ATC '25
• 14mOrbWeaver: Using IDLE Cycles in Programmable Networks for Opportunistic CoordinationVincent Liu, Liangcheng Yu, John Sonchack · 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22)
• 16mSöze: One Network Telemetry Is All You Need for Per-flow Weighted Bandwidth Allocation...Weitao Wang, T. S. Eugene Ng · OSDI '25