A hybrid encoding scheme for efficient single-cycle range matching in content addressable memory

Content addressable memory (CAM) is a parallel search engine chip that has been proven to accelerate network appliance functions that are search-intensive by nature, such as routing table lookups. CAMs enable searching for a match of a single input with hundreds of thousands of entries in parallel in a single clock cycle. However, CAMs are inefficient in matching a numeric range with existing encoding methods. Two-hot, binary and Gray encodings exhibit a depth scalability problem where the CAM depth required increases with the maximum number M in the range. One-hot and Johnson encodings exhibit poor CAM width scalability O(M). We present a unique hybrid encoding scheme mixing the features of two-hot and Johnson codes to solve both scalability problems. For an arbitrary range, it uses only three CAM entries in depth regardless of M, and has a width scaling of O(radicM ). Therefore, this hybrid encoding scheme can be efficiently applied to CAM-based range matching with arbitrary ranges, while maintaining single cycle searching