1 Universidade Federal do ParanáA Query Language for Network Search Uma linguagem de consultas para buscas de rede Misbah Uddin (KTH), Rolf Stadler (KTH) e Alexander Clemm (Cisco) International Symposium on Integrated Network Management - IM2013 Rafael Araújo da Silva Universidade Federal do Paraná 19/10/2015 1

2 Sumário Introdução Contribuição Experimento CríticaProblemas do Cenário Atual A Busca na Web Conceitos de Linguagens de Consulta Cenário Proposto – Busca de Rede Arquitetura Modelo de Dados – Objetos e Vínculos A Linguagem de Consultas para Buscas de Rede Processamento Testes e Resultados Obtidos Conclusão Próximos Passos Relevância, Viabilidade e Formato 19/10/2015

3 Trabalhos relacionadosManagement by network search NOMS 2012 (base) A real-time search in clouds IM 2013 Scalable matching and ranking for net search CNSN 2013 Graph search for cloud network management NOMS 2014 * Trabalhos dos mesmos autores 19/10/2015

4 Gerenciamento tradicionalGerenciamento de Falhas Gerenciamento de Configuração Gerenciamento de Segurança Aplicações SNMP Netflow SSH/CLI Protocolos de acesso Informações de estado e configuração Contadores em dispositivos SNMP MIBs Netflow explorer Objetos e atributos bem definidos – consultas diretamente na ferramenta de monitoramento (Falha, Config., Performance, Contab. & Segurança) (Problema!) Como responder rapidamente: porque o vídeo que os clientes XYZ estão assistindo está degradando em performance? Onde está a degradação de performance deste serviço? Necessidade de uma ferramenta de busca (Solução!) Elementos de rede Entidades Computacionais Dispositivos 19/10/2015

5 Como responder rapidamente questões como:Problema Como responder rapidamente questões como: Porque o vídeo que os clientes XYZ estão assistindo está degradando em performance? Como identificar e rastrear fluxos de mídia associados a uma videoconferência entre determinados nós da rede? 19/10/2015

6 Busca na web 19/10/2015 www.nr2.ufpr.brBase de dados é gigante, bases de dados não SQL, tipos de dados diversos 19/10/2015

7 Busca na web Solicitações de Busca: Algoritmos de busca:Termos (reais) para definir o que se busca Algoritmos de busca: Algoritmos: Entrada = problema (critérios)  saída retorna solução (elementos em espaço de procura - Itens conforme propriedades específicas) Novos tipos de busca (ao vivo, relacionamentos...) Dados de variados formatos e dinâmicos, classificação do dados conforme contexto, fatores como atualidade e relacionamentos contam na classificação (buscas ao vivo, busca de relacionamentos etc.)... combinação, classificação, pontuação, atualidade, relacionamentos 19/10/2015

8 Monitoramento DistribuídoBusca de Rede Busca na Web Google, Baidu, … Busca de Rede VLDB Cassandra, Dremel, Pig … Busca P2P Gnuttela, Chord, … Autores buscaram soluções em algumas áreas para incorporar em sua proposta: Busca na Web – índice distribuído invertido, match e ranking, keyword-relevance, conteúdo ao vivo, conteúdo de relacionamentos… Busca P2P – sem um servidor central, pesquisas repassadas de um nó para outro, multiplataforma Busca em VLDB – processamento distribuído (VLDB – Very Large Data Bases) big data – bases de dados muito grandes – non-SQL Google’s Dremel – Yahoo’s Pig (PigLatin) Monitoramento Distribuído MRTG, Zabbix, … 19/10/2015

9 Gestão com busca de redeDetecção de Anomalias Rastreamento de Conformidade Análise em Tempo Real Aplicações de gerenciamento Aplicações modulares genéricas “Googar” a rede Aprendizado de máquina Mineração de dados Processar grafos Busca, Classificação, Agregação, Abstração Algoritmos distribuídos Proposta - Contribuição Informações de estado e configuração Bases de dados locais em tempo real em nós de busca Redes IP Infraestrutura em nuvem Outras tecnologias Alvos 19/10/2015

10 Arquitetura Planos: Nós de Busca: Nós de Busca: Dispositivos:Gerenciamento Buscas Tecnologia alvo Nós de Busca: Coletam dados Armazenam Recebem e processam consultas Grafo de rede Nós de Busca: Coletam dados Armazenam Dispositivos: Fornecem os indicadores FCAPS – Fault, Configuration, Accounting, Performance & Security 19/10/2015

