Method and means for classifying data packets

摘要

For a system in which data packets are to be handled according to one of several rules, depending on two (or more) criteria present in each packet, such as source and destination addresses, a classification method is disclosed that allows to determine the applicable rule by a longest-matching-prefix search operation.Range tokens of non-uniform length are assigned to basic ranges of criterion values so that each combination of input values from a packet can be represented by a particular variable length combination of range tokens. A search tree containing stored rule identifiers is so designed that each particular range token combination, used as input for a longest-matching-prefix lookup operation, will provide the required identifier. Different range token combinations having the same prefix can use the same path to one stored rule identifier, so that this method reduces the storage and time requirements for the classification procedure and allows simple updating when rules change.