acceptodds
Withdrawn from ICLR 2027

Learning-Augmented Online Optical Interconnect Reconfiguration

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Optical interconnects are a novel switching technology currently deployed in data center networks due to their extremely low latency and high bandwidth. However, dynamically establishing optical circuits is not free and introduces undesirable delays, disrupting the network during reconfigurations. Existing approaches focus on two ends of a spectrum: either they dynamically reconfigure the network in an oblivious manner, or they optimize for long-lasting static solutions. We study the online optimization problem of such interconnects and present a learning-augmented algorithm that decides when and how to reconfigure. Our algorithm leverages predictions of the incoming traffic to strike a smooth tradeoff between the two previous extremes and shows close-to-optimal performances with regards to the predictions' accuracy.

Primary area:
optimization
Keywords:
learning-augmented algorithms, online algorithms, online matching, optical datacenter networks

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_uEh7OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies online reconfiguration in hybrid electrical and optical datacenter networks. In this setting, the system must balance the latency incurred by routing requests through the electrical switch against the cost of reconfiguring the optical matching. To address this problem, they first proposes a deterministic online GREEDY algorithm with a 6n6n-competitive ratio and proves an Ω(n)\Omega(n) lower bound for any online algorithm. It then develops a 4-approximation offline algorithm, OFF, which is used as a reference for the main learning-augmented algorithm, PRED. PRED receives a predicted matching and subsequently corrects it using observed traffic. The authors prove 4-consistency, O(nlog⁡n)O(n\log n)-robustness, and a smoothness bound parameterized by the matching prediction error. Experiments on several traffic traces evaluate GREEDY and PRED under synthetically controlled prediction errors.

Critical strengths

1.The paper studies a meaningful online reconfiguration problem and provides a fairly complete theoretical characterization of the no-prediction setting. The trade-off between serving requests through the slower electrical network and paying a fixed cost to reconfigure the optical matching is natural and practically relevant.

  1. The learning-augmented analysis provides more than a perfect prediction guarantee. PRED is analyzed in terms of consistency, robustness, and smooth degradation with prediction error. In particular, the paper proves that online corrections monotonically reduce the matching error within a superphase, which gives a principled connection between prediction quality and algorithmic performance.
Critical weaknesses

1.The learning-augmented algorithm has a weaker worst-case guarantee than the paper’s own non-predictive baseline. GREEDY is 6n6n-competitive, whereas PRED is only O(nlog⁡n)O(n\log n)-robust under arbitrarily bad predictions. Thus, introducing prediction can worsen the theoretical worst-case guarantee by a logarithmic factor. This substantially weakens the appeal of the learning-augmented formulation, since a desirable property would be to benefit from accurate predictions while falling back to the O(n)O(n) guarantee of the classical online algorithm when predictions are unreliable. The paper does not establish whether this degradation is unavoidable.
2. The prediction model is strong and is not instantiated by an actual learning system in the experiments. The predictor directly outputs a future matching rather than forecasting requests or traffic over a clearly defined horizon, while the matching is intended to remain relevant over a dynamically determined superphase. In the experiments, predictions are generated by first computing OFF on the complete future trace and then synthetically perturbing its matching by swapping η\eta edges. Therefore, the evaluation demonstrates how PRED behaves given oracle-like matching advice of controlled quality, but does not show that a realistic predictor can generate such advice or how real prediction errors map to the theoretical parameter η\eta.

Questions for authors
  1. Could PRED be modified so that, under arbitrarily bad predictions, its worst-case guarantee is no worse than that of the non-predictive GREEDY algorithm, while still benefiting from accurate predictions?

  2. Could the authors instantiate the prediction component using an actual traffic or matching prediction method, or compare with existing prediction-based optical reconfiguration approaches?

  3. Could the authors make the online interaction protocol of PRED more explicit?

  4. Could the authors clarify the temporal scope of a predicted matching M’ and its relationship to time t?

Reviewer_USHqOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper considers the scenario in which requests in data center networks can be routed either optically at low cost/delay (using optical interconnect switches) or electrically at a higher cost/delay. The goal is to avoid network saturation due to demand growing faster than the link capacity. The authors study the problem of choosing the optical connections inside a router. This boils down to a combinatorial problem of choosing the best sequence of matchings for a sequence of requests. The authors propose several algorithms: offline, online, online with prediction, and prove several results for these algorithms: approximation bound, competitive analysis, consistency, robustness, smoothness. They also show results of simulations of these algorithms.

Critical strengths
  • The paper tackles an important problem in optical networks. Optical routing is a key element to speed up traffic allowing a higher load and to reduce energy consumption.
  • The paper proposes several useful algorithms for different setting: online, offline, when a prediction is available and analyze them,
Critical weaknesses
  • Simple variants of the proposed algorithms (Algorithm 1, Algorithm 2) seem to be a lot more efficient, see discussion below.
  • The complexity of the offline problem is not discussed. However, the authors present an approximation algorithm for the problem. It is not obvious that the problem is not polynomial, and it only makes sense to present an approximation algorithm when the problem is not polynomial. This is an important problem as Algorithm 2 is then used as a brick in the main algorithm of the paper, Algorithm 3 PRED.
  • There are problems in some proofs, for example the proof of theorem 1.
Questions for authors

Algo 1 seems inefficient to me: The algorithm carries out reconfigurations without taking into account the traffic going on the matching edges. This does not seem like a good way to do it. The algo would potentially reconfigure an edge with a lot fewer connections than the one it will destroy. What is the meaning of the algorithm when alpha is smaller than n? The algorithm will reconfigure at each request not in the matching. This is strange.

