Patent application number | Description | Published |
20100023727 | IP ADDRESS LOOKUP METHOD AND APPARATUS BY USING BLOOM FILTER AND MULTI-HASHING ARCHITECTURE - The present invention relates to an IF address lookup apparatus using a Bloom filter and a multi-hashing architecture that includes a buffering means that outputs a prefix of an inputted address having the number of bits reduced by one bit whenever a control signal is received at the time of outputting the prefix of the inputted address; a hashing hardware that generates a plurality of hashing indexes by hashing the prefix (hereinafter, referred to as “output prefix”) outputted from the buffering means; a Bloom filter that determines whether or not the output prefix is an entry of the hash table by using the plurality of hashing indexes; and a processor that includes the hash table and an overflow table and outputs a prefix that matches the output prefix by searching entries of locations of the hash table indicated by the plurality of hashing indexes and entries stored in the overflow table when a Bloom filter's determination result is positive and outputs the control signal to the buffering means when the matched prefix is not provided or the Bloom filter's determination result is negative. | 01-28-2010 |
20100284405 | METHOD AND APPARATUS FOR SEARCHING IP ADDRESS - The present disclosure provides IP address lookup method and apparatus. In one embodiment of the disclosure, an IP address lookup apparatus stores node information generated for a binary search-on-levels architecture in a universal multi-hashing table prior to searching with an advance filtering by a universal Bloom filter minimizing the number of accesses to the universal multi-hashing table before executing the IP address lookup. | 11-11-2010 |
20110219010 | METHOD AND APPARATUS FOR PACKET CLASSIFICATION USING BLOOM FILTER - The present disclosure provides an apparatus and method for packet classification using a Bloom filter and includes determining a matching length of how long each field value of one or more fields in an input packet coincides with a field value of the corresponding field stored in a rule set by performing a field-by-field search on the fields in the input packet, and generating a tuple list made up of a combination of one or more of the matching length for the respective fields; selecting particular tuples existing in the rule set from the tuple list; filtering each of the selected tuples by using the Bloom filter; and searching for a best matching rule as a search pool exclusively within the tuples with the positive result of the filtering. According to the present disclosure, the object tuples to search can be substantially relieved to improve the searching performance. | 09-08-2011 |