Orientador: Nelson Luis Saldanha da Fonseca

Tese (doutorado) - Universidade Estadual de Campinas. Instituto de Computação

Resumo: O fenômeno do cascateamento caracteriza-se pela ausência de uma escala de tempo específica, na qual a explosividade do tráfego possa ser caracterizada. Faz-se necessário, portanto, que esse tráfego seja descrito em diferentes escalas de tempo. Esse fenômeno foi identificado pela primeira vez...

Resumo: O fenômeno do cascateamento caracteriza-se pela ausência de uma escala de tempo específica, na qual a explosividade do tráfego possa ser caracterizada. Faz-se necessário, portanto, que esse tráfego seja descrito em diferentes escalas de tempo. Esse fenômeno foi identificado pela primeira vez em traços de tráfego de redes locais. Verificou-se em traços de tráfego do protocolo Internet Protocol (IP), composto majoritariamente por tráfego gerado por conexões TCP, o fenômeno do cascateamento em pequenas escalas de tempo, bem como a existência de dependências de longa duração. Além disso, nesses traços o tráfego apresenta alta variabilidade, cascateamento não-uniforme e a distribuição marginal das suas medições (bytes e/ou pacotes) é não-gaussiana. Estas características são típicas de processos multifractais. A banda passante equivalente de um fluxo é a quantidade mínima de banda passante requerida para que os requisitos de Qualidade de Serviço (QoS) desse fluxo possam ser atendidos. Dispor de métodos eficientes para computar a banda passante equivalente de um fluxo permite realizar alocação eficiente de banda passante, o que é essencial em redes de alta velocidade. A computação da banda passante equivalente de um fluxo requer a solução de um sistema de filas alimentado por esse fluxo, que, por sua vez, requer a computação do instante de tempo em que esse sistema alcança o seu máximo em termo de trabalho não-realizado. Uma representação minimalista do fluxo que alimenta um sistema de filas, obtida com o uso de processos envelope, permite a derivação de soluções, que apresentam boa precisão, para esse sistema. Nesta tese, introduz-se um processo envelope, chamado de processo envelope do movimento Browniano multifractal (mBm), que é um limitante superior para o volume de trabalho gerado por um processo mBm. A derivação do processo envelope do mEm baseia-se na propriedade de auto-similaridade local de um processo mBm. Esta propriedade estabelece que os incrementos de um processo mBm, em escalas de tempo pequenas, são realizações de processos movimento Browniano fractal (fEm). O processo envelope do mEm foi extensivamente validado para se verificar a sua capacidade de representar o tráfego de um fluxo. Usou-se tanto fluxos de tráfego real quanto fluxos de tráfego sintético na validação desse processo envelope. Expressões para o cálculo da escala de tempo de interesse de um sistema de filas alimento por fluxos multifractais são derivadas. Estas expressões são utilizadas pelo algoritmo que implementa a heurística, proposta nesta tese, para computação da banda passante equivalente de um fluxo multifractal. Demonstra-se a efetividade destas expressões ao se avaliar o ganho obtido com a multiplexação estatística de fluxos multifractais. Introduz-se, também, um mecanismo baseado em janelas para o policiamento de tráfego multifractaL

Abstract: Scaling in network traffic can be identified as the absence of a typical time scale at which traffic burstiness can be characterized. Internet Protocol (IP) traffic presents both scaling and long-range dependence. Moreover, at small time scales, IP traffic shows non-uniform scaling and...

Abstract: Scaling in network traffic can be identified as the absence of a typical time scale at which traffic burstiness can be characterized. Internet Protocol (IP) traffic presents both scaling and long-range dependence. Moreover, at small time scales, IP traffic shows non-uniform scaling and high variability. Moreover, the marginal distribution of counting process is non-gaussian, which dearly differentiates IP traffic from L_ cal Area Network traffic, which is accurately modelled by monofractal (self-similar) processes. Such patterns can be precisely modelled by multifractal processes. The equivalent bandwidth of a traffic flow is the minimum amount of bandwidth which should be given to that flow in order to support its Quality of Service (QoS) requirements. Efficient algorithms for estimating the equivalent bandwidth of a flow is of paramount importance for network dimensioning and provisioning of QoS in high speed networks. The computation of the equivalent bandwidth requires solving a queueing system fed by this flow, and specially the identification of the time scale at which the queue length reaches its maximum value. A minimalist representation of the traffic flow such as those obtained by the use of envelope process is needed for the derivation of the solution of the queueing system.
In this thesis, an envelope process, called mBm envelope process, is introduced. This process is an upper bound to the amount of work arrived in a multifractal Brownian motion (mBm). The definition of the mBm envelope process is based on the local self-similarity property of the mBm processo the mBm envelope process was extensively validated using both real network traffic and synthetic generated traffic.
An expression for the time scale at which a queueing system fed by a multifractal flow is derived. This expression is used in a proposed algorithm for the computation of the equivalent bandwidth of a multifractal flow. The effectiveness of such algorithm is assessed by the evaluation of the multiplexing gain of several multifractal flows. A policing mechanism appropriate for multifractal flows is also introduced in this thesis