TCAM management approach that minimize movements

• US 8,090,901 B2
• Filed: 05/14/2009
• Issued: 01/03/2012
• Est. Priority Date: 05/14/2009
• Status: Expired due to Fees

• Current Assignee: Ruckus IP Holdings LLC
• Original Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Inventors: Lin, Kevin Kwun-Nan, Zhang, Gefan, Murtinty, Rajeshekhar
• Primary Examiner(s): Pham, Ly D
• Application Number:
  US12/466,277
• Publication Number:
  US 20100293327A1
• Time in Patent Office: 964 Days
• Field of Search: 711/108, 711/E12.001, 365/49.1, 365/49.16
• US Class Current: 711/108
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

Methods for efficiently managing a ternary content-addressable memory (TCAM) by minimizing movements of TCAM entries include determining a first node and a second node in the TCAM, determining if there is a free TCAM entry between the first node and the second node, and storing the new entry in the free TCAM entry. Upon determining that a free TCAM entry does not exist between the first node and the second node, further determining a chain of nodes and then determining if there is a free TCAM entry in the chain of nodes. Upon determining that there is a free TCAM entry within the chain of nodes, moving the TCAM entries identified as the nodes in the chain of nodes to generate a free node nearest to the new entry and inserting the new entry in the free node. Moving the TCAM entries identified as the nodes in the chain of nodes preserves the order of the nodes.

Claims

1. A method, comprising:

forming a chain of nodes, wherein the nodes have an order and each node is identified with a ternary content-addressable memory (TCAM) entry;

determining a location in the TCAM where a prefix is to be inserted;

identifying a first node that is nearest to the location and either higher or lower than the location;

identifying a free TCAM entry that is nearest to the location;

moving the TCAM entry identified as a node to the nearest free TCAM entry;

freeing the first node;

inserting the prefix in the first node;

wherein moving the TCAM entry identified as the node to the free TCAM entry and freeing the first node preserves the order of nodes in the chain of nodes.

2. The method of claim 1 wherein moving the TCAM entry identified as the node to the nearest free TCAM entry is moving the TCAM entry identified as the first node to the nearest free TCAM entry.

3. The method of claim 2 wherein freeing the first node is storing the contents of the first node in another TCAM entry making the first node available for inserting the prefix.

4. The method of claim 1 further comprising:

moving the TCAM entry identified as a second node to the node TCAM entry after the TCAM entry identified as the node is moved; and

moving the TCAM entry identified as the first node to the second node TCAM entry after the TCAM entry identified as the second node is moved.

5. The method of claim 4 wherein freeing the first node is storing the contents of the first node in another TCAM entry making the first node available for inserting the prefix.

6. A method, comprising:

forming a chain of nodes, wherein the nodes have an order and each node is a ternary content-addressable memory (TCAM) entry;

determining a range of TCAM entries in which a prefix is to be inserted, the range of the TCAM entries having a first node as an end point;

determining a location of a free TCAM entry that is nearest to where the prefix is to be inserted;

upon determining that the location of the free TCAM entry is within the range, inserting the prefix in the free TCAM entry;

upon determining that the location of the free TCAM entry is not within the range;

moving the TCAM entries identified as the nodes in the chain of nodes to free the first node;

inserting the prefix in the free first node;

wherein moving the TCAM entries identified as the nodes in the chain of nodes preserves the order of the nodes.

7. The method of claim 6 wherein moving the TCAM entries identified as the nodes further comprises shifting the TCAM entries identified as nodes so that a TCAM entry identified as the first node occupies the free TCAM entry and making the TCAM entry identified as the first node a free node.

8. The method of claim 6 wherein moving the TCAM entries identified as the nodes further comprises shifting the TCAM entries identified as the nodes so that a second node occupies the free TCAM entry and the first node occupies the second node entry.

