Patent ID: 8566276

Claim:
A network device comprising: a ternary content addressable memory (TCAM) programmed to include entries representing a plurality of prefix tree (trie) data structures used in processing network traffic received by the network device; logic to determine a first entry for insertion in the TCAM; logic to determine a first location of a second stored entry and a first location of a third stored entry; logic to determine if an empty space exists between the second stored entry and the third stored entry; logic to insert the first entry in the TCAM when the empty space exists; logic to push, when the empty space does not exist, the second stored entry from the first location of the second stored entry to a second location; logic to insert the first entry in the TCAM, based on pushing the second stored entry from the first location of the second stored entry to the second location and when the empty space exists after pushing the second stored entry; logic to push, when the empty space does not exist after pushing the second stored entry, the third stored entry from the first location of the third stored entry to a third location; logic to insert the first entry in the TCAM, based on pushing the third stored entry from the first location of the third stored entry to the third location and when the empty space exists after pushing the third stored entry; and logic to insert the first entry in the TCAM, when the empty space does not exist after pushing the third stored entry, based on a defragmentation operation performed on the TCAM in which a candidate entry having a relocation weight is chosen to be relocated as part of the defragmentation operation, the relocation weight being determined based on trie depths corresponding to entries that occupy the candidate entry before defragmentation.