11 Modelo de dados Objetos = pares de atributos e valoresnome-objeto ns:instance-­‐07 tipo-objeto VM nucleo-cpu 2 memoria 4 GB endereco ip no-de-busca ns:cloud-­‐01 uptime 35076 sec nome-objeto ns: : tipo-objeto ip-­‐flow porta-origem 24 porta-destino 93 bytes 2216 pacotes 23567 no-de-busca ns:cloud-­‐01 hora-ligado 14:12:35 May Objetos = itens do espaço de procura URN – Uniform Resource Name IETF RFC 2141 (melhor que URL Uniform Resource Locators) GDMO – SMI – CIM – YANG  pular para slide 25 de dúvidas sobre modelos atuais - Tipo e nome são mandatórios - Identificador exclusivo (URN) Modelos atuais são complexos para busca! 19/10/2015

12 Modelo de dados Vínculos = relações entre objetosnome-objeto ns:server-06 tipo-objeto servidor nucleo-cpu 16 memoria 32 GB endereco ip no-de-busca ns:cloud-­‐01 uptime sec nome-objeto ns:instance-­ ‐07 tipo-objeto VM nucleo-cpu 2 memoria 4 GB endereco ip no-de-busca ns:cloud-­‐01 hospedeiro ns:server-06 nome-objeto ns:appvirt-­‐34 tipo-objeto aplicação proprietário John endereco ip porta 8080 no-de-busca ns:cloud-­‐01 uptime 35076 sec Vínculo = Vínculo direto ou Existe um C pertencente ao espaço de procura tal que um vinculo direto entre A e C e outro entre C e B Vínculo direto: l(a,b)  exatamente mesmo par de atributo-valor Vínculo l*(a,b)  l(a,b) ou ∃c ∈ O : l∗(a, c) ∧ l∗(c, b) Combinações não precisam ser exatas para busca 19/10/2015

13 A linguagem de consultasRegra Descrição Exemplo Termo (token) T  A | V T  A op V endereco-ip= Operação = | < | ≈ | ... Consulta (query) Q  T ∧ … ∧ T Q  T ∨ … ∨ T servidor + nucleoCPU>11 + carga-cpu < 0,2 carga-cpu>0,8 OR carga-memoria>0,8 Vínculo (link) λ (Q) λ∗(Q) link ( , ) link_(John) Projeção Π(A,…,A)(Q) project(nome) servidor + nucleoCPU > 12 Agregação α(f,A)(Q) max(largura-banda) VM + *servidor*X Notação BNF (Formalismo de Backus-Naur) Link(x,y) = objetos que tem vínculo com ambos os valores/atributos Link*(x) = qualquer objeto que tenha algum vínculo com objetos que tem o valor/atributo 19/10/2015

14 Exemplo 19/10/2015

15 Interpretação Nome de servidores com pelo menos 12 núcleos de CPU e carga inferior a 20%: Π(nome)(servidor ∧ nucleoCPU > 11 ∧ carga-cpu < 0,2) project(nome) servidor + nucleoCPU>11 + carga-cpu<0,2 Nome e IP dos Servidores que executam processos do cliente John: Π(nome, enderecoIP)(servidor ∧ λ∗ John) project(nome,enderecoIP) servidor + link_(John) A busca pode não ser exata, portanto precisa de interpretação... Conceito de busca na rede/web é diferente da busca tradicional (SQL) 19/10/2015

16 Processamento 1 Início 2 Expansão 3 Contração 4 Resultadonó raiz recebe solicitação 2 Expansão mensagem de exploração 3 Contração Mensagem de eco agregação Mensagens de exploração contém as solicitações que são os critérios de busca expressos na linguagem de consulta Problemas: processamento caro… apresentam tendências de trabalhos futuros para melhorar este ponto. 4 Resultado 19/10/2015

17 Processamento Cada nó: Cada nó: repassa mensagem de exploraçãocompara a solicitação com a base de dados (match) classifica e pontua (rank score) agrega resultados parciais retorna resultado Compara (matching) – Classifica (ranking) – Pontua (score) resultados agrupados por um objeto agregador 19/10/2015

18 Para processar vínculos usa recursividadeObjeto agregador Objeto efetua processamento local e agrega resultados dos nós filhos (ou processa função de agregação – max, sum etc) Este processo não implementa a função vínculos… mas vínculo direto é feito com dois processamentos e vinculo (indireto) recursivamente… {A união objetos de D-A tal que exista a pertencente a A com vínculo entre a e o} Para processar vínculos usa recursividade q = processamento da consulta | fa = função de agregação 19/10/2015

