QPS-ToR: A Parallel Iterative Switching Algorithm for Reconfigurable Optical Datacenter Switching ∗
Dongzhao Song
Qianru Yu
Jun “Jim” Xu
Georgia Tech Atlanta, Georgia, USA
Georgia Tech Atlanta, Georgia, USA
Georgia Tech Atlanta, Georgia, USA
arXiv:2609.09400v1 [cs.NI] 8 Sep 2026
ABSTRACT Reconfigurable optical data center networks (RODCNs) have emerged as a promising solution for scaling DCN capacity, yet their scheduling mechanisms remain a performance bottleneck: traffic-oblivious schemes inherently limit throughput, while the state-of-the-art traffic-aware scheme, NegotiaToR, uses single-iteration iSLIP as its scheduling engine, which limits throughput to around 60% and treats all sourcedestination pairs with equal priority regardless of queue length. We propose QPS-ToR, which replaces NegotiaToR’s scheduling logic with SW-QPS, a sliding-window algorithm originally proposed for crossbar scheduling that achieves around 90% throughput with a single low-complexity iteration. QPSToR operates within NegotiaToR’s existing workflow, requiring only a revision of the scheduling cycle from threestep Request-Grant-Accept (RGA) to two-step Request-Grant (RG) with a sliding window mechanism. In flow-level simulations with 128 ToRs under realistic datacenter workloads, QPS-ToR achieves up to 36% higher throughput and 82% lower flow completion time (FCT) compared to NegotiaToR, and consistently outperforms RotorNet, a representative traffic-oblivious scheme, on the parallel network topology.
1.
INTRODUCTION
The sizes of data center networks (DCNs) and the volumes of network traffic across them continue to grow relentlessly, thanks to existing and emerging data-intensive applications, such as distributed artificial intelligence, cloud computing, and video streaming. At the same time, DCN designs are increasingly adopting a flattened (i.e., non-hierarchical) topology, in which Top-of-Rack (ToR) switches are interconnected directly via a flattened fabric of optical switches (e.g., in [3]) that can be abstracted into a single giant optical DCN switch. To transport and “direct” a massive amount of traffic to their respective destinations, DCN switching solutions capable of connecting many ToR switches, operating at high line rates (e.g., 40 Gbps), and delivering high throughput and delay performance, under any admissible traffic demand, are badly needed. ∗ This work was supported in part by the National Science Foundation under Grant No. CNS-2007006 and by a seed gift from Dolby Laboratories.
To appear in IFIP Performance 2026, November 2026, Ghent, Belgium.
The standard switching solution framework for modern DCN is called RODCN (reconfigurable optical data center network) [37, 30, 36, 28, 3, 4, 41, 34, 22, 1, 47, 30, 19, 16], in which all ToRs are interconnected via an optical circuit switch (OCS). Depending on whether or not the OCS configurations during a scheduling epoch vary with the (measured) traffic demand, RODCN schemes can be classified into two types: (1) traffic-oblivious; and (2) traffic-aware.
1.1
Traffic-oblivious solutions
Traffic switching and forwarding in traffic-oblivious schemes is mostly based on Valiant load-balancing (VLB) [42] as follows. In each epoch, the OCS follows a fixed, pre-determined sequence of N configurations (matchings), where N is the number of ToR switches in the DCN (This sequence can be partitioned into shorter subsequences when multiple parallel OCS are used, such as in [30]). These N matchings, by following a cyclic-shift connectivity pattern, allow each input port (server rack) to connect to each output port exactly once during an epoch; we call this all-to-all matchings in the sequel, using the term from [19]. Here a rack (its ToR switch) functions as both an input port (for receiving traffic from the downlink) and an output port (for sending traffic over the uplink) simultaneously, exactly like an RJ-45 port on an Ethernet switch. Now we explain, using an analogy, how traffic is forwarded in such a VLB-based scheme. These N OCS configurations comprise the “daily” (per scheduling epoch) “express bus schedule” (evolving connectivities between input-output port pairs). At each input port (“city”), each “passenger” (traffic) will first board the “first arriving bus” to the bus’ destination say R (that is uniformly random, as intended by VLB), and then from R wait for and board the “right bus” to the passenger’s destination if it is not R. As such, each forwarding decision does not require any nontrivial computation, which allows the traffic-oblivious schemes to be highly scalable (to a large N ). For this reason, the vast majority of existing RODCN schemes, such as RotorNet [30] that we compare with in this work, are traffic-oblivious. However, the flip side of the coin is that this VLB-based forwarding limits the throughput to around 60%, since the vast majority of passengers need to take two “bus rides” to reach their respective destinations.
1.2
Traffic-aware solutions
Only three RODCN schemes [46, 4, 19] belong to the traffic-aware type. In these traffic-aware schemes, for each epoch, the scheduler needs to compute, based on the (measured) traffic demand, a bipartite matching between the in-
put and the output ports that serves as the configuration of the OCS for the epoch. These matchings need to be of highquality w.r.t. the traffic demand, in the sense they result in great throughput and latency performances. As such, this problem formulation is almost identical to that of scheduling a single input-queued (IQ) crossbar (with N input ports and N output ports), also known as IQ switching. Indeed, all three traffic-aware schemes adopt standard IQ switching solutions with adaptations. When N is large, the standard IQ switching solutions for high-speed routers (e.g., in Juniper’s M160 and Cisco’s 12000 GSR [26]) are the PISA (Parallel Iterative Switching Algorithm) family, partly because a serial matching algorithm is too expensive computationally; for example, the state-of-the-art serial algorithm [6] that computes a maximum weighted (by the traffic demands) matching (MWM), which is considered the highest-quality matching for network switching purposes [39], has a whopping time complexity of O(N 3 ) [7]. PISA mitigates this high-complexity problem partly by spreading the complexity across the N input ports and the N output ports through parallelism, as follows. A PISA typically runs multiple iterations, each of which involves typically three back-and-forth rounds of message exchanges between input and output ports, in parallel. These three rounds are commonly called RGA [9] in the switching literature: R round in which each input port sends requests to all output ports it has traffic for; G round in which each output port grants to one of the requests received; and A round in which each input port accepts one of the grants received. In the context of IQ crossbar scheduling, multiple RGA iterations can be completed in a switching cycle, since input and output ports can exchange RGA messages using (extremely short) on-chip wirings between them. In the contemporary RODCN context, however, it is impossible to complete multiple RGA iterations in a scheduling epoch, since input and output ports are different ToR switches, and even a roundtrip between an input-output port pair can be longer than an epoch [19]. For this reason, in NegotiaToR [19], the state of the art traffic-aware RODCN scheme, only a single RGA iteration of iSLIP [27] is run to compute a matching (as the OCS schedule), at a performance cost: when there is no speedup of the “switching fabric,” its reported throughput is below 60% [19], which is consistent with the throughput of iSLIP [27] running a single iteration (after accounting for the OCS reconfiguration delay). Also for this reason, in NegotiaToR [19], even the R, G, and A rounds of an iteration have to spread out to three consecutive epochs, in a pipelined manner.
1.3
QPS-ToR Algorithm
We were recently aware of SW-QPS (Sliding Window Queue Proportional Sampling) [31], a PISA proposed several years ago for IQ crossbar scheduling. SW-QPS can attain high throughput (near or over 90% ) under all benchmark load matrices, while running only a single low-complexity iteration. Inspired by this work, in this work we ask and answer the following research question. Can we significantly improve the throughput and latency performances of NegotiaToR, by replacing the single-iteration iSLIP with (singleiteration) SW-QPS [31] as its OCS scheduler? Our answer is affirmative: with this replacement, the resulting RODCN scheme, which we call QPS-ToR, achieves up to 36% higher
throughput and up to 82% lower FCT (flow completion time), than NegotiaToR. In this work, we make two contributions. First, we take credit for coming up with this idea and revising the workflow of NegotiaToR to make this replacement happen. Second, we have resolved a read-after-write hazard caused by the conflict between the sliding-window operation of SW-QPS and the aforementioned pipelined operation of NegotiaToR, at a negligible performance cost.
2.
BACKGROUND
In § 2.1, we describe (1) NegotiaToR’s epoch structure, which QPS-ToR also follows, and (2) how its aforementioned pipelined RGA operation fit into the structure. In § 2.2, we describe the SW-QPS algorithm, from which QPS-ToR’s scheduling engine is adapted.
2.1
NegotiaToR workflow
In NegotiaToR, time is divided into equal-length intervals called epochs. Figure 1 illustrates four consecutive epochs, at times t, t + 1, t + 2, and t + 3. Each epoch consists of two phases: a short predefined phase, followed by a longer scheduled phase. During the predefined phases, the OCS supports the aforementioned pipelined (iSLIP’s) RGA operation, producing one completed matching per epoch. During each scheduled phase, the resulting matching is applied as the OCS schedule, pairing input and output ports for relatively bulk data transfers. As such, the predefined phase serves as an in-band control plane, whereas the scheduled phase serves as the data plane, of the RODCN. The pipelined RGA operation, that produces one (relatively) long-duration matching (OCS schedule) per epoch, is carried out as follows. During each predefined phase (in each epoch), the OCS (rapidly) cycles through the aforementioned (in its VLB context in §1.1) sequence of N allto-all matchings to exchange RGA messages. As explained earlier, the three rounds (namely R, G, and A) of message exchanges for computing a matching cannot fit in a single epoch and have to span three epochs. For example, Figure 1 illustrates an execution path Rt → Gt+1 → At+2 that produces (computes) a bipartite matching Mt+3 for use during the scheduled phase of epoch t + 3. Here, Rt stands for input ports sending requests to output ports during the predefined phase of epoch t according to the measured traffic demand right before time t; and Gt+1 and At+2 stands for the corresponding grants and accepts transmitted during the predefined phases of epochs t + 1 and t + 2 respectively. We can see from this example that without pipelined operation, NegotiaToR can only compute a matching every 3 epochs. To produce a matching in every epoch, this RGA operation is pipelined, as shown in Figure 1. In each epoch, the predefined phase carries out R, G, A rounds of message exchanges, for three consecutive (in time) matching computations respectively. For example, Rt for computing Mt+3 , Gt for computing Mt+2 , and At for computing Mt+1 are all carried out during the predefined phase at epoch t, The bulk transfers made by the OCS during the scheduled phases can efficiently handle nearly all large elements (inputoutput flows) in the traffic demand matrix (TDM). This efficiency comes from the fact that a large TDM element can fill up an edge (input-output connection) in the OCS configuration (matching) during a scheduled phase, which effectively amortizes the (nontrivial) OCS reconfiguration delay cost.
Figure 1: NegotiaToR’s Request-Grant-Accept
These bulk transfers, however, cannot efficiently handle the mice flows, some of which are also latency-sensitive. The predefined phases come to the rescue: the N short-duration matchings in each predefined phase give each mice flow, say from input port i to output port j, one chance (in the shortduration matching that contains the edge (i, j)) to transmit, by piggybacking after the (pipelined) RGA messages from i to j.
2.2
QPS and SW-QPS
In this section, we provide a brief introduction to SWQPS, the state of the art scheduling algorithm for (the crossbar of) a packet switch, that we will adapt into the scheduling engine of QPS-ToR, our RODCN solution. To this end, we first describe QPS (Queue-Proportional Sampling), which SW-QPS builds on. QPS computes a good-quality matching in a single iteration, with both time and communication complexity of O(1) [14]. A QPS iteration [13] contains only two phases: request and grant. In the request phase, each input port sends a pairing request to a single output port with a probability proportional to the length of the corresponding Virtual Output Queue (VOQ); here a VOQ, say VOQ(i, j) is the set of packets queued at the input port i that are destined for the output port j. In the grant phase, upon receiving one or more such requests, the output port grants the request accompanied by the largest VOQ length. Unlike iSLIP and most other PISAs (parallel iterative switching algorithms), a QPS iteration does not need a separate accept phase, since each input port sends out only one request and hence expects to receive at most one grant. SW-QPS enhances QPS with a sliding-window (say of length T ) mechanism that manages, at any time (slot) t, the computations of T matchings in the sliding-window (t, t+T ]: matchings to “graduate” and be used for time slots t + 1, t + 2, · · · , t + T , which we denote as Mt+1 , Mt+2 , · · · , Mt+T , respectively. At time t, a single request-grant iteration mostly identical to that in QPS is performed to add new edges (input-output pairings) to these T matchings. The only difference is that each request, say from input port i to output port j, contains a bitmap encoding i’s availability (whether it has already paired with an output port) during each of these T time slot; and that, upon receiving this request, j checks its schedule (availabilities in the window), and grants (to i) the earliest time slot when both i and j are available. Since these request (R) and grant (G) messages contribute to the computations of all T matchings in the window (t, t + T ], we denote these two rounds of message exchanges as RtT and GTt respectively, with the superscript T emphasizing that this window semantics. In SW-QPS, after this RG iteration, Mt+1 , the oldest matching in the window, is removed from the window (i.e.,
graduates) and used as the crossbar configuration for the time t + 1; and a new empty matching Mt+T +1 is added to the window. As such, the window slides one position to the right, becoming (t + 1, t + T + 1]. From the viewpoint of a matching, say Mt+1 in this example, it appears in T consecutive sliding windows, namely (t − T + 1, t + 1], (t − T + 2, t + 2], · · · , (t, t + T ], which provides Mt+1 with T opportunities (RG iterations) to gain edges before it graduates.
3.
QPS-TOR ALGORITHM
QPS-ToR simply replaces NegotiaToR’s pipelined (iSLIP’s) RGA operation, illustrated in Figure 1, with a pipelined (SW-QPS’) RG operation, illustrated in Figure 2. For example, as shown in Figure 2, RtT and GTt+1 messages are transmitted in the predefined phases of epochs t and t + 1 respectively to produce the matching Mt+2 , to be used (as the OCS configuration) for the scheduled phase of epoch t + 2. As such, the depth of the pipeline is 2 here (R and G segments), compared to 3 in NegotiaToR (R, G, and A segments), which translates to further improvement in latency performance beyond that due to SW-QPS being a better (crossbar) switching algorithm than iSLIP. As mentioned earlier (in §1.3), the pipelined RG operation in QPS-ToR has a read-after-write hazard that needs to be fixed. We illustrate this hazard by an example. As shown in Figure 2, the predefined phase contains two segments: RtT and GTt . RtT messages report the snapshot, right before time t, of input ports’ availabilities during the sliding-window (t + 1, t + T ]. In GTt messages, output ports add edges to matchings during the sliding-window (t, t + T − 1] according to the input ports’ availabilities reported at time t − 1 (in T Rt−1 messages). Since RtT and GTt happen concurrently in the predefined phase of epoch t, the following “double booking” scenario can occur: GTt contain an output port’s grant to pair with an input port i∗ at epoch τ ∈ (t, t+T −1], i∗ declares itself available (for pairing) in its request (among RtT ) to an output port o∗ due to this concurrency, and o∗ grants (the scheduled phase of) epoch τ to i∗ . QPS-ToR resolves this hazard by running two separate SW-QPS scheduler instances on two disjoint sets of epochs that partition a sliding window, as follows. Each request in RtT reports the input port’s availability at epochs t + 2, t + 4, t + 6, · · · , and the grants (in reply to RtT ) in GTt+1 will commit the input ports only to this half of the sliding window. This partitioning prevents the “double booking” in the example above, because a grant in GTt (in reply to T Rt−1 ) makes an input port newly unavailable in an epoch belonging to the other half of the sliding window (t+1, t+3, t + 5, · · · ). Although this partitioning in theory reduces an input port’s availability “by half,” its impact on throughput and latency performance is negligible according to our experiments. Note that NegotiaToR does not suffer from this hazard, because there Rt and Gt messages “refer to” input ports’ availabilities during t + 3 and t + 2, respectively.
4.
RELATED WORK
More than a decade ago, when DCN sizes and link rates were both much smaller than today’s, a DCN switching solution framework called hybrid circuit and packet switching was proposed as a cost-effective DCN switching solution [8, 33, 20, 15, 21, 12, 5, 17, 43, 25, 24, 23, 38]. In addition to
Figure 2: QPS-ToR’s Request-Grant
an N × N optical circuit switch (OCS), a hybrid-switched DCN uses an N × N electronic packet switch (EPS) to connect the N ToRs together. The EPS has a lower bandwidth than the OCS, typically by an order of magnitude (e.g., 10 vs. 100 Gbps per port), but does not incur a reconfiguration delay (guardband). The objective of a hybrid-switched DCN solution is to schedule the time-varying configurations (matchings) of its OCS over each epoch for the best possible throughput performance. This scheduling problem has three major differences with that in an RODCN. First, in hybrid switching, each epoch lasts milliseconds. In comparison, to achieve much lower latency (FCT) demanded by today’s latency-sensitive DCN applications, an epoch lasts only microseconds in an RODCN, like in this work. Second, hybrid switching solves the following batch scheduling problem: given a traffic demand matrix (TDM) D between the ToRs during an epoch, compute a set of configurations (matchings), of varying durations, that OCS should use over time, such that the OCS transmits the bulk of D and leaves a residue workload that is small enough for the EPS to handle. In comparison, RODCN computes one fixed-duration (the length of the scheduled phase in an epoch) matching at a time. Third, a hybrid-switched DCN has an EPS as a “dedicated helper” (e.g., to handle most of mice flows in D) whereas RODCN does not. Hybrid switching was an appealing solution because, with an “ideal separation of duties” between OCS (mostly for handling elephant flows) and EPS (for handling mice flows), the combined (OCS+EPS) switching system can achieve a much higher throughput performance than an OCS alone (e.g., using optical switching algorithms such as [40, 18, 10, 44, 45]); and this performance gain is much greater than that can be attributed to the minute bandwidth (or contribution) of the EPS, as shown in [23]. However, when the DCN size becomes larger, all existing hybrid switching algorithms except [38] become too computationally expensive to scale accordingly. For example, only QPS-Fit [38], the fastest hybrid switching algorithm thanks to its massively parallelable design, can compute an OCS schedule for an epoch within an epoch’s time (of 3 ms) when N = 96, whereas all other hybrid switching algorithms require computation times that are one to three orders longer. This relative (to RODCN) advantage of hybrid switching having an EPS as a dedicated helper became modest only recently, when OCS with negligibly small guardband (e.g., ranging from 10 ns to 100 ns in NegotiaToR [19]) became available at a reasonable cost, which has moderated the aggregate guardband time spent on the large number of mice flows. However, without a good scheduling algorithm, this improved optical hardware capability does not automatically translate into much better FCT and throughput. Our QPS-ToR is such an algorithm.
5.
EVALUATION
5.1
Evaluation setup
To ensure a fair head-on comparison, we use the following evaluation setup, which is largely identical to that used in the NegotiaToR evaluation [19]. Network setup. Same as in [19], the network consists of 8 parallel optical switches, each implemented as a 128×128 AWGR (arrayed waveguide grating router), interconnecting 128 ToR switches. Each ToR is viewed both as an input port and as an output port, following the RJ-45 analogy in Section §1.1. Each ToR is equipped with 8 optical transceivers, where the i-th transceivers across all 128 ToRs are interconnected through the i-th AWGR. Epoch settings. We adopt the same epoch length and structure as in [19]. During the predefined phase, the 8 optical switches collectively cycle through the aforementioned (in its VLB context in § 1.1) sequence of N = 128 predetermined short-duration all-to-all matchings. Since the 128 matchings are distributed across 8 parallel optical switches, the predefined phase consists of only 128/8=16 matching intervals. Each interval lasts 60 ns, consisting of a 10 ns reconfiguration delay (called the guardband in [19]) followed by 50 ns of data transmission. Consequently, the predefined phase lasts 16*60=960 ns. The scheduled phase is set to 2.7 µs, which was found in [19] to achieve a near-optimal throughput-latency tradeoff for NegotiaToR. Therefore, the total epoch length is 2.7+0.96=3.66 µs. Evaluation metrics. As in [19], we focus on two evaluation metrics: (1) latency, measured by average flow completion time (FCT); and (2) throughput. Also following [19], a flow is defined in terms of ToR-to-ToR traffic exchange, i.e., each flow originates at a source ToR and terminates at a destination ToR, and FCT is measured on a per-flow basis. Preliminary experiments indicate that the improvement trend also holds for 99th-percentile FCT. Baselines. We compare QPS-ToR against two schedulers: NegotiaToR [19, 11], the state-of-the-art on-demand trafficaware RODCN scheduler; and RotorNet [30, 29], the stateof-the-art VLB-based traffic-oblivious RODCN scheduler (described in Section § 1.1). All schedulers are implemented within the same YAPS [19, 11] simulator framework to ensure a controlled comparison. Specifically, the NegotiaToR implementation is obtained directly from its authors, QPSToR extends the NegotiaToR codebase with our scheduling logic, and RotorNet is implemented based on the descriptions in [30]. As a VLB-based traffic-oblivious scheduler, RotorNet does not include a scheduled phase. Hence, to ensure a fair comparison, RotorNet uses the same epoch length of 3.66 µs, with the entire epoch devoted to the predefined phase. Similar to the other schedulers, the predefined phase is divided into 16 time slots, during which the 8 parallel optical switches collectively cycle through the aforementioned 128 all-to-all matchings. Each slot lasts 3.66 µs/16 ≈ 229 ns, consisting of a 10 ns guardband and approximately 219 ns of data transmission. This configuration yields a duty cycle of approximately 95.6% over the rotation. Workload characteristics. Following [19], each experiment lasts 30 ms. We generate three workloads from the following publicly available DCN traces using the same methodology as in [19], where flows arrive according to a Poisson process and their size distribution follows the corresponding trace. Trace 1 is collected from Meta’s Hadoop clusters [35].
This trace is heavy-tailed: 60% of flows are smaller than 1 KB, while more than 80% of the traffic volume comes from elephant flows larger than 100 KB. Trace 2 is a more heavily tailed web-search workload [2], in which more than 80% of flows exceed 10 KB. Trace 3 is a lighter-tailed Google datacenter workload [32], where more than 80% of flows are smaller than 1 KB. As in [19], each of the 8 optical switches operates at 100 Gbps, collectively providing up to 800 Gbps of aggregate throughput to and from each ToR. We measure network throughput and FCT under offered loads ranging from 10% to 90%. A key distinction from the original NegotiaToR evaluation lies in how the offered load is normalized. NegotiaToR reports 100% throughput in its original evaluation due to a 2× link-rate speedup: while each ToR provides 800 Gbps of uplink capacity, the offered traffic load is normalized to only 400 Gbps. In contrast, our evaluation assumes no link-rate speedup, exposing the full 800 Gbps uplink capacity to offered loads of up to 800 Gbps. Under this setting, no scheduler can achieve 100% throughput.
5.2
Evaluation Result
Overall FCT. As shown in Figure 3, RotorNet consistently achieves lower FCT than NegotiaToR across all three workloads, suggesting that NegotiaToR’s queue-oblivious scheduler fails to fully utilize available optical capacity. QPS-ToR further outperforms both baselines across all workloads on the parallel topology at loads level above 0.5. Under the default Hadoop workload (Trace 1, Figure 3(a)), QPS-ToR reduces average FCT by roughly 72% relative to NegotiaToR and 35% relative to RotorNet at loads above 0.5. The gap further widens at load 0.7, reaching 82% and 50%, respectively. Under the heavier-tailed web-search workload (Trace 2, Figure 3(c)), where elephant flows dominate traffic volume, the advantage remains significant: QPS-ToR improves FCT by up to 68% over NegotiaToR and 37% over RotorNet at high loads. This behavior is expected, since queue-proportional sampling is most effective when large backlogs provide strong signals for constructing demand-aware matchings. Under the lighter-tailed Google datacenter workload (Trace 3, Figure 3(e)), where mice flows dominate, the improvement is more modest—roughly 50% over NegotiaToR and 21% over RotorNet—because the reduced prevalence of elephant flows limits the benefit of queue-aware scheduling. Across all three traces, the improvement arises from the same underlying mechanism: QPS-ToR dynamically steers optical capacity toward heavily loaded ToR pairs, draining large backlogs before substantial queue buildup occurs. Overall Throughput. As shown in Figures 3(b)(d)(f), QPS-ToR consistently achieves higher throughput than both baselines across all workloads and load levels. Under Trace 1 (Figure 3(b)), QPS-ToR improves throughput by approximately 24% over NegotiaToR and 8% over RotorNet at loads above 0.5. Under the heavier-tailed Trace 2 (Figure 3(d)), throughput gains follow a similar trend: QPSToR exceeds NegotiaToR by 22% and RotorNet by 15% at loads above 0.5. The gap further widens at load 0.9, reaching 36% and 22%, respectively. Under the lighter-tailed Trace 3 (Figure 3(f)), the throughput advantage is smaller in absolute terms but remains consistent across all loads. In all cases, NegotiaToR leaves optical capacity underutilized because its scheduling decisions are independent of queue occupancy, whereas QPS-ToR allocates matchings
Figure 3: FCT and throughput comparison under three workloads. according to observed demand. Even without workloadspecific parameter tuning, QPS-ToR demonstrates robust performance advantages across all three traffic distributions.
6.
CONCLUSION
In this paper, we propose QPS-ToR, a traffic-aware RODCN scheduler that replaces NegotiaToR’s single-iteration iSLIP engine with SW-QPS, a sliding-window queue-proportional sampling algorithm adapted from crossbar scheduling. QPSToR operates within NegotiaToR’s existing epoch workflow, requiring only a reduction of the scheduling pipeline from three-step RGA to two-step RG, and resolves the resulting read-after-write hazard by interleaving two independent scheduler instances on disjoint epoch subsets. In flow-level simulations with 128 ToRs under three realistic datacenter workloads, QPS-ToR reduces flow completion time by up to 82% compared to NegotiaToR and up to 50% compared to RotorNet, while improving throughput by up to 36% over NegotiaToR and up to 22% over RotorNet, consistently out-
performing both baselines at loads above 0.5 across all traffic distributions.
7.
REFERENCES
[1] V. Addanki, C. Avin, and S. Schmid. Mars: Near-optimal throughput with shallow buffers in reconfigurable datacenter networks. Proc. ACM Meas. Anal. Comput. Syst., 7(1), Mar 2023. [2] M. Alizadeh, A. Greenberg, D. A. Maltz, J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan. Data center TCP (DCTCP). In Proceedings of the ACM SIGCOMM 2010 Conference, SIGCOMM ’10, pages 63–74, New York, NY, USA, 2010. Association for Computing Machinery. [3] H. Ballani, P. Costa, R. Behrendt, D. Cletheroe, I. Haller, K. Jozwik, F. Karinou, S. Lange, K. Shi, B. Thomsen, and H. Williams. Sirius: A flat datacenter network with nanosecond optical switching. In Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM ’20, pages 782–797, New York, NY, USA, 2020. Association for Computing Machinery. [4] J. L. Benjamin, T. Gerard, D. Lavery, P. Bayvel, and G. Zervas. PULSE: Optical circuit switched data center architecture operating at nanosecond timescales. J. Lightwave Technol., 38(18):4906–4921, Sep 2020. [5] S. Bojja Venkatakrishnan, M. Alizadeh, and P. Viswanath. Costly circuits, submodular schedules and approximate Carathéodory theorems. In SIGMETRICS, pages 75–88. ACM, 2016. [6] R. Duan and H.-H. Su. A Scaling Algorithm for Maximum Weight Matching in Bipartite Graphs. In Proceedings of the ACM-SIAM SODA, pages 1413–1424, 2012. [7] J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248–264, Apr. 1972. [8] N. Farrington, G. Porter, S. Radhakrishnan, H. H. Bazzaz, V. Subramanya, Y. Fainman, G. Papen, and A. Vahdat. Helios: a hybrid electrical/optical switch architecture for modular data centers. SIGCOMM Comput. Commun. Rev., 40(4):339–350, 2010. [9] A. Firoozshahian, V. Manshadi, A. Goel, and B. Prabhakar. Efficient, fully local algorithms for CIOQ switches. In Proceedings of the IEEE INFOCOM, pages 2491–2495, 2007. [10] S. Fu, B. Wu, X. Jiang, A. Pattavina, L. Zhang, and S. Xu. Cost and delay tradeoff in three-stage switch architecture for data center networks. In HPSR, pages 56–61. IEEE, 2013. [11] P. X. Gao, A. Narayan, G. Kumar, R. Agarwal, S. Ratnasamy, and S. Shenker. pHost: Distributed near-optimal datacenter transport over commodity network fabric. Proceedings of the ACM CoNEXT, 2015. [12] M. Ghobadi, R. Mahajan, A. Phanishayee, N. Devanur, J. Kulkarni, G. Ranade, P.-A. Blanche, H. Rastegarfar, M. Glick, and D. Kilper. ProjecToR:
Agile reconfigurable data center interconnect. In Proceedings of the 2016 ACM SIGCOMM Conference, SIGCOMM ’16, pages 216–229, New York, NY, USA, 2016. Association for Computing Machinery. [13] L. Gong, P. Tune, L. Liu, S. Yang, and J. J. Xu. Queue-Proportional Sampling: A better approach to crossbar scheduling for input-queued switches. SIGMETRICS Perform. Eval. Rev., 45(1):4, June 2017. [14] L. Gong, J. J. Xu, L. Liu, and S. T. Maguluri. QPS-r: A cost-effective iterative switching algorithm for input-queued switches. In Proceedings of the 13th EAI International Conference on Performance Evaluation Methodologies and Tools, pages 19–26, 2020. [15] N. Hamedazimi, Z. Qazi, H. Gupta, V. Sekar, S. R. Das, J. P. Longtin, H. Shah, and A. Tanwer. FireFly: A reconfigurable wireless data center fabric using free-space optics. In Proceedings of the ACM SIGCOMM, pages 319–330, 2014. [16] M. Khani, M. Ghobadi, M. Alizadeh, Z. Zhu, M. Glick, K. Bergman, A. Vahdat, B. Klenk, and E. Ebrahimi. SiP-ML: high-bandwidth optical network interconnects for machine learning training. In Proceedings of the 2021 ACM SIGCOMM 2021 Conference, SIGCOMM ’21, pages 657–675, New York, NY, USA, 2021. Association for Computing Machinery. [17] C. Li, M. K. Mukerjee, D. G. Andersen, S. Seshan, M. Kaminsky, G. Porter, and A. C. Snoeren. Using indirect routing to recover from network traffic scheduling estimation error. In Proceedings of the Symposium on Architectures for Networking and Communications Systems, pages 13–24. IEEE Press, 2017. [18] X. Li and M. Hamdi. On scheduling optical packet switches with reconfiguration delay. IEEE J. Sel. Areas Commun., 21(7):1156–1164, 2003. [19] C. Liang, X. Song, J. Cheng, M. Wang, Y. Liu, Z. Liu, S. Zhao, and Y. Cui. NegotiaToR: Towards a simple yet effective on-demand reconfigurable datacenter network. In Proceedings of the ACM SIGCOMM 2024 Conference, ACM SIGCOMM ’24, pages 415–432, New York, NY, USA, 2024. Association for Computing Machinery. [20] H. Liu, F. Lu, A. Forencich, R. Kapoor, M. Tewari, G. M. Voelker, G. Papen, A. C. Snoeren, and G. Porter. Circuit switching under the radar with REACToR. In NSDI, volume 14, pages 1–15, 2014. [21] H. Liu, M. K. Mukerjee, C. Li, N. Feltman, G. Papen, S. Savage, S. Seshan, G. M. Voelker, D. G. Andersen, M. Kaminsky, et al. Scheduling techniques for hybrid circuit/packet networks. CoNEXT, 2015. [22] H. Liu, R. Urata, K. Yasumura, X. Zhou, R. Bannon, J. Berger, P. Dashti, N. Jouppi, C. Lam, S. Li, E. Mao, D. Nelson, G. Papen, M. Tariq, and A. Vahdat. Lightwave fabrics: At-scale optical circuit switching for datacenter and machine learning systems. In Proceedings of the ACM SIGCOMM 2023 Conference, ACM SIGCOMM ’23, pages 499–515, New York, NY, USA, 2023. Association for Computing Machinery. [23] L. Liu, L. Gong, S. Yang, J. Xu, and L. Fortnow. Best first fit (BFF): An approach to partially
reconfigurable hybrid circuit and packet switching. In 2018 IEEE 11th International Conference on Cloud Computing (CLOUD), pages 426–433, 2018. [24] L. Liu, L. Gong, S. Yang, J. J. Xu, and L. Fortnow. 2-Hop Eclipse: A fast algorithm for bandwidth-efficient data center switching. In Cloud Computing – CLOUD 2018: 11th International Conference, Held as Part of the Services Conference Federation, SCF 2018, Seattle, WA, USA, June 25–30, 2018, Proceedings, pages 69–83, Berlin, Heidelberg, 2018. Springer-Verlag. [25] L. Liu, J. Xu, and L. Fortnow. Quantized BvND: A better solution for optical and hybrid switching in data center networks. In IEEE/ACM 11th International Conference on Utility and Cloud Computing, pages 237–246. IEEE, New York, 2018. [26] N. McKeown. A fast switched backplane for a gigabit switched router. Business Communications Review, 27(12):1–30, 1997. [27] N. McKeown. The iSLIP Scheduling Algorithm for Input-queued Switches. IEEE/ACM Trans. Netw., 7(2):188–201, Apr. 1999. [28] W. M. Mellette, R. Das, Y. Guo, R. McGuinness, A. C. Snoeren, and G. Porter. Expanding across time to deliver bandwidth efficiency and low latency. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 1–18, Santa Clara, CA, Feb. 2020. USENIX Association. [29] W. M. Mellette, A. Forencich, R. Athapathu, A. C. Snoeren, G. Papen, and G. Porter. Realizing RotorNet: Toward practical microsecond scale optical networking. In Proceedings of the ACM SIGCOMM 2024 Conference, ACM SIGCOMM ’24, pages 392–414, New York, NY, USA, 2024. Association for Computing Machinery. [30] W. M. Mellette, R. McGuinness, A. Roy, A. Forencich, G. Papen, A. C. Snoeren, and G. Porter. RotorNet: A scalable, low-complexity, optical datacenter network. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication, SIGCOMM ’17, pages 267–280, New York, NY, USA, 2017. Association for Computing Machinery. [31] J. Meng, L. Gong, and J. Xu. Sliding-Window QPS (SW-QPS) a perfect parallel iterative switching algorithm for input-queued switches. ACM SIGMETRICS Perform. Eval. Review, 48(3):71–76, 2021. [32] B. Montazeri, Y. Li, M. Alizadeh, and J. Ousterhout. Homa: a receiver-driven low-latency transport protocol using network priorities. In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, SIGCOMM ’18, pages 221–235, New York, NY, USA, 2018. Association for Computing Machinery. [33] G. Porter, R. Strong, N. Farrington, A. Forencich, P. Chen-Sun, T. Rosing, Y. Fainman, G. Papen, and A. Vahdat. Integrating microsecond circuit switching into the data center. SIGCOMM Comput. Commun. Rev., 43(4):447–458, Aug. 2013. [34] L. Poutievski, O. Mashayekhi, J. Ong, A. Singh, M. Tariq, R. Wang, J. Zhang, V. Beauregard, P. Conner, S. Gribble, R. Kapoor, S. Kratzer, N. Li,
H. Liu, K. Nagaraj, J. Ornstein, S. Sawhney, R. Urata, L. Vicisano, K. Yasumura, S. Zhang, J. Zhou, and A. Vahdat. Jupiter evolving: transforming google’s datacenter network via optical circuit switches and software-defined networking. In Proceedings of the ACM SIGCOMM 2022 Conference, SIGCOMM ’22, pages 66–85, New York, NY, USA, 2022. Association for Computing Machinery. [35] A. Roy, H. Zeng, J. Bagga, G. Porter, and A. C. Snoeren. Inside the social network’s (datacenter) network. In ACM SIGCOMM Computer Communication Review, volume 45, pages 123–137. ACM, 2015. [36] V. Shrivastav, A. Valadarsky, H. Ballani, P. Costa, K. S. Lee, H. Wang, R. Agarwal, and H. Weatherspoon. Shoal: A network architecture for disaggregated racks. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19), pages 255–270, Boston, MA, Feb. 2019. USENIX Association. [37] A. Singh, J. Ong, A. Agarwal, G. Anderson, A. Armistead, R. Bannon, S. Boving, G. Desai, B. Felderman, P. Germano, et al. Jupiter rising: A decade of clos topologies and centralized control in google’s datacenter network. ACM SIGCOMM computer communication review, 45(4):183–197, 2015. [38] D. Song, J. Meng, Q. Yu, and J. J. Xu. QPS-Fit: An efficient and performant parallel algorithm for hybrid optical and packet switching. In 2025 IEEE 18th International Conference on Cloud Computing (CLOUD), pages 397–408, 2025. [39] L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12):1936–1948, Dec. 1992. [40] B. Towles and W. J. Dally. Guaranteed scheduling for switches with configuration overhead. IEEE/ACM Transactions on Networking, 11(5):835–847, 2003. [41] R. Urata, H. Liu, K. Yasumura, E. Mao, J. Berger, X. Zhou, C. Lam, R. Bannon, D. Hutchinson, D. Nelson, et al. Mission Apollo: landing optical circuit switching at datacenter scale. arXiv preprint arXiv:2208.10041, 2022. [42] L. G. Valiant. A scheme for fast parallel communication. SIAM journal on computing, 11(2):350–361, 1982. [43] S. Vargaftik, K. Barabash, Y. Ben-Itzhak, O. Biran, I. Keslassy, D. Lorenz, and A. Orda. Composite-path switching. In Proceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies, pages 329–343. ACM, 2016. [44] C.-H. Wang, T. Javidi, and G. Porter. End-to-end scheduling for all-optical data centers. In INFOCOM, pages 406–414. IEEE, 2015. [45] C.-H. Wang, S. T. Maguluri, and T. Javidi. Heavy traffic queue length behavior in switches with reconfiguration delay. In IEEE INFOCOM 2017 IEEE Conference on Computer Communications, pages 1–9, 2017. [46] K. Xi, Y.-H. Kao, and H. J. Chao. A petabit bufferless optical switch for data center networks. In C. Kachris,
K. Bergman, and I. Tomkos, editors, Optical Interconnects for Future Data Center Networks, pages 135–154. Springer New York, New York, NY, 2013. [47] J. Zerwas, C. Györgyi, A. Blenk, S. Schmid, and
C. Avin. Duo: A high-throughput reconfigurable datacenter network using local routing and control. Proc. ACM Meas. Anal. Comput. Syst., 7(1), Mar 2023.