On Algo 2: Similarly, a simple variant of Algo 2 seems more efficient. Compare the difference of performance between the current matching and the maximum matching. Only do the reconfiguration if the difference is higher than α/3\alpha/3. Also, it seems overkill to compute the maximum matching at each step. A dichotomy could be done or computed only after step t+\alpha/3. The complexity could be greatly reduced.

Problems in Proof of Theorem 1: You did not define a “saturating matching” which is used in your proof. (p13). Your cost definition is not clear.

I do not get how CN(P)≤3αC_N(P) \leq 3\alpha. The cost of the reconfiguration α\alpha is clear. However, there are n(n−1)/2−nn(n-1)/2 - n edges outside of the matching. Thus, if all edges outside of the matching reach values λ−1\lambda-1 before saturation, the serving cost would be [(n(n−1)/2−n)(λ−1)+1]α[(n(n-1)/2 - n)(\lambda-1)+1]\alpha. This is not ≤3α\leq 3\alpha in general. This looks like a major problem in the proof.

line 672. “the saturating matching is the one that concentrates the most requests during PiP_i”. This is not true for Algorithm 1. Did you confuse another algorithm?

**Additional comments. **

Introduction

p1 The reference Mellette et al. 027 (2017); Singh et al. (2016). are a bit old for predictions of expected bandwidth capacity growth. Could you find a more recent prediction?

“The network traffic of data centers grows explosively, roughly doubling each year,” Give a reference.

It may be interesting to explain this discrepancy between traffic growth and capacity growth. Was there a problem with predictions?

I am not sure of how optical interconnects may address the challenge. Optical interconnects speed up the routing

p2 Trustworthy knowledge? Is this the correct term?

p3 line 158-159. Check Grammar + definition in “For a deterministic algorithm, ALG is c- competitive if for every possible input sequence σ, ALG works not worse than c times the cost of OPT, c=supσALGσ/OPTσc = supσ ALG_σ/OPT_σ.”

p4 line 167 This sentence is not clear “...may actively try to degrade the algorithm’s cost”. Are you thinking of an attacker?

p4 line 175 We denote by ALGσALG_{\sigma}... The notation was used on the previous page .

p8 l420 upto -> up to

Proof of Theorem 2. p13 give a reference for Yao’s principle. p14 l708 Si2S_i^2 is not defined

p13 l160 it matching -> its matching

A3 and A4. The authors cite the Hungarian methods for the complexity of the matching problem. However, the algorithm is for bipartite graphs and not complete graphs. Cite Edmonds algorithm instead. It does not change the complexity analysis.

Reviewer_w7cQOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the problem of switching in optical networks via a hybrid optical–electrical switch whose optical connections form a matching. Requests outside that matching incur a service cost, while changing the matching incurs a fixed reconfiguration cost. It develops a prediction-free online algorithm, an offline approximation algorithm, and a prediction-assisted algorithm, PRED, that accepts proposed matchings and corrects them as requests arrive. The paper claims consistency, nlogn robustness, and graceful degradation with prediction error as contributions of its approach.

Critical strengths
  • The paper studies an important problem -- the abstract optimization model is clearly specified and separates service costs from reconfiguration costs.
  • The experiments examine multiple traffic patterns and reconfiguration costs. The reported benefits on HPC traces motivate further investigation, although the comparisons need strengthening (review weaknesses).
Critical weaknesses

Please review the following:

The main theoretical guarantees need stronger justification. I am not fully convinced that the claimed robustness follows from the algorithm as written. There are inconsistencies between the reconfiguration rule and its analysis that need to be resolved, particularly because these guarantees are central to the paper.

The baseline comparisons are not sufficiently convincing. The oblivious baseline reconfigures after every request, making it unnecessarily expensive as reconfiguration costs increase. Comparisons with better-tuned periodic schedules and methods that adapt to recent traffic would provide a more meaningful assessment.

The experiments assume access to unusually informative predictions. Predictions are generated by taking an offline solution that knows the future and introducing errors. This is useful for studying sensitivity, but the paper does not show whether a predictor using only past traffic can deliver comparable gains.

The connection to real network performance remains unclear. The evaluation measures a simplified cost rather than actual packet latency or flow completion time. Queueing, congestion, and traffic arriving during reconfiguration could materially change the practical benefits.

Scalability and operational overhead are insufficiently evaluated. Experiments use a single 32-port configuration, without reporting how long the algorithm takes to make decisions. Given the matching computations involved, I would like to see whether it can keep up with realistic traffic rates and larger switches.

Minor comments and nits

  • Section 4 describes the lookahead stopping threshold as alpha, while Algorithm 2 uses alpha/3.
Questions for authors

What is the exact threshold in Algorithm 3? Please address the corresponding counterexample above and provide a corrected Lemma 2 and robustness/consistency analysis. Which tie-breaking rules are required?

How are the global guarantees completed? Theorem 5 excludes the first and last superphases, while Theorem 4 states a whole-sequence guarantee. Appendix A.1 similarly treats an unfinished final block as negligible. How are these costs handled under the strict competitive-ratio definition in Section 2?

Which matching implementation is used? Does it solve general undirected matching, and have its outputs been checked against exact solutions on small instances?

Do the empirical gains survive stronger online comparisons? Please include holding-time-tuned oblivious schedules and a recent-history demand-aware baseline, alongside at least one predictor using only past traffic.

What supports the latency and deployment claims? Please report decision times, scaling with port count, workload preprocessing, and either a physical latency model or a narrower interpretation of the cost results.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.