Optimization Problems in Correlated Networks

Song Yang, Stojan Trajanovski, Fernando A. Kuipers

Introduction

In classical graph theory, fundamental problems such as finding the shortest path or the minimum cut are well-understood. Algorithms like Dijkstra's or Ford-Fulkerson provide optimal solutions in polynomial time, predicated on the assumption that link weights—representing costs, delays, or failure probabilities—are independent and additive. However, in real-world scenarios such as overlay networks, interdependent power grids, or Shared-Risk Link Groups (SRLGs), this assumption often fails. Physical proximity or shared infrastructure creates correlations: if one link experiences high latency, a related link is likely to follow.

This paper investigates the theoretical complexity and algorithmic solutions for network optimization when link weights are correlated. The authors demonstrate that while general correlation models lead to NP-hardness, specific constraints and stochastic modeling allow for efficient, optimal solutions.

Modeling Network Correlation

The authors propose two distinct frameworks to capture these interdependencies:

  1. Deterministic Correlated Model: In this model, the joint cost of correlated links is adjusted by a correlation coefficient $\rho$. When $\rho > 1$, a cost penalty is applied; when $\rho < 1$, costs overlap, reflecting shared risks.
  2. Stochastic Correlated Model: Link weights are treated as uncertain variables following a multivariate log-concave probability distribution (e.g., Normal or Weibull). This model effectively captures the variability of queuing delays and failure rates in dynamic environments.
Deterministic correlation model where path costs are non-additive.

Theoretical Challenges

The introduction of correlation fundamentally alters the landscape of network optimization:

  • Breakdown of Subpath Dominance: In standard networks, any segment of a shortest path is itself a shortest path. In correlated networks, a locally sub-optimal path might be globally optimal if it avoids significant correlation penalties later in the route. This invalidates greedy approaches like standard Dijkstra.
  • Max-Flow Min-Cut Divergence: The classic theorem equating maximum flow to minimum cut capacity no longer holds under correlation, necessitating new approaches for assessing network reliability.
  • Algorithmic Inefficiency: The authors prove that applying standard independent-link algorithms to correlated networks can result in solutions that are arbitrarily worse than the true optimum.

Algorithmic Solutions

Despite the general NP-hardness of these problems, the authors identify two tractable regimes:

Nodal Correlation

A critical insight is that if correlations are restricted to links sharing a common node (e.g., local interference at a router), the problem becomes solvable in polynomial time. The authors develop an auxiliary graph transformation that expands the original network to explicitly represent these local dependencies, allowing standard algorithms like Bellman-Ford to find the exact solution.

Auxiliary graph mapping for solving nodal correlation.

Stochastic Log-Concavity

For the stochastic model, the authors leverage the properties of log-concave distributions. They show that finding a path or cut that meets a specific probability threshold can be framed as a convex optimization problem. This allows the use of efficient modern solvers to find optimal solutions for uncertain, correlated environments.

Conclusion

This research highlights the significant impact of link correlation on network performance and reliability. While general deterministic correlation makes shortest path and min-cut problems NP-hard, the authors provide a roadmap for tractability through nodal correlation constraints and stochastic convex optimization. Future work remains to scale these exact algorithms for massive topologies and to validate these theoretical models against empirical data from modern software-defined networks.

Summary updated

BibTeX
@inproceedings{yang2016optimization,
  author = {Song Yang and Stojan Trajanovski and Fernando A. Kuipers},
  title = {{Optimization Problems in Correlated Networks}},
  booktitle = {Computational},
  year = {2016},
  doi = {10.1186/s40649-016-0026-y},
}
Figure