Abstract
Ternary content-addressable memories (TCAMs) have been becoming a popular hardware device for fast routing lookups. However, due to the need to keep a sorted list of entries on TCAM, the entries are moved to make the free space for the new entry. The slow update is performance bottleneck. This paper presents a TCAM-based forwarding engine that is update efficient. We analyze the hierarchy of prefixes in routing table, and give a Level-partitioning algorithm to construct the routing table in TCAM. In our scheme, the update algorithm is fast and simple, the number of movements per update depends on the inserting sequence of new prefixes, is independent of the initial prefixes. For the real route update traces, the average number of movements is less than 0.01.