STORAGE-EFFICIENT AND COLLISION-FREE HASH-BASED PACKET PROCESSING ARCHITECTURE AND METHOD

An architecture and method for data storage and retrieval which also addresses a number of key problems associated with systems employing hash-based techniques. The architecture and method employs a collision-free hashing scheme called Bloomier filter while eliminates its false positives in a storage efficient way. Wildcard support is added through the use of a scheme called prefix collapsing, while introducing only a small additional storage requirement and reduced hardware complexity. Real update traces indicate that both fast and incremental updates are provided—features generally not available in prior-art collision-free hashing schemes.