PtCAM: Scalable High-Speed Name Prefix Lookup using TCAM

Name prefix lookup is a core characteristic of name-based packet forwarding in ICN and also URL redirections in CDN. This operation is essentially a longest prefix match on URL-like names, which faces significant challenges in high-speed processing due to large set, length-unbounded names and per-packet lookup need. In this paper, we propose a scheme to support generic hierarchical name lookups on millions of prefixes with fast, constant and guaranteed performance using ternary content-addressable memory (TCAM). Our work has three contributions. First, a scheme, namely PtCAM, is proposed to exploit TCAM for name lookup using a binary Patricia trie. Second, several approaches are proposed to enhance efficiency and scalability. Third, experiments on various name datasets are carried out. The results show that our scheme has the potential to achieve high-speed lookup performance nearly equal to the given TCAM throughput. Notably, PtCAM can be implemented on TCAM-based IP linecards, which means that industrial commercial off-the-shelf devices can be directly involved in the advancement of information-centric innovation and deployment.