| Sonstiges: |
- Nachgewiesen in: USPTO Patent Grants
- Sprachen: English
- Patent Number: 7,516,126
- Publication Date: April 07, 2009
- Appl. No: 10/611770
- Application Filed: June 30, 2003
- Assignees: Intel Corporation (Santa Clara, CA, US)
- Claim: 1. A computer-implemented method utilizing a processor comprising: grouping single fields of a multiple-field source in a computer memory into a plurality of multiple-field keys (MFKs) of a search target, each MFK of the search target having single fields that correspond to single fields in one of a plurality of multiple-field vectors (MFVs) of entries in a data structure; utilizing the processor to generate a set of queries based, at least in part, on the MFKs, wherein each query includes one or more of the MFKs and wherein each query has a different MFK as a lead MFK; using a query to determine whether the non-wildcard values in the MFVs of an entry match the non-wildcard values in corresponding MFKs of the search target; and: if an entry has non-wildcard values in the MFVs that match the corresponding non-wildcard values in the MFKs, then performing an operation associated with the matching entry; or if no entry has non-wildcard values in the MFVs that match the corresponding non-wildcard values in the MFKs, then using the queries to determine whether the entry has non-wildcard values in a MFV that match the non-wildcard values in a corresponding lead MFK, and whether remaining MFVs of the entry match corresponding remaining MFKs based on matching the non-wildcard values and wildcard values.
- Claim: 2. The method of claim 1 , wherein the entries of the data structure are stored in the computer memory such that the MFVs that have non-wildcard values are located at the end of the entry.
- Claim: 3. The method of claim 1 , further comprising arranging the entries of the data structure so that the MFVs that have non-wildcard values are placed at the end of the entry.
- Claim: 4. The method of claim 1 , wherein the non-wildcard values comprise a fixed value, a range of fixed values, or both.
- Claim: 5. The method of claim 1 , further comprising: locating the entry having non-wildcard values in the MFV that match the non-wildcard values in the corresponding lead MFK and having remaining MFVs that match corresponding remaining MFKs based on matching the non-wildcard values and wildcard values; and performing an operation associated with the located entry.
- Claim: 6. The method of claim 1 , wherein the multiple-field source comprises a data packet having single fields in its header.
- Claim: 7. The method of claim 6 , wherein the operation comprises one of the following: dropping the data packet, mirroring, metering, traffic shaping, rate limiting, accounting, statistics gathering, providing quality of service (QoS), redirecting to a central processing unit (CPU) for further processing, or sampling a subset of the packets to a CPU.
- Claim: 8. The method of claim 1 , wherein fewer than all MFVs in the entries include one single field.
- Claim: 9. The method of claim 1 , wherein the MFVs in the entries include two or more single fields.
- Claim: 10. An apparatus comprising: a processor to process data; a computer memory to store data, the computer memory including a data structure having a plurality of entries, wherein each entry has a group of multiple-field vectors (MFVs) that each include a number of single fields having all wildcard values or all non-wildcard values; and a search unit to group single fields of a multiple-field source into a plurality of multiple-field keys (MFKs) of a search target, each MFK having single fields that correspond to the single fields in a corresponding MFV of the entries in the data structure, generate a set of queries based, at least in part, on the MFKs, wherein each query includes one or more of the MFKs and has a different MFK as a lead MFK, use a query to determine whether the non-wildcard values in the MFVs of an entry match the non-wildcard values in corresponding MFKs of the search target; and: if an entry has non-wildcard values in the MFVs that match the corresponding non-wildcard values in the MFKs, then performing an operation associated with the matching entry; or if no entry has non-wildcard values in the MFVs that match the corresponding non-wildcard values in the MFKs, using the queries to determine whether the entry has non-wildcard values in a MFV that match the non-wildcard values in a corresponding lead MFK, and whether remaining MFVs of the entry match corresponding remaining MFKs based on matching the non-wildcard values and wildcard values.
- Claim: 11. The apparatus of claim 10 , wherein the entries of the data structure are stored in the computer memory such that the MFVs that have non-wildcard values are located at the end of the entry.
- Claim: 12. The apparatus of claim 10 , wherein the search unit arranges the entries of the data structure so that the MFVs that have non-wildcard values are placed at the end of the entry.
- Claim: 13. The apparatus of claim 10 , wherein the non-wildcard values comprise a fixed value, a range of fixed values, or both.
- Claim: 14. The apparatus of claim 10 , wherein the search unit locates the entry having non-wildcard values in the MFV that match the non-wildcard values in the corresponding lead MFK and having remaining MFVs that match corresponding remaining MFKs based on matching the non-wildcard values and wildcard values; and performs an operation associated with the located entry.
- Claim: 15. The apparatus of claim 10 , wherein the multiple-field source comprises a data packet having single fields in its header.
- Claim: 16. The apparatus of claim 15 , wherein the operation comprises one of the following: dropping the data packet, mirroring, metering, traffic shaping, rate limiting, accounting, statistics gathering, providing quality of service (QoS), redirecting to a central processing unit (CPU) for further processing, or sampling a subset of the packets to a CPU.
- Claim: 17. The apparatus of claim 10 , wherein fewer than all MFVs in the entries include one single field.
- Claim: 18. The apparatus of claim 10 , wherein the MFVs in the entries include two or more single fields.
- Claim: 19. An article of manufacture comprising: a computer-readable storage medium including thereon sequences of instructions that, when executed, cause a processor to: group single fields of a multiple-field source in a computer memory into a plurality of multiple-field keys (MFKs) of a search target, each MFK of the search target having single fields that correspond to single fields in one of a plurality of multiple-field vectors (MFVs) of entries in a data structure; generate a set of queries based, at least in part, on the MFKs, wherein each query includes one or more of the plurality of MFKs and wherein each query has a different MFK as a lead MFK; use a query to determine whether the non-wildcard values in the MFVs of an entry match the non-wildcard values in corresponding MFKs of the search target; and: if an entry has non-wildcard values in the MFVs that match the corresponding non-wildcard values in the MFKs, then performing an operation associated with the matching entry; or if no entry has non-wildcard values in the MFVs that match the corresponding non-wildcard values in the MFKs, then use the queries to determine whether the entry has non-wildcard values in a MFV that match the non-wildcard values in a corresponding lead MFK, and whether remaining MFVs of the entry match corresponding remaining MFKs based on matching the non-wildcard values and wildcard values.
- Claim: 20. The article of manufacture of claim 19 , wherein the entries of the data structure are stored in computer memory such that the MFVs that have non-wildcard values are located at the end of the entry.
- Claim: 21. The article of manufacture of claim 19 , wherein the computer-readable storage medium further comprises sequences of instructions that, when executed, cause the electronic system to arrange the entries of the data structure so that the MFVs that have non-wildcard values are placed at the end of the entry.
- Claim: 22. The article of manufacture of claim 19 , wherein the non-wildcard values comprise a fixed value, a range of fixed values, or both.
- Claim: 23. The article of manufacture of claim 19 , wherein the computer-readable storage medium further comprises sequences of instructions that, when executed, cause the processor to: locate the entry having non-wildcard values in the MFV that match the non-wildcard values in the corresponding lead MFK and having remaining MFVs that match corresponding remaining MFKs based on matching the non-wildcard values and wildcard values; and perform an operation associated with the located entry.
- Claim: 24. The article of manufacture of claim 19 , wherein the multiple-field source comprises a data packet having single fields in its header.
- Claim: 25. The article of manufacture of claim 24 , wherein the operation comprises one of the following: dropping the data packet, mirroring, metering, traffic shaping, rate limiting, accounting, statistics gathering, providing quality of service (QoS), redirecting to a central processing unit (CPU) for further processing, or sampling a subset of the packets to a CPU.
- Claim: 26. The article of manufacture of claim 19 , wherein fewer than all MFVs in the entries include one single field.
- Claim: 27. The article of manufacture of claim 24 , wherein the MFVs in the entries include two or more single fields.
- Claim: 28. A system, comprising: a processor; a network interface coupled with the processor; and an article of manufacture comprising a computer-readable storage medium including thereon sequences of instructions that, when executed, cause a processor to: group single fields of a multiple-field source into a plurality of multiple-field keys (MFKs) of a search target, each MFK of the search target having single fields that correspond to the single fields in one of a plurality of multiple-field vectors (MFVs) of entries in a data structure; generate a set of queries based, at least in part, on the MFKs, wherein each query includes one or more of the plurality of MFKs and has a different MFK as a lead MFK; use a query to determine whether the non-wildcard values in the MFVs of an entry match the non-wildcard values in corresponding MFKs of the search target; and: if an entry has non-wildcard values in the MFVs that match the corresponding non-wildcard values in the MFKs, then performing an operation associated with the matching entry; or if no entry has non-wildcard values in the MFVs that match the corresponding non-wildcard values in the MFKs, then use the queries to determine whether the entry has non-wildcard values in a MFV that match the non-wildcard values in a corresponding lead MFK, and whether remaining MFVs of the entry match corresponding remaining MFKs based on matching the non-wildcard values and wildcard values.
- Claim: 29. The system of claim 28 , wherein the non-wildcard values comprise a fixed value, a range of fixed values, or both.
- Claim: 30. The system of claim 28 , wherein the multiple-field source comprises a data packet having single fields in its header.
- Current U.S. Class: 707/4
- Patent References Cited: 6542896 April 2003 Gruenwald ; 6778530 August 2004 Greene ; 7054315 May 2006 Liao ; 2002/0188587 December 2002 McGreevy
- Other References: V. Srinivasan et al., “Fast and Scalable Layer Four Switching”, Proc. of Sigcom, 1998, www.acm.org. cited by other ; P. Gupta et al., “Packet Classification on Multiple Fields”, Proc. of Sigcom, 1998, www.acm.org. cited by other
- Assistant Examiner: Chan, Sai-Ming
- Primary Examiner: Rao, Seema S
- Attorney, Agent or Firm: Blakely, Sokoloff, Taylor & Zafman LLP
|
