SRAM based longest prefix matching approach for multigigabit IP processing

This paper proposes a novel hardware architecture based on static random access memory (SRAM) for longest prefix match (LPM) search scheme to achieve wire speed IP processing. The central idea of this architecture is to store the IP prefixes virtually in routing table. To virtually store IP prefixes, we reserve only a single bit per prefix irrespective of their lengths. The proposed architecture consumes single memory write cycle to store the IP prefixes those share common initial bits and also takes single memory read cycle for LPM search unlike conventional and existing LPM solutions. The read, write, update time complexity is O(1). This architecture exhibits LPM search time as approximately 1.25 ns and offers search throughput of 805.8 million-search/sec. The numerical results show that this architecture significantly reduces memory requirement, power consumption, and transistor-count/bit requirement.