System and method for algorithmic TCAM packet classification

摘要

In a Ternary Content Addressable Memory (TCAM) optimized for network packet classification, network operation rules are preprocessed into sub-lists in accordance with a decision tree based packet classification algorithm. The decision tree is encoded as a lookup memory, which is accessed with a predetermined base address of higher order address bits combined with lower order address bits obtained from specific bit positions from a received network packet. Depending on the nodes traversed in the decision tree, different base addresses and values from different bit positions of the packet are used until a sub-list of potential rules is identified. A bitwise comparison of values of each rule against the packet is then executed, the matching rule with the highest precedence is returned as the matching table entry and the configured value associated with the entry is prepended to the packet.

主权项

1. A protocol independent network packet classification processing system for matching a network packet to one of a plurality of rules organized into sub-lists, comprising:
a compare tree engine for:
(a) receiving the network packet;(b) accessing content of a preconfigured look up table encoded in a memory using a final address composed of data values obtained from the network packet at specific bit positions identified by a predetermined bit extraction pattern and a predetermined base address, wherein the content is one of a null value indicating absence of a match, a pointer associated with one of the sub-lists, or a new predetermined bit pattern and a new predetermined base address;(c) when the accessed content is the new predetermined bit pattern and the new predetermined base address, changing the final address such that the final address is composed of data values obtained from the network packet at specific bit positions identified by the new predetermined bit extraction pattern and the new predetermined base address;(d) repeating steps (b) and (c) until the accessed content from step (b) is one of a null value or a pointer associated with one of the sub-lists;(e) when the accessed content is a pointer associated with one of the sub-lists, outputting the pointer; a serial match engine for:
receiving the pointer from the compare engine; andexecuting a linear search of each rule in the one sub-list associated with the received pointer to identify a highest matching precedent rule to preselected bit position values of the network packet.