An Update Method for a Low Power Cam Emulator Using an LUT Cascade Based on an EVMDD (k)
Hiroki Nakahara, Tsutomu Sasao, Munehiro Matsuura and Hisashi Iwamoto
Core routers perform longest prefix matching (LPM) using content addressable memories (CAMs). With the rapid growth of the Internet, LPM has become the bottleneck in network traffic management. In the previous publication, we have proposed an area-efficient and high-performance CAM emulator using an LUT cascade based on an edge-valued multi-valued decision diagram (EVMDD (k)). In the internet, registered vectors must be updated frequently. In this paper, we propose an algorithm to update an LUT cascade. We implemented the proposed algorithm on the ARM processor. Its update time is shorter than the peak update time of the BGP protocol. Also, we analyzed the power consumption of the LUT cascade with respect to both the static and the dynamic power. Experimental results show that, as for the lookup speed per area and the power consumption, our architecture outperforms existing CAM realizations on FPGAs.
Keywords: Content addressable memory (CAM), multi-valued decision diagram, longest prefix matching (LPM)