Incremental compilation for classification and filtering rules

Details Incremental compilation for classification and filtering rules Incremental compilation for classification and filtering rules

2007-06-26

2007-06-26

Nguyen, Chau (Department: 2616)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S401000

Reexamination Certificate

active

10170896

ABSTRACT:
A technique classifies packets in a manner that is both deterministic and efficient. A hierarchical arrangement of lookup tables is organized into levels to classify the packets. Entries contained in the lookup tables are incrementally built and added to the lookup tables as packets are classified. A packet is divided into a series of fields and a first-level lookup table is built for each of these fields. Successive-level-lookup tables are then allocated and initialized to contain “missing” entries. When a packet is classified, it is applied to the first-level lookup tables to produce a series of indices. These indices are then applied to the second-level lookup tables to select indices that are the applied to a next-level table and so on until an outcome index is selected from a final-level lookup table. If the entry selected in the second-level lookup table is empty the successive-level entries are built and the classification is retried.

REFERENCES:
patent: 5027350 (1991-06-01), Marshall
patent: 5473607 (1995-12-01), Hausman et al.
patent: 5509006 (1996-04-01), Wilford et al.
patent: 5852607 (1998-12-01), Chin
patent: 5872783 (1999-02-01), Chin
patent: 5881242 (1999-03-01), Ku et al.
patent: 5917820 (1999-06-01), Rekhter
patent: 5951651 (1999-09-01), Lakshman et al.
patent: 6091725 (2000-07-01), Cheriton et al.
patent: 6167445 (2000-12-01), Gai et al.
patent: 6219706 (2001-04-01), Fan et al.
patent: 6243667 (2001-06-01), Kerr et al.
patent: 6282546 (2001-08-01), Gleichauf et al.
patent: 6308219 (2001-10-01), Hughes
patent: 6324656 (2001-11-01), Gleichauf et al.
patent: 6341130 (2002-01-01), Lakshman et al.
patent: 6377577 (2002-04-01), Bechtolsheim et al.
patent: 6529508 (2003-03-01), Li et al.
patent: 6778530 (2004-08-01), Greene
Pankaj Gupta and Nick McKeown, Packet Classification on Multiple Fields, ACM SIGCOMM '99, Sep. 1999, Harvard University, pp. 1-14.
T.V. Lakshman and D. Stiliadis, High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching, 1998, pp. 203-214.
U.S. Appl. No. 09/557,480, Andrew McRae.
U.S. Appl. No. 10/072,824, Li et al.

Affiliated with

Also associated with

Rating

Incremental compilation for classification and filtering rules does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3835463