Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1999-02-08
2004-02-10
Najjar, Saleh (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S229000, C709S239000, C709S240000, C709S241000, C709S242000, C370S351000, C370S389000, C370S428000
Reexamination Certificate
active
06691168
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of computer networking. In particular the present invention discloses a method and apparatus for quickly processing network packets that are tested with a large number of rules.
BACKGROUND OF THE INVENTION
The Internet is a global interconnection of computer networks that share a set of well-defined data communication protocols. Specifically, most computer networks coupled to the global Internet communicate using the Transport Control Protocol (TCP) and Internet Protocol (IP).
A very large portion of the computers communicate on the global Internet are coupled to a local area network (LAN) that is coupled to the global Internet with an Internet gateway. The Internet gateway handles all communication between computers on the local area network and computers out on the global Internet. The Internet gateway may perform many different functions such as network address translation, network caching, routing, and packet filtering.
Packet filtering is the task of examining each packet to apply a set of filtering rules. Each packet-filtering rule specifies a particular packet filtering policy. For example, all packets incoming from the Internet that are destined for vulnerable server ports may be discarded in order to protect the internal servers on the local area network.
The number of packet filtering rules that are needed depends on the particular application. In simple packet filtering routers for small or home routers, the number of packet filtering rules is relatively small. However, an internet service provider (ISP) that provides classes of service for the internet service provider's customers, the internet service provider will need many thousands of packet filter rules to implement the class of service priority and other customer features.
There are several different current implementations of packet filtering rule processors. The simplest implementation of a rules processor is a linear searching rule processor. In such an implementation, the linear rule processor tests each received packet against each rule in the list of packet filtering rules. The time required to perform this type of rule processing is directly proportional to the number of packet filtering rules. This type of linear rule processing is not feasible for any system with a large number of packet-filtering rules.
To provide faster rule processing, improved methods of applying packet-filtering rules were introduced. One improved method is known as “rule splitting.” A rule splitting system divides the rules into several different sets of rules. When a packet is received, one or more aspects of the packet are examined to determine which subset of rules should be applied. For example, a rule splitting type of rule processor may only examine the Source and/or Destination ports of each packet in order to determine which set of rules to apply. Rule splitting types of rule processors are difficult to implement because rules have ranges associated with them.
Search trees provide another method of improving rule processing speed. Search trees divide the rules into a preprocessed organized format that improves the rule processing to a speed that is a logarithmic function of the number of rules in each dimension. This type of searching works well, but still does not provide a solution that is viable for high-speed network applications that require many thousands of rules. It would therefore be desirable to have an improved network rule processor that can process thousands of network rules.
SUMMARY OF THE INVENTION
The present invention introduces a high-speed rule processing method that may be used for packet filtering. The high-speed rule processor pre-processes a set of packet filtering rules such that the rules may be searched in parallel by a set of independent search units.
In the rule pre-processing of the method of the present invention, a set of packet filtering rules is first divided the rules into N dimensions. The N dimensions are orthogonal aspects of each packet that may be examined and tested in each rule. Each of the N dimensions are then divided into a set of dimension rule ranges wherein each rule range defines a non-overlapping contiguous range of values in a particular dimension and the rules that may apply to packets that fall within that rule range. Each rule range may be assigned an R-length bit vector that specifies the rules that may apply to packets that fall within that rule range. If the rules are prioritized wherein only the highest priority rule will be applied then such bit vectors will be organized into an order bit vector wherein the highest priority rule is at the beginning of the rule bit vector and the lowest priority rule will be at the end of the rule bit vector. The rule preprocessing is completed by creating a search structure (such as a look-up table, Patricia tree structure, or binary tree structure) for each of the N dimensions. Each search structure may be used by an independent search unit such that all N dimensions may be searched concurrently.
The packet processing method of the present invention activates the N independent search units to search the N pre-processor created search structures. In one embodiment, the output of each of the N search structures will be an R-length bit vector. In such an embodiment, the N output bit vectors are logically ANDed together to produce a final rule bit vector that is used to select the rule or rule to be applied. If the rules are prioritized, then only the first matching rule, (the highest priority rule) will be applied.
REFERENCES:
patent: 5463777 (1995-10-01), Bialkowski et al.
patent: 5574910 (1996-11-01), Bialkowski et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 5951651 (1999-09-01), Lakshman et al.
patent: 6012061 (2000-01-01), Sharma
patent: 6157955 (2000-12-01), Narad et al.
patent: 6170012 (2001-01-01), Coss et al.
patent: 6223172 (2001-04-01), Hunter et al.
patent: 6289013 (2001-09-01), Lakshman et al.
patent: 6341130 (2002-01-01), Lakshman et al.
patent: 6389532 (2002-05-01), Gupta et al.
patent: 6412000 (2002-06-01), Riddle et al.
patent: 6457051 (2002-09-01), Riddle et al.
Lakshman, T.V. et al., “High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching”,Computer Communication Review, vol. 28, No. 4, Oct. 1998, ISSN# 0146-4833, 12 pages.
Bal Subhash
Iyer Raghunath
Iyer Sundar
Rao Ramana
Johansen Dag
Najjar Saleh
PMC-Sierra
Stattler, Adeli, & Johanson, LLP
LandOfFree
Method and apparatus for high-speed network rule processing 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 apparatus for high-speed network rule processing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for high-speed network rule processing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3337932