Perfect Hashing for Network Applications Yi Lu, Balaji Prabhakar Dept. of Electrical Engineering Stanford University Stanford, CA 94305 yi.lu,balaji@stanford.edu Flavio Bonomi Cisco Systems 175 Tasman Dr San Jose, CA 95134 avio@cisco.com Abstract— Hash tables are a fundamental data structure in many network applications, including route lookups, packet classication and monitoring. Often a part of the data path, they need to operate at wire-speed. However, several associative memory accesses are needed to resolve collisions, making them slower than required. This motivates us to consider minimal perfect hashing schemes, which reduce the number of memory accesses to just 1 and are also space-efcient. Existing perfect hashing algorithms are not tailored for net- work applications because they take too long to construct and are hard to implement in hardware. This paper introduces a hardware-friendly scheme for minimal perfect hashing, with space requirement approa
