Esquema de Escalonamento de Fluxos

Esquema de Escalonamento de Fluxos

(Parte 1 de 3)

Abstract—The modern network traffic is composed of complex flows that present different statistical characteristics and quality of service requirements. This integration of flows motivates the introduction of new traffic congestion control and management schemes. In this work, we propose a new traffic flow scheduling scheme that incorporates the local singularity data of traffic processes. For this end, we initially verify the application of an algorithm that is based on the decay of wavelet coefficients in time windows to estimate the pointwise Hölder exponents. These exponents quantify the degree of traffic singularities. Next, we develop an adaptive prediction algorithm for the pointwise Hölder exponents of a traffic process. The simulations confirm that the proposed scheduling scheme provides lower data loss rate as well as higher link utilization than the GPS (Generalized Processor Sharing) scheme greatly used in network traffic routers.

Index Terms— Network Traffic, Scheduling, Prediction, Multifractals, Hölder Exponent.

Resumo—A integração de vários tipos de serviços nas redes de comunicações atuais traz consigo a necessidade de se introduzir novos esquemas de gerenciamento e controle de tráfego. Em alguns casos, os esquemas atuais podem ter sua eficiência reduzida devido ao comportamento repleto de diferentes singularidades locais dos fluxos de tráfego. Propomos neste artigo um esquema de escalonamento de fluxos de dados que utiliza informações da regularidade local de tráfego representada pelo expoente de Hölder pontual. Para tal, inicialmente verificamos a aplicação de um algoritmo de estimação dos expoentes de Hölder baseado no decaimento dos coeficientes wavelets em janelas de tempo. Em seguida, desenvolvemos um algoritmo adaptativo de predição dos expoentes de Hölder. Esse algoritmo de predição é incorporado na estratégia proposta de escalonamento de fluxos. As avaliações e simulações realizadas mostram que o esquema de escalonamento proposto provê uma menor perda de dados e uma utilização do enlace maior em comparação ao esquema de escalonamento GPS (Generalized Processor Sharing) convencional, implementado em muitos roteadores.

Palavras chave—Tráfego de Redes, Escalonamento, Predição, Multifractais, Expoente de Hölder.

Manuscrito recebido em 1 de Junho de 2007; revisado em 14 de

Novembro de 2007.

F. H. T. Vieira flavio@decom.fee.unicamp.br C. Jorge christian@fee.unicamp.br e L. L. Ling lee@decom.fee.unicamp.br pertencem ao Departamento de Comunicações (DECOM) da FEEC (Faculdade de Engenharia Elétrica e de Computação) da UNICAMP. Av. Albert Einstein - 400 - 13083-852- Campinas - SP.

Os serviços oferecidos pelas redes IP (Internet Protocol) atuais estão evoluindo do modelo de ‘melhor-esforço’ de transmissão da informação para um paradigma com várias classes de serviços, cada qual com seus requisitos de qualidade de serviço (QoS). Prover tais requisitos de qualidade de serviço usando a tecnologia IP é uma tarefa desafiadora para a engenharia de tráfego de redes.

Mecanismos preventivos são usados para alocar recursos com antecedência a fim de se evitar a ocorrência de congestionamentos. Nestes mecanismos, o algoritmo empregado de predição das características do tráfego desempenha um papel fundamental [2] [14]. Sabe-se que o desempenho de predição do tráfego depende de fatores tais como: quantidade de informações disponíveis do processo, a escala de tempo utilizada e o intervalo de predição. Um fator que tem grande influência no desempenho da predição é a própria natureza do tráfego [12] [14].

Na última década ocorreram mudanças significativas na compreensão do comportamento do tráfego de redes. Inicialmente houve a descoberta da propriedade de invariância à escala (scaling) do tráfego de pacotes [1]. Neste caso, modela-se o tráfego como um processo monofractal, cuja lei de escalas é determinada pelo parâmetro de Hurst. Entretanto em [6], verificou-se na verdade um comportamento multifractal do tráfego em escalas menores que algumas centenas de milissegundos. Esse comportamento se origina devido aos mecanismos do protocolo TCP/IP (Transmission Control Protocol) que fragmentam unidades de informação de uma camada de rede, em unidades menores na próxima camada [6].

