Systems and methods for packet filtering

Details Systems and methods for packet filtering Systems and methods for packet filtering

2002-02-14

2004-05-11

Hsu, Alpus H. (Department: 2665)

Multiplex communications

Diagnostic testing

Determination of communication parameters

C370S392000, C370S395320, C711S216000, C711S202000, C713S152000

Reexamination Certificate

active

06735179

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to the field of data networking. In particular, the invention relates to technologies for packet and flow identification in networks.
DESCRIPTION OF THE RELATED ART
Longest match searches are a ubiquitous feature in data networking technology, particularly for packet routing. For instance, in IP routing, a destination address for a given packet is matched against a routing table; amongst the multiple entries that match the destination address, the router picks the entry which has the longest subnet mask.
Given the prevalence of the longest prefix matching techniques, routing and packet processing hardware are typically implemented to support such algorithms. However, it may be desirable to match packets against additional parameters in a table by use of techniques other than longest match. For instance, network firewalls typically identify and filter packets based on numerous parameters in the packet headers. Moreover, rules that are implemented by firewalls for packet filtering are typically inserted through an interface such as a Command Line Interface, or CLI. Rules are typically presented to such interfaces in priority order, wherein the order of priority—rather than the length of a pattern match—dictates which rule is matched to the packet.
It may be desirable to accelerate packet processing devices such as a network firewall by use of hardware which implement longest match searches; however, such a device should be able to accept rules which are presented in priority order. As such, there is a need for technology to convert priority-based rules into equivalent rules suitable for a longest match search.
Another difficulty with prior art packet processing technologies is the rigidity and inflexibility, which precludes the use of such technology for general purpose packet matching. Fast packet processing is typically achieved by the use of dedicated hardware. Some routers, for instance, include customized ASICs for packet processing; as these ASICs are dedicated to specific networking tasks, they cannot be reprogrammed to search for different types of patterns in packets. Recent years have witnessed the introduction of programmable network processors. These network processors are limited in their programmability, however, as their data structures are generally fixed in size and are dedicated to specific types of searches on packets, such as longest matches on specific networking parameters. As such, there is a need to implement new types of data structures in network processors which allow searches on arbitrarily many networking parameters of different lengths.
SUMMARY OF THE INVENTION
The invention includes systems and methods for converting priority based rules into isomorphic longest match rules. In some embodiments of the invention, rules for packet processing are presented to a networking device in priority order. These rules may be presented to the networking device through an interface such as a Command Line Interface, or CLI. Alternatively, the rules may be presented by one or more software applications; these software applications may, in some embodiments, reside at least partially on the networking device itself.
In some embodiments of the invention, the networking device includes a hardware and/or software layer, referred to as a forwarding layer, for accelerating packet processing; the forwarding layer includes hardware and/or software designed to perform longest match searches on packets. The prioritized rules are converted into a data structure for the forwarding layer, which may include one or more longest match trees; this transformation ensures that for any given packet entering the networking device, a longest match search performed by the forwarding layer on the data structure is equivalent to a priority order search on the prioritized rules.
These and other embodiments are described in greater detail infra.


REFERENCES:
patent: 5950195 (1999-09-01), Stockwell et al.
patent: 6341309 (2002-01-01), Vaid et al.
patent: 2002/0009076 (2002-01-01), Engbersen et al.
patent: 2002/0157020 (2002-10-01), Royer

Affiliated with

Also associated with

Rating

Systems and methods for packet filtering does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Systems and methods for packet filtering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for packet filtering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3237967