Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-01-04
2003-03-25
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06539394
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer systems, and more particularly to a method and system for more efficiently testing filter rules.
BACKGROUND OF THE INVENTION
FIG. 1
depicts conventional networks
10
and
20
which may be connected to the Internet
30
. Each network
10
and
20
includes host
12
,
14
and
16
and
22
and
24
, respectively. Each network
10
and
20
also includes a switch
18
and
26
, respectively, and may include one or more servers such as the servers
17
,
19
and
28
, respectively. In addition, each network
10
and
20
may include one or more gateways
13
and
25
, respectively, to the Internet
30
. Not explicitly shown are routers and other portions of the networks
10
and
20
which may also control traffic through the networks
10
and
20
and which will be considered to be inherently depicted by the switches
18
and
26
, respectively, and the networks
10
and
20
in general.
In order to manage communications in a network, such as the network
10
or
20
, filter rules are used. Filter rules are typically employed by switches of the network. A filter rule tests packets which are being transmitted via a network in order to provide a variety of services. A filter rule may test packets entering the network from an outside source to ensure that attempts to break into the network can be thwarted. For example, traffic from the Internet
30
entering the network
10
may be tested in order to ensure that packets from unauthorized sources are denied entrance. Similarly, packets from one portion of a network may be prevented from accessing another portion of the network. For example, a packet from some of the hosts
12
,
14
or
16
may be prevented access to either the server
17
or the server
19
. The fact that the host attempted to contact the server may also be recorded so that appropriate action can be taken by the owner of the network. Filter rules may also be used to transmit traffic based on the priorities of packets. For example, packets from a particular host, such as the host
12
, may be transmitted because the packets have higher priority even when packets from the hosts
14
or
16
may be dropped. Filter rules may also be used to ensure that new sessions are not permitted to be started when congestion is high even though traffic from established sessions is transmitted. Other functions could be achieved based on the filter rule. Filter rules can also interact, based on the priority for the filter rule. For example, a first filter rule may be a default filter rule, which treats most cases. A second filter rule can be an exception the first filter rule. The second filter rule would typically have a higher priority than the first filter rule to ensure that where a packet matches both the first and the second filter rule, the second filter rule will control.
Filter rules test a key in order to determine whether the filter rule will operate on a particular packet. The key that is typically used is the Internet Protocol (IP) header of the packet. The IP header typically contains five fields of interest: the source address, the destination address, the source port, the destination port and the protocol. These fields are typically thirty-two bits, thirty-two bits, sixteen bits, sixteen bits and eight bits, respectively. Thus, the part of IP header of interest is typically one hundred and four bits in length. Filter rules typically utilize these one hundred and four bits, and possible more bits, in order to perform their functions. For example, based on the source and destination addresses, the filter rule may determine whether a packet from a particular host is allowed to reach a particular destination address.
Furthermore, the key often contains additional bits other than the fields of the IP header. For example, a TCP SYN (start of session) packet, which starts a session, may be characterized differently than a TCP packet for an existing session. This characterization is accomplished using bits in addition to those in the IP header. The additional bits may be used by a filter rule which manages traffic through a network. For example, when the network is congested, the filter rule may proactively drop the TCP SYN packet while transmitting TCP packets for existing sessions. These operations allow the network to continue to operate and help reduce congestion. In order to perform this function, however, the filter rule utilizes a SYN packet or the additional bits which characterize a packet as a start packet or a packet from an existing session. Thus, the filter rules typically operate using a key that includes at least some fields of the IP header of a packet and may include additional bits.
The filter rules themselves can generally be broken into two categories. The first type of filter rule utilizes an exact match. The filter rule operates on a packet if the key for the packet exactly matches the criteria for the filter rule. If no exact match exists, then the filter rule is not invoked. Such a filter rule is relatively easy to test keys against.
The second type of filter rule utilizes one or more ranges of values against which test keys are tested. The criteria for such a filter rule are typically a range of values for each field of a key. For example, if a key utilizes the IP header, the criteria for the filter rule would typically include a range of values for one or more of the five fields of the IP header. The values for each of the fields are determined by converting the bits in a field to a binary number. For example, the thirty-two bit source address field can be converted into an integer between zero (all digits of the thirty-two bit binary number are zeroes) and over four billion (all thirty-two digits of the binary number are ones). The filter rule is tested by determining whether keys for incoming packets have values that are within the ranges for the appropriate field.
Thus, filter rules, or portions of filter rules can be broken into two categories. A particular filter rule may use an exact match for each field of a key, may use ranges for each field of a key, or may use some combination of the two. The filter rule is tested by determining whether the key meets the criteria of the filter rule for each field. Where a filter rule uses a range of values as a criterion for the field, that portion of the filter rule is tested by determining whether the corresponding field of the key fits within the range of values. Where a filter rule requires an exact match for a field, that portion of the filter rule is tested by determining whether the corresponding field of the key exactly matches the value of the filter rule.
Although interval-based filter rules, which use ranges of values for criteria for one or more fields, are useful, one of ordinary skill in the art will readily recognize that such a filter rule is difficult to test. In order to test the filter rule against a particular key, it must be determined whether the field of the key is within the corresponding range of values for that field. The range of values for the field may be quite large. In order to explicitly test the key against this range of values, a structure which consumes a relatively large amount of memory must be built. In addition, such a test often requires a relatively large amount of time to complete. Thus, such a filter rule is expensive both in terms of time and memory. Moreover, multiple filter rules are typically used. It becomes extremely expensive to test such a myriad of filter rules.
Accordingly, what is needed is a system and method for testing filter rules which utilize ranges of values for criteria. The present invention addresses such a need.
SUMMARY OF THE INVENTION
The present invention provides a method and system for testing a plurality of filter rules in a computer system. The plurality of filter rules uses at least one range of values in at least one dimension. Each range includes a minimum and a maximum value. A key with a fixed, standardized number of bits such as one hundred and four bits is to be
Calvignac Jean Louis
Jeffries Clark Debs
Verplanken Fabrice
Cockburn Joscelyn G.
Mizrahi Diane D.
Mofiz Apu M.
Sawyer Law Group
LandOfFree
Method and system for performing interval-based testing of... 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 and system for performing interval-based testing of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing interval-based testing of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3020548