Predição de Fluxos em Redes de Computadores

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


• 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


• 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


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


Mestrado em Engenharia da Informação

Orlando da Silva Junior

Technology

Predição de Fluxos em Redes de Computadores