https://www.dagstuhl.de/07461

November 11 – 14 , 2007, Dagstuhl Seminar 07461

Numerical Methods for Structured Markov Chains

Organizers

Dario Andrea Bini (University of Pisa, IT)
Beatrice Meini (University of Pisa, IT)
Vaidyanathan Ramaswami (AT&T Labs Research – Florham Park, US)
Marie-Ange Remiche (Free University of Brussels, BE)
Peter Taylor (The University of Melbourne, AU)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Seminar Proceedings DROPS
List of Participants

Summary

Markov chain models are of paramount importance in many applications, including performance evaluation of telecommunications and computer systems, information retrieval, page ranking and queueing models. Whilst retaining algorithmic tractability, Markov chains offer flexibility in choosing the parameters one may incorporate into a model.

Systems such as the wireless standard IEEE 802.11, Peer-to-Peer (P2P) communication, wireless video transmission and congestion control algorithms in public telecommunications have been successfully modeled by means of Markov chains exhibiting particular structures. For example, Markov fluid models can be used to mimic IP traffic or to analyse the performance of a token bucket model, and Markov chains of M/G/1, G/M/1 and QBD-type have been used to solve a wide variety of queueing problems.

IIt is of note that the transition matrices resulting from such models often exhibit particular structures that allow for development of particularly efficient algorithms for their analysis.

Besides their importance in applications, structured Markov chains are interesting for the richness of the mathematical tools needed for their treatment. The analysis and development of efficient numerical methods for these Markov Chains constitutes one of the major incumbent challenges in this field. Conversely, the existence of such powerful methods actually incites engineers to model complex systems via Markov chains. Matrix analytic methods and structured matrix technology are important tools for the design of effective algorithms.

The analysis and development of efficient numerical methods for Markov Chains constitutes one of the major incumbent challenges in this field. Conversely, the existence of such powerful methods actually incites engineers to model complex systems via Markov chains. Matrix analytic methods and structured matrix technology are important tools for the design of effective algorithms.

The seminar was attended by 26 scholars, mostly from the academic world, including 8 PhD students and postdoctoral fellows. The participants came from North America, Europe, and Australia.

The seminar included 22 talks of 30 minutes duration, plus discussion, dealing with the latest results on theory, algorithms and applications concerning Markov chains and queueing models. This left enough time for informal discussions.

One session was devoted to celebrate the 60th birthday of Guy Latouche, one the major experts in this multidisciplinary field of applied probability, numerical analysis and modeling. In this session the most recent advances on numerical methods for structured Markov chains were presented.

Specific subjects of interest can be grouped in the following areas:

  • theory of phase-type and matrix-exponential distributions,
  • matrix analytic methods
  • design and analysis of algorithms
  • model analysis and inference procedures in the telecommunications

The seminar was closed by an open discussion on the state of the art of research and on the future research directions.

This Dagstuhl seminar has brought together leaders and young researchers in the fields of analysis of numerical algorithms, applied stochastic modeling and statistical inference, with the result of stimulating exchange of methodologies and experiences and generating synergetic collaborations.

This has favored a better communication between these worlds where problems from the applications feed the theoretical research and where advanced numerical tools can be utilized in applications with reciprocal advantages.

Classification

  • Modelling / Simulation
  • Data Structures / Algorithms / Complexity
  • Networks

Keywords

  • Matrix analytic methods
  • Markov processes
  • Queuing theory
  • Numerical methods
  • Structured matrices
  • Telecommunication modeling
  • Performance evaluation

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.