Back to search

Georgia Institute of Technology

Algorithm Design and Performance of QPS-based Parallel Algorithm on Optical Network Switch

Abstract

dc:description.abstract

The 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

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Song, Dongzhao. Algorithm Design and Performance of QPS-based Parallel Algorithm on Optical Network Switch. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/81618