Georgia Institute of Technology
Algorithm Design and Performance of QPS-based Parallel Algorithm on Optical Network Switch
Abstract
dc:description.abstractThe relentless growth of sizes and traffic volumes in data center networks (DCN) is posing a significant challenge on switching: A single giant switch in a modern flattened-topology DCN needs to direct terabits of traffic per second to hundreds of top-of-rack switches in a low latency of just a few milliseconds. The vast majority of existing switching schedulers have yet to address this challenge: Traffic-oblivious RODCN (reconfigurable optical DCN) schedulers do not have high throughput utilization, whereas on-demand hybrid (circuit and packet) switching schedulers are too computationally expensive. To this end, we propose an efficient and performant hybrid switching scheduler, named QPS-Fit, which computes high-quality on-demand schedules in a fully parallelizable way. QPS-Fit builds on QPS (Queue-Proportional Sampling), a request strategy in which each input port samples an output port with a probability proportional to the amount of traffic destined for it, so that larger traffic demands tend to be scheduled earlier when output-port schedules are still wide open. Our algorithm simultaneously fits many transmissions into the schedule, all by parallel ``dirt-cheap'' request-grant message exchanges between input and output ports. BFF (Best First Fit) is the fastest existing hybrid switching algorithm, which exploits a partial reconfigurability assumption of the optical circuit switch to attain better throughput and lower time complexity than other hybrid switching schemes, but is still too computationally expensive to scale beyond a few dozen ports. According to our simulation, QPS-Fit achieves similar throughput utilization as BFF, the state-of-the-art on-demand hybrid switching scheduler, while being nearly 27x faster when running on 96 threads. Beyond hybrid switching, we further extend the QPS family to pure optical switching fabrics with QPS-ToR, an adaptation of SW-QPS (Sliding-Window QPS) to the epoch-based optical switching architecture of NegotiaToR, a recent on-demand RODCN scheduler. QPS-ToR replaces NegotiaToR's queue-oblivious iSLIP-based scheduler with queue-proportional sampling and a sliding window of future matchings, addressing the core limitation of binary request signals that leave the scheduler blind to traffic volume. Under realistic DCN workloads driven by published Meta Hadoop traces, our packet-level simulations show that QPS-ToR achieves 30%-40% lower average flow completion time (FCT) and consistently higher goodput than NegotiaToR and RotorNet at moderate to high loads, with the FCT advantage growing to roughly 40% at load 0.9; these improvements hold consistently across workloads ranging from mice-flow-dominated to elephant-flow-dominated distributions, demonstrating that the approach is robust to workload variation without per-scenario parameter tuning.
Degree
thesis:*- Name thesis:degree_name
- Computer Science, MS
- Department thesis:degree_department
- Computer Science
- Grantor
- Georgia Institute of Technology
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Song, Dongzhao
- Advisor dc:contributor.advisor
-
- Xu, Jun (Jim)
- Committee members dc:contributor.committeemember
-
- Said Mohamed Tawfik Issa, Ahmed
- Dainotti, Alberto
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/81618