9. The method of claim 6 wherein moving the TCAM entries identified as the nodes further comprises shifting the TCAM entries identified as the nodes so that a third TCAM entry identified as a third node entry occupies the free TCAM entry, a second TCAM entry identified as a second node entry occupies the third node entry, and the first TCAM entry identified as the first node entry occupies the second TCAM entry identified as the second node entry.

10. The method of claim 6 wherein the first node is the nearest higher node to the prefix.

11. The method of claim 6 wherein the chain of nodes comprises all ancestors and all descendents of the first node.

12. The method of claim 11 further comprising:

identifying free TCAM entries in both the ancestor and descendents of the first node;

upon determining that there is not a free TCAM entry within the chain of nodes, determining if there is a free TCAM entry in the descendents portion of the chain of nodes;

upon determining that there is a free TCAM entry within the descendents portion of the chain of nodes, moving the TCAM entries identified as the nodes in the descendents portion of the chain of nodes to generate a free TCAM entry identified as a free node nearest to the prefix; and

inserting the prefix in the free node;

wherein moving the TCAM entries identified as the nodes in the descendents portion of the chain of nodes preserves the order of the nodes.

13. The method of claim 12 further comprising:

upon determining that there is not a free TCAM entry within the descendents portion of the chain of nodes, determining if there is a free TCAM entry in the ancestors portion of the chain of nodes;

upon determining that there is a free TCAM entry within the ancestors portion of the chain of nodes, moving the TCAM entries identified as the nodes in the ancestors portion of the chain of nodes to generate a free node nearest to the prefix; and

inserting the prefix in the free node;

wherein moving the TCAM entries identified as the nodes in the ancestor'"'"'s portion of the chain of nodes preserves the order of the nodes.

14. The method of claim 11 further comprising:

upon determining that there is not a free TCAM entry within the chain of nodes, determining if there is a free TCAM entry in the ancestors portion of the chain of nodes;

upon determining that there is a free TCAM entry within the ancestors portion of the chain of nodes, moving the TCAM entries identified as the nodes in the ancestors portion of the chain of nodes to generate a free node nearest to the prefix; and

inserting the prefix in the free node;

wherein moving the TCAM entries identified as the nodes in the ancestor'"'"'s portion of the chain of nodes preserves the order of the nodes.

15. The method of claim 14 further comprising:

upon determining that there is not a free TCAM entry within the ancestors portion of the chain of nodes, determining if there is a free TCAM entry in the descendents portion of the chain of nodes;

upon determining that there is a free TCAM entry within the descendents portion of the chain of nodes, moving the TCAM entries identified as the nodes in the descendents portion of the chain of nodes to generate a free node nearest to the prefix; and

inserting the prefix in the free node;

wherein moving the TCAM entries identified as the nodes in the descendents portion of the chain of nodes preserves the order of the nodes.

16. A method, comprising:

forming a chain of nodes, wherein the nodes have an order and each node is a ternary content-addressable memory (TCAM) entry;

determining a first node and a second node in the TCAM in between which a prefix is to be inserted;

determining if there is a free TCAM entry between the first node and the second node;

storing the prefix in the free TCAM entry upon determining that a free TCAM entry does exist between the first node and the second node;

upon determining that a free TCAM entry does not exist between the first node and the second node;

determining if there is a free TCAM entry between ancestors of the first node;

upon determining that there is a free TCAM entry within the ancestors, shifting the ancestor nodes so that an ancestor node occupies the free TCAM entry and the first node is free, without loosing the order of the nodes in the chain, and storing the prefix in the first node; and

upon determining that a free TCAM entry does not exist between the ancestor nodes, determining if there is a free TCAM entry between descendents of the second node; and

upon determining that there is a free TCAM entry within the descendents, shifting the descendent nodes so that a descendent node occupies the free TCAM entry and the second node is free, without loosing the order of the nodes in the chain, and storing the prefix in the second node.

17. The method of claim 16 further comprising deleting a node by marking a TCAM as a free entry.