Associative cache structure for lookups and updates of flow records in a network monitor

• US 6,771,646 B1
• Filed: 06/30/2000
• Issued: 08/03/2004
• Est. Priority Date: 06/30/2000
• Status: Expired due to Term

• Current Assignee: Packet Intelligence LLC (Packet Intelligence Holdings LLC)
• Original Assignee: Hifn, Inc. (Maxlinear Incorporated)
• Inventors: Sarkissian, Haig A., Dietz, Russell S.
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): Nguyen, Alan V.
• Application Number:
  US09/608,266
• Time in Patent Office: 1,495 Days
• Field of Search: 370/241.1, 370/252, 370/253, 370/352, 370/353, 370/355, 370/389, 370/392, 370/401, 370/395.1, 709/223, 709/224
• US Class Current: 370/392
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

A cache system for looking up one or more elements of an external memory includes a set of cache memory elements coupled to the external memory, a set of content addressable memory cells (CAMs) containing an address and a pointer to one of the cache memory elements, and a matching circuit having an input such that the CAM asserts a match output when the input is the same as the address in the CAM cell. The cache memory element which a particular CAM points to changes over time. In the preferred implementation, the CAMs are connected in an order from top to bottom, and the bottom CAM points to the least recently used cache memory element.

Claims

1. A packet monitor for examining packet passing through a connection point on a computer network, each packets conforming to one or more protocols, the monitor comprising:

(a) a packet acquisition device coupled to the connection point and configured to receive packets passing through the connection point;

(b) a memory for storing a database comprising flow-entries for previously encountered conversational flows to which a received packet may belong, a conversational flow being an exchange of one or more packets in any direction as a result of an activity corresponding to the flow;

(c) a cache subsystem coupled to the flow-entry database memory providing for fast access of flow-entries from the flow-entry database;

(d) a lookup engine coupled to the packet acquisition device and to the cache subsystem and configured to lookup whether a received packet belongs to a flow-entry in the flow-entry database, to looking up being the cache subsystem; and

(e) a state processor coupled to the lookup engine and to the flow-entry-database memory, the state processor being to perform any state operations specified for the state of the flow starting from the last encountered state of the flow in the case that the packet is from an existing flow, and to perform any state operations required for the initial state of the new flow in the case that the packet is from an existing flow.

2. A packet monitor according to claim 1, further comprising:

a parser subsystem coupled to the packet acquisition device and to the lookup engine such that the acquisition device is coupled to the lookup engine via the parser subsystem, the parser subsystem configured to extract identifying information from a received packet,

wherein each flow-entry is identified by identifying information stored in the flow-entry, and wherein the cache lookup uses a function of the extracted identifying information.

3. A packet monitor according to claim 2, wherein the cache subsystem is an associative cache subsystem including one or more content addressable memory cells (CAMs).

4. A packet monitor according to claim 2, wherein the cache subsystem includes:

(i) a set of cache memory elements coupled to the flow-entry database memory, each cache memory element including an input port to input a flow-entry and configured to store a flow-entry of the flow-entry database;

(ii) a set of content addressable memory cells (CAMs) connected according to an order of connections from a top CAM to a bottom CAM, each CAM containing an address and a pointer to one of the cache memory elements, and including;

a matching circuit having an input such that the CAM asserts a match output when the input is the same as the address in the CAM cell, an asserted match output indicating a hit,

a CAM input configured to accept an address and a pointer, and

a CAM address output and a CAM pointer output;

(iii) a CAM controller coupled to the CAM set; and

(iv) a memory controller coupled to the CAM controller, to the cache memory set, and to the flow-entry memory,

wherein the matching circuit inputs of the CAM cells are coupled to the lookup engine such that that an input to the matching circuit inputs produces a match output in any CAM cell that contains an address equal to the input, and

wherein the CAM controller is configured such that which cache memory element a particular CAM points to changes over time.

5. A packet monitor according to claim 4, wherein the CAM controller is configured such that the bottom CAM points to the least recently used cache memory element.

6. A packet monitor according to claim 5, wherein the address and pointer output of each CAM starting from the top CAM is coupled to the address and pointer input of the next CAM, the final next CAM being the bottom CAM, and wherein the CAM controller is configured such than when there is a cache hit, the address and pointer contents of the CAM that produced the hit are put in the top CAM of the stack, the address and pointer contents of the CAMs above the CAM that produced the asserted match output arc shifted down, such that the CAMs are ordered according to recentness of use, with the least recently used cache memory element pointed to by the bottom CAM and the most recently used cache memory element pointed to by the top CAM.

