Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2005-11-29
2005-11-29
Ton, Dang (Department: 2666)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
06970462
ABSTRACT:
The present invention allows for processing classification and/or security filtering rules by using bitmaps as representations. In one instance, the packet header involved in the packet classification is divided into sections (fields) such as 16 bit portions. Once, this is performed, a data lookup table is built for each of the packet header fields. In particular, a bitmap is created representing which filter rules match a certain packet header field value. The created data lookup tables, typically one for each packet header field, are merged to form intermediate level data lookup tables. The intermediate level data lookup tables are continuously merged until one final data lookup table is formed. The result of the final data lookup table represents all the possible packets to be classified. Thus, each final data entry has a bitmap representing the filtering rules that matches this entry. The bitmap can be used to selectively provide a desired result of the classification. For instance, a first matching rule is represented by the first bit set in the bitmap; the best matching rule is determined by processing the bitmap and selecting the most appropriate rule; and a complete set of rules that match is represented by the full bits set in the bitmap.
REFERENCES:
patent: 5027350 (1991-06-01), Marshall
patent: 5473607 (1995-12-01), Hausman 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: 6219706 (2001-04-01), Fan et al.
patent: 6289013 (2001-09-01), Lakshman et al.
patent: 6449256 (2002-09-01), Varghese et al.
patent: 6529508 (2003-03-01), Li et al.
patent: 6643260 (2003-11-01), Kloth et al.
patent: 6665293 (2003-12-01), Thornton et al.
SIGCOMM '99 Session Archive. Sep. 9, 1999.
Pankaj Gupta and Nick McKeown, Packet Classification on Multiple Fields Sep. 2, 1999.
Dawson R. Engler and M. Frans Kaashoek, DPF: Fast, Flexible Message Demultiplexing using Dynamic Code Generation, 1996, pp. 53-59.
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/162,730, filed Sep. 29, 1998, Ullum et al.
U.S. Appl. No. 09/535,810, filed Mar. 28, 2000, Gai et al.
U.S. Appl. No. 09/688,895, filed Oct. 16, 2000, Wu et al.
Cesari and McKenna LLP
Cisco Technology Inc.
Harper Kevin C.
Ton Dang
LandOfFree
Method for high speed 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 Method for high speed packet classification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for high speed packet classification will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3498484