Methods and apparatus for packet classification with multi-level data structure
AssigneeRedback Networks Inc.
InventorsRenwei Li, Thomas W. Ng, Paul Terry, Henry Lee
Life of this patent
Estimating the term…
Abstract
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.
Claims18
A method for classifying data packets in a network, the method comprising, in a packet handling device:
- a) providing a set of packet classification rules embodied in a plurality of lookup tables, the lookup tables comprising a first table containing conditions on a first parameter and one or more subsequent tables linked to the first table and containing conditions on one or more corresponding subsequent parameters, the rules defining a plurality of classes;
- b) reading a signature comprising values for a plurality of parameters of an incoming data packet;
- c) identifying one of the subsequent tables by searching the first table for a match between one of the conditions and a first parameter value of the signature and sequentially searching identified subsequent tables for conditions matching subsequent parameter values, each time obtaining a pointer identifying a next one of the subsequent lookup tables, wherein a condition is duplicated in two different subsequent tables;
- and,
- d) searching a final one of the subsequent tables for a match to a final parameter value and obtaining a class identifier corresponding to a matched rule.
A medium carrying a set of computer-readable signals corresponding to instructions which, when run on a computer, cause the computer to perform a method for classifying data packets in a network, the method comprising:
- a) reading a signature comprising values for a plurality of parameters of an incoming data packet;
- a) determining a class for the data packet from the signature by searching a set of packet classification rules embodied in a plurality of lookup tables, the lookup tables comprising a first table containing conditions on a first parameter and one or more subsequent tables linked to the first table and containing conditions on one or more corresponding subsequent parameters, the rules defining a plurality of classes, searching the set of packet classification rules comprising:
- i) identifying one of the subsequent tables by searching the first table for a match between one of the conditions and a first parameter value of the signature and sequentially searching identified subsequent tables for conditions matching subsequent parameter values, each time obtaining a pointer identifying a next one of the subsequent lookup tables, wherein a condition is duplicated in two different subsequent tables;
- and,
- ii) searching a final one of the subsequent tables for a match to a final parameter value and obtaining a class identifier corresponding to a matched rule.
Apparatus for classifying data packets, the apparatus comprising:
- (a) a processor capable of obtaining a signature comprising N parameter values for the packet to be classified, where N is an integer with N>=3;
- (b) a memory accessible to the processor;
- (c) a data structure in the memory, the data structure comprising N levels of tables, the tables including a first level lookup table associated with a first one of the parameter values, a plurality of intermediate lookup tables associated with each of one or more intermediate parameter values and a plurality of final level lookup tables associated with an Nth one of the parameter values, each of the tables containing entries which include a condition on a parameter value which corresponds to the table, wherein a condition is duplicated in two different tables at a same level;
- wherein the processor is adapted to, beginning with the first level table, iteratively, search a table for a condition which matches the parameter value in the signature which corresponds to the level to obtain a pointer to a subsequent table to search for a condition matching a subsequent parameter value in the signature of the packet until the processor identifies a final level table and wherein the processor is adapted to obtain the class identifier applicable to the packet by searching the final level table for a condition which matches the Nth parameter value in the signature.
Dependencies are inferred from the claim text.