PaperlayerView exact revision on arXiv

Source-linked AI summary

CFR-RL: Traffic Engineering with Reinforcement Learning in SDN

Junjie Zhang, Minghao Ye, Zehua Guo, Chen-Yu Yen, H. Jonathan Chao

arXiv:2004.11986v1cs.NIcs.LG

TL;DR

Traffic Engineering must balance link utilization while limiting disturbance from rerouting, but selecting effective critical flows is difficult because the candidate space is enormous. CFR-RL learns a critical-flow selection policy with reinforcement learning and reroutes the selected flows through linear programming. It achieves near-optimal load balancing while rerouting 10.0%-21.3% of traffic and outperforming rule-based heuristics by 1.3%-12.2%.

  • Problem

    Selecting a small set of critical flows for rerouting is difficult because the solution space is huge, while frequent or extensive rerouting can disturb the network.

  • Method

    CFR-RL uses reinforcement learning to learn critical-flow selection from network-performance rewards, then reroutes selected flows using a linear programming optimization problem.

  • Results

    CFR-RL achieves near-optimal load balancing, reroutes 10.0%-21.3% of total traffic, and outperforms rule-based heuristics by 1.3%-12.2%.

  • Takeaways & Limitations

    CFR-RL selects a small number of critical flows for each traffic matrix while reducing end-to-end delay and network disturbance, and it generalizes to traffic matrices not explicitly used for training.

Abstract

from arXiv · show

Traditional Traffic Engineering (TE) solutions can achieve the optimal or near-optimal performance by rerouting as many flows as possible. However, they do not usually consider the negative impact, such as packet out of order, when frequently rerouting flows in the network. To mitigate the impact of network disturbance, one promising TE solution is forwarding the majority of traffic flows using Equal-Cost Multi-Path (ECMP) and selectively rerouting a few critical flows using Software-Defined Networking (SDN) to balance link utilization of the network. However, critical flow rerouting is not trivial because the solution space for critical flow selection is enormous. Moreover, it is impossible to design a heuristic algorithm for this problem based on fixed and simple rules, since rule-based heuristics are unable to adapt to the changes of the traffic matrix and network dynamics. In this paper, we propose CFR-RL (Critical Flow Rerouting-Reinforcement Learning), a Reinforcement Learning-based scheme that learns a policy to select critical flows for each given traffic matrix automatically. CFR-RL then reroutes these selected critical flows to balance link utilization of the network by formulating and solving a simple Linear Programming (LP) problem. Extensive evaluations show that CFR-RL achieves near-optimal performance by rerouting only 10%-21.3% of total traffic.

I. INTRODUCTION

Traditional TE can optimize link utilization but may cause network disturbance by rerouting many flows. CFR-RL learns to select a small set of critical flows adaptively, then reroutes them with LP to balance utilization while limiting disturbance.

  • Traditional TE periodically reroutes many flows to minimize maximum link utilization, but frequent rerouting can cause packet reordering and service disruption.
  • ECMP forwards most traffic over equal-cost paths, while SDN selectively reroutes critical flows with dominant effects on network performance.
  • Selecting critical flows is difficult because choosing 10 among 100 flows yields approximately 17 trillion combinations.
  • Rule-based heuristics cannot reliably adapt to changing traffic matrices and network dynamics when their design assumptions are violated.
  • CFR-RL learns a critical-flow selection policy from network-performance rewards and reroutes selected flows using a linear programming optimization problem.
  • CFR-RL outperforms rule-based heuristics by up to 12.2%, reroutes 11.4%-14.7% less traffic on average, and achieves near-optimal performance with 10%-21.3% of total traffic rerouted.

II. RELATED WORKS

Prior TE work uses optimization, multipath routing, hybrid routing, and machine learning to improve network performance. The cited approaches generally do not address disturbance and service disruption caused by rerouting, motivating CFR-RL's selective-flow design.

  • Prior MPLS, OSPF, and ECMP approaches formulate routing or tune link costs to distribute traffic and balance link utilization.
  • Dynamic hybrid routing and partial-SDN designs react to traffic variation or improve utilization and packet loss through routing-policy and deployment choices.
  • Machine-learning studies apply semi-supervised learning or reinforcement learning to network protocols, routing decisions, signaling delay, and related optimization objectives.
  • The cited prior works do not consider mitigating network disturbance and service disruption caused by rerouting.
  • CFR-RL learns a critical-flow selection policy from traffic matrices and combines it with LP-based rerouting rather than applying RL to the flow-routing optimization itself.

IV. LEARNING A CRITICAL FLOW SELECTION POLICY

