XXI Congresso da Sociedade
Brasileira de Computação
Jornada de Atualização em Informática
Curso de Modelagem Estocástica
de Tráfego de Redes de Alta Velocidade
Jorge Luiz de Castro e Silva
Profa. Marcilia Andrade Campos
Prof. Paulo Roberto Freire Cunha
Julho 2001
Jorge Luiz
Conteúdo
Motivação
Redes de Alta Velocidade e Aplicações
Evolução das tecnologias e aplicações multimídia
Requisitos para transmissão de conteúdos multimídia
Serviços para redes multimídia
Conceitos Básicos
Processo estocástico
Momentos de um processo estocástico
média
variância
covariância
correlação
Jorge Luiz
Conteúdo - (cont.)
Visão Geral sobre Modelagem de Tráfego
O que se deve medir
Fontes de tráfego
Qual o objetivo da modelagem
Modelos para Modelar Tráfego
Modelos tradicionais
Modelos de series temporais
Distribuições de caudas pesadas
Modelo auto-similar
Jorge Luiz
Referências
D.L.Jagerman et al., “Stochastic Modeling of Traffic Process”,
1996 http://rutcor.rutgers.edu/melamed
M.E.Crovella et al.,”Self-Similarity in World Wide Web Traffic:
Evidences and Possibles Causes”, 1997.
http://cs.bu.edu/faculty/crovella/papers.html
V. Paxson and S. Floyd, “Wide-Area Traffic: The Failure of
Poisson Modeling”, 1995. http://www-nrg.ee.lbl.gov/nrgpapers.html
W. Willinger et al.,”Self-Similarity and Heavy Tails: Structural
Modeling of Network Traffic”,
Http://www.cs.bu.edu/pub/barford/ss-lrd.html
Z. Sahinoglu and S. Tekinay, “On Multimedia Networks: SelfSimilar Traffic and Network Performance”, 1999, IEEE Comm.
Magazine.
Jorge Luiz
1a Parte
Motivação
Jorge Luiz
Motivação da Análise e
Modelagem de Tráfego em Redes
Situação 1: Suponha um sistema onde os usuários
disputam o acesso a um recurso cuja a capacidade
é finita. Ex. o uso de uma canal de comunicação.
O ferramental para análise e modelagem deste
problema pode ser a Teoria das Filas.
Medidas de desempenho como o comprimento da
fila ou o tempo de espera dos objetos (bytes,
pacotes, etc) na fila podem ser estimadas para
alocação e compartilhamento eficiente do recurso.
Jorge Luiz
Motivação da Análise e
Modelagem de Tráfego em Redes
Situação 2: Suponha que se tenha medidas diárias sobre
o tráfego na Internet. O objetivo é prever o número de
acessos para os próximos 6 meses.
A modelagem estocástica para este tipo de problema
pode ser Séries Temporais e a Teoria Bayesiana.
Jorge Luiz
Motivação da Análise e
Modelagem de Tráfego em Redes
Para que usar modelagem de tráfego:
Planejamento e dimensionamento de redes
Análise de desempenho de redes
Congestionamento de redes
Análise de perda de pacotes
Estudo do comportamento dos usuários
Geralmente, dados coletados e avaliados fornecem a
base para os modelos analíticos. Os dados, então,
representam o comportamento do tráfego da rede.
Jorge Luiz
Motivação da Análise e
Modelagem de Tráfego em Redes
A partir das propriedades observadas nos dados
empíricos é desenvolvido um modelo ou uma
expressão matemática. O modelo matemático serve
como uma aproximação do que acontece na
realidade. O modelo matemático pode ser usado para
analisar o desempenho da rede, como tamanho da
fila, atraso na fila, probabilidade de perda, etc.
Por exemplo, analisando as perdas de informação
que podem ocorrer em um sistema de transmissão
de áudio e vídeo unicast.
Jorge Luiz
Motivação da Análise e
Modelagem de Tráfego em Redes
Sistema de áudio e vídeo unicast
Camera/
Microfone
from network
A/D
Adaptador
de Rede
Codificador
controle de taxa
Decodificador
controle de erro
Adaptador
de Rede
D/A
to network
Monitor/
Caixa de som
Elementos de um sistema de comunicação para transferência multimídia
Jorge Luiz
Motivação da Análise e
Modelagem de Tráfego em Redes
Antes
Os usuários da rede trabalhavam com aplicações
tradicionais (transferência de dados) que demandavam um
serviço com baixas taxas de erro.
Hoje
Aplicações multimídia que exigem um nível mínimo de QoS
(garantia de um mínimo de banda passante e baixos níveis
de retardo e variação de atraso).
Os serviços fornecidos pela rede podem ser determinístico
(com garantia absoluta de retardo máximo, vazão e taxa
máxima de perdas) ou probabilístico (com garantia relativa
em função de uma modelagem estocástica da fonte
geradora do tráfego).
Jorge Luiz
Motivação da Análise e
Modelagem de Tráfego em Redes
Fontes de Tráfego ou Classes de Tráfego
ATM Forum
IETF
Para SG -> CBR e VBR
Para ME -> UBR e ABR
Para ME -> rajadas
CBR = Constant Bit Rate
VBR = Variable Bit Rate
UBR = Unspecified Bit Rate
ABR = Available Bit Rate
ATM = Asynchronous Transfer Mode
IETF = Internet Engineering Task Force
Jorge Luiz
Motivação da Análise e
Modelagem de Tráfego em Redes
O tráfego em rajadas apresenta períodos ativos, durante
os quais há geração de tráfego, intercalados por
períodos de inatividade. Parâmetros para caracterizar
esse tipo de tráfego incluem a duração média dos
períodos de atividade e a explosividade da fonte (razão
entre a taxa de pico e a taxa média de utilização.
O tráfego CBR é constante. A taxa média é igual a sua
taxa de pico.
O tráfego VBR apresenta variações na taxa de
transmissão ao longo do tempo. Parâmetros com a
média e a variância da taxa de transmissão caracterizam
o comportamento desse tipo de tráfego.
Jorge Luiz
2a Parte
Redes de Alta Velocidade e
Aplicações
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
O que está mudando?
As tecnologias de redes de alta velocidade estão sendo
desenvolvidas em resposta a uma série de mudanças na
área de:
Computação
Comunicação de dados
Telecomunicações
Aplicações
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Evolução da Computação
O desempenho dos processadores está dobrando a
cada ano
Memória de massa: disk array
Sistemas gráficos que usam tecnologias avançadas
possibilitando altas taxas de transferência (na ordem de
gigabit por segundo)
Sofware - o incremento na potência de processamento
tem possibilitado o uso de novas aplicações. Ex:
aplicações que fazem o reconhecimento de voz em
tempo real.
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Evolução da Comunicação de Dados
Capacidade de interligar sistemas de comunicação com
tecnologias diferentes de forma transparente para os
usuários (internetworking).
Novas aplicações interativas interconectadas via rede
como conferências multimídia.
Melhorias nos protocolos de interconexão de redes
Uso de tecnologias que permitem garantir a qualidade e
o desempenho dos serviços de comunicação.
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Evolução das Telecomunicações
Perfil da demanda está mudando: nos USA o tráfego de
voz cresce a uma taxa de 3% enquanto o de dados
cresce mais de 20%.
As companhias estão diversificando seus serviços (TV a
cabo, RDSI, etc)
Vantagens da integração de todos serviços em uma
única rede de telecomunicações e capacidade de
oferecer novos serviços aos usuários.
Já existe uma infra-estrutura digital que pode ser usada
tanto para voz como para dados.
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Evolução das Aplicações
Educação a distância
Entretenimento
Vídeo conferência
Biblioteca virtual
Telemedicina
Vídeo sob demanda
HDTV
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Resumindo
Evolução conjunta das áreas de computação,
comunicação de dados e telecomunicações.
São pressionadas para oferecer tecnologias que
suportam taxas de Gigabits por segundo e suporte às
aplicações multimídia, integrando o tráfego de dados,
voz e imagem de forma estática ou interativa.
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Para se transmitir arquivos multimídia é importante
que os serviços providos pela rede sejam
confrontados com os requisitos dos conteúdos
multimídia.
Requisitos para transmissão de conteúdos multimídia
Requisitos de largura de banda. Depende da qualidade do
áudio e vídeo.
Áudio com qualidade fone requer 64 Kbps
Com qualidade CD requer 1,4 Mbps
HDTV não comprimido requer 200 Mbps.
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Requisitos para transmissão de conteúdos multimídia
Fatores de sincronização requeridos para áudio e vídeo
Retardo deve ser menor que 100 ms.
Jitter e skew devem ser menores que 10 ms.
Em vídeo, a sincronização dos lábios deve ser menor que 80 ms.
Transmissão com qualidade fone, a taxa de erro de bits é cerca
de 1%. Para qualidade CD a taxa deve ser melhor (0,1%).
Fatores que influenciam a sincronização
retardo
jitter
skew
taxa de bits
taxa de erro de bits
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Tecnologias e Serviços de Redes Multimídia
Serviços de redes WAN
Serviços de redes LAN
comutação de circuitos
comutação de pacotes
Internet
Ethernet
redes em anel
ATM
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Serviços de Redes WAN - Comutação de circuitos
Requer pouca complexidade de processamento nos
seus nós e suporta taxa bit constante
Características
estabelecimento de conexão fim-a-fim
impossibilidade de estabelecer conexão qdo não existem
circuitos disponíveis
tarifação baseada na distância e no tempo de conexão
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Serviços de Redes WAN - Comutação de circuitos
Analógico
Serviço telefônico atual - provê conexões até 56 Kbps. Para
transmissões multimídia de baixa qualidade.
Linhas privadas analógicas.
Digital
RDSI (BRI E PRI) - Rede Digital de Serviços Integrados
Basic Rate Interface - de 128 Kbps a 192 Kbps. Para transmissões
de voz digitalizada e vídeo conferência de baixa qualidade.
Primary Rate Interface - 1,54 a 2 Mbps. Para vídeo com qualidade
VCR.
Linhas privadas digitais - T1, T2, T3 e T4. Inicia em 1,544 Mbps
(T1) e vai até 274 Mbps (T4). T1 transporta vídeo com qualidade
VCR e T4 pode transportar HDTV.
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Serviços de Redes WAN - Comutação de pacotes
Requer maior complexidade de processamento nos
seus nós, mas oferece, em contrapartida, suporte ao
tráfego inconstante, ou seja, com taxa de bit variável.
Características
pacotes de tamanho variável
conexões lógicas multiplexando uma única conexão física
aloca banda de transmissão sob demanda
técnica tipo store-and-foward
tarifação baseada no tráfego e no tempo
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Serviços de Redes WAN - Comutação de pacotes
X.25 - não é apropriado a transmissão multimídia em
tempo real. Produz delay e jitter em excesso.
Frame Relay - minimiza o retardo, pois não controla
fluxo fim-a-fim e nem corrige erros. Até 1,544 Mbps.
SMDS - serviço não orientado à conexão. Opera com
taxas de 1,54 a 155 Mbps (com ATM)
ADSL - (velox) - Usa fibra ótica. Prover taxa de até 1,544
Mbps, se o assinante estiver a menos de 5,5 km. Acesso
a Internet e vídeo sob demanda.
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Internet
O protocolo TCP/IP não foi projetado para transmitir
tráfego multimídia. O IP é um protocolo não confiável,
best effort e não orientado à conexão. O TCP é
orientado à conexão e, por isso, usa excessivos
reconhecimentos e retransmissões de segmentos.
Para suprir essas deficiências, foram criados outros
protocolos para a Internet.
RTP - protocolo de aplicação para transmissão multimídia
em tempo real.
RSVP - configura e controla recursos oferecidos pela rede,
tais como largura de banda e buffers.
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Internet
Para superar os problemas encontrados na Internet,
existem 2 pesquisas:
Internet2
NGI (Next Generation Internet)
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Vantagens da comutação de circuitos
Inexistência de congestionamento
Adequado para aplicações com taxa de transmissão fixa
e alto índice de utilização
Suporta aplicações sensíveis a atrasos, como a voz
Vantagens da comutação de pacotes
Utilização otimizada do meio de transmissão
Adequado para aplicações com taxa de transmissão
variável
no caso de falha de nó ou enlace, permite o uso de rota
alternativa
Jorge Luiz
Redes de Alta Velocidade e
Aplicações
Redes Locais
Não foram projetadas para transportar multimídia
Ethernet, Fast Ethernet e Gigabit Ethernet
Redes em anel - FDDI
ATM
Concebida para suportar tráfego multimídia, inclusive
em tempo real
Princípio da comutação de células (53 bytes)
Células comutadas em hardware baixo retardo
Taxas de transmissão de 34 a 155 Mbps
Com fibra ótica a taxa chega a 622 Mbps
Jorge Luiz
3a Parte
Noções Básicas
de Processos Estocásticos
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Suponham as seguintes variáveis:
Tempo de CPU consumido por programas
Número de pacotes no buffer de um roteador
Número total de bytes enviados por dia
Evolução do percentual médio de utilização da rede a
cada segundo
Intervalo de tempo entre pacotes recebidos
Tempo de resposta de um servidor
ATENÇÂO: o período (tempo) onde as variáveis são mensuradas
tem uma grande importância no comportamento delas. Cada
uma das variáveis acima são variáveis aleatórias que variam no
tempo.
Jorge Luiz
Noções Básicas de
Processos Estocásticos
O
termo estocástico vem do grego. Significa
conjecturar, supor, advinhar. Podemos imaginar que
um Processo Estocástico é um processo sobre o qual
só podemos ter palpites sobre o comportamento, mas
jamais certezas.
Processo estocástico é uma coleção de variáveis
aleatórias indexadas pelo tempo. Representa-se por
{ X(t), t T } ou então {Xt, t T}
Espaço de parâmetros e de estados (T e E).
O espaço de estados “E” representa o conjunto de
todos possíveis valores que as variáveis podem
assumir.
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Processos
com parâmetro discreto e contínuo
Processos com espaço de estado discreto e
contínuo
Para que serve?
A finalidade do estudo dos processos estocásticos é
compreender o comportamento da trajetória de um
sistema com objetivo de fazer previsões e/ou
controlar o futuro do sistema.
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Tu = tempo consumido de CPU por processos durante um dia
T = { t R 0 t 24 }, E = { x R x 0 }
Tu
0
24 t
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Np = número de pacotes no buffer de um roteador durante um dia
T = { t R 0 t 24 }, E = { 0,1,...,n }
Np
0
24
t
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Nb = número de total de bytes enviados por dia durante um ano
T = { t R t = 1,2,...,365 }, E = { 0,1,...,n }
Np
1
2
3
...
365 t
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Em = evolução do percentual médio de utilização da rede a cada
segundo durante uma hora
T = { t R t = 1,2,...,3600}, E = { x R x 0 }
Em
...
1
2
3
...
3600 t
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Momentos de um Processo Estocástico
É interessante encontrar um conjunto de medidas que ressaltem
as características dominantes da variável.
Media de X t : E[ X t ] t
Se X discreto e tomar apenas um número finito de valores, então
n
E ( X ) xt p( xt )
1
Pode ser considerado como tuma
média ponderada dos valores
possíveis de x1, ..., xn. Se todos valores possíveis forem igualmente
prováveis, então
n
_
1
E ( X ) x xt
n t 1
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Momentos de um Processo Estocástico
Variância de X t : V ( X ) E[ X E ( X )]2
E[ X t ] {E[ X t ]}
2
2
A variância mede a dispersão de uma v.a. em relação à sua
média. Grandes valores de 2 implicam grande dispersão em
relação à média. Pequenos valores implicam forte concentração
da distribuição na vizinhança da média.
A variância amostral é dada por:
n
_
1
2
V ( X ) ( xt x) 2
n t 1
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Momentos de um Processo Estocástico
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Momentos de um Processo Estocástico
O primeiro momento de duas variáveis, X e Y, que nos dá uma
medida de sua interdependência, é (X,Y) = E[(X - mX)(Y - mY)].
É chamado covariância de X e Y.
Processo estocástico estacionário
As funções de distribuição conjunta de um processo estacionário
são iguais, ou seja, as funções de distribuição são invariantes sob
mudanças da origem do tempo.
F ( x1 ,...,xn ; t1 ,...,tn ) F ( x1 ,...,xn ; t1 k ,...,tn k )
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Momentos de um Processo Estocástico
Suponha {Xt}, t=0,1,2,... é um processo estocástico estacionário.
Um processo estacionário tem média estacionária = E[Xt],
variância finita e estacionária 2 = E[(Xt - )2] e função de autocovariância k = E[(Xt - )(Xt+k - )], que depende somente de k e
não de t. Isto é, para esse processo, a média e variância
independem do tempo e a covariância da diferença dos tempos.
Auto-covariância amostral é dada por
_
_
1 nk
k ( xt x)(xt k x), k 0,1,...,n 1
n t 1
Jorge Luiz
Noções Básicas de
Processos Estocásticos
Momentos de um Processo Estocástico
Observe que 0 = 2. A função de auto-correlação de Xt no atraso
k é denotada como k. Por definição a autocorrelação amostral é
k = k /0.
Valores positivos de mostram que Xt+k tende a crescer com o
crescimento de Xt, enquanto valores negativos mostram que Xt+k
tende a decrescer. Um valor de próximo de zero indica ausência
de relação entre Xt e Xt+k. Valores próximos de +1 e -1 indicam
auto grau de relação entre as variáveis.
_
_
k k
1 nk
k ( xt x)(xt k x) e k 2
n t 1
0
Jorge Luiz
4a Parte
Visão Geral
sobre Modelagem de Tráfego
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
Ferramenta de maior utilização -> Teoria das Filas
tráfego oferecido a uma fila
efetua-se medidas de desempenho, através de
metodologias analíticas ou simulações.
O tráfego simples consiste:
de chegadas de entidades (células , pacotes, etc.)
formam um fluxo caracterizado por uma sequência de
observações nos instantes de tempo ...,tn-1, tn, tn+1, ...
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
Processos que modelam chegadas de entidades
discretas podem ser matematicamente descritos
como processos pontuais compostos por uma
seqüência de instantes de chegada t0 = 0, t1, t2,..., tn,
medidos a partir da origem zero.
Descrições equivalentes de processo pontuais
Processo de contagem
Processo de intervalos entre chegadas
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
Processo de contagem {Xt}t=0 é um processo
estocástico de valores inteiros não negativos e
contínuo no tempo, onde Xt é o número de chegadas
no intervalo de tempo (0, t].
Processo de intervalos entre chegadas é uma
seqüência aleatória não negativa {An}n=1, onde
An = tn - tn-1 é a duração do intervalo de tempo que
separa a n-ésima chegada da anterior.
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
As observações podem descrever:
intervalos de tempo entre chegadas sucessivas de
comandos -> mostra o comportamento do usuário
intervalos de tempo entre chegadas de pacotes ou os
tamanhos dos pacotes -> mostra o comportamento da
aplicação
os Xti normalmente tem uma fdp (função de distribuição
de probabilidade) conhecida.
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
O que se deve mensurar:
Telnet
Intervalo de tempo entre chegadas de sessões (em
segundos)
Duração de cada sessão (entre o login e logout)
distribuição log-normal
Intervalo de tempo entre chegadas de pacotes
ajusta-se a uma distribuição exponencial - f(x)=e-x
distribuição de Pareto
Tamanho do pacote (em bytes)
nenhuma distribuição conhecida
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
=3
f(x)=e-x
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
=0.9
k=2,3,4,5
f(x)= .k/x+1, x=k,...,)
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
O que se deve mensurar:
FTP
Chegadas de sessões FTP (num intervalo de 1 hora)
Número de arquivos transferidos numa sessão FTP
ajusta-se a uma distribuição Poisson
nenhuma distribuição conhecida
Tamanho de cada item de uma sessão FTP
distribuição log-normal
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
=2
=1
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
O que se deve mensurar:
Tráfego de vídeo VBR
Teleconferência - não tem mudanças de cenas ou corte e
movimento moderado
Intervalo de tempo entre frames é constante - 33
milisegundos para NTSC (30 frames/s) e 40 milisegundos
para PAL-M (25 frames/s)
Vídeo MPEG - fluxo mais explosivo - frequentes mudanças
de cena e movimentos. Deve-se levar em consideração:
Duração da cena
Três tipos de frames codificados: Intra-coded(I),
Predicition(P) e Bidirectional(B) -> Tamanho dos três tipos de
frame.
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
O que modelar:
Tráfego WWW - gerado pelos browsers
Crovella provou que segue o modelo auto-similar
Intervalo de tempo médio entre solicitações - depende da
popularidade do site e do número de usuários. Site da
NCSA tem 400.000 solicitações/dia. Para um usuário, o
número médio de solicitações é 5,75 em 1/2 hora. Poisson.
Tamanho do documento transferido - Ajusta-se a uma
distribuição de Pareto com 0,40 0,63 e 21 kbytes.
Grau de variação do tamanho do doc. é muito grande.
Variedade de documentos (HTML, images(gif, jpeg,
bitmap), postscript, audio(wav, etc.) e vídeo(MPEG)
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
O que modelar:
Tráfego WWW - gerado pelos browsers
Crovella provou que segue o modelo auto-similar
Intervalo de tempo médio entre solicitações - depende da
popularidade do site e do número de usuários. Site da
NCSA tem 400.000 solicitações/dia. Para um usuário, o
número médio de solicitações é 5,75 em 1/2 hora. Poisson.
Tamanho do documento transferido - Ajusta-se a uma
distribuição de Pareto com 0,40 0,63 e 21 kbytes.
Grau de variação do tamanho do doc. é muito grande.
Variedade de documentos (HTML, images(gif, jpeg,
bitmap), postscript, audio(wav, etc.) e vídeo(MPEG)
Jorge Luiz
Visão Geral sobre
Modelagem de Tráfego
Como obter os traces de dados:
Simuladores de rede
tcpdump
ntop
Existem traces prontos na Internet.
NS (Network Simulator)
OPNET
Analisadores de tráfego
NetSpec
HP LAN Analyzer
Jorge Luiz
5a Parte
Modelos
para Modelar Tráfego
Jorge Luiz
Modelos Tradicionais
Processos de Renovação
Variáveis são independentes e identicamente
distribuídas (IID) - as observações no tempo t não
dependem de observações do passado ou do futuro.
Característica -> inexistência de uma função de
autocorrelação
Processos de renovação mais usados em modelagem
de tráfego
Poisson
Bernoulli
Jorge Luiz
Modelos Tradicionais
POISSON
Um processo de Poisson descreve o número de
chegadas de entidades observadas no intervalo de
tempo (0,t]. Tem a seguinte fdp:
(t ) x e t
P( X t x)
, x 0,1,...
x!
O n-ésimo tempo An entre duas chegadas sucessivas é
descrito por uma distribuição exponencial:
t
P( An t ) 1 e , t 0.
Jorge Luiz
Modelos Tradicionais
BERNOULLI
As chegadas podem acontecer em algum slot de
tempo. A probabilidade de uma chegada em um slot de
tempo é p, independente das outras chegadas. A
probabilidade que aconteçam k chegadas em n slots de
tempo é dada por:
n k
nk
P( X t k ) p (1 p) , k 0,...,n.
k
Jorge Luiz
Modelos Tradicionais
Processos de Renovação
Possíveis aplicações
Chegada de usuários para utilizar alguma facilidade
(aplicação) do computador
Chegada de pacotes em um nó da rede, desde que o
tráfego observado não apresente autocorrelação.
Fluxo de comandos digitados pelo usuário, desde que não
se observe dependência proveniente do passado.
Supõem que o tráfego não é correlacionado
Na realidade o tráfego é correlacionado, contradizendo
a suposição da independência da V.A.
Jorge Luiz
Modelos Tradicionais
Processos de Markov
Jorge Luiz
Modelos Tradicionais
Processos Markovianos
Descreve dependências entre os Xt.
A probabilidade (p ij ) do próximo estado observado
Xn+1=j depende somente do estado atual Xn=i .
p ij independe do tempo que o processo permaneceu no
seu estado atual.
Para definir a probabilidade da cadeia estar em um dado
estado no presente basta olhar onde ela estava no
instante imediatamente anterior. Esta propriedade é
chamada de Propriedade Markoviana.
Jorge Luiz
Modelos Tradicionais
Processos Markovianos
Um bêbado deseja se deslocar de um ponto A para
um ponto B. Chamemos de Xt a posição do bêbado
no instante t. Para simplificar, suponhamos que o
bêbado só possa se deslocar uma posição para trás
e para frente ou então permanecer na mesma
posição que ele estava no instante anterior, com a
mesma probabilidade
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
A
1
2
3
4
5
6
7
8
B
Jorge Luiz
Modelos Tradicionais
Depois de doze passos o bêbado está no estado 2.
Seja Xn a posição do bêbado no instante n. Lembrese que E = {A,1,2,3,4,5,6,7,8,B} e T Z+. Observe que
P( X13 = 3 | X12 = 2 ) = 1/2
P( X13 = 5 | X12 = 2 ) = 0
A propriedade Markoviana não é uma propriedade
válida para todos os processos e aqueles que a
possuem são ditos Markovianos.
Jorge Luiz
Modelos Tradicionais
Exemplo - mudança do estado de uma rede
Considere uma rede que pode estar em um de dois
estados: UP e DOWN.
Considere o conjunto E = {0,1} para representar os
estados dessa rede: 0 corresponde a DOWN e 1 a UP.
O estado dessa rede é observado a cada hora. T =
{0,1,2,...}
Desta forma temos uma cadeia estocástica {Xn}, onde
Xn é o estado da rede na n-ésima hora de observação.
Jorge Luiz
Modelos Tradicionais
Considere ainda que:
Se a rede estiver no estado UP a probabilidade dela
falhar na próxima hora é dada por ;
Se a rede estiver no estado DOWN a probabilidade
de se consertar a falha na próxima hora é ;
Probabilidades de transição:
p00 = P(Xn+1 = 0 | Xn = 0) = 1 -
p01 = P(Xn+1 = 1 | Xn = 0) =
p10 = P(Xn+1 = 0 | Xn = 1) =
p11 = P(Xn+1 = 1 | Xn = 1) 1 -
Jorge Luiz
Modelos Tradicionais
Diagrama de transição P
1-
1-
1
0
Jorge Luiz
Modelos Tradicionais
A matriz de transição P é dada por:
down na hora n
down na
hora n+1
up na
hora n+1
1-
= P
up na hora n
1-
Jorge Luiz
Modelos Tradicionais
Modelos de Tráfego usando Cadeias de
Markov
Possíveis aplicações
Comportamento do usuário no terminal. A próxima
ação é determinada pela ação anterior.
Falha / mudança do estado da Rede ou do sistema.
Jorge Luiz
Modelos
Modelos Estocásticos
Lineares (Séries Temporais)
Jorge Luiz
Modelos Estocásticos
Lineares
Série Temporal é a classe de fenômenos cujo
processo de observação e a conseqüente
quantificação numérica gera uma seqüência de
dados distribuídos no tempo. Na maioria das
séries, as observações são tomadas em
intervalos de tempo discretos e eqüidistantes.
Uma série temporal discreta pode ser
representada por XT = { x1, x2, ..., xT}, sendo que
cada observação discreta xt está associada a um
instante de tempo distinto.
Jorge Luiz
Modelos Estocásticos
Lineares
O objetivo inicial da análise de séries temporais é
a realização de inferências sobre as propriedades
ou características básicas do mecanismo gerador
do processo estocástico das observações da
série. A partir das observações da série é
possível construir um modelo matemático que
represente a realidade de forma simplificada.
Após a construção do modelo, é possível utilizálo para testar hipóteses e realizar a previsão de
valores futuros da série.
Jorge Luiz
Modelos Estocásticos
Lineares
Considerando um conjunto de observações de uma
série temporal coletadas até o instante t e de um
modelo que represente esses fenômenos, a previsão
do valor da série no tempo t + h pode ser obtida.
t
t+h
Jorge Luiz
Modelos Estocásticos
Lineares
Método de previsão é um conjunto de procedimentos
usados no desenvolvimento de um determinado
prognóstico. Se baseia na suposição de que
observações passadas contém todas informações
sobre o padrão de comportamento da série e esse
padrão é recorrente no tempo.
O propósito dos métodos de provisão consiste em
distinguir o padrão de qualquer ruído que possa estar
contido nas observações e então usar para prever os
valores futuros.
Jorge Luiz
Modelos Estocásticos
Lineares
Univariados
Método de previsão
Funções de Transferência
Multivariados
Decomposição
Univariados
Simples de previsão
Avançados
Jorge Luiz
Modelos Estocásticos
Lineares
Método de Decomposição
Identifica componentes (não observáveis) individuais
presentes no padrão básico da série histórica de
dados e a partir daí extrapola o futuro.
Xt = f(St, Tt, Ct, Et)
St é a componente sazonal para o período t
representa as flutuações da série de acordo com algum fator
de sazonalidade.
Ct é a componente de ciclo para o período t
comportamento similar ao sazonal, embora tenha
comprimento maior
Jorge Luiz
Modelos Estocásticos
Lineares
Método de Decomposição
Tt é a componente de tendência para o período t
representa o aumento ou declínio gradual nos valores das
observações.
Et é a componente aleatória no período t
É determinada pela identificação e remoção das componentes
anteriores.
Jorge Luiz
Modelos Estocásticos
Lineares
Método Simples de Previsão
Considera como previsão para o período futuro a média
das observações passadas recentes.
Método da Média Móvel - mais conhecido
xt 1 xt 2 ... xt n
xt
n
O termo média móvel é usado porque à medida que a
próxima observação se torna disponível, a média das
observações é recalculada, incluindo essa observação no
conjunto das observações e desprezando a observação
mais antiga.
Modelos Estocásticos
Lineares
Método Avançados de Previsão
Os modelos mais conhecidos são:
AR(p) - Autoregressivo Linear de ordem p
MA(q) - Médias Móveis de ordem q
ARMA(p,q) - Autoregressivo e de Médias Móveis
ARIMA(p,d,q) - Autoregressivo integrado e de Médias Móveis
Box e Jenkins
Esses modelos obtém a previsão de algum valor
futuro da série temporal pela combinação dos valores
reais passados e/ou dos erros ocorridos.
Jorge Luiz
Modelos Estocásticos
Lineares
Modelo Autoregresssivo - AR(p)
É dado pela equação:
xt 1xt 1 2 xt 2 ... p xt p t
onde xt corresponde à observação da série no tempo t,
ou seja, xt é a soma ponderada dos p valores anteriores
mais o ruído aleatório ou ruído branco;
p corresponde ao parâmetro do modelo AR de ordem p;
t representa o erro de eventos aleatórios que não
podem ser explicados pelo modelo.
Jorge Luiz
Modelos Estocásticos
Lineares
Modelo de Médias Móveis - MA(q)
É dado pela equação:
xt t 1 t 1 2 t 2 ... q t q
onde t representa o erro dos eventos aleatórios que nâo
podem ser explicados pelo modelo;
q corresponde ao parâmetro do modelo MA de ordem q;
Essa equação é similar à equação anterior, exceto pelo
fato de que o valor previsto para a observação depende
dos valores dos erros observados em cada período
passado, ao invés das próprias observações.
Jorge Luiz
Modelos Estocásticos
Lineares
Modelo Autoregressivo e de Médias Móveis - ARMA(p,q)
É dado pela equação:
xt 1xt 1 2 xt 2 ... p xt p t 1 t 1 2 t 2 ... q t q
os modelos ARMA relacionam os valores futuros com as
observações passadas, assim como também com os
erros passados apurados entre os valores reais e os
previstos.
Jorge Luiz
Modelos Estocásticos
Lineares
Modelo Autoregressivo Integrados - ARIMA(p,d,q)
É dado pela equação:
xt 1wt 1 2 wt 2 ... p wt p t 1 t 1 2 t 2 ... q t q
sendo wt = xt - xt-d;
onde p e q são os parâmetros do processo ARMA de
ordem p e q;
t representa o erro dos eventos aleatórios que nâo
podem ser explicados pelo modelo;
d eqüivale ao grau de homogeneidade não-estacionária.
Jorge Luiz
Modelos Estocásticos
Lineares
Método de BOX e JENKINS
Consiste na busca de um modelo ARIMA que
represente o processo estocástico gerador da série
temporal, a partir de um modelo ARMA aplicável na
descrição de séries temporais estacionárias,
estendendo esse conceito para séries temporais não
estacionarias.
Jorge Luiz
Modelos
Distribuição de Caudas
Pesadas
Jorge Luiz
Distribuição de Caudas
Pesadas
X
10
100
1000
Cálculo x- para = 0.5, 1, 1.5
-0.5
-1
x
0.316228
0.1
0.031622
x
0.1
0.001
0.0001
-1.5
x
0.031622
0.001
0.000032
Para fixo, a medida que x cresce, a função não tende a
zero. Quanto menor o valor de , mais vagarosamente a
função tende a zero.
Jorge Luiz
Distribuição de Caudas
Pesadas
Características
V.A. que tem distribuição de caudas pesadas
apresentam uma grande variabilidade nos valores
observados. A média é muito afetada pelos valores
extremos.
A variância ou o desvio padrão é muito grande. Uma
distribuição de cauda pesada tem grande infinita.
Se o fenômeno observado apresenta grande
variabilidade em diversas escalas de tempo, a distrib.
de probabilidade tem que ter caudas pesadas.
Jorge Luiz
Distribuição de Caudas
Pesadas
Forma
A v.a. X segue uma distribuição de cauda pesada se:
P( X x) ~ x , x , 0 2
Por ex., a distribuição normal N(0,1) não tem caudas
pesadas. P( N(0,1)>3 ) 0.
Uma distribuição de caudas pesadas apresenta
probabilidades diferentes de 0 para valores grandes
de x.
Jorge Luiz
Distribuição de Caudas
Pesadas
=0.9
k=2,3,4,5
f(x)= .k/x+1, x=k,...,)
Jorge Luiz
Distribuição de Caudas
Pesadas
Distribuição de Pareto
f ( x) k x
( 1)
, 0, k 0, x k
A função de distribuição acumulada é:
k
F ( x) P( X x) 1 , 0, k 0, x k
x
k
P( X x) , 0, K 0, x k
x
Jorge Luiz
Distribuição de Caudas
Pesadas
Variáveis encontradas no estudo do comportamento das
redes que seguem uma distribuição de caudas pesadas:
tempo de transmissão de arquivos;
tamanho de arquivos disponíveis nos servidores Web;
Tempo entre chegadas de pacotes em roteadores da Internet;
número de sites visitados;
Jorge Luiz
Modelos
Modelo Auto-Similar
Jorge Luiz
Modelo Auto-Similar
Conjuntos Cantor com 5 níveis de recursão
Jorge Luiz
Modelo Auto-Similar
S0 = [0,1]
S1 = [0,1/3] U [2/3,1]
s2 = [0,1/9] U [2/9,1/3] U [2/3,7/9] U [8/9,1]
Duas propriedades do fenômeno auto-similar:
o conjunto mantém um padrão na sua estrutura,
mesmo em escalas pequenas
A estrutura se repete. Uma estrutura auto-similar
contém pequenas réplicas de si mesma.
Jorge Luiz
Modelo Auto-Similar
Seja {Xt} um processo estocástico estacionário
média estacionária: = E[Xt]
variância finita e estacionária: v = E[(Xt - )2]
auto-covariância estacionária: k = E[(Xt - )(Xt+k - )]
Se k=0, então v = 0
auto-correlação no atraso k é k. Por definição k = k / 0
Jorge Luiz
Modelo Auto-Similar
Dividir {Xt} em blocos não superpostos de tamanho
m.
É criar uma novas séries de tempo ou séries amostrais de Xt
Seja Xj(m) é a media amostra Xjm-m+1+...+Xjm, então
Xj(m) = ( Xjm-m+1+...+Xjm)) / m
Se o processo é um ruído branco, então os Xjmm+1+...+Xjm serão mutuamente não correlacionados,
i.e., k = 0 e vm = vm-1
No caso que k 0 e k=- k < , a variância da média
da amostra vm decai para zero proporcionalmente a
m-1, i.e., vm vcm-1
Jorge Luiz
Modelo Auto-Similar
O processo de Markov e as séries temporais
conhecidas (AR,MA,ARMA) tem um vm decaindo
dessa forma.
Existem processos em vm decai mais lentamente, i.e.,
a uma taxa menor que m -1. Por ex. vm poderia decair
proporcionalmente a m-, para algum (0,1).
Se vm é proporcional a m-, então k=- k é
proporcional a m1-, i.e., k=- k Cm1-
Como < 1, implica que k=- k e que a autocorrelação decai lentamente de uma forma não
totalizável.
Jorge Luiz
Modelo Auto-Similar
Decaimento rápido da auto-correlação
1.0
0.8
0.6
0.4
0.2
0.0
0
10
20
30
40
50
Jorge Luiz
Modelo Auto-Similar
Decaimento mais lento da auto-correlação
1.0
0.8
0.6
0.4
0.2
0.0
0
10
20
30
40
50
Jorge Luiz
Modelo Auto-Similar
Dependências de Curto e Longo Alcance
Um processo {Xt} é dito ter dependência de curto
alcance, se k=- k < . Sua função de autocorrelação decai exponencialmente e os {Xj(m)}
tendem a um ruído puro qdo m .
Um processo {Xt} é dito ter dependência de longo
alcance, se k=- k . Sua função de autocorrelação decai mais lentamente (hiperbolicamente)
e os {Xj(m)} não formam um ruído puro.
Jorge Luiz
Modelo Auto-Similar
Processo Auto-Similar (definição)
Um processo {Xt} é dito ser exatamente auto-similar
de segunda ordem, se k(m) = k, m e k, i.e., a
estrutura da correlação é preservada em diferentes
escalas de tempo.
Um processo {Xt} é dito ser assintoticamente autosimilar se k(m) k, para m e k grande.
Exemplo de processos auto-similar: FBm
Jorge Luiz
Modelo Auto-Similar
Como identificar um Processo Auto-Similar
O parâmetro H (Hurst) é um indicador de autosimilaridade.
É uma medida que verifica a “persistência”do
processo em um longo período.
Processo que tem LRD: 0,5 < H < 1
Como estimar H
estatística R/S
baseado na análise do pediograma
estimador de Abry-Veit
Jorge Luiz
FIM
Muito obrigado
Jorge Luiz
Download
