摘要 |
PURPOSE: A method for classifying data packets is provided to process with respect to applicable rules, in response to the values of a plurality of criteria contained in each packet. CONSTITUTION: In the classification process, input values of the relevant criteria are taken from the received input item. For this general description, it is assumed that the items to be classified are communication packets, and that the criteria are the destination address and the origin address. The two particular address values(I1 and I2) are taken as input values for a lookup procedure in stored tables. In the next step it is determined, separately for each criterion, into which range of preselected basic ranges the respective input value falls. This results in the identification of two basic ranges(Xi and Yj) for the two input values. So far, these steps are the same as in other classification procedures already known. Now, in another lookup operation in stored tables, a range token is found for each of the previously determined basic ranges, thus obtaining range tokens(RT(Xi) and RT(Yj)). At least one of these range tokens is obtained from a set of range tokens of non-uniform length. The range tokens are so selected and mapped to the basic ranges that they form a prefix-oriented set adapted to the distribution of rules over the value ranges of input values. The two range tokens obtained for the actual input values are then used, in a predetermined combination, for a longest-matching-prefix lookup or search operation in a stored data structure which may be a binary search tree, and which is designed on the basis of rule prefixes to optimally utilize the occurring range token combinations as search keys, to finally obtain as output the identifier of that rule which is to be used for the particular combination of input values(I1 and I2) received. |