Packet filter optimization techniques for high-speed network monitoring

摘要

Effective network monitoring is vital for a growing number of control and management applications typically found in present-day networks. The ever-increasing link speeds and the complexity of monitoring applications' needs have exposed severe limitations of existing monitoring techniques. A majority of the current monitoring tasks require only a small subset of all observed packets, which share some common properties such as identical header fields or similar patterns in their data. In order to capture only these useful packets, a large set of expressions needs to be evaluated. This evaluation should be done as efficiently as possible when monitoring multi-gigabit networks. To speed up this packet classification process, this article presents different packet filter optimization techniques. Complementary to existing approaches, we propose an adaptive optimization algorithm which dynamically reconfigures the filter expressions based on the currently observed traffic pattern. The performance of the algorithms is validated both analytically and by means of the implementation in a network monitoring framework. The various characteristics of the algorithms are investigated, including their performance in an operational network intrusion detection system.%Aujourd'hui, l'analyse du trafic des réseaux est essentielle pour la gestion de nombreuses applications. La croissance de la vitesse des réseaux et la complexité des besoins en analyse de trafic ont révélé des limitations sévères des méthodes et des outils existants. La plupart des tâches d'analyse n'exige qu'une partie de tous les paquets observés. Ces paquets partagent typiquement quelques propriétés comme des champs d'entêté identiques ou des séquences de caractères similaires dans leurs données. Pour capturer seulement ces paquets utiles, il faut évaluer une grande collection d'expressions. Cette évaluation doit être aussi performante que possible pour analyser des réseaux multi-gigabit. Cet article présente plusieurs techniques d'optimisation pour accélérer la procédure de classification des paquets. En complément des approches existantes, nous proposons un algorithme d'optimisation adaptif qui réorganise dynamiquement les expressions de filtrage à partir de l'observation du trafic. La performance des algorithmes est validée analytiquement et par une implémentation dans un système de surveillance du réseau. Les caractéristiques des algorithmes sont évaluées, y compris leur performance dans une application de détection d'intrusion opérationnelle.