TreeCAM

Authors:

Abstract
Packet Classification is a key functionality provided by modern routers. Previous approaches --- TCAM and algorithmic --- perform well in either lookup efficiency (power and number of accesses) or update effort but not both. To perform well in both, we propose TreeCAM, which employs three novel ideas. (1) Dual versions of TreeCAM's decision tree to decouple lookups and updates: A coarse version with a few thousand rules per leaf achieves efficient lookups and a fine version with a few tens of rules per leaf reduces update effort. (2) Interleaved layout of the rules in the TCAM: Combined with the fine version's few rules per leaf, the layout enables us to bound our worst-case update effort. (3) Path-by-path updates to enable update work to be interspersed with packet lookups (i.e., non-atomic updates), eliminating packet buffering or packet drops during update. Using simulations of 100,000-rule classifiers, we show that TreeCAM performs well in both lookups and updates: (1) 6--8 TCAM subarray accesses per packet, matching modern TCAMs. (2) close to an idealized TCAM in worst-case update effort while requiring little buffering of packets.

This publication has 17 references indexed in Scilit: