Skip navigation
Please use this identifier to cite or link to this item: https://repositorio.ufpe.br/handle/123456789/2153
Title: Optimizing finite automata for DPI engines
Authors: Thyago Antonello, Rafael
Keywords: Reconhecimento de padrões; Otimização de sistemas DPI; Gerenciamento de Redes de Computadores
Issue Date: 31-Jan-2012
Publisher: Universidade Federal de Pernambuco
Citation: Thyago Antonello, Rafael; Kelner, Judith. Optimizing finite automata for DPI engines. 2012. Tese (Doutorado). Programa de Pós-Graduação em Ciência da Computação, Universidade Federal de Pernambuco, Recife, 2012.
Abstract: Nos últimos 40 anos a Internet se tornou um componente central para o comércio eletrônico internacional, comunicações, e para o desenvolvimento técnico e científico. Inicialmente as pesquisas relacionadas à Internet se focavam em melhoramentos na velocidade de transmissão de dados, capacidade e cobertura geográfica. Atualmente medição, modelagem e análise em redes de computadores, particularmente classificação de tráfego, tornaram-se um ponto crucial para manutenção do funcionamento da rede. Isto se deve principalmente ao crescimento exponencial das redes de computares em termos de tamanho, complexidade e diversidade de serviços. Neste contexto, sistemas de Deep Packet Inspection (DPI) se tornaram um elemento importante para medição de tráfego, já que classificação de aplicações baseada em portas caiu em desuso devido ao tunelamento de protocolos e uso indevido de portas padrões, por exemplo, softwares P2P que usam portas não bloqueadas para burlar regras de firewalls. Tradicionalmente, sistemas de DPI classificavam tráfego usando técnicas de string matching, i.e., as assinaturas de aplicações eram representadas por strings (cadeias de caracteres). Dessa maneira o procedimento de busca de padrões se dava através da inspeção da carga útil dos pacotes a procura dessas strings. String matching funciona bem para padrões simples, porém falha ao descrever padrões mais complexos, e.g., padrões com tamanho variável. Para solucionar este problema, sistemas de DPI têm substituído assinaturas representadas com strings por padrões descritos através de expressões regulares. Embora mais precisos, sistemas de DPI demandam maior poder computacional e geralmente não escalam bem conforme as velocidades dos enlaces aumentam. Este fato abriu espaço para várias pesquisas relacionadas à otimização de tais sistemas. Aproveitando este espaço, esta tese propõe um novo modelo de Deterministic Finite Automata (DFA) para casamento de padrões em sistemas DPI, o Ranged Compressed DFA (RCDFA). O RCDFA, junto com três otimizações propostas, atingem níveis de compressão de até 98% em bases de assinaturas bem conhecidas. Além do mais, o RCDFA codificado com um novo layout de memória (ALE) proposto neste trabalho é até 46 vezes mais rápido que os motores de DPI baseados em DFAs tradicionais
URI: https://repositorio.ufpe.br/handle/123456789/2153
Appears in Collections:Teses de Doutorado - Ciência da Computação

Files in This Item:
File Description SizeFormat 
arquivo9564_1.pdf6.58 MBAdobe PDFView/Open


This item is protected by original copyright



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.