Tópicos em Redes de Computadores - UFPR
Supporting System-Wide Similarity Queries for
Networked System Management
Suporte a Consultas de Similaridade de Sistema
para de gestão de redes
Songyun Duan and Xiaoqiao Meng and Hui Zhang and Guofei Jiang
IBM T.J.Watson Research Center & NEC Labs America
NOMS 2010
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
1
Gestão de Redes - Evolução

Aumento do número de sistemas de larga
escala.

Aumento da complexidade dos sistemas.

Aumento do volume de dados a analisar.

Exemplo:

Os data centers da Google têm centenas de servidores
que processam milhões de consultas todos os dias. Esses
sistemas são complexos e bastante heterogêneos.
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
2
Gestão de Redes - Questões

Como monitorar este tipo de sistemas?



Monitorando extensivamente cada um dos seus
componentes → Enorme volume de dados
Como correlacionar os dados para que seja
possível obter uma visão holística, i.e. global,
do estado da rede e da sua performance?
Como consultar os dados provenientes dos
variados componentes da rede de uma forma
simples?
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
3
Gestão de Redes - Soluções

Soluções existentes no mercado que suportam
vizualização/navegação de dados ou consultas
SQL-like:

AT&T SWIFT-3D

UC Berkley TelegraphCQ

Yahoo Pig

Facebook Hive

Microsoft DryadLINQ
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
4
Consultas de Similaridade



Soluções apresentadas somente consultam os
dados coletados.
E as semelhanças de comportamento dos
objetos durante um determinado tempo?
Objetivo:

Conhecer a similaridade ou a dissimilaridade entre
objetos da rede para que os operadores possam
analisar melhor o estado global do sistema.
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
5
Consultas de Similaridade - Exemplos



Ao encontrar um problema de performance no
período de tempo T, será que já foi detectado
um problema similar no passado que entretanto
já foi diagnosticado e resolvido?
Quais os protocolos que apresentam um padrão
mais similar a uma determinada hora?
Entre várias instâncias de máquinas virtuais
quais as que têm uma carga similar e quais as
que têm uma carga mais distinta?
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
6
Consultas de Similaridade - Exemplos


Supondo que existe um histórico temporal
indexado sobre o estado de um sistema.

SH – Estados saudáveis

SU – Estados de falha
Quando existir um estado de falha SQ o
administrador poderia fazer consultas do tipo:
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
7
S2Q Framework - Etapas
Formulação e
execução de consultas
Indexação
Cálculo da similaridade
Modelagem do sistema
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
8
Modelagem do Sistema

Fluxo de dados contínuo

D – Fluxo de dados

Xi é uma série de valores de uma métrica, medida numa
localização i em determinados pontos no tempo t0,t1,...
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
9
Modelagem do Sistema

Relações de dependência pares:
1.Dependências físicas – relacionamento direto entre
componentes
2.Dependências estatísticas – calcula correlações
estatísticas com base em séries temporais para um
par de componentes de sistema usando uma métrica
de correlação

Exemplo simples: Correlação linear

Proposta: Matriz de correlação
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
10
Relações de Dependência Pares
1ºCálculo


Gerar a matriz de auto-covariância do
componente X

ω – tamanho da janela temporal

m – tamanho da janela de histórico

Xi,ω – Série temporal começando no instante i até i+ω-1

X'i,ω – Matriz transposta de Xi,ω
Repetir para o componente Y
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
11
Relações de Dependência Pares
2ºCálculo

Calcular o valor da dependência entre X e Y
baseando-se nas matrizes de auto-covariância.

Decompor as matrizes usando decomposição em
valores singulares (SVD)

Toda a matriz A ε IRmxn pode ser escrita como:
A = USVT
onde Umxm e Vnxn são ortogonais e Smxn é diagonal.

O valor de dependência é calculado como a distância
entre os k maiores valores singulares de X e Y
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
12
Relações de Dependência Pares

1º passo do cálculo define sinopses locais.

2º passo define sinopses globais.

Desta forma o sistema permite rastrear o estado
de cada componente monitorado ou encadear
vários para criar uma visão global do sistema.
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
13
Relações de Dependência Pares
Atualização Incremental

Equal-Importance

Decaying-Importance
Mt – matriz de covariância no instante t
18 de Outubro de 2010
β –Nuno
parâmetro
decadência
Manuel Ferreirade
Gonçalves
- UFPR
14
Cálculo da Distância

Supondo V1 e V2 (vectores de colunas) das
matrizes de covariância


Decompor em valores singulares (SVD) o produto de
ambos [U,S,V] = SVD(V'1*V2)
Se o maior valor singular em S for aproximadamente
1 então os subespaços estão próximos
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
15
Métricas de Similaridade


Objetivo: Encontrar estados passados que são
similares ao estado atual s.
Instance-Based retrieval


Clustering


Procurar o vizinho mais próximo de s considerando os
estados passados.
Agrupar os estados passados dos vizinhos e calcular o
centroide que está mais próximo a s utilizando k-médias
Classification

Agrupar estados que têm padrões comuns.
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
16
Métricas de Similaridade

Graph-based Approach

V – componentes alvo do sistema

Et – conjunto de relações de dependência entre
componentes do sistema no instante t

Ambos calculados usando a matriz de covariância

D() distância entre os grafos
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
17
Índices

Índices baseados em detecção de mudanças



Quando o estado do sistema não muda as distâncias
para os vizinhos deve ser aproximadamente 0.
Quando existe uma mudança nos estados a distância
aumenta
Índice construído com base nas mudanças
verificadas, desta forma a obtenção de estados
passados é mais rápida.
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
18
Experimentos - Matlab

Duas séries temporais:
X1=sin(t)
X2=X1+U(0, 1),
t:1-1000
18 de Outubro de 2010

Nuno Manuel Ferreira Gonçalves - UFPR
19
Experimentos – Resistência ao Ruido
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
20
Experimentos - Matlab
Timestamp start: 200
18 de Outubro de 2010
Timestamp start: 400
Nuno Manuel Ferreira Gonçalves - UFPR
21
Experimentos – Detecção de padrões
de Tráfego
Dados de tráfego e padrões porta 137, ptocolo UDP
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
22
Críticas e Sugestões




Somente o primeiro passo do framework foi
descrito corretamente.
Notação confusa
Problemas de performance em sistemas com
muitas varáveis a comparar
Muito útil em sistemas que necessitem de uma
resposta em tempo real
28 de Setembro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
23
Perguntas?
18 de Outubro de 2010
Nuno Manuel Ferreira Gonçalves - UFPR
24