UNIVERSIDADE FEDERAL DO PARANÁ
SETOR DE TECNOLOGIA
DEPARTAMENTO DE ENGENHARIA ELÉTRICA
MESTRADO EM TELECOMUNICAÇÕES
Amostragem de trajetória para
observação direta de tráfego
Disciplina: COMUNICAÇÃO DE DADOS
Professor: Eduardo Parente Ribeiro
Vilson R. Mognon
Estrutura da apresentação
• Introdução
• Descrição do método
– Datagrama IP
– Função Hash
•
•
•
•
Amostragem ótima
Medida de tráfego
Discussão
Conclusão
Introdução
• $
• Qualidade de serviço (QoS)
• Administração de tráfego
– Controle de tráfego
• controle automático em caso de perdas de links ou falha de roteamento
– Engenharia de tráfego
• Alocação de recursos da rede para diferentes classes de tráfego
Métodos de medida
• Método direto
– confia na observação direta de tráfego em
pontos múltiplos na rede.
• Método indireto
– conta com um modelo de rede e informação do
estado desta para deduzir o fluxo espacial de
tráfego pelo domínio.
Médotos indiretos
– sofrem a incerteza associada com o estado
físico e lógico de uma grande rede heterogênea
– fontes deliberadas de aleatoriedade na rede
– comportamentos da rede pode depender de
eventos fora do controle do domínio
– a interação entre esquemas adaptáveis pode ser
muito complexo de caracterizar e predizer
– com o aumento do tamanho e complexidade,
aumenta-se probabilidade de falhas
Métodos diretos
– não conta com um modelo de rede e estimação
do seu estado e do seu comportamento esperado
– não sofre das fontes de incerteza
Amostragem de tragetória
– amostra pacotes que atravessam um subconjunto
de links dentro um domínio de medida
– decisão amostragem tem base numa função hash
deterministica em cima do conteúdo de pacote
– etiquetamento do pacote
– quantia de tráfego de medida gerado é modesto
– método direto
– pode ser implementado usando DSPs
Representação esquemática
Descrição formal do método
– Função de invariância
– Função hash
– Decisão de amostragem
– Função de identificação
Datagrama IP
Trajetórias ambígüas
– etiquetas são alocadas pseudorandomicalmente
há obviamente uma chance de colisão de
etiqueta no mesmo período de medida.
– em quais circunstâncias pode-se eliminar a
ambigüidade destas trajetórias ?
Exemplos de trajetórias
Especificação das funções
– Função hash
– Decisão de amostragem
– Função de identificação
Exemplo
r-1
Exemplo
Pacotes idênticos
– decisão de amostragem e suas etiquetas serão
também idênticas
– como não são amostrados
pseudorandomicamente pelo método pode
conduzir a estimadores tendenciosos
– pacotes idênticos são raros na prática
Colisão de pacotes
Propriedades estatísticas dos
algoritmos hashs
– Uma propriedade desejável da amostragem
hash é que o pacote amostrado deva aparecer
independente de um subconjunto do conteúdo
do pacote.
– A distribuição de qualquer atributo variável do
pacote deva ser o mesmo para pacotes
amostrados como para a população original.
Testes da hipótese de
independência
• Distribuições do Prefixo de endereço
• Distribuições dos bits de endereço
• Distribuições de amostragem temporais
Amostragem ótima
• confiabilidade das estimativas de tráfego
aumenta com o número de amostras não
ambíguas coletadas
• temos que limitar a quantidade total de
tráfego de medida entre os roteadores no
domínio e no sistema de coleção.
Problema de otimização
• maximizar o número esperado de amostras únicas
(não ambíguas), sujeito a limitação de que o total
de tráfico de medida não deve exceder uma
constante c predefinida
probabilidade que a etiqueta é gerada
precisamente uma vez o domínio
número médio de amostras únicas
fixando m = c / n
Exemplo
c = 10^6 bits
n* = 5.15 x 10^4
m = 19.4 bits
p=0.072
Medida de Tráfego
Qual fração de
tráfego no link
do back bone
vem do link de
acesso do
cliente ?
Simulação para c =1 Kbits
M = 693.1
B = 691
n = 106
Simulação para c =10 Kbits
M = 6931.5
B = 6917
n = 782
Implementação
• Dispositivo capaz
– computar a amostragem hash e fazer uma
decisão de amostragem
– computar a hash identificação para os pacotes
Implementação
Implementação
• interface de administração
– habilitar/desabilitar amostragem de pacote
– dizer ao dispositivo onde enviar o tráfico de medida
– fixar os parâmetros das “hash function”.
• Um protocolo de administração de rede simples
(SNMP) e uma base de informação de
administração (MIB), indexado pelo endereço IP
da interface, poderia cumprir esta função.
Outros métodos
• Medida de link
• Agregação de fluxo
• Provas fim-a-fim ativas
Medida de link
• Baseado em agregação, direto
• estatística de trafego (bytes e pacotes transferidos
e derrubados) são medida por link e reportadas
periodicamente
• não permite classificar o tráfego
• não permite inferir o caminho do fluxo de tráfego
• detecta problemas potenciais, mas não pode
analisar e remediar problemas de roteamento
Agregação de fluxo
• Baseado em agregação, indireto
• roteadores do domínio coletam informação por
fluxo (sequência de pacotes com campos comuns)
• Considerável quantia de dados de medida
• pode obter matrix de caminho completa do
domínio
• depende da emulação de protocolos de roteamento
Provas fim-a-fim ativas
• Baseado em amostragem, indireto
• host enviam pacotes de prova para outros host
para estimar medidas, como taxa de perda de
pacotes, e tempo de ida e vinda (round-trip delay)
• características devem ser inferidas para links
• não requer nenhum suporte de medida da rede
Conclusão
• O método apresenta características desejáveis:
– simples processamento
– estado do roteador não é requerido
• não requer cache no roteador
– pacotes são observados diretamente
• não requer o modelo da rede