Modelação de tráfego em redes de telecomunicações - modelos Markovianos e baseados em sistemas de Lindenmayer

Abstract

A modelação de tráfego tem uma importância cada vez maior na gestão e dimensionamento das redes de telecomunicações. Os modelos de trafego são utilizados, por exemplo, no dimensionamento de ligações e armazéns de pacotes tendo em conta os efeitos de multiplexagem estatística e em análise de desempenho de redes. Na Internet, a complexidade associada aos processos de geração e controle do tráfego, bem como a diversidade de aplicações, veio introduzir um conjunto de características peculiares no trafego, de que são exemplos a auto-similaridade, a dependência longa e a multifractalidade. Estas características têm um impacto muito significativo no desempenho da rede e necessitam portanto de ser devidamente modeladas. Esta Tese propõe um conjunto de modelos de trafego, capazes de descrever estes comportamentos peculiares, e que podem ser classificados em dois tipos: modelos Markovianos e modelos baseados em sistemas de Lindenmayer. Em ambos os tipos consideram-se modelos para trafego com pacotes de comprimento fixo e pacotes de comprimento variável. Na primeira parte da Tese são propostos dois modelos Markovianos e os respectivos procedimentos de inferência de parâmetros. O primeiro modelo é um processo de Poisson modelado à Markov em tempo discreto (dMMPP) que caracteriza as chegadas de pacotes. É obtido por sobreposição de um dMMPP sem memória com um número arbitrário de estados (M-MMPP) e de um conjunto de dMMPPs com dois estados (2-dMMPPs). Para inferir os parâmetros do processo, os 2-dMMPPs são utilizados para aproximar a função de autocovariância empírica e o M-MMPP é utilizado para modelar a função massa de probabilidade empírica tendo em conta as restrições impostas pelos 2- dMMPPs. O número de estados do processo pode ser ajustado de acordo com as características do tráfego a modelar. O segundo modelo é um processo de Markov com chegadas em rajada em tempo discreto (dBMAP) e corresponde a uma extensão do primeiro que permite incorporar o tamanho dos pacotes. Neste processo as chegadas de pacotes ocorrem de acordo com um dMMPP e os comprimentos seguem uma distribuição geral que depende da fase do dMMPP subjacente. Para inferir os parâmetros do dMMPP subjacente é utilizado o procedimento do primeiro modelo. Na segunda parte da Tese são propostos modelos de tráfego baseados em sistemas de Lindenmayer (sistemas-L) e os respectivos procedimentos de inferência de parâmetros. Os sistemas-L foram introduzidos em 1968 por A. Lindenmayer para modelar o crescimento de plantas. Um sistema-L gera iterativamente sequencias de símbolos progressivamente maiores, a partir de um símbolo inicial, por aplicação sucessiva de regras de produção. Para definir modelos de trafego baseados em sistemas-L, os símbolos são interpretados como taxas de chegadas ou comprimentos médios de pacotes e cada iterac˜ao é associada a uma escala temporal do trafego. São propostos um modelo para caracterizar as chegadas de pacotes e três modelos para caracterizar simultaneamente as chegadas e os comprimentos dos pacotes. Estes modelos conseguem capturar as características multiescalares e multifractais do trafego. Os modelos propostos nesta Tese foram testados com trafego medido e foram avaliados comparando (i) as estatísticas de primeira e segunda ordem, (ii) o desempenho sobre uma fila de espera e (iii) as características de similaridade escalar, do trafego medido com as mesmas do trafego gerado a partir dos modelos inferidos. Os resultados obtidos mostram que os modelos propostos são, em geral, capazes de reproduzir de forma bastante rigorosa as principais características do tráfego.

Traffic modeling has an increasing importance in the management and dimensioning of telecommunications networks. Traffic models are used, for example, in the dimensioning of links and buffers while considering the effects of statistical multiplexing and in network performance analysis. In the Internet, the complexity associated with the generation and traffic control mechanisms, as well as the diversity of applications and services, introduced a set of peculiar traffic characteristics, such as self-similarity, long range dependence and multifractality. These characteristics have a strong impact on the network performance and, therefore, need to be properly modeled. This Thesis proposes a set of traffic models, which are able to describe these peculiar behaviors, and that can be classified in two classes: Markovian models and models based on Lindenmayer systems. In both cases, we propose models for traffic with fixed and variable packet size. In the first part of the Thesis we propose two Markovian models and the respective parameter inference procedures. The first model is a Markov modulated Poisson process in discrete time (dMMPP) which characterizes the packet arrivals. It is obtained by superposing a memoryless dMMPP with an arbitrary number of states (M-dMMPP) and a set of dMMPPs with two states (2- dMMPPs). In order to infer the parameters, the 2-dMMPPs are used to fit the empirical autocovariance function and the M-dMPPP is used to fit the empirical probability mass function considering the restrictions imposed by the 2- dMMPPs. The number of states of the process can be adjusted according to the traffic characteristics. The second model is a batch Markovian arrival process in discrete time (dBMAP). It extends the first model by allowing the modeling of the packet size. In this process the packet arrivals occur according to a dMMPP and the packet sizes have a general distribution which depends on the phase of the subjacent dMMPP. The inference procedure of the first model is used to infer the parameters of the subjacent dMMPP. In the second part of the Thesis we propose traffic models based on Lindenmayer systems (L-Systems) and the respective parameter inference procedures. L-Systems were introduced in 1968 by A. Lindenmayer as a method to model plant growth. Starting from an initial symbol, an L-System generates iteratively progressively longer sequences of symbols, by successive application of production rules. In order to define traffic models based on L-Systems, the symbols are interpreted as arrival rates or mean packet sizes and each iteration is associated with a time scale of the traffic. We proposed one model to characterize the packet arrivals and three models to characterize simultaneously the packet arrivals and the packet sizes with different levels of detail. These models are able to capture the multiscaling and multifractal characteristics of the traffic. The proposed models were tested using measured traffic and were evaluated by comparing (i) the first and second order statistics, (ii) the queuing behavior and (iii) scaling characteristics, of the measured traffic and of synthetic traffic generated according to the inferred models. The obtained results show that the proposed models are, in general, able to reproduce rigorously the main traffic characteristics.