AI Research Portal

This paper introduces Hierarchical Reinforcement Learning with Topology-Aware Exploration (HRL-TAE), an end-to-end framework designed to solve the multi-path commodity flow problem (MPCFP) in communication networks. HRL-TAE dynamically generates high-quality routing solutions based on real-time network states by integrating a topology-aware exploration mechanism and a State Transition Guiding List (STGL) to transform the problem into a Markov Decision Process. It employs a two-layer network for path construction and ratio allocation, along with an adaptive constraint-driven mask and a Quadruple Collaboration Training (QCT) method. The authors claim that HRL-TAE achieves superior performance in simulations and real-world experiments compared to existing algorithms.

The paper identifies several bottlenecks in existing approaches to the Multi-Path Commodity Flow Problem (MPCFP):

Neglect of Real-time Network State: Current studies often rely on pre-generated routing paths, which fail to account for the real-time load state of the network.

HRL-TAE is presented as the first fully end-to-end framework to solve MPCFP by addressing its two coupled sub-problems: path construction and ratio allocation, using a two-layer network to enhance solution quality.
A unique Tree-Like Exploration Process (TLEP) rule is designed to facilitate topology awareness, exploration, and decision-making, dynamically updating the State Transition Guiding List (STGL) to transform MPCFP into a Markov Decision Process (MDP).
An adaptive constraint-driven mask mechanism is developed to eliminate infeasible actions during exploration, ensuring strict adherence to problem constraints without heuristic repair.
The Quadruple Collaboration Training (QCT) method is proposed to jointly train the two layers, recombining training and baseline networks to obtain accurate gradient estimates, tackle credit assignment, and enhance training efficiency.

HRL-TAE is a fully end-to-end hierarchical reinforcement learning framework. The problem is transformed into a Markov Decision Process (MDP) using the Tree-Like Exploration Process (TLEP) and a dynamically updated State Transition Guiding List (STGL).

Architecture: The framework consists of two closely coupled layers:

Path Construct Layer: Selects one or more nodes for future visits.
Ratio Allocate Layer: Allocates traffic ratios among the selected nodes. Both layers adopt a similar structure, which includes an Input Embedding, Encoder Mask, Encoder (with Multi-Head Attention, Scaled Dot-Product Attention, Feed Forward, Add & Norm), Decoder Embedding, and Decoder (with Multi-Head Attention, Scaled Dot-Product Attention, Concat & Linear, SoftMax/Normal, Add & Norm).

Adaptive Constraint-Driven Mask Mechanism: This mechanism filters out infeasible actions. In the path construct layer, the encoder mask blocks already visited nodes, and the decoder selects only unvisited neighbors of the current node. In the ratio allocate layer, the encoder mask is identical to the path construct layer's, but the decoder is restricted to nodes selected by the path construct layer.

Objective: The primary objective is to minimize the Maximum Link Utilization (MLU), calculated as: MLU = max(Σq∈Q,k∈K Pq,k(i, j) * Uq,k) / C(i, j), ∀i, j∈ N (4)

Key Equations (Problem Constraints):

Edge Capacity Limitation: Σq∈Q,k∈K (p(i, j) × Uq,k) ≤ C(i, j),∀i, j∈ N (1)
Flow Split Conservation: Σi∈N p(i, j) = Σz∈N p(j, z), ∀j∈N{sq, dq},∀q ∈ Q,∀k ∈ Κ (2)
Commodity Demand Constraints: Σk∈K uq,k = Bq, ∀q ∈ Q (3)

State Transition Guiding List (STGL): At each step τ, STGL contains (Nτ, Bτ), where Nτ are IDs of nodes to visit and Bτ are quantities allocated to those nodes. STGL guides state transitions by clearing data at the first position, marking the current node as reached, updating edge capacities, incorporating new decisions, and sorting based on distance to the destination.

