Predição de Fluxos em Redes de Computadores
Mestrado em Engenharia da Informação
Orlando da Silva Junior
Dra. Ana Carolina Lorena Dr. Carlos Alberto Kamienski
Motivação
• Redes Definidas por Software (SDN)
– As consultas enviadas pelo switch ao controlador produzem um atraso inicial na comunicação
– Solução: instalar fluxos de maneira antecipada nos switches
• Como? Por meio da predição de tráfego
• Quê tráfego? O tráfego gerado pelas aplicações de rede
2
Objetivo Geral
• Investigar a predição de fluxos em redes de computadores
– A investigação é fundamentada nos conceitos de SDN
3
Motivação
• Como fazer predição de fluxos em SDN?
– Arcabouço da Predição de Links (PL), uma recente área de Análise de Redes Complexas (ARC)
– Outro desafio: a topologia da rede lógica é diferente da topologia da rede física
• Solução: mapeamento entre as duas redes
– É possível ter uma melhor solução?
• Técnicas de Aprendizado de Máquina (AM)
4
Objetivos Específicos
• Elaborar um método de mapeamento entre as redes física e de aplicação
• Investigar uma nova forma de predizer ligações que se formam e se mantêm
• Experimentar diferentes algoritmos de PL e AM supervisionado
• Comparar os resultados de PL e AM
5
Conceitos Fundamentais
Redes complexas, predição de links, SDN e aprendizado de máquina
6
Redes Complexas | Conceitos
• Uma rede complexa é um conjunto de itens com conexões entre eles • As redes podem ser vistas como medidas estatísticas ou grafos do tipo:
– Não-orientado: G=(V, E) – Orientado: G=(V, A)
• Vértices (V): representam entidades do mundo • Arestas (E) ou Arcos (A): representam as conexões entre as entidades
• Existem diversos modelos de redes que representam mais fielmente as redes do mundo real:
a) Modelo Erdős–Rényi (Aleatória) b) Modelo Watts-Strogatz (Mundo Pequeno) c) Modelo Barabási-Albert (Sem Escala)
7
Predição de Links | Conceitos
• Investiga a probabilidade de associações futuras entre entidades de uma rede – Qual é a chance de duas entidades se conectarem no
futuro?
• Principais Tarefas
– Predição de novos links: links que se formarão – Persistência de links: links que permanecem conectados
• Métodos comuns – Não-supervisionado: atribuição de escores, não-temporal – AM supervisionado: utilização de diferentes escores,
temporal
8
Predição de Links | Conceitos
• Os algoritmos tradicionais de PL são preditores que atribuem um escore a cada um dos pares de nós do conjunto de dados.
• O escore representa a probabilidade preditiva de um determinado par de nós estar conectado
• Os algoritmos tradicionais podem ser baseados: – No grau do nó – Na vizinhança do nó – No caminho entre nós
• Exemplo: 𝐶𝑁 𝑢, 𝑣 = Γ 𝑢 ∩ Γ 𝑣
9
Aprendizado de Máquina| Conceitos
• Técnicas de AM criam hipóteses a partir de experiências passadas – Processo indutivo: situações particulares inferem conclusões
genéricas – Conjunto de dados: formado por exemplos que contém
atributos
• Indução preditiva
– Encontra hipóteses a partir dos valores dos atributos dos dados de treinamento
– Paradigma supervisionado: os algoritmos aprendem a hipótese utilizando um conjunto de dados pré-classificados
– Algoritmos: C5.0, SVM, Naïve Bayes e k-NN.
10
Predição de Links | Conceitos
• Links positivos e Links negativos • X: conjunto de nós da rede inicial em Δt • Y: conjunto de nós da rede posterior em Δt+σ • U: conjunto de todos os pares de nós possíveis
11
SDN | Conceitos
• Em geral, as arquiteturas de redes são formadas por dois componentes principais: – Plano de controle: configuração dos nós da rede – Plano de dados: encaminhamento dos dados
• Tradicionalmente, esses planos são combinados.
• Em SDN, os planos são desacoplados:
– Separação lógica entre os planos – Centralização das tarefas em um controlador
• Manipula os dispositivos da rede • Possui visão global do estado da rede • Fornece alta abstração para o desenvolvedor
12
Predição de Fluxos em Redes de Computadores
Metodologia, dados, mapeamento, predição e avaliação
13
Metodologia | Predição de Fluxos
14
Gerenciamento | Predição de Fluxos
• Redes de Aplicação
• Redes Físicas com 𝑁𝑐 = {10, 15, 25, 50, 100, 200} • Rede Aleatória com 𝑝 = 0,25
• Rede de Mundo Pequeno com 𝑔 = 2, 𝑝 = 0,25
• Rede Sem Escala com conexão preferencial linear
• Modelo sem topologia
15
Mapeamento| Predição de Fluxos
16
Particionamento| Predição de Fluxos
• Rede P2P: 12h/12h
• Rede de e-mails: 3 anos (1998-2000)/1 ano (2001)
17
Predição| Predição de Fluxos
• Seleção e Configuração dos Algoritmos – Tradicionais de Predição de Links
• Grau do nó (3): Graus do nó de Entrada/Saída e Conexão Preferencial;
• Vizinhança (6): Vizinhos Comuns, Jaccard, Adamic/Adar, RAI, HPI, HDI;
• Caminho (3): CMC, Katz, PropFlow
– Aprendizado de Máquina
• C4.5, SVM linear, Naïve Bayes e 1-NN
• Ferramenta R
• Avaliação de Desempenho – Validação Cruzada com 10 subconjuntos
– Medida F1
18
Resultados
Resultados e discussão
19
Rede P2P (PL) |Resultados
20/27
Rede P2P (AM) |Resultados
21/27
Rede de E-mails (PL) |Resultados
22/27
Rede de E-mails (AM) |Resultados
23/27
Considerações Finais | Resultados
• Algoritmos – Os resultados das técnicas de AM são, em geral, superiores aos das técnicas
de PL • Melhores casos: redes pequenas
– Por outro lado, a deterioração do desempenho é mais rápida em AM – Destacam-se os algoritmos mais simples
• CMC e medidas de grau • Naïve Bayes e k-NN
• Modelos Topológicos
– Bom desempenho dos preditores no modelo sem topologia – As redes de mundo pequeno e sem escala representam mais fielmente as
situações do mundo real
• Conclusão: a rede física subjacente também influencia na predição de fluxos
24
Conclusão
Conclusões, contribuições, limitações e trabalhos futuros
25
Principais Resultados| Conclusão
• Corroboração da influência preditiva entre as redes mapeadas
– Confirmação nas duas categorias de preditores
– Auxílio do método de mapeamento
• Abordagem de predição conjunta
– Predição de links que se formam
– Predição de links que se mantêm
26
Contribuições e Limitações| Conclusão
• Revisão de Literatura em PL – Inclusão de técnicas de AM supervisionado e métodos
usualmente empregados
• Inter-relacionamento de conceitos
– Redes Complexas e Predição de Links – Redes Definidas por Software – Aprendizado de Máquina
• Predição de Fluxos em redes de computadores
– O trabalho não apresenta uma aplicação concreta, mas é uma contribuição para as soluções de predição na área
27
Trabalhos Futuros| Conclusão
• Confirmação prática – O trabalho limitou-se a investigar os fluxos por meio
de redes complexas – O comportamento da predição precisa ser analisado
em redes de computadores reais (simulação)
• Experimentação da abordagem conjunta em
diferentes conjuntos de dados – Poucas redes e um único domínio
• Adoção de outros algoritmos
28
Predição de Fluxos em Redes de Computadores
Mestrado em Engenharia da Informação
Orlando da Silva Junior