# US 10,313,240 B2 · Technologies for efficient network flow classification with vector bloom filters > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,313,240 B2 - Document ID: US10313240B2 - Status: Granted - Kind: B2 - Application number: 15/632,592 - Filed: 2017-06-26 - Published: 2018-12-27 - Granted: 2019-06-04 - Earliest claimed: 2017-06-26 - Assignees: Intel Corporation - Applicants: Intel Corporation - Inventors: Sameh Gobriel; Wei Shen; Tsung-Yuan C. Tai; Ren Wang - Web page: https://patentgrep.com/patent/US10313240B2 ## CPC - H04L 45/74: Address processing for routing - H04L 45/7459: using Bloom filters - H04L 45/74591: {using content-addressable memories [CAM]} - H04L 61/5046: Resolving address allocation conflicts; Testing of addresses (testing when self-assigning an address H04L61/5092) - H04L 45/021: Ensuring consistency of routing table updates, e.g. by using epoch numbers - H04L 45/7453: using hashing - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Technologies for efficient network flow classification include a computing device that receives a network packet that includes a header. The computing device generates a vector Bloom filter (VBF) key as a function of the header and searches multiple VBFs for a VBF that matches the VBF key. Each VBF is associated with a flow sub-table that includes one or more flow rules. Each flow sub-table is associated with a mask length. If a matching VBF is found, the computing device searches the corresponding flow sub-table for a flow rule that matches a masked header of the network packet. If no matching VBF is found or if no matching flow rule is found, the computing device searches all of the flow sub-tables for a flow rule that matches the header. The computing device applies a flow action of a matching flow rule. Other embodiments are described and claimed. ## Claims ### Claim 1 A computing device for network packet routing, the computing device comprising: one or more processors; a memory having a plurality of instructions stored thereon that, when executed by the one or more processors, causes the computing device to establish: an input stage to receive a network packet that includes a header; a sub-table lookup stage to (i) generate a vector Bloom filter key as a function of the header of the network packet, and (ii) search a plurality of vector Bloom filters for a first vector Bloom filter that matches the vector Bloom filter key, wherein each vector Bloom filter is associated with a flow sub-table, wherein each flow sub-table comprises one or more flow rules, and wherein each flow sub-table is associated with a mask; a rule lookup stage to search a flow sub-table that is associated with the first vector Bloom filter for a first flow rule that matches the header of the network packet in response to a search of the plurality of vector Bloom filters for the first vector Bloom filter comprises to: (i) mask the header of the network packet with the mask associated with the flow sub-table to generate a masked header and (2) search the flow sub-table for a flow rule that matches the masked header; and an action stage to apply a flow action of the first flow rule in response to a search of the flow sub-table. ### Claim 2 (depends on 1) The computing device of claim 1, wherein: to search the plurality of vector Bloom filters comprises to determine whether the vector Bloom filter key matches any vector Bloom filter of the plurality of vector Bloom filters; and to search the flow sub-table comprises to determine whether the header of the network packet matches any flow rule of the flow sub-table that is associated with the vector Bloom filter. ### Claim 3 (depends on 2) The computing device of claim 2, further comprising a fallback search stage to: search the plurality of flow sub-tables for the first flow rule that matches the header of the network packet in response to a determination that the vector Bloom filter key does not match any vector Bloom filter or in response to a determination that the header of the network packet does not match any flow rule of the flow sub-table that is associated with the vector Bloom filter, wherein the first flow rule is included in a first flow sub-table; wherein the sub-table lookup stage is further to insert the vector Bloom filter key into a vector Bloom filter that is associated with the first flow sub-table in response to a search of the plurality of flow sub-tables for the first flow rule. ### Claim 4 (depends on 3) The computing device of claim 3, wherein to apply the flow action of the first flow rule further comprises to apply the flow action of the first flow rule in response to the search of the plurality of flow sub-tables for the first flow rule. ### Claim 5 (depends on 3) The computing device of claim 3, wherein to search the plurality of flow sub-tables comprises to: mask the header of the network packet with the mask associated with a flow sub-table to generate a masked header; generate a Bloom filter key as a function of the masked header; and determine whether the Bloom filter key matches a Bloom filter associated with the flow sub-table. ### Claim 6 (depends on 3) The computing device of claim 3, wherein to search the plurality of flow sub-tables comprises to sequentially search each flow sub-table of the plurality of flow sub-tables in an order that is determined based on a length of the mask associated with each flow sub-table. ### Claim 7 (depends on 3) The computing device of claim 3, wherein to search the plurality of flow sub-tables for the first flow rule that matches the header of the network packet comprises to determine whether the header of the network packet matches any flow rule of the plurality of flow sub-tables. ### Claim 8 (depends on 7) The computing device of claim 7, wherein the action stage is further to apply a default flow action in response to a determination that the header of the network packet does not match any flow rule of the plurality of flow sub-tables. ### Claim 9 (depends on 1) The computing device of claim 1, wherein to generate the vector Bloom filter key comprises to: hash the header of the network packet with a plurality of hash functions to generate a plurality of hash values; and generate a plurality of bit positions as a function of the plurality of hash values, wherein each bit position corresponds to a hash value. ### Claim 10 (depends on 1) The computing device of claim 1, wherein to search the flow sub-table for the flow rule that matches the masked header comprises to index the flow sub-table with the masked header. ### Claim 11 (depends on 1) The computing device of claim 1, wherein the network packet comprises a data link layer packet. ### Claim 12 (depends on 1) The computing device of claim 1, wherein the network packet comprises an Ethernet frame. ### Claim 13 A method for network packet routing, the method comprising: receiving, by a computing device, a network packet that includes a header; generating, by the computing device, a vector Bloom filter key as a function of the header of the network packet; searching, by the computing device, a plurality of vector Bloom filters for a first vector Bloom filter that matches the vector Bloom filter key comprises (i) masking the header of the network packet with the mask associated with the flow sub-table to generate a masked header and (ii) searching the flow sub-table for a flow rule that matches the masked header, wherein each vector Bloom filter is associated with a flow sub-table, wherein each flow sub-table comprises one or more flow rules, and wherein each flow sub-table is associated with a mask; searching, by the computing device, a flow sub-table that is associated with the first vector Bloom filter for a first flow rule that matches the header of the network packet in response to searching the plurality of vector Bloom filters for the first vector Bloom filter; and applying, by the computing device, a flow action of the first flow rule in response to searching the flow sub-table. ### Claim 14 (depends on 13) The method of claim 13, wherein: searching the plurality of vector Bloom filters comprises determining whether the vector Bloom filter key matches any vector Bloom filter of the plurality of vector Bloom filters; and searching the flow sub-table comprises determining whether the header of the network packet matches any flow rule of the flow sub-table that is associated with the vector Bloom filter. ### Claim 15 (depends on 14) The method of claim 14, further comprising: searching, by the computing device, the plurality of flow sub-tables for the first flow rule that matches the header of the network packet in response to determining that the vector Bloom filter key does not match any vector Bloom filter or in response to determining that the header of the network packet does not match any flow rule of the flow sub-table that is associated with the vector Bloom filter, wherein the first flow rule is included in a first flow sub-table; and inserting, by the computing device, the vector Bloom filter key into a vector Bloom filter that is associated with the first flow sub-table in response to searching the plurality of flow sub-tables for the first flow rule. ### Claim 16 (depends on 15) The method of claim 15, wherein searching the plurality of flow sub-tables comprises: masking the header of the network packet with the mask associated with a flow sub-table to generate a masked header; generating a Bloom filter key as a function of the masked header; and determining whether the Bloom filter key matches a Bloom filter associated with the flow sub-table. ### Claim 17 (depends on 13) The method of claim 13, wherein generating the vector Bloom filter key comprises: hashing the header of the network packet with a plurality of hash functions to generate a plurality of hash values; and generating a plurality of bit positions as a function of the plurality of hash values, wherein each bit position corresponds to a hash value. ### Claim 18 One or more non-transitory, computer-readable storage media comprising a plurality of instructions that in response to being executed cause a computing device to: receive a network packet that includes a header; generate a vector Bloom filter key as a function of the header of the network packet; search a plurality of vector Bloom filters for a first vector Bloom filter that matches the vector Bloom filter key comprises to: (i) mask the header of the network packet with the mask associated with the flow sub-table to generate a masked header and (ii) search the flow sub-table for a flow rule that matches the masked header, wherein each vector Bloom filter is associated with a flow sub-table, wherein each flow sub-table comprises one or more flow rules, and wherein each flow sub-table is associated with a mask; search a flow sub-table that is associated with the first vector Bloom filter for a first flow rule that matches the header of the network packet in response to searching the plurality of vector Bloom filters for the first vector Bloom filter; and apply a flow action of the first flow rule in response to searching the flow sub-table. ### Claim 19 (depends on 18) The one or more non-transitory, computer-readable storage media of claim 18, wherein: to search the plurality of vector Bloom filters comprises to determine whether the vector Bloom filter key matches any vector Bloom filter of the plurality of vector Bloom filters; and to search the flow sub-table comprises to determine whether the header of the network packet matches any flow rule of the flow sub-table that is associated with the vector Bloom filter. ### Claim 20 (depends on 19) The one or more non-transitory, computer-readable storage media of claim 19, further comprising a plurality of instructions that in response to being executed cause the computing device to: search the plurality of flow sub-tables for the first flow rule that matches the header of the network packet in response to determining that the vector Bloom filter key does not match any vector Bloom filter or in response to determining that the header of the network packet does not match any flow rule of the flow sub-table that is associated with the vector Bloom filter, wherein the first flow rule is included in a first flow sub-table; and insert the vector Bloom filter key into a vector Bloom filter that is associated with the first flow sub-table in response to searching the plurality of flow sub-tables for the first flow rule. ### Claim 21 (depends on 20) The one or more non-transitory, computer-readable storage media of claim 20, wherein to search the plurality of flow sub-tables comprises to: mask the header of the network packet with the mask associated with a flow sub-table to generate a masked header; generate a Bloom filter key as a function of the masked header; and determine whether the Bloom filter key matches a Bloom filter associated with the flow sub-table. ### Claim 22 (depends on 18) The one or more non-transitory, computer-readable storage media of claim 18, wherein to generate the vector Bloom filter key comprises to: hash the header of the network packet with a plurality of hash functions to generate a plurality of hash values; and generate a plurality of bit positions as a function of the plurality of hash values, wherein each bit position corresponds to a hash value.