19 Testes e Resultados Experimento com IaaS usando OpenStack24 servidores físicos – 24 cores ~64Gb cada 1 nó de busca por servidor + 1 estação de gerenciamento Nós rodando MongoDB para base local 4 tipos de objeto (servidor, VM, aplicação e cliente) objetos por servidor (1-1.5Mb de disco) Polling gerou carga de 2% de CPU Buscas em torno de 20ms (exceto links_) 2 a 5 termos por busca / carga de 25 a 700 por segundo IaaS – infraestrutura como serviço | OpenStack – plataforma aberta de virtualização | MongoDB – base aberta orientada a objetos Autores entendem que a performance está ruim se pretendem escalabilidade 19/10/2015

20 Versus modelo relacionalSerá tão expressivo quanto relacional se: Restringir busca aos objetos de mesmo tipo Aplicar somente a forma a op v Select: termo + operação + consulta Semijunção: A1∧(λA2) = R1 ⋉ R2 Genérico: Diferentes atributos p/ mesmo tipo de objeto Apenas um atributo chave (nome do objeto) Permite buscar por atributos Autores argumentam que a linguagem que propõe possibilita muitos outros tipos de busca que o relacional (SQL) não permite (mantendo todos os que o relacional suporta) Isso é a conclusão? Foi colocado no meio do artigo, logo após a seção que descreve a linguagem proposta... 19/10/2015

21 Próximos passos Classificação e ranqueamento EscalabilidadeAtualidade e Localização Escalabilidade Def. domínio + redução do espaço de procura Reduzir espaço das buscas com vínculos Bases de dados locais Privacidade e segurança - multidomínio Listar as questões pendentes e oportunidades futuras 19/10/2015

22 Análise Crítica - PropostaVantagens Há demanda para solução (relevante) Suporta diferentes atributos nos objetos Permite uso de vínculos e grafos de rede Simples Desvantagens Processamento caro (no caso de vínculos) Consultas e resultados necessitam interpretação Muitas questões pendentes 19/10/2015

23 Análise Crítica - ArtigoPontos positivos Diagramas e figuras Contextualização Sequência de ideias Pontos negativos Cenário de testes limitado Trabalhos relacionados Título e conclusão Conclusão – o problema foi resolvido? (fecharam sem conclusão) O título não é o foco do que foi apresentado no artigo 19/10/2015

24 Obrigado pela atenção! Contato: Rafael Araújo da Silva 19/10/2015

25 Anexo I – Outros modelosGDMO – Cellsoft (2012) Guidelines for Definition of Managed Objects CIM – DMTF (2012) Common Information Model YANG – IETF RFC 6020 (2012) A Data Modeling Language for the Network Configuration Protocol SMIv2 – IETF RFC 2578 (1999) Structure of Management Information Version 2 19/10/2015

26 Anexo II - Autores Alexander Clemm Rolf Stadler Misbah UddinArquiteto Sênior da Cisco Ph.D. em Computação pela Universidade de Munique Mestre em Computação pela Universidade de Stanford Rolf Stadler Professor no Instituto Real de Tecnologia da Suécia Ph. D. em Computação pela Universidade de Zurique Mestre em Matemática pela Universidade de Columbia Misbah Uddin Doutorando no Instituto Real de Tecnologia da Suécia 19/10/015

27 Anexo III – Ideias similaresNQL (2002) - David Pallmann: Descrita como primeira linguagem da era da engenharia de conteúdo Baseada em scripts Serve para agregar, analisar, interpretar e redistribuir informações via rede BiQL (2012) - Anton Dries Similar ao SQL mas para exploração de grafos Base de dados orientada para exploração de redes Que tal uma interface em linguagem natural? Outras propostas de linguagem: NQL (2002) - BiQL (2012) NLUI – Natural Language User Interfaces  Siri (ou outro assistente pessoal) Métodos atuais de gerenciamento não atendem todas as demandas de informações que administradores de rede necessitam Métodos de acesso  SNMP, CLI, WMI, NetConf… Algumas das sugestões tem alto custo computacional (link) 19/10/2015

28 Anexo IV – Outras referênciasBusca na Web – Brin et al. (1998) The anatomy of a large-scale hypertextual web search engine Pontuação por Relevância – Jain et al. (2011) Indexing the World Wide Web: The Journey So Far Sistema Weaver SQL – Stadler et al. (2005) Realtime views of network traffic using decentralized management Sistema NetQuery – Schneider et al. (2010) A knowledge plane for reasoning about network properties Modelo Relacional – C. J. Date (2003) Introduction to Database Systems 19/10/2015