Quantity calculation: q' = (r' × QT) / Σr' (5)
Capacity update: C(Xτ,v)' = C(Xτ,v) – q', σ∈ [1,k'] (6)

Reward: The reward is defined as the negative of MLU, provided until the current flow is fully routed. Both layers receive an identical and undiscounted reward.

Architecture:
- Both layers (path construct and ratio allocate) adopt a similar structure.
- Components include Input Embedding, Encoder Mask, Encoder (with Multi-Head Attention, Scaled Dot-Product Attention, Feed Forward, Add & Norm), Decoder Embedding, and Decoder (with Multi-Head Attention, Scaled Dot-Product Attention, Concat & Linear, SoftMax/Normal, Add & Norm).
Loss/Objective:
- The training of both layers employs the REINFORCE algorithm with a rollout baseline.
- The loss value for the training of path construct layer's neural parameters is calculated as: loss = − Σi=1 to n (R(πI) – R(πBL))logPe(πI) − Σi=1 to n (R(πI) – R(πBL))logo(πI) (7)
Optimization:
- Optimizer: Adam optimizer.
- Learning Rate: Dynamically decaying, starting at lr = 0.0001.
Training Settings:
- Epochs: 1000.
- Batches per epoch: 10.
- Batch Size: 128.
- Training data: Synthetic datasets randomly generated based on connectivity patterns of each topology.
Hardware:
- Processor: 9th Intel Core i9 processor.
- GPU: NVIDIA GeForce GTX1660Ti.
- RAM: 32GB.
- Software: Python 3.10.

Datasets:
- Simulation Experiments: Four real network topologies from the Internet topology zoo data set: Abilene (11 nodes, 14 links), ATT (25 nodes, 56 links), Geant (37 nodes, 56 links), DFN (58 nodes, 87 links). Each case consists of 20 instances.
- Real-World Experiments: Two topologies generated via the Waxman algorithm: H9N (9 nodes, 18 links) and H18N (18 nodes, 37 links).
Metrics:
- Objective (Obj.): Maximum Link Utilization (MLU). Lower values are better.
- Time(s.): Execution time in seconds.
Baselines:
- TEAL: Pre-generates paths by KSP and allocates flows using a deep reinforcement learning network.
- ECMP: Constructs K subpaths for each flow and evenly allocates flow.
- DRSIR: Uses a DRL network to select paths and allocate flows among pre-generated paths in a software-defined network.
- Abl.1: HRL-TAE framework without QCT, using basic REINFORCE to update both layers together.
- Abl.2: HRL-TAE framework with layers trained alternately, switching every 10 epochs.
Numeric Results (Simulation):
- HRL-TAE consistently achieves lower Objective (MLU) values across all 20 cases for Abilene, ATT, Geant, and DFN topologies compared to TEAL, ECMP, and DRSIR.
- Average improvements over baselines: 7.08% (TEAL), 15.35% (ECMP), and 9.74% (DRSIR).
Numeric Results (Real-World):
- HRL-TAE consistently achieves lower Objective (MLU) values across all 10 cases for H9N and H18N topologies compared to TEAL, ECMP, and DRSIR.
- Average improvements over baselines: 6.90% (TEAL), 15.80% (ECMP), and 8.72% (DRSIR).
Ablation Study Results:
- HRL-TAE outperforms Abl.1 and Abl.2 in all cases, showing average improvements of 8.86% and 4.75%, respectively.
- QCT markedly reduces learning fluctuations and enhances training efficiency, as shown in training curves on Geant topology.
Runtime/Training Cost:
- HRL-TAE's execution time is comparable to baselines, generally higher than ECMP but similar to or faster than TEAL and DRSIR in many cases. For example, in simulation case 1 (Abilene), HRL-TAE: 0.12s, TEAL: 0.16s, ECMP: 0.04s, DRSIR: 0.13s.

The paper states that future work will "continue to conduct research on MPCFP, apply it to more complex scenarios, such as joint optimization in multiple sub-nets with hybrid protocols, and adopt more advanced algorithms." This implies that the current HRL-TAE framework may not yet be fully optimized for or capable of handling these more complex scenarios, hybrid protocols, or may benefit from more advanced algorithms.

Method evidence: "To overcome the aforementioned limitations, we propose HRL-TAE, a fully end-to-end approach with two-layer network for MPCFP. In HRL-TAE, the path construct layer constructs subpaths for each flow, and the ratio allocate layer allocates traffic ratios among them." (section: Introduction)
Result evidence: "As shown in the table, HRL-TAE demonstrates superior performance with comparable execution time across diverse cases. Specifically, compared with the TEAL, ECMP, and DRSIR algorithms, the routing schemes generated by HRL-TAE achieve average improvements of 7.08%, 15.35%, and 9.74%, respectively." (section: Results)
Limitation evidence: "In the future, we will continue to conduct research on MPCFP, apply it to more complex scenarios, such as joint optimization in multiple sub-nets with hybrid protocols, and adopt more advanced algorithms." (section: Conclusion)