An Update Method for a CAM Emulator Using an LUT Cascade Based on an EVMDD (K)

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 a 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 inter-net, 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. Experimental results show that, as for the lookup speed per area, our architecture outperforms existing CAM realizations on FPGAs.