# US 8,571,023 B2 · Methods and Apparatus Related to Packet Classification Based on Range Values > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,571,023 B2 - Document ID: US8571023B2 - Status: Granted - Kind: B2 - Application number: 12/794,175 - Filed: 2010-06-04 - Published: 2011-06-09 - Granted: 2013-10-29 - Earliest claimed: 2008-09-30 - Assignees: Juniper Networks, Inc. - Applicants: Ramesh Panwar; Deepak Goel; Srinivasan Jagannadhan - Inventors: Ramesh Panwar; Deepak Goel; Srinivasan Jagannadhan - Web page: https://patentgrep.com/patent/US8571023B2 ## CPC - H04L 49/1515: Non-blocking multistage, e.g. Clos - H04L 45/7459: using Bloom filters - H04L 49/3009: {Header conversion, routing tables or routing tags} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract In one embodiment, an apparatus comprises a range selection module, a first stage of bloom filters, a second stage of bloom filters and a hashing module. The range selection module is configured to define a set of hash key vectors based on a set of range values associated with at least a portion of an address value from a data packet received at a multi-stage switch. The first stage of bloom filters and the second stage of bloom filters are collectively configured to determine that at least a portion of a hash key vector from the set of hash key vectors has a probability of being included in a hash table. The hashing module is configured to produce a hash value based on the hash key vector such that a first policy vector is selected based on the hash value and the first policy vector is decompressed to produce a second policy vector associated with the data packet. ## Claims ### Claim 1 An apparatus, comprising: a range selection module configured to define a set of hash key vectors based on a set of range values associated with at least a portion of an address value from a data packet received at a multi-stage switch; a first stage of bloom filters and a second stage of bloom filters collectively configured to determine that at least a portion of a hash key vector from the set of hash key vectors has a probability of being included in a hash table; and a hashing module configured to produce a hash value based on the hash key vector such that a first policy vector is selected based on the hash value and the first policy vector is decompressed to produce a second policy vector associated with the data packet. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein the second policy vector is configured to trigger routing of the data packet through the multi-stage switch. ### Claim 3 (depends on 1) The apparatus of claim 1, further comprising: a tag filter module configured to match a portion of the hash key vector to a bit vector stored in a tag table, the hashing module configured to define the hash value in response to the portion of the hash key vector being matched to the bit vector stored in the tag table. ### Claim 4 (depends on 1) The apparatus of claim 1, wherein the portion of the address value is a first portion of the address value, the hash key vector includes a plurality of binary bits having a length corresponding to a range value from the set of range values and a plurality of binary bits corresponding to a second portion of the address value from the data packet, the second portion of the address value being associated with the range value from the set of range values. ### Claim 5 (depends on 1) The apparatus of claim 1, wherein the range selection module, the first stage of bloom filters, the second stage of bloom filters, and the hashing module are implemented in hardware and integrated on a single semiconductor chip. ### Claim 6 (depends on 1) The apparatus of claim 1, further comprising: a memory configured to store a range table including the set of range values, the range selection module configured to retrieve the set of range values from the range table based on the portion of the address value from the data packet. ### Claim 7 An apparatus, comprising: a plurality of bloom filters collectively configured to receive a set of hash key vectors associated with a portion of an address value from a data packet, the plurality of bloom filters collectively configured to determine that at least a portion of a hash key vector from the set of hash key vectors has a probability of being included in a hash table; and a hashing module configured to produce a hash value based on the hash key vector, the hashing module configured to select a policy vector from the hash table based on the hash value and based on the portion of the hash key vector from the plurality of the bloom filters. ### Claim 8 (depends on 7) The apparatus of claim 7, further comprising: a range selection module configured to receive the data packet, the range selection module configured to define the set of hash key vectors based on a set of range values associated with the portion of the address value. ### Claim 9 (depends on 7) The apparatus of claim 7, wherein the plurality of bloom filters are implemented in hardware. ### Claim 10 (depends on 7) The apparatus of claim 7, wherein the hashing module is configured to perform at least two hash functions via hardware computational units. ### Claim 11 (depends on 7) The apparatus of claim 7, wherein the plurality of bloom filters and the hashing module are each implemented as hardware units. ### Claim 12 (depends on 7) The apparatus of claim 7, wherein the plurality of bloom filters and the hashing module are implemented in hardware and integrated on a single semiconductor chip. ### Claim 13 (depends on 7) The apparatus of claim 7, further comprising: a range selection module configured to receive the data packet, the range selection module configured to define the set of hash key vectors based on a set of range values associated with the portion of the address value; and a memory configured to store a range table including the set of range values, the range selection module configured to retrieve the set of range values from the range table based on the portion of the address value from the data packet. ### Claim 14 (depends on 7) The apparatus of claim 7, further comprising: a first memory configured to store a tag table including a plurality of bit vectors, each bit vector from the plurality of bit vectors corresponding to at least a portion of an entry within the hash table, the filter module, the hashing module and the tag table are implemented in hardware and integrated on a semiconductor chip, the hash table is included in a second memory separate from the semiconductor chip. ### Claim 15 An apparatus, comprising: a switch fabric of a multi-stage switch of a data center; a policy vector module operatively coupled to the switch fabric, the policy vector module configured to receive a data packet and configured to define a set of key vectors based on a set of range values associated with a portion of an address value from the data packet, the policy vector module configured to select a remainder key vector from the set of key vectors, the policy vector module configured to select a policy vector from a policy vector database based on the remainder key vector; and a packet processing module operatively coupled to the policy vector module and configured to receive the policy vector from the policy vector module, the packet processing module configured to trigger routing of the data packet via the switch fabric when at least one bit value of the policy vector represents that a policy condition associated with a routing policy has been satisfied. ### Claim 16 (depends on 15) The apparatus of claim 15, wherein the policy vector module includes a range selection module configured to define the set of key vectors based on the set of range values associated with at least the portion of the address value from the data packet received at the multi-stage switch. ### Claim 17 (depends on 15) The apparatus of claim 15, wherein the policy vector module includes a first stage of bloom filters and a second stage of bloom filters collectively configured to determine that the reminder key vector from the set of key vectors has a probability of being included in a hash table. ### Claim 18 (depends on 15) The apparatus of claim 15, wherein the policy vector module includes a hashing module configured to produce a hash value such that the policy vector is selected based on the hash value. ### Claim 19 (depends on 15) The apparatus of claim 15, further comprising: a memory configured to store a range table including the set of range values, the policy vector module configured to retrieve the set of range values from the range table based on the portion of the address value from the data packet. ### Claim 20 (depends on 15) The apparatus of claim 15, wherein the policy vector module is implemented in hardware on a single semiconductor chip.