Um processo multifractal é caracterizado por irregularidades (singularidades) locais mais acentuadas, com leis de escalas mais complexas do que se supunham os modelos monofractais. Neste contexto, costuma-se empregar o conceito de expoente de Hölder, oriundo da análise multifractal, para caracterizar a regularidade local do processo de tráfego, ou seja, o grau de rajadas presente nos dados [13].

A análise da regularidade local é importante para o gerenciamento e controle de congestionamento da rede por fornecer informações que podem tornar os esquemas de alocação de recursos mais eficientes. Com relação a isso, sabe-

Esquema de Escalonamento de Fluxos de Dados

Baseado nas Singularidades Locais do Tráfego Internet

Flávio Henrique Teles Vieira, Christian Jorge, & Lee Luan Ling

REVISTA TELECOMUNICAÇÕES, VOL. 1, NO. 01, MAIO DE 200824 se que um fluxo de tráfego de dados com alto grau de rajadas (grau alto de irregularidade) proporciona um menor aproveitamento dos recursos [1].

Assim sendo, este artigo contribui para o gerenciamento e controle preventivo do tráfego de redes através da proposta de uma nova disciplina de escalonamento de fluxos de dados em roteadores que leva em consideração as regularidades locais dos fluxos. Mostraremos que esta disciplina de escalonamento resulta em uma melhor distribuição da taxa de transmissão de um enlace para o escoamento dos fluxos presentes e uma menor perda de dados com relação à disciplina de escalonamento GPS (Generalized Processor Sharing).

O artigo está organizado da seguinte forma. Na seção I, caracterizamos a regularidade local de uma função utilizando a transformada wavelet. Na seção I, apresentamos um algoritmo para a estimação em janelas da regularidade local de fluxos de tráfego. A Seção IV é dedicada ao desenvolvimento de um novo algoritmo adaptativo de predição de séries temporais. Nesta mesma seção são analisados os erros de predição dos expoentes de Hölder. Na Seção V, propomos um esquema de escalonamento que incorpora a predição dos expoentes de Hölder pontuais como critério de alocação das taxas de transmissão de cada fluxo. Finalmente na Seção VI, apresentamos as conclusões obtidas.

A. Análise Wavelet

A transformada wavelet pode caracterizar o comportamento local e em escala de um sinal (processo) através de uma representação do mesmo no espaço e no domínio da freqüência. Conceitualmente, a transformada wavelet é um produto-convolução do sinal analisado com a wavelet-mãe ψ. Uma das ferramentas mais utilizadas da análise wavelet é o coeficiente wavelet. Os coeficientes wavelet dj,k são obtidos ajustando-se a wavelet-mãe ψ a uma determinada escala j e transladando-a até um ponto 2jk do sinal, com Zkj∈,, ou seja [4]

com Zkj∈,.

Pode-se dizer que com o aumento do valor de dj,k tem-se um aumento na variação do sinal no ponto 2jk [6]. Esta propriedade é importante para a caracterização das singularidades de um sinal por meio do decaimento do valor absoluto dos coeficientes wavelet dj,k [9].

B. Expoente de Hölder Pontual

O expoente de Hölder pontual é capaz de descrever o grau de uma singularidade local, o que é interessante para a caracterização das rajadas de dados em redes de computadores. O expoente de Hölder pontual é definido da seguinte forma:

Definição 1 (Expoente de Hölder pontual): Seja α um número real estritamente positivo, K uma constante e Rx∈0.

