Method and system for classifying data packets

Details Method and system for classifying data packets Method and system for classifying data packets

2011-01-18

2011-01-18

Ton, Dang T (Department: 2475)

Multiplex communications

Network configuration determination

Using a particular learning algorithm or technique

C709S252000

Reexamination Certificate

active

07872993

ABSTRACT:
Embodiments of the invention provide a method for building a classification tree based on a plurality of rules. Each rule includes multiple fields having different priority levels. The classification tree is built to provide for single pass classification of a received packet according to the multiple rules. The classification tree is built level-by-level, where each level represents one of the priority levels. Building a single level of the classification tree includes: creating, for each of the logical decision paths received from a next higher priority level, a respective sub-tree. The sub-tree includes only nodes and related logical decision paths that are necessary to satisfy rules associated with a respective next higher priority level node. Building of the single level further includes: creating, for each non-lowest priority level, logical decision paths from nodes within the current priority level to a next lower priority level.

REFERENCES:
patent: 6134599 (2000-10-01), Chiu et al.
patent: 6397324 (2002-05-01), Barry et al.
patent: 2003/0193959 (2003-10-01), Lui et al.
patent: 2007/0195714 (2007-08-01), Schales et al.
patent: 1 453 253 (2004-09-01), None
patent: 1 515 501 (2005-03-01), None
Jon Bentley and Bob Sedgewick, “Ternary Search Trees”, http:www.ddj.com/windows/184410528;jsessionid=J5OAHM5V32MVUQSNDLPSKHSCJUNN2JVN?—requestid=115264, Apr. 1, 1998.
Jeremie Bourdon, “Patricia Tries in the Context of Dynamical Systems,” Algorithms Seminar, Mar. 19, 2001, http://algo.inria.fr/seminars/sem00-01/bourdon.html.
Readme for Net-Patricia, “Net: Patricia—Patricia Trie per1 module for fast IP address lookups,” http://search.cpan.org/src/PLONKA/Net-Patricia-1.014/README May 1, 2008.
Harry A. Clampett, Jr., “Randomized Binary Searching With Tree Structures,” Communications of the ACM, vol. 7, No. 3, Mar. 1964, pp. 163-165.
Huan Liu, “Routing Table Compaction in Ternary CAM,” IEEE Micro, Jan.-Feb. 2002, pp. 58-64.
P. Gupta, et al., “Routing Lookups in Hardware at Memory Access Speeds,” IEEE INFOCOM Apr. 1998, vol. 3, pp. 1240-1247, San Francisco.
M. Waldvogel, et al., “Scalable High Speed IP Routing Lookups,” Computer Communication Review, a publication of ACM SIGCOMM, vol. 27, No. 4, Oct. 1997. ISSN#0146-4833.
Sasao T: “Ternary decision diagrams. Survey” Multiple-Valued Logic, 1997. Proceedings., 1997 27thInternational Symposium on Antigonish, NS, Canada May 28-30 1997, Los Alamitos, CA, USA, IEEE Comput. Soc, US, May 28, 1997, pp. 241-250.
International Search Report and the Written Opinion of The International Searching Authority, Or The Declaration, in PCT/US2009/005708, Alcatel Lucent, Applicant, dated Mar. 2, 2010, 15 pages.

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2690478