Learning-based Algorithms
for Network Optimization
Nicola Di Cicco
IIJ Research Laboratory Seminar
13/08/2024

About me

Jeff set me up forthis presentation.
Help!
8/29/2024

IIJ Research Laboratory Seminar1About me
I’m a 3rd year PhD student at
Politecnico di Milano, Italy

TL;DR of this talk• Optimization algorithms solve problem instances individually,
but instances are strongly correlated in practice!
• We want to discover and exploit these correlations todevelop specialized and efficient solving algorithms• Machine Learning is a great hammer for this problem• Illustrative numerical results look pretty good
8/29/2024

IIJ Research Laboratory Seminar3

Outline of this talk (if you’re still listening)
1) We will practically see why Machine Learning for optimization
makes actual sense (it is not just drinking the 2024’s Kool-aid)

2) We will see general design paradigms of ML for optimization,with practical examples from recent networking papers
3) We will discuss in greater technical detail two contributions on
the topic from my research group at Politecnico di Milano, Italy

8/29/2024

IIJ Research Laboratory Seminar4

“Why care about Machine
Learning for Optimization?” ** excerpt from a review I got for a submission at INFOCOM two years ago (the reviewer assigned me 1/5 and killed my paper)

Brief rundown on “optimization”• We want to find the values for decision variables that optimize
an objective function while satisfying a set of constraints• Example: Knapsack problem• 𝑥𝑖 is 1 if object 𝑖 is in the knapsack• Maximize profit s.t. capacity constraint

8/29/2024

IIJ Research Laboratory Seminar

6

Should you care about the general case?
• Suppose you’re interested in solving a
fancy new optimization problem…
• … but you find that it is, in general,computationally intractable• However, if you focus on instanceswith specific characteristics…
• … you might be able to discoverinteresting things!
8/29/2024

IIJ Research Laboratory Seminar

7

Example: Oblivious Routing• Problem: find the best way to distribute network flows
irrespectively from the actual demands (hence, “oblivious”)• Unfortunately, NP-Hard in the general case…
• … but can be made tractable for certain topologies [1][1] S. Supittayapornpong et al., “Optimal Oblivious Routing for Structured Networks,” in INFOCOM, 2022
8/29/2024

IIJ Research Laboratory Seminar

8

Example: Traffic Engineering with ECMP
• Problem: find the best integer edge weights, such that traffic is
optimally distributed via equal-cost shortest paths• Does not achieve optimal flow distribution in general…
• … but it provably does for Clos networks [2][2] M. Chiesa et al., “Traffic Engineering with ECMP: an Algorithmic Perspective,” in ToN, 20178/29/2024

IIJ Research Laboratory Seminar

9

Example: RSA in Optical Networks• Problem: route network flows through optical wavelengths thatmust be contiguous over spectrum and continuous over paths• Unfortunately, NP-Hard in the general case…
8/29/2024

IIJ Research Laboratory Seminar

10

Example: RSA in Optical Networks• … but optical networks have structure!
• How do we systematically exploit this? (Open question!)
8/29/2024

IIJ Research Laboratory Seminar

11

Your turnTake 30 seconds to think about anotheruse-case where problem instances are, inpractice, strongly correlated!

8/29/2024

IIJ Research Laboratory Seminar

12

Main takeaway

Real-world problem instances
stem from data distributions!

8/29/2024

IIJ Research Laboratory Seminar

13

State-of-the-Art in Optimization• As of 2024, there exist a bunch of very efficient solvers…

• … but these solvers are tailored for the general case, and may
not work well for the problems we’re interested in solving!
8/29/2024

IIJ Research Laboratory Seminar

14

State-of-the-Art in Optimization• Of course, we can leverage specialized algorithms…

• … but designing them requires extensive domain knowledge
for discovering the special characteristics of a problem!
8/29/2024

IIJ Research Laboratory Seminar

15

The big question

Can machines autonomously learn
specialized algorithms from data?

8/29/2024

IIJ Research Laboratory Seminar

16

Learning for Optimization

8/29/2024

IIJ Research Laboratory Seminar

17

A Taxonomy of ML for Optimization
1. End-to-End Learning• We use ML to directly predict solutions for our problem

2. Learning Algorithm Configurations• We use ML to provide “information” to an optimization algorithm

3. Learning Alongside Optimization• We use ML to implement “subroutines” of a larger algorithm[3] Y. Bengio et al., “ML for Combinatorial Optimization: A Methodological Tour D’Horizon” in EJOR, 2021
8/29/2024

IIJ Research Laboratory Seminar18

End-to-End Learning• We learn statistical relations between a problem instance anddecision variables (no optimization is happening!)• e.g., in a Knapsack, high-value low-weight items are likely to be packed+ Fast and scalable- No performance guarantees- Difficult to enforce hard constraints
8/29/2024

IIJ Research Laboratory Seminar

19

Premise: Multi-Commodity Flow
• Problem: given a network, a set of source-destination paths and a
traffic matrix, decide how to optimally distribute the traffic• A classical objective is minimizing the maximum link utilization

8/29/2024

IIJ Research Laboratory Seminar

20

