An MTIDD Based Firewall

This paper explores the use of Multi-Terminal Interval Decision Diagrams (MTIDDs) as the central structure of a firewall packet filtering mechanism. This is done by first relating the packet filtering problem to predicate logic, then implementing a prototype which is used in an empirical evaluation. The main benefits of the MTIDD structure are that it provides access to Boolean algebra over filters, efficient classification time, and a compact representation. Results from the empirical evaluation shows that MTIDDs are scalable in terms of memory usage: a 50,000 rule filter requires only 3MB of memory, and efficient for packet classification: it is able to handle more rules than the schemes it was compared to without causing a degradation in performance.