Methods for performing packet classification

Details Methods for performing packet classification Methods for performing packet classification

2005-03-31

2010-02-23

Nguyen, Steven H (Department: 2416)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395320, C370S395420

Reexamination Certificate

active

07668160

ABSTRACT:
Methods for performing packet classification. In one embodiment, packets are classified using a rule bit vector optimization scheme, wherein original rule bit vectors in recursive flow classification (RFC) chunks are optimized by removing useless bits that have no effect on the ultimate rule identified by an associated RFC lookup process. The unique optimized rule bit vectors for associated chunks are then cross-producted to produce an optimized downstream chunk. In another embodiment, a rule database splitting scheme is employed. Under this technique, split criteria is defined to split a rule database, such as splitting based on a particular field value or range. A respective set of downstream chunks is then generated for each partition, beginning with the chunks in a split phase. The applicable rule bit vectors for the chunks associated with a common group and partition are identified, and then unique applicable rule bit vectors for those chunks are cross-producted to produce downstream chunks.

REFERENCES:
patent: 5951651 (1999-09-01), Lakshman et al.
patent: 6266706 (2001-07-01), Brodnik et al.
patent: 6289013 (2001-09-01), Lakshman
patent: 6600744 (2003-07-01), Carr et al.
patent: 6970462 (2005-11-01), McRae
patent: 7054315 (2006-05-01), Liao
patent: 7136926 (2006-11-01), Iyer et al.
patent: 7236493 (2007-06-01), McRae
patent: 7325074 (2008-01-01), McRae
patent: 2002/0089937 (2002-07-01), Venkatachary et al.
patent: 2002/0191605 (2002-12-01), Lunteren et al.
patent: 2003/0108043 (2003-06-01), Liao
patent: 2004/0170170 (2004-09-01), Joung et al.
patent: 2005/0262127 (2005-11-01), Mishra et al.
patent: 2006/0164980 (2006-07-01), Guru
Baboescu et al., “Aggregated Bit Vector Search Algorithms for Packet Filter Lookups”, Dept. of Computer Science and Engineering, pp. 1-26.
Gupta et al., “Packet Classification using Hierarchical Intelligent Cuttings”, Computer Systems Laboratory, Stanford University.
Singh et al., “Packet Classification Using Multidimensional Cutting”, SIGCOMM'03, Aug. 25-29, 2003, Karlsruhe, Germany, pp. 213-224.
“42P21553 OA Mailed Mar. 4, 2008 for U.S. Appl. No. 11/096,960”, Whole Document.
Non-Final Office Action for U.S. Appl. No. 11/170,230 mailed Feb. 10, 2009; 21 pages.
Haoyu Song and John W. Lockwood, “Efficient Packet Classification for Network Intrusion Detection using FPGA”, Feb. 20, 2005, FPGA '05, ACM, (Feb. 20, 2005), Whole Document.
Spitznagel, Edward W., “Compressed Data Structures for Recursive Flow Classification”, May 16, 2003, Washington University in St. Louis, (May 16, 2003), Whole Document.
USPTO, “Final Office Action for U.S. Appl. No. 11/170,230 dated Sep. 1, 2009.”, (Sep. 1, 2009), Whole Document.
USPTO, “Office Action for U.S. Appl. No. 11/170,230 mailed Feb. 10, 2009”, (Feb. 10, 2009), Whole Document.

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4177989