Data processing: artificial intelligence – Knowledge processing system
Reexamination Certificate
2000-04-14
2003-10-14
Starks, Jr., Wilbert L. (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
C705S037000
Reexamination Certificate
active
06633860
ABSTRACT:
FIELD AND BACKGROUND OF THE INVENTION
The present invention relates to data classification in general, more particularly to a method for classifying a datum according to a set of filters and more specifically: to a method for classification of packets of information traveling across networks.
Due to the explosive use of networking (i.e. the Internet) in recent years, and with the advance of firewalls and service differentiation, there is an increased demand to build fast message filters machines (routers) that can filter packets according to data at various fields in the packet's header at very high throughputs.
The filtering enables the routers to decide which packet to block, which to forward and at what priority, how much to charge the flow and what service to provide to each packet i.e., on which queue to place the packet. The starting point is the problem description and setup is given by V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “
Fast and scalable layer four switching
”, in Proc. ACM SIGCOMM 98, September 1998.
Each router has a set of filters by which packets should be filtered. Each filter consists of a set of K value-ranges. Each value-range specifies a range of values that are acceptable for a certain parameter in the packet header. A value-range is either exact, a range or star (*).
Exact value range specifies that the corresponding packet parameter has to exactly match the value given in the value-range. Exact range may be used for example to block packets coming from a particular source. A range value-parameter specifies a range of values in which the corresponding packet parameter should reside. A range value may be used to block packets arriving from a subnet. The range may be specified as a prefix or as a minimum and maximum values. A star (*) value-range specifies don't care, i.e., the corresponding packet parameter may have any legal value.
Each message doing through the classifying machine has several parameters by which it is classified such as: destination address, source address, destination port number, source port number and protocol type. This information is contained in fields in the packet header. The classifier has a large set of filters; each one specifies a valid (acceptable) range of values for each of the message's parameters in the packet header.
A packet matches a filter only if the value in each field of the packet complies with the corresponding value range in the filter.
Besides, filters are ranked according to a pre-determined priority. If a packet matches several filters, the highest priority filter it matches, is the filter which applies to the packet.
The specific classification problem for packets on the net is relatively new, but its relevance is increasingly growing because of the exponential increase of traffic across the net.
The best matching filter problem can be stated as a problem in computational geometry. Each filter specifies a K dimensional axis parallel box, and each packet with K parameters defines a point in K dimensions. The corresponding computational geometry problem is as follows: given a point and a set of axis parallel boxes in K dimensions, find the highest priority box in which the point resides. This problem is known as the Stabbing Query Problem in computational geometry. It was described by: M. de Berg, M. van Kreveld, and J. Snoeyink, “
Two and three-dimensional point location in rectangular subdivisions.
”, in J. Algorithms, 18, 256-277, 1995.
The present art with regard to mechanisms for solving such classification problems is described by: T. V. Lakshman and D. Stiliadis, “
High speed policy-based packet forwarding using efficient multidimensional range matching
”, in Proc. ACM SIGCOMM 98. September 1998, and by: Srinivasan et al., 1998. Both references deal with the best matching filter problem and provide efficient solutions to filtering packets according to two fields in the two dimensional case.
The time it takes to solve the best matching filter query problem in Srinivasan et al., 1998 is proportional to w, while using nw size memory, where w is the number of bits in a value (e.g., an IP address) and n is the total number of filters. The time it takes the hardware 30 solution suggested in Lakshman et al., 1998 to solve the two dimensional case, is proportional to (w+log n) and it requires 0(n) space. Note that logarithms herein are base 2 logarithms.
When packet classification is performed on more than 2 parameters tile solutions provided by these papers are not as attractive. The multi-dimensional solution in Srinivasan et al., 1998 suggests to maintain a cross product table, each entry of which corresponds to a set of packet headers that comply with exactly the same subset of filters. An arriving packet is independently and separately classified according to each of its header fields to give it the K coordinates in the cross product table.
If that table entry is in the cache, classification is done. If however that entry is not in the table, a linear search costing O(nK) time is used. The full size of the cross product table is d
1
·d
2
· . . . d
n
, where d
i
is the number of different value-ranges in the i's dimension, i.e., the number of filters with different value-ranges in the i's coordinate.
The solution of Lakshman et al., 1998 is in hardware and requires O(n) steps in the multi-dimensional case. Being a hardware solution it is inflexible, and hard to adapt to changes in the filters, which is a must in networking today.
Applications that rely on packet filtering may add and remove new filters many times during operation. For example, in a network that supports QoS (Quality of Service), a new filter is added to the routers along a path of a new flow that has particular QoS requirements. Therefore, we cannot rely on having all the filters preprocessed and present in a large cross product table stored in memory, or in hardware.
The 2 dimensional solution is not always satisfactory since there may be situations that a value-range of ranges is used in more than 2 values of the filters. For example in virtual networks it may be wanted to allow traffic from a range of sources to a range of destinations over a range of ports and protocols to go through the routers of our virtual private network.
In the general case, for filters with K dimension, the set of n filters is represented as:
filter
1
: [l
i
l
,r
I
1
]x . . . x[l
K
1
,r
K
1
]
filter
2
: [l
l
2
,r
1
2
]x . . . x[l
K
2
,r
K
2
]
filter n: [l
l
n
,r
1
n
]x . . . x[l
K
n
,r
K
n
]
where the l and the r are the lower and the upper boundaries respectively of the filter in the appropriate dimension.
The packet is considered to be a point in K dimensions. The parameters of the packet received are: (&ugr;
1
, &ugr;
2
, . . . &ugr;
K
). These are called the coordinates of the packet.
The problem is then to find the highest priority filter in which the packet's parameters reside, i.e.: the highest priority filter, j such that: [l
1
l
≦&ugr;
1
≦r
1
l
]and . . . and[l
K
j
≦&ugr;
K
≦r
K
j
]
The packet satisfying these inequalities is said to stab filter j. To solve the problem of the filters being stabbed by the packet, several methods have been suggested which are briefly described below:
a. Linear Scan
The most straightforward approach to solve the problem is to sort the filters in decreasing order of priority. A query is then carried out by scanning all the filters in the sorted order, each one in all dimensions, until the first filter that the packet stabs in all the dimensions is found. Such a solution requires linear space, linear O(Kn) query time, and at most O(log n) time to add a new filter to the sorted list. Another naive approach is to first find all the filters that the packet matches only in the first parameter, i.e., all the filters such that [l
l
≦&ugr;
I
≦r
l
]. Namely, all the filters that the packet stabs in the first coordinate. This is shown in
FIG. 2A
to which reference is n
Afek Yehuda
Bremler Anat
Har-Peled Sariel
Friedman Mark M.
Ramot At Tel Aviv University Ltd.
Starks, Jr. Wilbert L.
LandOfFree
Method for fast multi-dimensional packet classification does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for fast multi-dimensional packet classification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for fast multi-dimensional packet classification will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3172358