Application of Bloom filters in Fast Packet Classification

摘要

Packet classification finds various applications in computer networks like QoS, Firewalls, multimedia communication, telecommunication, security, monitoring data traffic etc. To classify packets to a particular flow or the set of flows, Intermediate nodes which are present in the network must perform search for a rule which defines the flow of that particular packet which is chosen on the basis of different field present in the data packet. The rule set is predefined by the user, which is constructed on the basis of algorithmic and architectural methodology. The major constraint in this methodology is searching speed of particular rule. Since few decades researches are finding the best computational methodology for packet classification. But the current algorithms which are used in the packet classification highly rely on expensive and high power consuming devices like TCAM (Ternary content addressable memory). Therefore searching of fast and power efficient algorithms for packet classification is still the subject of interest for researchers. In this paper we have delivered a new direction to packet classification which includes algorithmic and architectural structure for packet classification. Our inception is from well-known Cross product algorithm which is very fast but introduce additional rules which increases memory requirement. We have shown how to enhance the crossproduct in a way which drastically reduces this addition of extra rules, without affecting the throughput of the algorithm, unnecessary memory access to the off chip memory are avoided by filtering them through on chip bloom filter. For packets that matches p rules in a rule set, our algorithm requires only P+4+ε memory access to find all the matching rules. Where ε «1 which is a constant that depends on small false positive rate of Bloom filter. Using two SRAM chips search speed of 38 million packets per second can be achieved. For the rule set size of few hundred to thousand rules an average rules set expansion factor is 1.2 to 1.4 and average memory consumption is 32 to 45 bytes.