Date Added: Aug 2009
Several common packet processing tasks make use of directed graph data structures in which edge labels are used to match symbols from a finite alphabet. Examples include tries used in IP route lookup and string-matching automata used to implement deep packet inspection for virus scanning. In this paper, the authors develop a novel representation for such data structures that is significantly more compact than conventional approaches. This compactness can lead to higher performance in implementation contexts where they have small on-chip memories with ample memory bandwidth and larger off-chip memories with more limited bandwidth. These characteristics are common to conventional processors, network processors, ASICs and FPGA implementations.