Redback Networks Inc.

Henry Lee

Paul Terry

Thomas Ng

Renwei Li

Providing different levels of quality of service for different data flows being transported over a data link requires a very fast way to classify individual packets. Providing meaningful classification generally requires classifying data packets in several dimensions. A classification method represents a rule base as a hierarchy of linked tables and sequentially matches each parameter value in a packet signature against tables in the hierarchy. The method supports longest prefix matching and avoids time consuming backtracking by adding rules to the rule base.

Methods and apparatus for packet classification with multi-level data structure

Providing different levels of quality of service for different data flows being transported over a data link requires a very fast way to classify individual packets. Providing meaningful classification generally requires classifying data packets in several dimensions. A classification method processes multiple parameter values for a packet in parallel to obtain answer sets indicating which rules are matched by each parameter value. Answer indexes identify logical blocks in each answer set which contain TRUE values. The method performs an AND operation on the answer indexes to identify those blocks in the answer sets which could contain bits corresponding to matched rules. An AND operation is performed on the identified blocks to identify the particular rule matched by the packet. The classification method allows extremely fast wire speed packet classification.

Growing community of inventors

Coquitlam, Canada

Henry Lee