Software management tree implementation for a network processor

Details Software management tree implementation for a network processor Software management tree implementation for a network processor

2006-09-12

2006-09-12

Kindred, Alford W. (Department: 2163)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C715S252000, C717S143000

Reexamination Certificate

active

07107265

ABSTRACT:
Novel data structures, methods and apparatus for a Software Managed Tree (SMT) which provides a mechanism to create tree structures that follow a search mechanism defined by a control point processor. The search mechanism does not require storage on the previous pointer and uses only a forward pointer along with a next bit or group of bits to test thereby reducing storage space for nodes. The search mechanism processes multiple filter rules for an application without requiring multiple searches and also allows various filter rules to be chained. Two patterns of the same length are stored in each leaf to define a range compare. A compare at the end operation is either a compare under range or a compare under mask. In a compare under range, the input key is checked to determine if it is in the range defined by the two patterns. In a compare under mask, the bits in the input key are compared with the bits in a first leaf pattern under a mask specified in a second leaf pattern.

REFERENCES:
patent: 5857196 (1999-01-01), Angle et al.
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 2002/0099855 (2002-07-01), Bass et al.
patent: 2003/0093613 (2003-05-01), Sherman
patent: 02-260334 (1990-10-01), None
patent: 05-167640 (1993-07-01), None
patent: 10-162013 (1998-06-01), None
patent: 10-257066 (1998-09-01), None
patent: 2001-357071 (2001-12-01), None
patent: 96/00945 (1996-01-01), None
“Address Resolution for IP Routing”, Kenshin Yamada et al., Technical Report of the IEICE, SSE98-72, IN98-53(2), CS98-69(Sep. 1998), pp. 1-6.
“Study on Efficient Cache Structures Providing Policy-Based Servies in IP Routers”, Shingo Ata et al., Technical Report of the IEICE, CS99-155, CQ99-78(Feb. 2002), pp. 43-48.
Abstract of Masami Shishibori, et al., “Improvement of Binary Digital Search (BDS)—Tree Using Hierarchical Structures”, The Institute of Electronics, Information and Communication Engineers, Information and Communication Engineers, D-I, vol. J79-D-I, No. 2, Feb. 1996, pp. 79-87 (Abstract in English).

Affiliated with

Also associated with

Rating

Software management tree implementation for a network processor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Software management tree implementation for a network processor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Software management tree implementation for a network processor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3567916