CFR-RL formulates critical-flow selection as reinforcement learning over traffic-matrix states and a large combinatorial action space. Its policy is trained with LP-derived rewards, baselines, and entropy-enhanced policy gradients.

  • A. Reinforcement Learning Formulation: The RL agent uses the traffic matrix as its state while omitting topology information because the topology typically remains unchanged.
  • A. Reinforcement Learning Formulation: Selecting K critical flows creates a combinatorial action space over N∗(N−1) possible flows, so CFR-RL samples K distinct actions.
  • A. Reinforcement Learning Formulation: After rerouting sampled critical flows, CFR-RL defines reward as 1/U, where U is maximum link utilization obtained from the rerouting optimization problem.
  • B. Training Algorithm: The policy network maps a traffic-matrix state to action probabilities and represents a K-flow solution as a combination whose action order does not matter.
  • B. Training Algorithm: REINFORCE updates policy parameters using reward relative to a state-specific average-reward baseline, reinforcing solutions that empirically obtain better rewards.
  • B. Training Algorithm: Entropy regularization encourages exploration by discouraging premature convergence to suboptimal deterministic policies.

V. REROUTING CRITICAL FLOWS

The rerouting stage balances link utilization for the selected critical flows through an optimization procedure. The supplied passages identify the training algorithm components but provide little detail about the optimization formulation itself.

  • The rerouting stage is designed to balance network link utilization for the selected critical flows.
  • Algorithm 1 initializes policy parameters and state statistics, samples batches of states and solutions, receives rewards, and updates the policy.
  • The training update combines policy-gradient terms with reward baselines and entropy regularization before adjusting the policy parameters.

A. Notations

CFR-RL reroutes selected critical flows explicitly while leaving remaining traffic on ECMP. The rerouting LP chooses flow-specific routing ratios to minimize maximum link utilization, subject to routing constraints.

  • Remaining traffic uses ECMP, while the selected critical-flow set fK receives explicit routing optimization.
  • The optimization takes network capacities, critical-flow demands, and background ECMP link loads as inputs.
  • The LP obtains explicit routing ratios σs,d_i,j that minimize maximum link utilization U.
  • Routing ratios are constrained between 0 and 1 for every selected flow and network link.
  • The solution accounts for link capacity, flow conservation, and a small path-length penalty that prioritizes minimizing U.
  • An LP solver produces the explicit routing solution, which the SDN controller installs and updates at switches.

VI. EVALUATION

The evaluation uses simulation experiments on real-world network topologies to assess CFR-RL and compare it with rule-based heuristic schemes.

  • Simulation experiments evaluate CFR-RL using real-world network topologies.
  • The study compares CFR-RL against other rule-based heuristic schemes.

A. Evaluation Setup

The evaluation combines a three-layer policy network, four real-world ISP topologies, measured Abilene traffic matrices, and parallel actor training. It also uses a load-balancing performance ratio to compare CFR-RL with optimal explicit routing.

  • Implementation: The policy network uses a 3 × 3 convolutional layer with 128 filters, a 128-neuron fully connected layer, and an N ∗(N −1)-neuron output layer for possible critical flows.
  • Evaluation setup: Evaluation covers Abilene and three ROCKETFUEL ISP topologies using measured Abilene traffic matrices sampled every 5 minutes.
  • Implementation: Twenty parallel actor agents send state, action, and advantage tuples to a central learner for policy-network updates.
  • Metrics: The load-balancing performance ratio compares CFR-RL's maximum link utilization with the optimal explicit-routing value, with 1 indicating equal performance.

4) Metrics:

The evaluation defines ratios for load balancing, end-to-end delay, and rerouting disturbance. These metrics compare CFR-RL with optimal routing and quantify how much traffic is rerouted.

  • Load balancing: The load-balancing ratio uses optimal maximum link utilization as its reference, and lower values indicate greater distance from optimal routing.
  • Load balancing: The optimal-routing comparison solves a similar LP for all flows with zero background link load.
  • End-to-end delay: The end-to-end delay ratio compares CFR-RL's delay with the minimum delay achieved by optimal explicit routing for all flows.
  • End-to-end delay: A higher end-to-end delay ratio is better, and a value of 1 matches the optimal-routing delay.
  • Rerouting disturbance: The disturbance metric is based on the amount of traffic that needs rerouting, with smaller RD indicating less disturbance.

5) Rule-based Heuristics:

