Method and device for storing and matching arbitrary wide expressions to content addressable memories
AssigneeTelefonaktiebolaget LM Ericsson (publ)
InventorsKjell Gunnar Torkelsson, Johan Mathijs Ditmar, Lars-Orjan Kling, Hakan Otto Ahl
Life of this patent
Estimating the term…
Abstract
The present invention relates to a method for storing arbitrarily wide expressions (31) in a set of Content Addressable Memory (CAMs) elements (33) where each CAM element is of lesser width than the expression (31). The CAM element may be a physical CAM or part of a physical CAM. The invention also relates to a method for searching wide expressions in such sets of CAM elements (33). The invention further relates to a device and a computer program for performing the method.
Claims18
Method for storing expressions of arbitrary width in content addressable memories (CAMs), wherein the method comprises the steps of dividing the expression into a number of consecutive parts, hereafter named CAM words, storing each word in a respective CAM element, wherein said CAM elements are a number of physical CAMs and/or designated parts of one physical CAM, associating each CAM word with the other CAM words of the expression where all the associated CAM words express the stored expression and, if a CAM word intersects with one or more of the CAM words of a CAM element, creating a word, hereafter named share, consisting of the union of the intersecting CAM words, assigning an association value to the share, and setting said association value to match the association values of the intersecting words.
Method according to any of the preceding claims, comprising the further step of assigning the share a higher priority than the intersecting words.
Device for storing expressions of arbitrary width in content addressable memories (CAMs), comprising means for dividing the expression into a number of consecutive parts, hereafter named CAM words, means for storing each word in a respective CAM element, wherein said CAM elements are a number of physical CAMs and/or designated parts of one physical CAM, means for associating each CAM word with the other CAM words of the expression where all the associated CAM words express the stored expression and means for creating a word, hereafter named share, consisting of the union of the intersecting CAM words, assigning an association value to the share, and setting said association value to match the association values of the intersecting words, if a CAM word intersects with one or more of the CAM words of a CAM element.
Dependencies are inferred from the claim text.