Packet classification

Details Packet classification Packet classification

2004-05-21

2009-06-09

Sefcheck, Gregory B (Department: 2419)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395320, C707S793000

Reexamination Certificate

active

07545809

ABSTRACT:
Methods and apparatus are provided for classifying data packets in a data processing device. In one aspect, packets are classified according to a plurality of sets of processing rules. Each rule defines a plurality of rule ranges, each rule range indicating a range of possible values of a corresponding data item in the packet for which the rule applies, and rule ranges defined in different rule sets correspond to a common set of data items. Independent item searches are performed for respective data items in the packet corresponding to rule ranges defined in the rule sets. The item search for a data item comprises selecting a range identifier corresponding to the value of the data item from a predetermined set of range identifiers for that data item. This set of range identifiers indicates, for all possible values of the data item, which of the rule ranges corresponding to the data item in the rule sets a value intersects. Next, respective final searches are performed for the rule sets based on range identifiers selected by the item searches. The final search for each rule set uses the selected range identifier for each data item corresponding to a rule range defined in that rule set, and predetermined rule data encoding the rule ranges for rules in that set, to identify at least one rule of any rules in the set which are applicable to the data packet. Thus packets can be classified according to multiple rule sets, but the initial item searches are performed only once, for all the rule sets.

REFERENCES:
patent: 6587466 (2003-07-01), Bhattacharya et al.
patent: 6600744 (2003-07-01), Carr et al.
patent: 6633835 (2003-10-01), Moran et al.
patent: 6718326 (2004-04-01), Uga et al.
patent: 7031314 (2006-04-01), Craig et al.
patent: 7061874 (2006-06-01), Merugu et al.
patent: 7149216 (2006-12-01), Cheriton
patent: 7193997 (2007-03-01), Van Lunteren et al.
patent: 7251651 (2007-07-01), Lunteren
patent: 7257590 (2007-08-01), Heiner et al.
patent: 7403999 (2008-07-01), Corl et al.
patent: 2002/0116527 (2002-08-01), Chen et al.
patent: 2002/0191605 (2002-12-01), Lunteren
patent: 2003/0174705 (2003-09-01), Shankar et al.
patent: 2004/0258067 (2004-12-01), Irish et al.
patent: 1128608 (2001-08-01), None
A.P.J.Engernersen and J. Van Lunteren, “Research Report-Prefix based Parallel Packet Classification,” Mar. 6, 2000, 15 pages.
T.V. Lakshman and D. Stiliadis, Bell laboraties, “High Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching,” SIGCOMM 1998, 13 pages.
J. Van Lunteren and Tom Engbersen, IBM Research, “Dynamic Multi-Field Packet Classification,” Zurich Research Laboratory,IEEE pp. 2215-2219, 2002.
Pankaj Gupta and Nick McKeown, “Packet Classification on Multiple Fields,” Computer System Laboratory, Stanford University, SIGCOMM Aug. 1999, 14 pages.

Affiliated with

Also associated with

Rating

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 Packet classification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet classification will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4120902