A prefix-based approach for managing hybrid specifications in complex packet filtering

摘要

The coexistence of range-based and prefix-based fields within the filtering policy is one of the most important causes that make the packet filtering problem difficult to solve and the proposed hybrid solutions hard to implement. In general, a packet filter must support rule sets involving any conditions and it must be able to scale the number of rules, the number of fields, and the field sizes that it supports in order to avoid being outdated by future Internet developments. Since the prefix-based solutions are the most efficient in practice, we try to efficiently incorporate ranges in such data structures using the new concept of signed prefixes that helps to guarantee homogeneity when matching on multiple packet header fields of distinct types. The proposed two-staged prefix-based model is able to achieve good performance in a practical environment and it scales well as the filtering list size increases and contains a large variety of range specifications. The proposed packet filtering model gives a worst case time complexity of O((log_2(w))~2) and a worst case space complexity of O(Nwlog_2 (w)) in the case of performing a binary search on each stage with N the size of the filtering table and w the size of packet header field to be inspected.