Method and device for virtualization of multiple data sets on same associative memory

• US 7,281,085 B1
• Filed: 01/31/2005
• Issued: 10/09/2007
• Est. Priority Date: 01/31/2005
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Gupta, Pankaj, Garg, Ashish
• Primary Examiner(s): Verbrugge; Kevin
• Application Number:
  US11/047,793
• Time in Patent Office: 981 Days
• Field of Search: None
• US Class Current: 711/108
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

A system (200) can provide data aggregation with a single primary table (206) formed in a content addressable memory (CAM) section (202). Within a primary table (206) CAM entries can be part of a primary table, one or more aggregate tables, or both. In one arrangement, valid bits in each CAM entry can indicate which particular schemes a CAM entry belongs to (primary table, or any of the aggregate tables). Associated data for each table can be stored in a RAM section (204) and can be accessed according to an offset address generated according to a scheme value (i).

Claims

1. A method of providing multiple data sets for search on a single physical set of storage entries, comprising the steps of:

storing at least one data value of a first data set in one physical entry of a plurality of globally maskable content addressable memory (CAM) entries;

storing at least a second data value of a second data set, different form the first data set, in the one physical entry; and

distinguishing between the first and second data value by applying a predetermined global mask to the one globally maskable CAM entry.

2. The method of claim 1, further including:

storing associated data for each data value of the first data set in a first memory section starting at a first offset location; and

storing associated data for each data value of the second data set in a second memory section having different addresses than the first memory section, the second memory section starting at a second offset location.

3. The method of claim 1, wherein:

the first data set includes a network flow primary table and the second data set comprises at least one aggregation scheme;

the step of storing at least one data value of a first data set in the one physical entry includes storing network flow information in corresponding physical CAM entries to form network flow entries of the primary table;

the step of storing at least a second data value in the one physical entry comprises using an existing primary network flow entry as an aggregation entry that corresponds to the at least one aggregation scheme; and

storing associated data for each flow entry in a first associated data area, storing associated data for each aggregation scheme in a different associated data area.

4. The method of claim 3, wherein:

storing network flow information further includes

setting a primary table valid bit in the physical entry for each network flow entry.

5. The method of claim 4, wherein:

the primary table has primary table entries that each include “

k”

data fields, where k is an integer greater than 1;

each aggregation scheme includes a subset “

p”

of the k data fields, where p<

k; and

distinguishing between the first and second data value includes

searching while applying a scheme global mask value that masks all but the p data fields of the k data fields to search the aggregation scheme, and

searching without the scheme global mask value to search the primary table.

6. The method of claim 5, wherein:

the global maskable CAM entries store a primary table and a plurality of aggregation schemes; and

the step of storing network flow information includes

receiving new network flow information,

searching for an existing aggregation scheme entry having a subset of fields that match the new network flow information fields, and

if writing the new network flow information would not alter a field value combination utilized by the existing aggregation scheme entry, storing the new network flow information in the matching CAM entry, and

if writing the new network flow information would alter the field value combination utilized by the existing aggregation scheme entry, storing the new network flow information in an unused CAM entry, if an unused CAM entry is available.

7. The method of claim 3, further including:

receiving a delete command to delete an existing primary table entry and aggregate the data of the primary table entry;

in response to the delete command

for each of a plurality of aggregation schemes, searching for an existing aggregation entry having a subset of fields that match corresponding fields of the primary table entry, and

if an existing aggregation entry cannot be found that has the subset of fields that match corresponding fields of the primary table entry, converting said network flow entry into an aggregation scheme entry.

8. The method of claim 3, further including:

further distinguishing flow entries from aggregation entries according to valid bits in each entry.

9. The method of claim 8, wherein:

the valid bits include

at least one unique bit location corresponding to a primary table for each flow entries, and

at least one bit location unique to each aggregation scheme.

10. The method of claim 9, further including:

accessing associated data for each aggregation entry by generating an offset address according to a scheme value, and adding the offset address to an index value corresponding to a matching aggregation entry.

11. The method of claim 1, wherein:

the first data set includes a first type service designation for a data packet and the second data set includes a second type service designation for the data packet; and

the step of applying the predetermined global mask includes masking all but a desired service type designation to generate packet forwarding data corresponding to the desired service type.

12. The method of claim 11, wherein:

each CAM entry includes a predetermined number of service type bit locations, each bit location corresponding to a different service type designation, each service type bit location having a set state and not set state.

13. The method of claim 12, wherein:

the step of storing at least one data value includes

setting a predetermined service type bit for a plurality of entries to a set state to establish a default service value for the data values of the entries.

