Back to results
US 7,257,590 B2Granted
Method and system for classifying binary strings
AssigneeNokia Corporation
InventorsAndreas Heiner, Carl Eklund
Life of this patent
Estimating the term…
Abstract
The present invention relates to a method and network element for classification of bit strings such as data packets on a per-flow basis, wherein a plurality of classification fields are searched for in respective search trees based on a matching procedure in which an index value is obtained in a leaf node of a search tree for each classification field. Index values obtained in said searching step are used to derive a policy to be applied to said data packet, wherein the number of index values is reduced by combining intermediate results of the searching step or the deriving step. Thereby, computational efficiency can be improved and memory requirements reduced.
Claims22
A method for classifying a binary string, comprising:
- searching for a plurality of classification fields for said binary string in respective search trees based on a matching procedure in which an index value is obtained in a leaf node of a respective search tree for each classification field found during said searching;
- deriving from index values obtained in said searching a policy configured to be applied to said binary string;
- reducing a number of index values by combining intermediate results of said searching or said deriving and mapping the number of index values onto one value by use of a knowledge of searches;
- incorporating said one value into said knowledge of searches to use said one value during a next search;
- storing an index value of a first classification field in a list attached to the leaf node of a second classification field, when a policy exists for a combination of the index values of said first and second classification fields;
- searching for said index value of said first classification field in said list attached to said leaf node of said second classification field when the search for said second classification field has reached said leaf node of said second classification field,
- deriving a classification for the binary string, and
- outputting the classification.
5 more elements
A software program product, embodied on a computer-readable medium, for executing a method for classifying a binary string when run on a data processing system, the method comprising:
- searching for a plurality of classification fields for said binary string in respective search trees based on a matching procedure in which an index value is obtained in a leaf node of a respective search tree for each classification field found during said searching;
- deriving from index values obtained in said searching a policy configured to be applied to said binary string;
- reducing a number of index values by combining intermediate results of said searching or said deriving and mapping the number of index values onto one value by use of a knowledge of searches;
- incorporating said one value into said knowledge of searches to use said one value during a next search;
- storing an index value of a first classification field in a list attached to the leaf node of a second classification field, when a policy exists for a combination of the index values of said first and second classification fields;
- searching for said index value of said first classification field in said list attached to said leaf node of said second classification field when the search for said second classification field has reached said leaf node of said second classification field,
- deriving a classification for the binary string, and
- outputting the classification.
5 more elements
A hardware implementation of a program for executing a method for classifying a binary string when run on a data processing system, the method comprising:
- searching for a plurality of classification fields for said binary string in respective search trees based on a matching procedure in which an index value is obtained in a leaf node of a respective search tree for each classification field found during said searching;
- deriving from index values obtained in said searching a policy configured to be applied to said binary string;
- reducing the number of index values by combining intermediate results of said searching or said deriving and mapping the number of index values onto one value by use of a knowledge of searches;
- incorporating said one value into said knowledge of searches to use said one value during a next search;
- storing an index value of a first classification field in a list attached to the leaf node of a second classification field, when a policy exists for a combination of the index values of said first and second classification fields;
- searching for said index value of said first classification field in said list attached to said leaf node of said second classification field when the search for said second classification field has reached said leaf node of said second classification field,
- deriving a classification for the binary string, and
- outputting the classification.
5 more elements
A network element, comprising:
- search means for searching for a plurality of classification fields for a binary string in respective search trees based on a matching procedure in which an index value is obtained in a leaf node of a respective search tree for each classification field found during said searching;
- derivation means for deriving from index values obtained by said search means a policy configured to be applied to said binary string;
- and
- reduction means for reducing a number of index values by combining intermediate results of said search means or said derivation means and for mapping the number of index values onto one value by use of a knowledge of searches;
- incorporation means for incorporating said one value into said knowledge of searches to use said one value during a next search;
- storage means for storing an index value of a first classification field in a list attached to the leaf node of a second classification field, when a policy exists for a combination of the index values of said first and second classification fields;
- and
- search means for searching for said index value of said first classification field in said list attached to said leaf node of said second classification field when the search for said second classification field has reached said leaf node of said second classification field,
- wherein the network element is configured to classify said binary string, which is configured to be represented by at least one classification field.
6 more elements
A network element, comprising:
- a search unit configured to search for a plurality of classification fields for a binary string in respective search trees based on a matching procedure in which an index value is obtained in a leaf node of a respective search tree for each classification field found during said search;
- a derivation unit configured to derive from index values obtained in said search a policy configured to be applied to said binary string;
- and
- a reduction unit configured to reduce the number of index values by combining intermediate results of said searching or deriving and to map the number of index values onto one value by use of a knowledge of searches;
- an incorporation unit configured to incorporate said one value into said knowledge of searches to use said one value during a next search;
- a storage unit configured to store an index value of a first classification field in a list attached to the leaf node of a second classification field, when a policy exists for a combination of the index values of said first and second classification fields;
- and
- a search unit configured to search for said index value of said first classification field in said list attached to said leaf node of said second classification field when the search for said second classification field has reached said leaf node of said second classification field,
- wherein said network element is configured to classify said binary string, which is configured to be represented by at least one classification field.
6 more elements
Dependencies are inferred from the claim text.