Mean-Field Approximation Techniques for Markov Models
Project Number: 612.063.918
Project Manager: Prof. dr. B.R.H.M. Haverkort
Faculty of Electrical Engineering, Mathematics and Computer Science - EEMCS
Newest generation communication networks often consist of a really large number ofrelatively simple nodes. Wireless sensor networks for civil or military surveillance purposes, distributed P2P file sharing applications or malicious self-aggregating botnets, they all are composed of autonomous, interacting nodes. If each node is modelled explicitely, a formal performance or dependability evaluation is limited to the restricted case where only a few nodes participate since the global model of a realistic number of nodes suffers from state space explosion.
We tackle this problem by applying mean-field approximation. It was originally developed for physical models, like the interaction of molecules in a gas. The principle already has been applied to various areas in computer science, but there is no common framework that provides a complete theory and algorithms for the use of mean-field approximation techniques in performance and dependability evaluation. Many models used for this task come from the family of Markov models. For some of these models there are already mean-field approximation results, but the picture is by no means complete.
We will explore the theory necessary to apply mean-field approximation to all types of Markov models, including nondeterminism and rewards. Intertwined with theory development we will work on practical algorithms and their implementation. Research progress will be shown by case studies from the above mentioned areas. The final product will be a framework for mean-field approximation techniques on Markov models for the analysis of large-scale communication systems which is complete in a theoretical and a practical sense.
Project duration: 2010-2014
Project budget: 200.013 €
Number of person/years: 1.2 fte / year
Involved groups: Design and Analysis of Communication Systems (DACS)