14. The method of claim 12, wherein:

each CAM entry further includes at least a destination field that indicates the destination of a data packet.

15. The method of claim 11, further including:

receiving a delete command to delete an existing first data set entry, the delete command indicating matching field values and at least one service type; and

in response to the delete command finding each first data set entry having fields that match the matching fields of the delete command, and

if the service type designations of the entry do not match all of the at least one service type of the delete command, setting the matching service type designations to a non-set state,

if all of the service type designations of the entry match the at least one service type of the delete command, deleting the entry.

16. The method of claim 11, further including:

accessing associated data for each aggregation entry by generating an offset address according to the service type designation, and adding the offset address to an index value corresponding to the service designation.

17. The method of claim 11, further including:

receiving a write command indicating matching field values and at least one service type; and

in response to the write command finding an entry having fields that match the matching fields of the write command, and

if the service type designations of the entry do not match the service type of the write command, setting the matching service type designation of the entry to a non-set state.

18. A method for providing multiple data set values with a single set of globally maskable content addressable memory (CAM) entries, comprising the steps of:

storing first data set values in the CAM entries, each data set value comprising a plurality of unique fields; and

utilizing a CAM entry that stores a first data set value to simultaneously store a proxy value for at least one other data set, each proxy value representing a data set value that shares a subset of the unique fields of the first data set values.

19. The method of claim 18, wherein:

storing first data set values includes storing associated data for each first data set value in a first random access memory (RAM) section accessed with a first table offset address value; and

storing associated data for other data set in a corresponding other RAM section accessed with other offset address values unique to each other data set.

20. The method of claim 18, further including:

in one type of read function,

reading RAM data according to the first table address offset values and an index value generated by searching the first data set values; and

in another type of read function,

reading RAM data according to one of the other address offset values and an index value generated by searching proxy values for the other data set of the other address offset value.

21. The method of claim 18, further including:

in one type of data modify operation,

reading old data from a RAM location accessed by one of the address offset values and an index value, and modifying the old data with data from a newly received data packet; and

in another type of data modify operation,

reading old data from a RAM location accessed by one of the other address offset values, and modifying the data with other data read from a RAM location accessed by the first table address offset value.

22. The method of claim 18, wherein:

the first data set values are a primary network flow identification table having a first data set value corresponding to each flow of a monitored data network; and

the at least one other data set value includes at least one data aggregation scheme that aggregates selected values of monitored flows.

23. The method of claim 18, wherein:

the first data set values are packet forwarding values corresponding to one type of network packet transmission service; and

the at least one other data set values are packet forwarding values corresponding to at least one other type of network packet transmission service.

24. A system for searching multiple data set values with a single content addressable memory (CAM) table, comprising:

a CAM section having N globally maskable CAM entries, each CAM entry operable to store N data set values that index to first set associated data, at least one second set associated data, or both first and second set associated data; and

a control section comprising,

an address generator that generates offset addresses corresponding to a predetermined global mask value, the offset addresses including a first data set offset address and a plurality of secondary set offset addresses each corresponding to a different set of associated data.

25. The system of claim 24, further including:

an associated data section comprising

a first section having no more than N entries that store first set associated data, and

at least a second section having no more than N entries for storing second set associated data.

26. The system of claim 24, wherein:

the control section is selected from the group consisting of;

an application specific integrated circuit formed on a different integrated circuit than the CAM section, a programmable logic device formed on a different integrated circuit than the CAM section, and a processor executing instructions.

27. The system of claim 24, wherein:

the control section is formed in the same integrated circuit as the CAM section.

28. The system of claim 24, wherein:

each CAM entry includes a plurality of valid bits; and

the CAM section includes a global mask register that generates global masks for searching the CAM entries, the global mask register including a global mask corresponding to each valid bit.

29. The system of claim 24, wherein:

each CAM entry comprises a plurality of valid bits; and

the control section further includes an input parse section that adds valid bits to received search key data to generate an internal search key applied to the CAM entries.

30. The system of claim 24, wherein:

the control section further includes

an address modifier that generates a new address based on an offset address from the address generator and an index value from the CAM section.

31. The system of claim 24, wherein:

the data set values that index to the first set associated data and both the first and second set associated data comprises a primary table, where each data set value defines a network flow; and

the data set values that index to the second set of associated data and both the first and second set associated data comprises an aggregation table, where each data set value defines a network flow data aggregation scheme.

32. The system of claim 24, wherein:

the data set values that index to the first set associated data comprises forwarding information for a first type of packet transmission service; and

the data set values that index to the second set of associated data comprises forwarding information for a second type of packet transmission service.