A função RRf→: é )(0xCα se existir um polinômio Pn de grau α<n tal que

O expoente de Hölder pontual αp da função f em x0 é definido como

Note que o polinômio Pn pode ser encontrado mesmo se o desenvolvimento da função f em série de Taylor ao redor de x0 não existir.

C. Espectro Multifractal

O espectro multifractal (ou espectro de singularidades) provê informações sobre quais singularidades ocorrem em um dado processo e quais singularidades predominam.

Definição 2 (Espectro multifractal): Seja f uma função: Rba→],[, a < b e seja )(xα o expoente de Hölder pontual de f em cada ponto ],[bax∈. O espectro multifractal )(αD de f é definido como

}))(|({)(ααα==xxdDH (4) em que dH denota a dimensão de Hausdorff [5].

Uma maneira muito utilizada para a estimação do espectro multifractal de um sinal com suporte compacto consiste na aplicação da transformada de Legendre [5] [13]. Para isso, inicialmente estima-se a função de partição ),(jqS do processo analisado. A função de partição ),(jqS é calculada em termos dos coeficientes wavelets dj,k do sinal pela seguinte equação

Seja )(qτ a função estrutura definida como [5] jqSqj−∞→=τ (6)

Assim, o espectro multifractal D(α) do sinal analisado pode ser calculado como [13] em que )(*ατ é a transformada inversa de Legendre da função estrutura )(qτ, ou seja ))((min)(*qταατ−=.

A Figura 1 apresenta os expoentes de Hölder de um processo de tráfego Internet assim como o seu espectro multifractal de Legendre.

VIEIRA et al: ESQUEMA DE ESCALONAMENTO DE FLUXOS DE DADOS BASEADO NAS SINGULARIDADES LOCAIS25

Fig. 1 - Acima: expoentes de Hölder pontuais referentes a um trecho da série de tráfego lbl-pkt-5 na escala de tempo de 100 ms. Abaixo: espectro multifractal.

DTipos de Singularidades

Existem diferentes funções com um mesmo expoente de

Hölder num determinado ponto, mas com comportamentos distintos ao redor desse mesmo ponto. Isso é devido ao tipo de singularidade que a função possui. Podemos destacar dois tipos [8] [19]:

Definição 3 (Singularidade não-oscilante): Seja fα(-n) a primitiva de n-ésima ordem da função fα. Dizemos que fα. possui uma singularidade não-oscilante, com expoente de

Hölder pontual α em x0, se

Desta forma, a função fα deve ser regular o suficiente, para que dado um ponto x0 com expoente de Hölder α, a derivada de fα apresente expoente de Hölder α-1 em x0 e a integral de fα apresente expoente de Hölder α+1 no mesmo ponto. A função αα||)(0xxxf−=representa o exemplo mais simples de singularidade não-oscilante em x0 .

Definição 4 (Singularidade oscilante): seja gα,β(-n) a primitiva de n-ésima ordem da função gα,β. Pode-se dizer que gα,β possui uma singularidade oscilante em x0, com expoente de Hölder pontual α e expoente de oscilação β > 0, se

Este tipo de singularidade ocorre em funções cujo expoente de Hölder pontual em x0 aumenta mais que a unidade quando integradas. Isto se deve aos efeitos da suavização das oscilações presentes, causados pela operação de integração da função [9]. A função ,0 representa o exemplo mais simples de singularidade oscilante em x0.

E. Decaimento dos Coeficientes Wavelets

O expoente de Hölder h de uma função no ponto x0 pode ser aproximado usando |da,b|~ah, com os coeficientes wavelets máximos absolutos Zbbad∈||, imersos num cone do tipo Kaxx≤−||0 , onde K é uma constante [8][18]. Porém, esse tipo de análise só é condizente para singularidades nãooscilantes [8].

Para tráfego de redes, devido à alta irregularidade presente, devemos levar em consideração também as singularidades oscilantes que possuem expoente de oscilação β > 0. Nesse caso, os coeficientes wavelets máximos absolutos estão imersos num cone parabólico mais largo que o citado

Dessa forma, para uma caracterização correta do comportamento local de um processo, devemos levar em consideração não apenas a amplitude dos coeficientes wavelets, mas também sua localização no tempo. Assim, utiliza-se a seguinte desigualdade [3]:

Com base nessa desigualdade, Seuret et al. [15] propuseram um algoritmo para estimação dos expoentes de Hölder pontuais tanto para singularidades oscilantes quanto nãooscilantes. Na próxima seção descreveremos como os fundamentos deste método podem ser aplicados para se realizar a estimação dos expoentes de Hölder em janelas de tempo.

Nesta seção, apresentamos um método para estimar a regularidade local de um processo de tráfego.

Seja um sinal amostrado contendo 2n amostras na escala de tempo j onde quanto maior o seu valor, maior a escala considerada. A estimação do expoente de Hölder pontual para uma amostra k0 pode ser feita considerando os seguintes passos [15]:

REVISTA TELECOMUNICAÇÕES, VOL. 1, NO. 01, MAIO DE 200826

Passo 1) Construa, em um mesma figura, para cada nj≤<0, a seguinte curva paramétrica (com parâmetro

Passo 2) Encontre todas as retas D: y = αx + C que satisfaçam as duas restrições a seguir:

1. D está acima de todos os pontos (xj(k),yj(k)), ou seja:

2. D toca uma das curvas paramétricas, ou seja, existe uma seqüência de pares (jm, km) tal que

Passo 3) Calcule αmax o maior coeficiente angular encontrado em todas as retas D satisfazendo (13) e (14). O coeficiente αmax é o expoente de Hölder pontual do sinal para a amostra k0.

Note que a estimação do expoente de Hölder pontual para o

instante amostral k0 se dá inicialmente construindo-se uma “nuvem” de pontos (xj(k),yj(k)). O expoente de Hölder para o instante de tempo k0 corresponde ao coeficiente angular da reta que se encaixa tão precisamente quanto possível no topo dessa

“nuvem” [15]. Com relação ao número de pontos na obtenção da nuvem de pontos, utiliza-se a restrição

2)2(log),(32−≤≤nkjx, sendo 2n o número de amostras do processo. Isto permite que seja levado em conta os coeficientes wavelets máximos absolutos em uma extensão suficiente de expoentes de oscilação β e gerar uma quantidade de pontos (xj(k), yj(k)) tal que seja possível uma construção precisa da reta que toca o topo desta “nuvem”. Para tal, utilizamos neste trabalho a função Morlet como waveletmãe [4].

senx que apresenta uma singularidade oscilante, sua respectiva “nuvem de pontos” e a reta que toca o topo da nuvem.

A. Estimação do Expoente de Hölder Pontual em Janelas de Tempo

Nesta seção, propomos uma estratégia dinâmica para a estimação do expoente de Hölder pontual para um dado sinal. Esta estratégia se baseia na utilização de uma quantidade fixa de amostras consecutivas (janela de tempo) para a estimação do expoente de Hölder pontual relativo a cada amostra do sinal. Para cada amostra do processo estimamos o seu respectivo expoente de Hölder utilizando somente as amostras da janela ao invés de todas as amostras do processo. Dessa forma, utiliza-se uma menor quantidade de amostras (assim como uma menor quantidade de coeficientes wavelet) para a estimação do expoente em cada instante de tempo.

Fig.2. Acima: função |x|0,7sen(1/|x|1,2) ; Direita: “nuvem de pontos” associada ao ponto de singularidade oscilante da função. Abaixo: O coeficiente angular da reta é a estimativa do expoente de Hölder pontual.

A diminuição da quantidade de coeficientes wavelet utilizada em cada estimação possibilita um processamento mais rápido das informações, podendo ser usada em roteadores e switches como indicadores das condições de tráfego. Comparamos então os expoentes de Hölder pontuais estimados por meio de janelas de tempo com os expoentes de Hölder pontuais de referência. Definimos este último como sendo os expoentes de Hölder pontuais estimados utilizando-se todas as amostras disponíveis de um processo de tráfego (sem uso de janelas de tempo).

(Parte 1 de 3)

Comentários