An mtidd based firewall using decision diagrams for packet filtering

Abstract. 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 filter-ing 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, effi-cient 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 ef-ficient for packet classification: it is able to handle more rules than the schemes it was compared to without causing a degradation in performance