TCAM Management Approach That Minimize Movements
First Claim
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.
10 Assignments
0 Petitions
Accused Products
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.
-
Citations
25 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
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. - View Dependent Claims (17)
-
-
18. A method of adding a new entry in a ternary content-addressable memory (TCAM), wherein the new entry comprises a prefix, the method comprising:
-
identifying a specified range of the new entry; searching for a node range that overlaps the specified range, wherein the searching begins at a root node; upon determining that the node range overlaps the specified range in an overlapping region, selecting a TCAM entry in the overlapping region that is closest to a predetermined preference of the specified range; upon determining that the selected TCAM entry is at a start or an end of the node range, adjusting the node range to make a free TCAM entry; upon determining that the free TCAM entry is not at the start or the end of the node range, breaking a node in the node range into two nodes and adding a new node which is a free TCAM entry; and adding the new entry into the free TCAM entry. - View Dependent Claims (19, 20, 21, 22, 23)
-
-
24. A method of adding a new entry with a specified range and a start of a specified range in a ternary content-addressable memory (TCAM), wherein the new entry comprises a prefix, the method comprising:
-
searching a plurality of nodes for the smallest node having a range start that is larger than the start of a specified range; removing the smallest node having a range start that is larger than the start of a specified range; wherein the plurality of nodes are each arranged to have a contiguous range of free entries; and wherein the searching is done in descending order starting from the node having a range start that is larger than the start of a specified range and is closest to the start of the specified range.
-
-
25. A method of adding a new entry with a specified range and a start of a specified range in a ternary content-addressable memory (TCAM), wherein the new entry comprises a prefix, the method comprising:
-
searching a plurality of nodes for a target node having a target node range that overlaps the specified range; removing a start of the target node range, upon locating the target node; adjusting the target node range after the start of the target node range has been removed; wherein the plurality of nodes are each arranged to have a contiguous range of free entries; and wherein the searching is done in descending order starting from the node having a range start that is larger than the start of a specified range and is closest to the start of the specified range.
-
Specification