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
17 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)
-
Specification