Example: DOTE [4]• Goal: solve large-scale multi-commodity flow problems• Idea: leverage differentiability of the objective with respect to asolution to train a end-to-end a predictive neural network[4] Y. Perry et al., “DOTE: Rethinking (Predictive) WAN Traffic Engineering” in NSDI, 2023
8/29/2024

IIJ Research Laboratory Seminar

21

Learning Algorithm Configurations• Given a specific problem instance, a ML model predicts the“optimal configuration” of an optimization algorithm.
• e.g., algo’s hyperparameters, warm-starting solution, …

+ Can guarantee feasibility (and possibly optimality)- Harder to train (Supervised Learning might not be possible)
8/29/2024

IIJ Research Laboratory Seminar

22

Example: TEAL [5]• Problem: solve large-scale multi-commodity flow problems• Idea: use ML to predict a tentative solution, then do local searchwith ADMM to improve the solution and fix broken constraints[5] Z. Xu et al., “Teal: Learning-Accelerated Optimization of WAN Traffic Engineering” in SIGCOMM, 2023
8/29/2024

IIJ Research Laboratory Seminar

23

Learning Alongside Optimization• A ML model implements subroutines of a “master algorithm”• e.g., mutation function in a GA, neighbour selection policy in a LS

+ Very powerful+ Can guarantee feasibility (and possibly optimality)- Harder to train (Supervised Learning might not be possible)
8/29/2024

IIJ Research Laboratory Seminar

24

Example: DeepLS [6]• Problem: learn problem-tailored neighbourhood selection
policies for Local Search algorithms• Idea: train a neural net with Reinforcement Learning to do it[6] Di Cicco et al., “DeepLS: Local search for network optimization based on lightweight deep reinforcement learning” in TNSM, 2023
8/29/2024

IIJ Research Laboratory Seminar

25

Takeaways
ML for optimization can be roughly divided in two:
1. Machine Learning only
2. Machine Learning integrated with classical algorithms• Using only Machine Learning allows us to trivially leverage
massive hardware acceleration (GPUs, etc.), but enforcing
feasibility and performance guarantees is challenging• ML + optimization allows us to build upon tens of years ofliterature, at the price of a possibly more complex training
procedure and implementation
8/29/2024

IIJ Research Laboratory Seminar26

st
1 Case Study:

Augmenting Local Search withReinforcement Learning

8/29/2024

IIJ Research Laboratory Seminar

27

Reference paper

8/29/2024

IIJ Research Laboratory Seminar28

What the paper does
1. Learn problem-specific neighbor selection policies in Local
Search algorithms via Deep Reinforcement Learning
2. Use a special type of neural network with symmetries(equivariant nets) for scaling to larger instances than training

8/29/2024

IIJ Research Laboratory Seminar

29Premise: Reinforcement Learning• RL is a paradigm for solving generic decision-making problems• The RL objective is maximizing the accumulation of rewards, i.e.,

8/29/2024

IIJ Research Laboratory Seminar30Premise: Deep Reinforcement Learning• State and action spaces might be too large for exact algorithms• We can use NNs as universal function approximators!
• DRL algorithms generally follow this workflow:
1. Collect a bunch of experiences by running 𝜋𝜃 𝑎 𝑠 on the env
2. Update 𝜃 using some pseudo-gradient• e.g., Policy Gradient algorithms[7] J. Schulman et al., “High-Dimensional Continuous Control Using Generalized Advantage Estimation” in ICLR, 2016
8/29/2024

IIJ Research Laboratory Seminar

31

Local Search as a DRL problem• State: value of each decision variable + variable-specific features• e.g., if variables are link weights, include link centrality and bandwidth• Action: select which variable to perturb• Reward: change in the objective function’s value
8/29/2024

IIJ Research Laboratory Seminar32Permutation-equivariant neural nets
• Equivariant NNs are NNs with symmetry• A set function 𝑓: 𝑋 𝑀 → 𝑌 𝑀 is permutation-equivariant if:
𝜋 𝑓 𝑥 = 𝑓 𝜋 𝑥 for every permutation 𝜋• i.e., if we permute the ordering of the inputs, the same
permutation is reflected in the ordering of the outputs

8/29/2024

IIJ Research Laboratory Seminar

33

Equivariant NNs for Local Search• Problem: traffic engineering with ECMP
• Decision variables: link weights• n. of links is arbitrary; n. of features per link is fixed
8/29/2024

IIJ Research Laboratory Seminar

34

Illustrative numerical results• Problem: traffic engineering with ECMP
• Objective: minimize the maximum link load
• DeepLS scales to instances up to~4x larger than training• DeepLS outperforms competitive
ML-based (MARL-GNN) and non(DEFO) algorithms

8/29/2024

IIJ Research Laboratory Seminar

35

Illustrative numerical results• Problem: Routing and Spectrum assignment in optical networks• Objective: maximize the n. of admitted requests• DeepLS scales to instances up to~5x larger than training• DeepLS is on-par with a heavily
customized Genetic Algorithm
for RSA (GA-FF), at a fraction of
the complexity
8/29/2024

IIJ Research Laboratory Seminar

36

