|
Abstract : |
Routers must perform packet classification at high speeds to efficiently implement functions such as firewalls and QoS routing. Packet classification requires matching each packet against a database of filters (or rules), and forwarding the packet according to the highest priority filter. Existing filter schemes with fast lookup time do not scale to large filter databases. Other more scalable schemes work for 2-dimensional filters, but their lookup times degrade quickly with each additional dimension. While there exist good hardware solutions, our new schemes are geared towards software implementation. We introduce a generic packet classification algorithm, called Tuple Space Search (TSS). Because real databases typically use only a small number of distinct field lengths, by mapping filters to tuples even a simple linear search of the tuple space can provide significant speedup over naive linear search over the filters. Each tuple is maintained as a hash table that can be searched in one memory access. Building on this idea, we introduce several techniques for further refining the search of the tuple space, and demonstrate their effectiveness on some industrial firewall databases. For example, a real database of 278 filters had a tuple space of 41 which our algorithm prunes to 11 tuples. Our experiments show (using a random two-dimensional filter generation model) that as we increase the filter database size from 1K to 100K, the size of the tuple space grows from 53 to only 186, and the pruned tuples only grow from 1 to 4. Our Pruned Tuple Space search is also the only scheme known to us that allows fast updates and fast search times., |
