TL;DR
This paper introduces CFR-RL, a novel reinforcement learning (RL) approach for traffic engineering (TE) in Software-Defined Networks (SDN). CFR-RL intelligently identifies and reroutes a small subset of "critical" traffic flows to balance network load, significantly improving performance and reducing network disturbance compared to traditional methods.
What Problem Does This Paper Address?
Traditional traffic engineering (TE) aims to optimize network performance by rerouting traffic to balance link utilization. However, existing methods often reroute a large number of flows, leading to negative impacts like packet out-of-order, increased network disturbance, and a high burden on SDN controllers. While Equal-Cost Multi-Path (ECMP) is a common baseline, it doesn't dynamically adapt to traffic fluctuations. The challenge lies in finding a TE solution that can achieve near-optimal performance with minimal network disturbance, especially in dynamic network environments. Specifically, identifying which flows are "critical" for rerouting is a computationally hard problem with a vast solution space, making rule-based heuristics insufficient as they cannot adapt to changing traffic patterns.
Methods
CFR-RL tackles this problem by decoupling it into two sub-problems: critical flow selection and rerouting.
- Critical Flow Selection: This is the core innovation. CFR-RL uses a Reinforcement Learning (RL) agent to learn a policy for selecting critical flows. The agent takes the current traffic matrix as its state and outputs a probability distribution over possible critical flow selections. The RL algorithm used is a customized REINFORCE algorithm with a baseline to reduce gradient variance. The reward signal for the RL agent is derived from the outcome of the rerouting optimization, specifically the inverse of the maximum link utilization achieved after rerouting. This allows the agent to learn, from scratch, which flows, when rerouted, lead to the best network performance.
- Rerouting: Once a small set of critical flows is identified by the RL policy, these flows are rerouted using a Linear Programming (LP) optimization problem. This LP formulation aims to minimize the maximum link utilization across the network, considering both the rerouted critical flows and the background traffic from non-critical flows (which continue to use ECMP). The authors argue that LP is efficient and optimal for this sub-problem because the number of critical flows is small.
Datasets
The paper uses a combination of real-world and synthetic datasets:
- Real-world: The Abilene network topology and traffic matrices collected over a week.
- Synthetic: Three ISP network topologies (EBONE, Sprintlink, Tiscali) from ROCKETFUEL. For these, link capacities were inferred from link costs, and traffic matrices were generated using both exponential and uniform traffic matrix generation tools.
The Abilene traffic matrices were measured every 5 minutes, providing a rich dataset for evaluating dynamic performance. For the ISP networks, 50 synthetic exponential and 50 synthetic uniform traffic matrices were generated for each topology. A portion of the data was used for training, and the remainder for testing.
Key Insights and Ideas
- RL for Intelligent Flow Selection: The most significant insight is that an RL agent can learn to effectively identify "critical" flows without relying on predefined heuristics. This learned policy adapts to traffic dynamics, leading to better TE decisions.
- Minimal Rerouting for Near-Optimal Performance: CFR-RL demonstrates that rerouting a small percentage of traffic (10%-21.3% of total traffic) can achieve performance comparable to rerouting all traffic or using more complex heuristic methods.
- Trade-off Between Performance and Disturbance: By focusing on critical flows, CFR-RL inherently minimizes network disturbance (packet out-of-order, controller load) while still achieving excellent load balancing and end-to-end delay performance.
- Limitations of Rule-Based Heuristics: The experiments highlight that fixed-rule heuristics (like Top-K flows or Top-K flows on congested links) struggle to adapt to different traffic patterns (e.g., exponential vs. uniform), whereas CFR-RL shows consistent performance.
Key Results
- Load Balancing: CFR-RL achieved near-optimal load balancing performance, outperforming ECMP by a significant margin and showing improvements over rule-based heuristics (e.g., ~7.4% better than Top-K critical on Abilene, ~12.2% better on EBONE).
- End-to-End Delay: CFR-RL also demonstrated strong performance in reducing end-to-end delay, outperforming heuristic schemes and ECMP in most networks.
- Rerouting Disturbance: CFR-RL significantly reduced network disturbance by rerouting only 10%-21.3% of total traffic on average, compared to rule-based heuristics which rerouted substantially more (e.g., up to 42.9% for Top-K).
- Generalization: The trained CFR-RL policy generalized well to unseen traffic matrices from subsequent weeks, indicating its robustness.
- Training Time: Training for the Abilene network took approximately 3 hours, and for the larger EBONE network, about 16 hours. Inference time was reported to be less than 1-2 seconds per network.
Limitations and Future Work
- Scalability: The paper acknowledges that scaling CFR-RL to larger networks is a challenge, as the LP problem for reward calculation becomes more complex with more critical flows and network size. Future work includes exploring parallelization techniques (e.g., more actor agents, GA3C) and multi-SDN controller architectures.
- Retraining: While CFR-RL is trained offline, the authors suggest that periodic retraining could adapt the policy to new traffic patterns. They propose investigating when and how to retrain, and which traffic matrices to include in the training dataset.
- Other Objectives: CFR-RL could be formulated to optimize for other objectives, such as minimizing overall end-to-end delay directly, or explicitly minimizing rerouting traffic. The paper suggests exploring the trade-off between maximizing performance and minimizing rerouting traffic.
- Hyperparameter Tuning: While a good trade-off was found, further investigation into hyperparameter sensitivity and optimization could be beneficial.
Summary updated