Takeaways• The performance of Local Search algorithms strongly depends
on the considered neighbour selection policy• We can use Reinforcement Learning and simple neural networks
to autonomously learn the best neighbourhood selection
policy for a specific problem class• Numerical results illustrate better or comparable performancewith respect to to handcrafted solutions
8/29/2024

IIJ Research Laboratory Seminar

37

nd
2

Case Study:

Machine Learning for LowMargin Optical-Network Planning

8/29/2024

IIJ Research Laboratory Seminar

38

Reference paper

8/29/2024

IIJ Research Laboratory Seminar

39

What the paper does
1. Use Machine Learning to model the Bit-Error-Rate of opticalsignals in Elastic Optical Networks
2. Integrate the ML model with an ILP-based optimization
algorithm to forbid BER-unfeasible solutions

8/29/2024

IIJ Research Laboratory Seminar

40Premise: Elastic Optical Networks• Wavelength-Division Multiplexing (WDM) optical networks
use a fixed spectrum grid -> spectrum underutilization• Elastic Optical Networks use finer (e.g., 12.5 GHz) subcarriers,
with the possibility of using multiple modulation formats[8] M. Imran et al., “A Survey of Optical Carrier Generation Techniques for Terabit Capacity Elastic Optical Networks” in COMST, 20178/29/2024

IIJ Research Laboratory Seminar

41

Premise: Quality-of-Transmission (QoT)• A lightpath must be of sufficient “quality” to function properly• Generally, we want an Optical Signal-To-Noise Ratio (OSNR)
achieving a low-enough Bit-Error-Rate (e.g., 10−3 pre-FEC)• The OSNR at the receiver depends upon many things, including:• Total path length and fiber types• Nonlinear noise caused by the fiber’s Kerr effect• Non-flatness of the amplifier’s gain profile• Filtering penalties• Connector losses
8/29/2024

IIJ Research Laboratory Seminar

42

Premise: The Gaussian-Noise (GN) Model• The GN Model is the current SoTA for optical-network planning• Accurate and fast (it is just computing a formula!), but…

• … it’s a conservative approximation, resulting in large margins[9] D. Semrau et al., “A Closed-Form Approximation of the Gaussian Noise Model …”, in JLT, 20198/29/2024

IIJ Research Laboratory Seminar

43

Machine Learning for QoT Estimation• We treat QoT estimation as a classification problem• We predict whether a lightpath will be OSNR-feasible or notbased on a general set of lightpath features

8/29/2024

IIJ Research Laboratory Seminar

44

Iterative RSA with Machine Learninge.g., suppose that LP 1 is unfeasible• We impose that LP 1 and its closest
neighbors (LPs 2 and 3) cannot be
simultaneously chosen• Do the same for all unfeasible LPs
8/29/2024

IIJ Research Laboratory Seminar

45

Illustrative numerical results• Baseline: margined reach tables for each path-modformat

8/29/2024

IIJ Research Laboratory Seminar46

Takeaways• In practice, optical networks operate subject to large QoT
margins, which can result in spectrum underutilization• We can leverage data (field or testbed measurements) and ML
for accurately estimating the lightpaths’ QoT, enabling nearzero margin optical-network planning• Numerical results illustrate ~35% spectrum savings w.r.t.
conventional margined network planning approaches
8/29/2024

IIJ Research Laboratory Seminar

47

Challenges &Research Opportunities

8/29/2024

IIJ Research Laboratory Seminar

48

Optimization Under Uncertainty• Optimization under uncertainty is very well-studied• The effectiveness of all of the above methodologies heavily
relies on a suitable model of parameter uncertainty
8/29/2024

IIJ Research Laboratory Seminar49

Uncertainty Quantification• Many ML algorithm can estimate predictive uncertainties• Gaussian Processes, Quantile Regression, Conformal Prediction…

How to best integrate ML uncertainty quantification withmethods from optimization under uncertainty?
[9] M. Zecchin et al., “Forking Uncertainties: Reliable Prediction…” in arXiv preprint, 2023
8/29/2024

IIJ Research Laboratory Seminar

50Generalization• “Learning without generalization is pointless” [3]• It is expected that a ML-based optimization algorithm is able togeneralize to problem instances “different” than training• One aspect of generalization: scaling to large instances
How to design ML models and input representations thatenable consistent scalability to instances larger than training?
[3] Y. Bengio et al., “ML for Combinatorial Optimization: A Methodological Tour D’Horizon” in EJOR, 2021
8/29/2024

IIJ Research Laboratory Seminar

51

Generalization• Generalization is closely related to instance distribution
How do we generate training data that covers the
distribution of instances we are interested in?

How can we enable generalization / fast adaptation to
instances from a data distribution different than training?

8/29/2024

IIJ Research Laboratory Seminar52

Interpretability• Operators are reluctant about using technologies they cannot
satisfactorily explain “why they work” to stakeholders• Machine Learning models not only are black boxes, but they can
perform arbitrarily bad under ”unlucky” or adversarial inputs
How to distill human-understandable, actionable algorithmic
insights from ML-based optimization algorithms?

8/29/2024

IIJ Research Laboratory Seminar53

that’s all folks