Reinforcement Learning for Call Admission Control and Routing in Integrated Service Networks

Peter Marbach, Oliver Mihatsch, Miriam Schulte, John N. TsitsiklisNeurIPS 1997

Overview

This paper applies Reinforcement Learning (RL) to the complex problem of managing call traffic in integrated service telecommunication networks. By decomposing the network into individual "link processes" and using Temporal Difference learning, the authors developed a decentralized policy that outperformed standard industry heuristics (like OSPF) by 50%, coming remarkably close to the theoretical maximum revenue.

The Challenge: Admission Control and Routing

In modern telecommunication networks, providers must solve two simultaneous problems to maximize revenue:

  1. Call Admission Control (CAC): Deciding whether to accept or reject an incoming call.
  2. Routing: Choosing the best path for an accepted call.

While this can be framed as a Dynamic Programming problem, the "curse of dimensionality" makes it impossible to solve exactly. For even a small 4-node network, there are approximately $10^{45}$ possible feature configurations. Traditional methods cannot handle this scale, and existing heuristics often fail to account for the long-term "opportunity cost" of filling up a link with a low-value call that might block a high-value one later.

Methodology

The authors utilize Reinforcement Learning, specifically Sutton’s TD(0) algorithm, to approximate the optimal value function. The core innovations include:

  • Decomposition Approach: Instead of learning one massive global value function, the network is decomposed into individual links. Each link maintains its own local value function, $J^{(l)}$, representing the expected future revenue associated with that specific link.
  • Decentralized Learning and Control: Because the value functions are link-based, training and decision-making can be done locally. When a call arrives, the system simply sums the values of the links in a potential route to decide if it is worth accepting.
  • Quadratic Function Approximation: To handle the continuous state space, the authors use a quadratic approximator that is linear with respect to its parameters. This offered the best balance of convergence speed and performance.
  • Exploration Strategy: During training, the model used a 50% exploration rate (random actions) to ensure it discovered a wide variety of network states, significantly improving the final policy's robustness.

Experimental Setup

Rather than a static dataset, the paper utilizes a simulated integrated service network environment:

  • Topology: A 4-node network with 12 unidirectional links.
  • Traffic Model: Independent Poisson processes for call arrivals.
  • Service Types: Three distinct types of calls with varying bandwidth demands, holding times, and rewards (e.g., Type 3 calls have high bandwidth needs but yield very high rewards).
  • Benchmark: The model is evaluated against the Open-Shortest-Path-First (OSPF) heuristic, a common industry standard.

Key Insights

  • The Power of Local Knowledge: A complex global optimization problem can be effectively solved by summing local, link-specific estimates. This makes the RL approach scalable to much larger networks.
  • Strategic Sacrifice: The RL policy learned a sophisticated admission strategy. It discovered that it should almost exclusively use direct routes for low-reward calls (Types 1 and 2) to save the multi-hop "alternative" routes for high-reward calls (Type 3).
  • Heuristics vs. RL: While heuristics like OSPF are easy to implement, they are "greedy"—they take any call they can fit. The RL agent learns "patience," realizing that rejecting a small reward now can lead to a much larger reward in the near future.

Results

  • Revenue Boost: The RL-based policy achieved an average reward of 212 per time unit, compared to only 141 for the OSPF heuristic—a 50% improvement.
  • Near-Optimality: The theoretical maximum reward (if every single call were accepted) is 242. Reaching 212 suggests the RL policy is very close to the true mathematical optimum.
  • Lower Rejection Rates: Despite being more selective, the RL policy actually reduced the overall number of rejected calls across all service types compared to OSPF.
  • Training Efficiency: The decomposition method led to much shorter training times than a global RL approach would have required.

Limitations and Future Work

  • Simulation Constraints: The results are based on a relatively small 4-node simulation. While the decomposition suggests scalability, performance on massive, real-world topologies with thousands of nodes remains to be tested.
  • Static Traffic Patterns: The model assumes Poisson arrival processes with fixed means. In reality, network traffic is bursty and non-stationary. Future work could involve adapting the RL agent to handle shifting traffic demands in real-time.
  • Function Approximation: While quadratic approximators worked well here, more complex architectures (like neural networks) might be needed for networks with more diverse service types or complex constraints.

Summary updated

BibTeX
@inproceedings{marbach1997reinforcement,
  author = {Peter Marbach and Oliver Mihatsch and Miriam Schulte and John N. Tsitsiklis},
  title = {{Reinforcement Learning for Call Admission Control and Routing in Integrated Service Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1997},
}
Figure