Advanced

Hidden Markov models - Traffic modeling and subspace methods

Andersson, Sofia LU (2002)
Abstract
The main motivation for this thesis, however not the only one, is the search for models for traffic in telecommunication networks. Traffic characterization and modeling are of great importance in the analysis and dimensioning of communication systems. During the last decades we have experienced an explosive growth of our telecommunication networks. New important properties, both on macroscopic and microscopic time scales, have been revealed. These new features have a profound impact on network performance and thus needs to be taken into consideration. In Paper A we study the microdynamics of some data sets of traffic on the link level. Our approach is Poissonification, a kind of random local smoothing of a point process. The idea is to use... (More)
The main motivation for this thesis, however not the only one, is the search for models for traffic in telecommunication networks. Traffic characterization and modeling are of great importance in the analysis and dimensioning of communication systems. During the last decades we have experienced an explosive growth of our telecommunication networks. New important properties, both on macroscopic and microscopic time scales, have been revealed. These new features have a profound impact on network performance and thus needs to be taken into consideration. In Paper A we study the microdynamics of some data sets of traffic on the link level. Our approach is Poissonification, a kind of random local smoothing of a point process. The idea is to use Poissonification on empirical data materials in order to find the (small) time scale where the process switch from a doubly stochastic to a homogeneous behavior.



The models used and studied are hidden Markov models (HMMs). In Paper B we study specifically the Markov-modulated Poisson process (MMPP). In fitting an MMPP to some sets of observed traffic we concentrate on maximum likelihood (ML) methods, but also use moment methods. The ML methods are computationally more complex but concerning performance they prove to be superior to moment methods.



As a possible candidate for a method to combine the simplicity of the moment methods, and the accuracy of the likelihood methods, we have subspace methods. To be able to use subspace methods for HMMs the process needs to be represented in state space form. In Paper C of this thesis we show that it is possible to represent an HMM as a state space system in innovation form. This reformulation is complicated by the non-minimality within the state space representation of the HMM. The reformulation involves deriving solutions to algebraic Riccati equations which are usually treated under minimality assumptions.



In Paper D we develop a subspace identification algorithm especially designed for HMMs. Some of the crucial assumptions on the system, needed for the subspace methods to work, fail to be met by HMMs and thus commonly used methods are not directly applicable. Therefore we need to consider each of the steps in existing algorithms with regard to the specific conditions of the HMM and in this way develop a new algorithm. Consistency is proved of this algorithm. However, we manage to estimate the system parameters only seen as a projection on a certain subspace and only up to a similarity transformation. (Less)
Please use this url to cite or link to this publication:
author
opponent
  • Professor Gustafsson, Fredrik, Link√∂ping University
organization
publishing date
type
Thesis
publication status
published
subject
keywords
programming, actuarial mathematics, Statistik, operationsanalys, Statistics, operations research, subspace identification, state space representation, likelihood estimation, Poissonification, traffic analysis, hidden Markov model, Markov-modulated Poisson process, programmering, aktuariematematik
pages
144 pages
publisher
Centre for Mathematical Sciences, Lund University
defense location
Centre of Mathematical Sciences, Sölvegatan 18, Lund, sal C
defense date
2002-06-07 13:15
ISSN
1404-0034
ISBN
91-628-5253-1
language
English
LU publication?
yes
id
c9552490-2702-451b-a424-ba8685678e39 (old id 464752)
date added to LUP
2007-09-27 14:42:25
date last changed
2016-09-19 08:44:56
@phdthesis{c9552490-2702-451b-a424-ba8685678e39,
  abstract     = {The main motivation for this thesis, however not the only one, is the search for models for traffic in telecommunication networks. Traffic characterization and modeling are of great importance in the analysis and dimensioning of communication systems. During the last decades we have experienced an explosive growth of our telecommunication networks. New important properties, both on macroscopic and microscopic time scales, have been revealed. These new features have a profound impact on network performance and thus needs to be taken into consideration. In Paper A we study the microdynamics of some data sets of traffic on the link level. Our approach is Poissonification, a kind of random local smoothing of a point process. The idea is to use Poissonification on empirical data materials in order to find the (small) time scale where the process switch from a doubly stochastic to a homogeneous behavior.<br/><br>
<br/><br>
The models used and studied are hidden Markov models (HMMs). In Paper B we study specifically the Markov-modulated Poisson process (MMPP). In fitting an MMPP to some sets of observed traffic we concentrate on maximum likelihood (ML) methods, but also use moment methods. The ML methods are computationally more complex but concerning performance they prove to be superior to moment methods.<br/><br>
<br/><br>
As a possible candidate for a method to combine the simplicity of the moment methods, and the accuracy of the likelihood methods, we have subspace methods. To be able to use subspace methods for HMMs the process needs to be represented in state space form. In Paper C of this thesis we show that it is possible to represent an HMM as a state space system in innovation form. This reformulation is complicated by the non-minimality within the state space representation of the HMM. The reformulation involves deriving solutions to algebraic Riccati equations which are usually treated under minimality assumptions.<br/><br>
<br/><br>
In Paper D we develop a subspace identification algorithm especially designed for HMMs. Some of the crucial assumptions on the system, needed for the subspace methods to work, fail to be met by HMMs and thus commonly used methods are not directly applicable. Therefore we need to consider each of the steps in existing algorithms with regard to the specific conditions of the HMM and in this way develop a new algorithm. Consistency is proved of this algorithm. However, we manage to estimate the system parameters only seen as a projection on a certain subspace and only up to a similarity transformation.},
  author       = {Andersson, Sofia},
  isbn         = {91-628-5253-1},
  issn         = {1404-0034},
  keyword      = {programming,actuarial mathematics,Statistik,operationsanalys,Statistics,operations research,subspace identification,state space representation,likelihood estimation,Poissonification,traffic analysis,hidden Markov model,Markov-modulated Poisson process,programmering,aktuariematematik},
  language     = {eng},
  pages        = {144},
  publisher    = {Centre for Mathematical Sciences, Lund University},
  school       = {Lund University},
  title        = {Hidden Markov models - Traffic modeling and subspace methods},
  year         = {2002},
}