Robust measurement-based buffer overflow probability estimators for QoS provisioning and traffic anomaly prediction applicationm

Spyridon Vassilaras, Ioannis Ch. PaschalidisarXiv 2016 · OpenReview

TL;DR

This paper tackles the challenge of accurately estimating rare event probabilities (like buffer overflows) in complex communication networks using real-world data. The authors introduce a novel, efficient, and provably convergent algorithm to solve the underlying optimization problems, making these estimators practical for real-time applications like Quality of Service (QoS) provisioning and network anomaly detection.

What Problem Does This Paper Address?

In modern communication networks, ensuring Quality of Service (QoS) is paramount. A key metric for QoS is the probability of rare events, such as buffer overflows, which can lead to data loss or delays. While Large Deviations (LD) theory provides powerful tools for approximating these probabilities, it often requires knowledge of the underlying traffic models, which are rarely known perfectly in practice.

Previous work by the authors proposed "measurement-based" LD estimators that rely on observed data rather than perfect models. These estimators, however, are formulated as complex, non-linear, multi-dimensional optimization problems. While a heuristic algorithm was previously developed, it lacked guaranteed convergence, making its real-time application risky. This paper addresses this gap by developing a new algorithm that is both efficient and guaranteed to converge to the correct solution, thereby enabling the practical deployment of these robust estimators.

Methods

The core of this paper lies in developing an efficient and convergent algorithm for solving a specific class of non-linear optimization problems. These problems arise from measurement-based Large Deviations estimators for buffer overflow probabilities.

The authors first analyze the structure of the objective function and constraint set of these optimization problems. They then propose an algorithm, building upon their previous heuristic approach, that leverages the specific structure of these problems. The key innovation is the introduction of a modified Armijo rule for step-size selection, which is proven to guarantee convergence to the global optimum. This algorithm is designed to be computationally efficient, a critical requirement for real-time applications.

Datasets

Not discussed in the paper. The paper focuses on the theoretical development of an algorithm for solving optimization problems derived from statistical estimation, rather than on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Bridging Theory and Practice: The paper successfully bridges the gap between theoretical Large Deviations approximations and practical, measurement-based estimation by providing a convergent algorithm for the associated optimization problems.
  • Guaranteed Convergence is Crucial: The lack of guaranteed convergence in previous heuristic algorithms was a significant barrier to real-time deployment. The development of Algorithm B, with its modified Armijo rule, directly addresses this critical limitation.
  • Exploiting Problem Structure: The efficiency of the proposed algorithm stems from its ability to exploit the specific structure of the objective function and constraint set, which are not generic but arise from the LD estimation framework.
  • Real-time Applicability: The paper emphasizes that efficient and provably convergent algorithms are a prerequisite for using these LD estimators in real-time scenarios like call admission control and traffic anomaly detection.

Key Results

The paper's main result is the development and proof of convergence for a new algorithm (Algorithm B) designed to solve the non-linear optimization problems underlying measurement-based buffer overflow probability estimators. This algorithm is shown to converge to the global minimum of the objective function. While specific quantitative performance metrics (e.g., speedup percentages) are not detailed, the paper strongly implies that this algorithm is significantly more efficient than generic optimization methods due to its tailored approach. The theoretical guarantee of convergence makes the proposed estimators practical for real-time applications.

Limitations and Future Work

  • Computational Complexity for Large M: While the algorithm is efficient, the paper acknowledges that for large numbers of states (M) in the Markov chains, the optimization problems can still be computationally demanding, with the number of decision variables growing quadratically with M.
  • Assumption A: The algorithm's convergence proof relies on Assumption A, which states that the observed data is sufficient to estimate all necessary transition probabilities for irreducible Markov chains. In practice, obtaining such complete data might require prolonged observation periods.
  • Future Work: The paper implicitly suggests that further exploration into the practical performance of Algorithm B across various network scenarios and parameter settings would be valuable. Additionally, investigating extensions to more complex network models or different types of rare event estimation problems could be future directions.

Summary updated

Abstract

Suitable estimators for a class of Large Deviation approximations of rare event probabilities based on sample realizations of random processes have been proposed in our earlier work. These estimators are expressed as non-linear multi-dimensional optimization problems of a special structure. In this paper, we develop an algorithm to solve these optimization problems very efficiently based on their characteristic structure. After discussing the nature of the objective function and constraint set and their peculiarities, we provide a formal proof that the developed algorithm is guaranteed to always converge. The existence of efficient and provably convergent algorithms for solving these problems is a prerequisite for using the proposed estimators in real time problems such as call admission control, adaptive modulation and coding with QoS constraints, and traffic anomaly detection in high data rate communication networks.
BibTeX
@misc{vassilaras2016robust,
  author = {Spyridon Vassilaras and Ioannis Ch. Paschalidis},
  title = {{Robust measurement-based buffer overflow probability estimators for QoS provisioning and traffic anomaly prediction applicationm}},
  year = {2016},
  eprint = {1605.00705},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1605.00705},
}
Figure