Scalable Packet Classification

Speaker: Mary Bond, Ph.D. candidate, Department of Computer Science, UK

Packet classification, recognizing packets based on fields 
usually located in the IP or transport header, is necessary 
for supporting applications such as firewalls, intrusion
detection, and differentiated services.  The existing 
software solutions scale poorly either in time or space
as filter databases grow in size.  Hardware solutions,
such as TCAMs, scale poorly for large classifiers, that is,
classifiers consisting of many rules.  The authors of this
paper produce a scalable packet classification solution 
called Aggregated Bit Vector (ABV) using a previously 
developed Bit Vector (BV) scheme along with two new ideas: 
recursive aggregation of bit maps and filter rearrangement. 
The ABV solution takes logarithmic time for many databases,
and the authors provide simulations showing that ABV 
outperforms BV by an order of magnitude.