The evaluation compares CFR-RL with rule-based heuristics and examines how increasing the number of selected critical flows affects load balancing and rerouting disturbance. CFR-RL reaches near-optimal load balancing with a small selected-flow fraction, while heuristic comparisons use traffic-matrix and network-wide evaluations.

  • Rule-based heuristics: Top-K selects the K largest flows by demand volume, whereas Top-K Critical selects the K largest flows on the most congested links.Both heuristics assume that these flows have a dominant impact on network performance.
  • Critical-flow count: K = 0 represents default ECMP routing, and increasing K leaves room for further load-balancing improvement.CFR-RL experiments vary the number of selected critical flows while fixing other parameters.
  • Performance comparison: The comparisons evaluate average and per-traffic-matrix load-balancing performance, with one-standard-deviation error bars reported for average results.The evaluation covers four networks and compares CFR-RL with the rule-based schemes and ECMP.
  • Critical-flow count: 10% of flows is sufficient for CFR-RL to achieve near-optimal load balancing across the four networks.The subsequent experiments set K = 10% ∗N ∗(N −1) for each network.
  • Rerouting disturbance: CFR-RL’s average rerouting disturbance is compared in Table II against Top-K, Top-K Critical, and ECMP.Rerouting disturbance is treated as the percentage of total traffic rerouted.

2) Performance Comparison:

The performance comparison evaluates load balancing and end-to-end delay across four networks, traffic matrices, and traffic models. CFR-RL performs consistently across traffic models, reduces rerouted traffic, and outperforms the heuristic schemes and ECMP in end-to-end delay except on EBONE.

  • End-to-end delay: CFR-RL outperforms heuristic schemes and ECMP in end-to-end delay in all networks except EBONE.In EBONE, heuristic schemes perform better with the exponential traffic model.
  • Network disturbance: CFR-RL greatly reduces network disturbance by rerouting at most 21.3%, 11.2%, 11.3%, and 11.2% of total traffic across the four networks.Top-K Critical reroutes more traffic, while Top-K reroutes more than 42% on Abilene and 32%, 33%, and 32% on the other networks for exponential traffic matrices.
  • Overall performance: CFR-RL achieves near-optimal load balancing while reducing end-to-end delay and network disturbance by selecting and rerouting a small number of critical flows.The corresponding rerouted traffic amount is also small for uniform traffic matrices, where the three schemes reroute similar amounts.
  • Traffic-model robustness: Top-K Critical performs well under the exponential traffic model but degrades under the uniform traffic model.The text attributes this degradation to saturated links and unavailable underutilized alternative paths for selected flows.
  • Traffic-matrix evaluation: The week-two evaluation compares full CDFs and daily load-balancing and end-to-end-delay performance for four traffic matrices.Training uses first-week traffic matrices and evaluation uses the following week for Abilene.

3) Generalization:

CFR-RL requires substantial offline training, with training time increasing for larger networks, while its compact policy enables fast inference. Hyperparameter choices affect training stability and representation capacity.

  • Training and inference time: Approximately 3 hours were required to train Abilene, compared with approximately 16 hours for the larger EBONE network.Abilene required about 10,000 iterations, whereas EBONE required about 60,000 iterations.
  • Hyperparameters: Table III compares average load balancing performance ratios across different hyperparameter settings in the Abilene network.
  • Training and inference time: Inference took less than 1 second for Abilene and EBONE and less than 2 seconds for Sprintlink and Tiscali.
  • Hyperparameters: A learning rate that is too large can destabilize training, while smaller rates are more stable but may require longer training.The authors selected α = 0.001 to encourage exploration early in training.
  • Hyperparameters: Too few convolutional filters or fully connected neurons may restrict the representation learned by CFR-RL.

5) Hyperparameters:

CFR-RL automatically selects critical flows with reinforcement learning and reroutes them through optimization, while future work addresses objectives, scalability, and retraining. The evaluations report lower rerouting traffic alongside stronger performance than rule-based heuristics.

  • Conclusion: CFR-RL learns critical-flow selection without domain-specific rule-based heuristics and reroutes selected flows through an optimization problem.
  • Objectives: CFR-RL could be reformulated to minimize overall end-to-end delay by changing the reward and rerouting optimization objective.
  • Results: CFR-RL reroutes 10.0%-21.3% of traffic and performs 1.3%-12.2% better than rule-based heuristic schemes.The authors attribute this to searching candidate flows rather than considering only elephant flows on congested links.
  • Scalability: Scaling to larger networks is constrained by increasing LP complexity, larger solution spaces, and longer reinforcement-learning convergence.
  • Retraining: The offline training policy can be periodically updated with new traffic matrices, but retraining criteria and dataset selection remain open questions.The paper specifically suggests including outlier traffic matrices for retraining.
Loading 2004.11986v1…