Ewha University-Industry Collaboration Foundation

Cisco Technology, Inc.

Hyesook Lim

Monica Dattatraya Joshi

Yeo-jin Chung

Philip Ngai

David Michael Thornburg

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.

Method and apparatus for packet classification using bloom filter

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.

Method and apparatus for searching IP address

The present invention relates to an apparatus and method of looking up an IP address using a Bloom filter and a multi-hashing architecture. The present invention generates a plurality of hashing indexes by hashing inputted prefixes, determines whether a bit vector corresponding to the plurality of hashing indexes is positive or negative by using the Bloom filter, and outputs a prefix matching the inputted prefix by searching entries of locations indicated by the plurality of hashing indexes in the hash table when the bit vector is determined to be positive. The present invention further outputs the prefix that matches the inputted prefix by searching entries stored in the overflow table.

IP address lookup method and apparatus by using Bloom filter and multi-hashing architecture

The present invention relates to an IP address lookup method and hardware architecture. There is provided an IP address lookup method using a hashing table, the hashing table being constructed with an SRAM, the hashing table including main tables and sub-tables corresponding to prefix lengths of the IP address, entries being stored in the main tables and the sub-tables, the method comprising steps of: (a) performing a hashing process on an incoming IP address based on the prefix lengths of the IP address by using a hashing hardware unit, wherein the hashing hardware unit is constructed based on the prefix lengths of the IP address; (b) comparing prefixes, each of which is stored at a location in the main table pointed by a hashing value with the prefix of the IP address, searching entries of the main table having the prefix matched with the prefix of the IP address, and forwarding information on prefix-matched entries; (c) if there is no prefix-matched entry as a result of Step (b), searching entries of the sub-table having the prefix matched with the prefix of the IP address starting from a location in the sub-table pointed by a pointer of the main table, and forwarding information on prefix-matched entries; and (d) searching an entry having the longest-matched-prefix among the prefix-matched entries by using the information forwarded in Steps (b) and (c). Accordingly, it is possible to perform an IP address lookup process on all the prefixes in parallel by classifying prefixes based on the prefix lengths and constructing separate tables corresponding to the classified prefix lengths of the IP address. As a result, it is possible to easily apply a hashing process to the IP address and to reduce searching time.

IP address lookup using either a hashing table or multiple hash functions

Disclosed are, inter alia, methods, apparatus, data structures, computer-readable medium, mechanisms, and means for merging indications of matching items of multiple groups and possibly associated with skip conditions to identify winning entries of particular use for implementing access control lists. Indications are received typically from an associative memory bank indicating which locations were matched during a lookup operation. Each of the entries is typically associated with one or more hierarchical groups and a skip or no-skip condition. The matching entries are merged to identify one or more wining entries, these being matching entries not in a group that is skipped. A group is typically skipped if the highest priority matching entry of the particular group is associated with a skip condition. A priority encoder can be used to identify a single highest priority winning entry from the winning entries.

Merging indications of matching items of multiple groups and possibly associated with skip conditions to identify winning entries of particular use for implementing access control lists

Growing community of inventors

Seoul, South Korea

Hyesook Lim