Multi-protocol data classification using on-chip cam

Abstract

An apparatus is equipped with a content addressable memory (CAM) to store one or more key entries corresponding to a data class represented by the CAM. Each of the one or more key entries is associated with a key tag corresponding to one of one or more subclasses of the data class. The apparatus is further equipped with logic coupled to the CAM to extract a data key from a data stream, to compare all or part of the data key with the one or more key entries to determine if the data key is a member of the data class, and to classify the data key as belonging to one of the one or more subclasses of the data class if the data key is determined to be a member of data class.

1. An apparatus comprising:
 a content addressable memory (CAM) to store key entries corresponding to one or more classes of data represented by the CAM, each of said key entries being associated with one of a plurality of key tags, wherein each key tag corresponds to one of a plurality of subclasses of data; and  
 logic to extract a data key from a data stream, to compare at least a portion of the data key with said key entries to determine if the data key matches any of the key entries, and to output one or more key tags associated with matching ones of the key entries to form at least a portion of a categorization vector to facilitate classification of the data stream.  
 
     
     
       2. The apparatus of  claim 1 , further comprising a plurality of CAMs to store a plurality of key entries and associated key tags, wherein each of said plurality of CAMs represents a unique one of a plurality of classes of data. 
     
     
       3. The apparatus of  claim 2 , wherein said logic compares at least a portion of the data key with said plurality of key entries to determine if the data key and said plurality of key entries are equivalent. 
     
     
       4. The apparatus of  claim 2 , wherein said logic comprises logic to extract a plurality of data keys from a single packet of a data stream. 
     
     
       5. The apparatus of  claim 2 , wherein output from each of the plurality of CAMs is concatenated together to form a portion of the categorization vector. 
     
     
       6. The apparatus of  claim 5 , wherein if the data key does not match any of the key entries stored within a given one of the plurality of CAMs, a predetermined bit value is output to form a portion of the categorization vector dedicated to the given one of the plurality of CAMs to indicate such. 
     
     
       7. The apparatus of  claim 1 , wherein the one or more key tags are concatenated together to form at least the portion of the categorization vector. 
     
     
       8. The apparatus of  claim 1 , wherein each key tag within the categorization vector corresponds to a unique key entry. 
     
     
       9. A method comprising:
 extracting a data key from a data stream;  
 comparing at least a portion of the data key with one or more key entries stored within a first content addressable memory (CAM) representing one or more classes of data to determine if the data key matches any of the key entries, wherein each key entry is associated with one of a plurality of key tags each representing one of a corresponding first plurality of subclasses of data;  
 outputting one or more of the plurality of key tags associated with matching ones of the key entries to form at least a first portion of a categorization vector; and  
 classifying the data stream based at least in part upon the categorization vector.  
 
     
     
       10. The method of  claim 9 , wherein extracting the data key comprises extracting at least one bit of data from a data packet of the data stream. 
     
     
       11. The method of  claim 9 , further comprising:
 comparing at least a portion of the data key with one or more key entries stored within a second CAM representing a second class of data, wherein each key entry stored within the second CAM is associated with one of a second plurality of key tags each representing one of a corresponding second plurality of subclasses of data.  
 
     
     
       12. The method of  claim 11 , wherein if the data key matches one or more key entries stored within the first or second CAMs, a corresponding one or more of said first or second plurality of key tags are output to further form at least part of the categorization vector. 
     
     
       13. The method of  claim 9 , wherein each of said plurality of key tags comprises a binary representation of 2*N subclasses of data. 
     
     
       14. An integrated circuit comprising:
 a plurality of content addressable memories (CAMs), each associated with one of a plurality of data classes and equipped to store one or more of a plurality of key entries and one or more of a plurality of key tags associated with said plurality of key entries, each of said plurality of key entries representing one of said plurality of data classes and each of said key tags representing one of a plurality of data subclasses; and  
 logic coupled to the plurality of CAMs to extract a data key from a data stream, to compare at least a portion of the date key with said plurality of key entries to determine if the data key matches any of said plurality of key entries, and to output one or more key tags associated with matching ones of the key entries to format least a portion of a categorization vector to facilitate classification of the data stream.  
 
     
     
       15. The integrated circuit of  claim 14 , wherein each of said plurality of CAMs represents a unique one of said plurality of data classes. 
     
     
       16. The integrated circuit of  claim 14 , wherein said logic comprises logic to extract a plurality of data keys from a single packet of a data stream. 
     
     
       17. The integrated circuit of  claim 16 , wherein at least one of said plurality of data keys is classified as belonging to a first data subclass of a first of said plurality of CAMs, and a second data subclass of a second of said plurality of CAMs. 
     
     
       18. The integrated circuit of  claim 14 , further comprising at least one programmable nybble-wide mask coupled to the plurality of CAMs to mask at least part of said data key. 
     
     
       19. An apparatus comprising:
 a first CAM to store a first plurality of key entries and an associated, first plurality of key tags;  
 a second CAM to store a second plurality of key entries and an associated second plurality of key tags;  
 logic to extract a data key from a data stream, to compare at least a portion of the data key against the first and second pluralities of key entries in the first and second CAMs to determine if the data key matches any of the first and second pluralities of key entries,  
 logic to output one or more of the first plurality of key tags from the first CAM, to form a first portion of a categorization vector designed to facilitate classification of the data stream, upon the data key matching a corresponding one or more of the first plurality of key entries; and  
 logic to output one or more of the second plurality of key tags from the second CAM to form a second portion of the categorization vector upon the data key matching a corresponding one or more of the second plurality of key entries.  
 
     
     
       20. The apparatus of  claim 19 , wherein the categorization vector comprises a plurality of binary representations concatenated together. 
     
     
       21. The apparatus of  claim 20 , wherein each of the plurality of binary representations corresponds to a predetermined bit location representing one of the first and second CAMs. 
     
     
       22. An apparatus comprising:
   a content addressable memory  ( CAM )  configured to store key entries associated with one or more classes of data, wherein one or more of the key entries is associated with one of a plurality of key tags, and wherein one or more of the key tags is associated with one of a plurality of subclasses of data; and        logic configured to determine whether a data key extracted from a data stream matches any one of the key entries, and to output one or more key tags associated with matching ones of the key entries to form at least a portion of a categorization vector to facilitate classification of the data stream.     
     
     
       23. The apparatus of  claim 22 , further comprising a plurality of CAMs configured to store a plurality of key entries and associated key tags, wherein at least one of the plurality of CAMs represents a unique one of a plurality of the classes of data. 
     
     
       24. The apparatus of  claim 23 , wherein the logic is further configured to determine whether the data key and the plurality of key entries are equivalent based, at least in part, on a comparison of at least a portion of the data key with the plurality of key entries. 
     
     
       25. The apparatus of  claim 23 , wherein the logic is further configured to extract a plurality of data keys from a single packet of the data stream. 
     
     
       26. The apparatus of  claim 23 , wherein the logic is further configured to concatenate outputs of the plurality of CAMs to form at least a portion of the categorization vector. 
     
     
       27. The apparatus of  claim 22 , wherein the logic is further configured to concatenate the one or more key tags to form the at least a portion of the categorization vector. 
     
     
       28. The apparatus of  claim 22 , wherein at least one key tag within the categorization vector is associated with a unique key entry. 
     
     
       29. A method comprising:
   determining whether a data key extracted from a data stream matches any one of one or more key entries stored within a first content addressable memory  ( CAM )  representing a first class of data, wherein at least one of the one or more key entries is associated with one of a plurality of key tags, and wherein one or more of the key tags represents one of an associated first plurality of subclasses of data;        forming at least a first portion of a categorization vector based, at least in part, on one or more of the plurality of key tags associated with matching ones of the key entries; and        classifying the data stream based, at least in part, upon the categorization vector.     
     
     
       30. The method of  claim 29 , and further comprising extracting the data key from a data packet of the data stream as at least one bit of data. 
     
     
       31. The method of  claim 29 , wherein the determining whether the extracted data key matches any one of the one or more entries further comprises comparing at least a portion of the extracted data key with one or more key entries stored within a second CAM representing a second class of data, and wherein one or more key entries stored within the second CAM is associated with one of a second plurality of key tags representing one of an associated second plurality of subclasses of data. 
     
     
       32. The method of  claim 31 , and further comprising:
   forming at least a portion of the categorization vector based, at least in part, on one or more of the first plurality of key tags in response to the data key matching one or more key entries stored within the first CAM; and        forming at least a portion of the categorization vector based, at least in part, on one or more of the second plurality of key tags in response to the data key matching one or more of the key entries stored within the second CAM.     
     
     
       33. The method of  claim 29 , wherein one or more of the plurality of key tags comprise a binary representation of  2  N subclasses of data. 
     
     
       34. An integrated circuit comprising:
   a plurality of content addressable memories  ( CAMs ) , wherein one or more of the CAMs is associated with one of a plurality of data classes and is configured to store one or more of a plurality of key entries and one or more of a plurality of key tags associated with the plurality of key entries, and wherein one or more of the plurality of key entries represents one of the plurality of data classes and one or more of the key tags represents one of a plurality of data subclasses; and        logic configured to determine whether a data key extracted from a data stream matches any one of the plurality of key entries, and to format at least a portion of a categorization vector comprising one or more key tags associated with matching ones of the key entries, the categorization vector facilitating classification of the data stream.     
     
     
       35. The integrated circuit of  claim 34 , wherein one or more of the plurality of CAMs represents a unique one of the plurality of data classes. 
     
     
       36. The integrated circuit of  claim 34 , wherein the logic is further configured to extract a plurality of data keys from a single packet of a data stream. 
     
     
       37. The integrated circuit of  claim 36 , wherein at least a first data key of the plurality of data keys is associated with a first data subclass associated with a first CAM of the plurality of CAMs, and a second data key of the plurality of data keys is associated with a second data subclass associated with a second CAM of the plurality of CAMs. 
     
     
       38. The integrated circuit of  claim 34 , further comprising at least one programmable nybble- wide mask coupled to the plurality of CAMs and configured to mask at least a portion of the data key.   
     
     
       39. An apparatus comprising:
   a first CAM configured to store a first plurality of key entries and an associated first plurality of key tags;        a second CAM configured to store a second plurality of key entries and an associated second plurality of key tags;        logic configured to determine whether at least a portion of a data key extracted from a data stream matches any one of the first and second pluralities of key entries;        logic configured to form a first portion of a categorization vector facilitating classification of the data stream, the data stream comprising one or more of the first plurality of key tags from the first CAM in response to a match of the portion of the extracted data key with one or more of the first plurality of key entries; and        logic configured to form a second portion of the categorization vector comprising one or more of the second plurality of key tags from the second CAM in response to a match of the portion of the extracted data key with one or more of the second plurality of key entries.     
     
     
       40. The apparatus of  claim 39 , wherein the categorization vector comprises a plurality of concatenated binary representations. 
     
     
       41. The apparatus of  claim 40 , wherein one or more of the plurality of binary representations is associated with a predetermined bit location representing one of the first and second CAMs. 
     
     
       42. A method comprising:
   determining whether a data key extracted from a data packet matches any one of one or more key entries stored within a first content addressable memory  ( CAM )  representing a first class of data, wherein at least one of the one or more key entries is associated with one of a plurality of key tags, and wherein one or more of the key tags represents one of an associated first plurality of subclasses of data;        forming at least a first portion of a categorization vector based, at least in part, on one or more of the plurality of key tags associated with matching ones of the key entries; and        classifying the data packet based, at least in part, upon the categorization vector.     
     
     
       43. The method of  claim 42 , wherein the at least one of the one or more key entries comprises a VLAN tag.