Docsity
Docsity

Prepare-se para as provas
Prepare-se para as provas

Estude fácil! Tem muito documento disponível na Docsity


Ganhe pontos para baixar
Ganhe pontos para baixar

Ganhe pontos ajudando outros esrudantes ou compre um plano Premium


Guias e Dicas
Guias e Dicas

Esquema de Escalonamento de Fluxos, Notas de estudo de Engenharia Elétrica

Esquema de Escalonamento de Fluxos

Tipologia: Notas de estudo

2011

Compartilhado em 09/01/2011

diogo-vieira-12
diogo-vieira-12 🇧🇷

4.8

(27)

77 documentos

Pré-visualização parcial do texto

Baixe Esquema de Escalonamento de Fluxos e outras Notas de estudo em PDF para Engenharia Elétrica, somente na Docsity! 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 11 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. I. INTRODUÇÃO 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. 11, 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 II, caracterizamos a regularidade local de uma função utilizando a transformada wavelet. Na seção III, 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. II. CARACTERIZAÇÃO DA REGULARIDADE LOCAL 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] ( )∫ ∞ ∞− −− −= dxkxxfd jjkj 2)(2, ψ (1) 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 α|||)()(| 00 xxKxxPxf n −≤−− (2) O expoente de Hölder pontual αp da função f em x0 é definido como )}(|0sup{)( 00 xCfxp ααα ∈>= (3) 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 }))(|({)( ααα == xxdD H (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 ∑= k q kjdjqS ||),( , (5) Seja )(qτ a função estrutura definida como [5] 2log ),(loglim)( j jqSq j −∞→=τ (6) Assim, o espectro multifractal D(α) do sinal analisado pode ser calculado como [13] )()( * ατα =D (7) em que )(* ατ é a transformada inversa de Legendre da função estrutura )(qτ , ou seja ))((min)(* qqq ταατ −= . 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 LOCAIS 25 refh janref hhEEQMN 2 2 ])[( σ − = (15) onde hjan é o expoente de Hölder pontual estimado via janelamento, href é o expoente de Hölder pontual usado como referência e refh 2σ é a variância dos expoentes de Hölder pontuais de referência. TABELA I ERRO QUADRÁTICO MÉDIO NORMALIZADO Janela 12 Janela 13 Janela 14 série dec-pkt-1 0,4899 0,2483 0,0426 série lbl5 0,5423 0,4332 0,2116 Fig.3. Expoentes de Hölder pontuais de amostras da série lbl-pkt-5 na escala de 100ms, estimados com três tamanhos diferentes de janelas de tempo. Conforme mostram a Tabela I e a Figura 3, verifica-se que ao se diminuir o tamanho da janela, aumenta-se a imprecisão da estimação do expoente de Hölder pontual em relação aos expoentes de Hölder de referência. Em contrapartida, a estimação se dá de maneira mais rápida, devido à diminuição da quantidade de coeficientes wavelets relativos a cada janela de tempo. Além disso, os erros obtidos apontam que as regularidades locais do tráfego de redes podem ser de fato estimadas adaptativamente usando o algoritmo de estimação do expoente de Hölder pontual em janelas. IV. PREDIÇÃO DO EXPOENTE DE HÖLDER PONTUAL Pode-se afirmar que a série temporal formada pelos expoentes de Hölder é mais apropriada para se realizar predição de suas amostras futuras do que a série correspondente de tráfego propriamente dita. Esta afirmação se fundamenta no decaimento da função de autocorrelação das séries formadas pelos expoentes de Hölder, que é mais simples de ser tratada pelos algoritmos de predição. A Figura 4 apresenta a função de autocorrelação das amostras de um processo de tráfego e a série correspondente de expoentes de Hölder pontuais. Pode-se notar um decaimento assintótico mais lento da função de autocorrelação do processo de tráfego, confirmando sua propriedade de dependência de longo prazo [12]. Entretanto, há um decaimento mais acelerado das funções de autocorrelação das séries de expoentes de Hölder pontuais, o que indica que tais séries não apresentam dependência de longo prazo. Isto sugere a possibilidade do uso de técnicas mais simples de predição de séries temporais, tais como o filtro de Mínimos Médios Quadrados (Least-Mean Squares - LMS) e o filtro de Kalman [7] para a predição dos valores dos expoentes de Hölder. Fig. 4 – Função de autocorrelação das amostras de uma série de tráfego e de seus respectivos expoentes de Hölder pontuais. Esquerda: série lbl-pkt-5 na escala de tempo de 100 ms. Apresentaremos na próxima seção um algoritmo adaptativo de predição aplicado à predição dos valores dos expoentes de Hölder estimados em janelas de tempo. Pretende-se portanto, estimar com antecedência as intensidades dos surtos de rajadas de cada fluxo de tráfego, disponibilizando essa informação para os mecanismos de controle de tráfego. A. Algoritmo de Predição com Estimação Adaptativa dos Ruídos do Sistema Um dos algoritmos adaptativos de predição mais usados é o filtro de Kalman. O filtro de Kalman é um estimador recursivo dos estados de um processo, muito utilizado em várias aplicações do mundo real [7]. Com base nestas equações recursivas de estimação, introduzimos um preditor que apresenta uma nova estratégia de atualização adaptativa dos ruídos do sistema, sendo o mesmo preciso para predições dos expoentes de Hölder. Seja o modelo de sistema descrito pelas seguintes equações no espaço de estado [7]: )()()1( kkk 1ηww +=+ (16) )()()()( 2 kkkky η+= wu T (17) Nestas equações, w(k) é o estado do sistema, y(k) é a saída medida, [ ]TNk,...,uk,ukuk )()1()()( −−=u é o vetor de entradas do sistema, N denota a ordem do filtro e k é o instante REVISTA TELECOMUNICAÇÕES, VOL. 11, NO. 01, MAIO DE 200828 de tempo discreto, com Zk ∈ . O vetor )(k1η é conhecido como ruído de processo, o qual se assume como sendo um processo gaussiano com média zero e covariância Q(k) dada por: T 1( ) [ ( ) ( )]k E k k= 1Q η η (18) De modo semelhante, a variável )(2 kη é conhecida como ruído de medida e modelada como um processo gaussiano com média zero e variância P(k) dada por: )]([)( 22 kEkP η= (19) Para que seja possível aplicar esse modelo de espaço de estados, é necessário que a covariância Q(k) e a variância P(k) sejam conhecidas. Na prática, é comum encontrar sistemas nos quais Q(k) e P(k) são desconhecidos, ou parcialmente conhecidos. Pode-se verificar que a escolha destes parâmetros influencia no desempenho do preditor. Dessa forma, propomos um método de estimação adaptativa destes parâmetros. Seja w(k) o vetor de coeficientes de um filtro transversal, o vetor η1(k) pode ser visto como o ajuste dos coeficientes do algoritmo NLMS (Normalized Least-Mean Squares) [7]. Assim, )]()([ ||)(|| ~ )( 2 kekk k u u η1 µ = (20) em que µ~ é o passo de adaptação e e(k) é o erro de estimação. Pode-se dizer que estamos usando um filtro NLMS para se estimar o ruído de processo η1(k). Segundo a equação (17), o ruído de medida η2(k) é dado por: )()()()()(2 kekkkyk T =−= wuη (21) Objetivamos o cálculo adaptativo dos ruídos de predição. Então, utilizamos as seguintes equações recursivas para a média )(2 kη e a variância r(k) de η2(k) [17]: )(1)1(1)( 222 kk k k kk ηηη +−−= (22) 2 22 ))()(( 1)1(1)( kk k kr k kkr ηη −+−−= (23) A matriz de covariância Q(k) pode ser estimada através dos valores de variância do ruído de processo η1(k). Seja o vetor T ,12,11,1 )](),...,(),([)( kkkk Nηηη=1η . Cada )(,1 kjη , onde j = 1, 2, ..., N, possui variância qj(k) que pode ser calculada recursivamente por: 2 11 ))()(( 1)1(1)( kk k kq k kkq jj ηη −+− − = (24) Dessa forma, a matriz de covariância Q(k) é dada por: ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = )(00 0 0)( 00)( )( 2 1 kq kq kq k NK MOM LM K Q (25) Tomando como base as equações recursivas do filtro de Kalman, apresentamos a seguir as equações que regem o preditor proposto cuja saída é y(k+1): Algoritmo de Predição: Passo 1) Calcula-se o ganho de Kalman )(kK : ( ) ( )( ) ( ) ( ) ( ) ( ) k kk k k k r k = +T P uK u P u (26) Passo 2) Atualiza-se os pesos: )](ˆ)()()[()(ˆ)1(ˆ kkkykkk wuKww T−+=+ (27) Passo 3) Calcula-se a variância )(kP : )(1)1(1)( 222 kk k k kk ηηη +−−= (28) 2 22 ))()(( 1)1(1)( kk k kP k kkP ηη −+−−= (29) Passo 4) Calcula-se a matriz Q(k): 2 11 ))()(( 1)1(1)( kk k kq k kkq jj ηη −+− − = (30) ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = )(00 0 0)( 00)( )( 2 1 kq kq kq k NK MOM LM K Q (31) Passo 5) Atualiza-se P(k): ( 1) ( ) ( ) ( ) ( ) ( )k k k k k k+ = + − TP P Q K u P (32) Passo 6) A saída do algoritmo de predição é dada por: )1(ˆ)1()1(ˆ ++=+ kkky wuT (33) em que K(k) é chamado de ganho de Kalman e )1(ˆ +kw é a estimação do próximo estado do sistema. B. Avaliação do Preditor Proposto Avaliamos o desempenho do preditor proposto através de simulações utilizando os expoentes de Hölder pontuais estimados com as janelas 11 (211 amostras), 12 (212 amostras) e 13 (213 amostras) para as séries de tráfego Internet dec-pkt-1, dec-pkt-2 e lbl-pkt-5. Com relação à configuração do preditor proposto, adotou-se o valor de N=7 para a ordem do preditor; valor acima do qual VIEIRA et al: ESQUEMA DE ESCALONAMENTO DE FLUXOS DE DADOS BASEADO NAS SINGULARIDADES LOCAIS 29 o EQM de predição em geral decai infimamente para as séries consideradas. Por meio de simulações, constatamos que o valor de µ~ que resultou em um melhor comportamento do preditor proposto foi de µ~ = 0,02. Além disso, as condições iniciais consideradas foram: 0)0(ˆ ≅w (34) TwwK )0(ˆ)0(ˆ)0( = (35) Comparamos o desempenho do algoritmo de predição com o desempenho de outros preditores bastante utilizados na literatura. Consideramos como critério para avaliação do desempenho de predição, duas versões do erro quadrático médio normalizado (EQMN), definidos pelas seguintes equações [16]: janh janpred hhEEQMN 2 2 ])[( 1 σ − = (36) ])[( ])[( 2 2 2 janua janpred hhE hhE EQMN − − = (37) onde hjan é o expoente de Hölder pontual estimado via janelamento, hpred é o expoente de Hölder predito, janh 2σ é a variância dos expoentes de Hölder estimados e hua é o expoente de Hölder anterior a hjan. Basicamente, o EQMN nos fornece uma comparação entre o EQM do preditor avaliado com o EQM de um preditor mais simples. No cálculo do EQMN1 considera-se a média amostral do sinal analisado como preditor mais simples. Enquanto no cálculo do EQMN2, compara-se o EQM do preditor avaliado com o EQM de um preditor que considera a última amostra disponível do sinal como valor predito. É desejável que um preditor a ser empregado possua ambos EQMNs menores que a unidade. Caso contrário, pode-se concluir que seu desempenho será, na melhor das hipóteses, similar aos preditores mais simples citados. Além do preditor proposto, os outros preditores avaliados são o filtro NLMS (preditor 1) e o filtro de Kalman (preditor 2). A ordem do filtro para os preditores 1 e 2 é a mesma para o preditor proposto (N=7). O valor do passo de adaptação µ~ do preditor 1 é escolhido de forma a obter o menor erro quadrático médio possível para cada série de tráfego analisada. TABELA II - EQMNS PARA PREDIÇÃO DE AMOSTRAS DA SÉRIE DE TRÁFEGO DEC-PKT-1 NA ESCALA DE TEMPO DE 100 MS E DE SEUS EXPOENTES DE HÖLDER PONTUAIS. EQMN1 EQMN2 série dec-pkt-1 0,7474 0,7129 expoentes de Hölder pontuais ( janela 13) 0,3246 0,6317 expoentes de Hölder pontuais ( janela 12) 0,3757 0,6347 expoentes de Hölder pontuais ( janela 11) 0,3991 0,6350 Observando a Tabela II, pode-se constatar um melhor desempenho de predição para o preditor proposto em relação aos demais analisados. De fato, além de possuir EQMNs menores que a unidade, o preditor proposto também possui EQMNs menores do que aqueles referentes aos preditores 1 e 2. Outro fator importante na verificação da eficiência de um preditor é o decaimento do erro quadrático com o tempo [2]. O decaimento temporal do erro quadrático de predição para a série lbl-pkt-5 é mostrado na Figura 5. Esta figura nos mostra que o preditor proposto possui o decaimento mais íngreme deste erro, em comparação aos outros preditores analisados. Com poucas amostras iniciais, o erro quadrático do preditor proposto decai e se mantém abaixo dos outros preditores. Fig. 5 - Erro quadrático de predição dos expoentes de Hölder de amostras da série lbl-pkt-5 nas escalas de tempo de 100 ms. V. DISCIPLINA DE ESCALONAMENTO UTILIZANDO OS EXPOENTES DE HÖLDER PONTUAIS As disciplinas de escalonamento são úteis em pontos de multiplexação de dados pois permitem que vários fluxos ou sessões compartilhem de uma melhor forma a taxa de transmissão (capacidade) de um enlace. Dentre estas disciplinas, uma das mais conhecidas é a Generalized Processor Sharing (GPS) [11]. Uma de suas propriedades mais importantes é a proteção aos fluxos de dados. Esta propriedade refere-se ao isolamento dos fluxos de entrada do escalonador, não permitindo que um fluxo mal-comportado afete o desempenho dos demais fluxos. Nesta seção propomos um novo esquema de escalonamento de fluxos de tráfego Internet tendo como base o GPS. A inovação deste esquema está na utilização do expoente de Hölder pontual como parâmetro de decisão da prioridade de cada fluxo em cada intervalo de tempo considerado. Nosso objetivo é obter uma melhor distribuição da taxa de transmissão do enlace aos fluxos e como conseqüência uma menor perda de dados. A. Esquema de Escalonamento de Fluxos de Tráfego Utilizando Predição dos Expoentes de Hölder O GPS é uma disciplina de escalonamento onde n fluxos de entrada compartilham um servidor de taxa fixa c. Um conjunto REVISTA TELECOMUNICAÇÕES, VOL. 11, NO. 01, MAIO DE 200830
Docsity logo



Copyright © 2024 Ladybird Srl - Via Leonardo da Vinci 16, 10126, Torino, Italy - VAT 10816460017 - All rights reserved