7. A packet monitor for examining packet passing through a connection point on a computer network, each packets conforming to one or more protocols, the monitor comprising:

a packet acquisition device coupled to the connection point and configured to receive packets passing through the connection point;

an input buffer memory coupled to and configured to accept a packet from the packet acquisition device;

a parser subsystem coupled to the input buffer memory, the parsing subsystem configured to extract selected portions of the accepted packet and to output a parser record containing the selected portions;

a memory to storing a database of one or more flow-entries for any previously encountered conversational flows, each flow-entry identified by identifying information stored in the flow-entry;

a lookup engine coupled to the output of the parser subsystem and to the flow-entry memory and configured to lookup whether the particular packet whose parser record is output by the parser subsystem has a matching flow-entry, the looking up using at least some of the selected packet portions and determining if the packet is of an existing flow;

a cache subsystem coupled to and between the lookup engine and the flow-entry database memory providing for fast access of a set of likely-to-be-accessed flow-entries from the flow-entry database; and

a flow insertion engine coupled to the flow-entry memory and to the lookup engine and configured to create a flow-entry in the flow-entry database, the flow-entry including identifying information for future packets to be identified with the new flow-entry,

the lookup engine configured such that if the packet is of an existing flow, the monitor classifies the packet as belonging to the found existing flow; and

if the packet is of a new flow, the flow insertion engine stores a new flow-entry for the new flow in the flow-entry database, including identifying information for future packets to be identified with the new flow-entry,

wherein the operation of the parser subsystem depends on one or more of the protocols to which the packet conforms.

8. A monitor according to claim 7, wherein the lookup engine updates the flow-entry of an existing flow in the case that the lookup is successful.

9. A monitor according to claim 7, further including a mechanism for building a hash from the selected portions, wherein the hash is included in the input for a particular packet to the lookup engine, and wherein the hash is used by the lookup engine to search the flow-entry database.

10. A monitor according to claim 7, further including a memory containing a database of parsing/extraction operations, the parsing/extraction database memory coupled to the parser subsystem, wherein the parsing/extraction operations are according to one or more parsing/extraction operations looked up from the parsing/extraction database.

11. A monitor according to claim 10, wherein the database of parsing/extraction operations includes information describing how to determine a set of one or more protocol dependent extraction operations from data in the packet that indicate a protocol used in the packet.

12. A method according to claim 7, further including a state processor coupled to the lookup engine and to the flow-entry-database memory, and configured to perform any state operations specified for the state of the flow starting from the last encountered state of the flow in the case that the packet is from an existing flow, and to perform any state operations required for the initial state of the new flow in the case that the packet is from an existing flow.

13. A method according to claim 12, wherein the set of possible state operations that the state processor is configured to perform includes searching for one or more patterns in the packet portions.

14. A monitor according to claim 12, wherein the state processor is programmable, the monitor further including a state patterns/operations memory coupled to the state processor, the state operations memory configured to store a database of protocol dependent state patterns/operations.

15. A monitor according to claim 12, wherein the state operations include updating the flow-entry, including identifying information for future packets to be identified with the flow-entry.

16. A method of examining packets passing through a connection point on a computer network, each packets conforming to one or more protocols, the method comprising:

(a) receiving a packet from a packet acquisition device;

(b) performing one or more parsing/extraction operations on the packet to create a parser record comprising a function of selected portions of the packet;

(c) looking up a flow-entry database comprising none or more flow-entries for previously encountered conversational flows, the looking up using at least some of the selected packet portions and determining if the packet is of an existing flow, the lookup being via a cache;

(d) if the packet is of an existing flow, classifying the packet as belonging to the found existing flow; and

(e) if the packet is of a new flow, storing a new flow-entry for the new flow in the flow-entry database, including identifying information for future packets to be identified with the new flow-entry,

wherein the parsing/extraction operations depend on one or more of the protocols to which the packet conforms.

17. A method according to claim 16, wherein classifying the packet as belonging to the found existing flow includes updating the flow-entry of the existing flow.

18. A method according to claim 16, wherein the function of the selected portions of the packet forms a signature that includes the selected packet portions and that can identify future packets, wherein the lookup operation uses the signature and wherein the identifying information stored in the new or updated flow-entry is a signature for identifying future packets.

19. A method according to claim 16, wherein the looking up of the flow-entry database uses a hash of the selected packet portions.

20. A method according to claim 16, wherein step (d) includes if the packet is of an existing flow, obtaining the last encountered state of the flow and performing any state operations specified for the state of the flow starting from the last encountered state of the flow;

and wherein step (e) includes if the packet is of a new flow, performing any state operations required for the initial state of the new flow.