Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
2000-04-10
2004-01-06
Maung, Zarni (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C707S793000, C711S118000
Reexamination Certificate
active
06675223
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to computer networks, and in particular, to a network processor for managing network traffic that uses static and dynamic matching trees for processing frames.
2. Description of the Related Art
Computer networks have evolved to a point where switch routers are insufficient to handle:complex network routing and filtering requirements. Network processors, such as the International Business Machines (IBM) Network Processor (NP) have been developed to fill this need. Utilizing a connection similar to that of a network switch, an NP provides a level of control and flexibility that surpasses that of the network switch. Parallel lookup operations can be performed on a frame, complex modifications can be performed on packets, and policies can be managed at complex levels. Multiple processors are used to achieve a very high frame processing throughput.
Instructions for managing frame routing in an NP, known as “picocode,” reside in memory but are directly used by the hardware to efficiently process frames according to a fixed set of rules. The rules are entered by administration software and compiled into picocode that drives the logical engines for controlling frame routing, frame filtering and Quality of Service (QoS) requests.
Two types of classifier trees can be used to implement the frame processing commands: Software Managed Trees (SMTs) and Fixed Match Trees (FMTs). SMTs provide the capability of performing operations on ranges, while FMTs only apply to a specific values i.e. Media Access Control (MAC) layer addresses. The advantage of SMTs is the support of range-operations that are required to perform such functions as Internet Protcol (IP) sub-netting, the disadvantage is they cannot be easily updated on-the-fly. Since the SMT is compiled from a set of complex rules, it cannot be updated by changing a single leaf. The entire SMT needs to be recompiled and downloaded to a pico-processor. Therefore, the rules implemented in the SMT are typically static. In contrast, dynamic rules may be implemented in an FMT. Since the rules operate on fixed values, a single dynamic rule entry may be added or deleted. Dynamic rule processing in FMTs is faster than static rule processing in SMTs, since the hashing operation to determine actions to perform in response to a given frame is direct. SMTs must perform range checking and determine if a given frame value is within the actionable range.
The present disclosure provides an improved method for processing frames by combining dynamic trees with static trees allowing use of both SMTs and FMTs.
SUMMARY OF THE INVENTION
The objective of using dynamic and static trees together to control network frame processing is achieved in a network processor. A set of dynamic classifiers is searched with a frame key to determining whether or not a dynamic classifier for processing the frame exists within the set of dynamic classifiers. If the dynamic classifier does not exist, a set of static classifiers is searched to find a static classifier having a rule for processing the frame. If a dynamic classifier was found, it may contain an indication to search or not search the static classifiers. A set of inhibit keys may also be provided as a bit field resulting from actions taken in response to dynamic classifier rules. These inhibit keys may be used to prevent duplicate actions from being generated by static classifiers that are found having actions for processing the frame.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 6154775 (2000-11-01), Coss et al.
patent: 6173364 (2001-01-01), Zenchelsky et al.
patent: 6233686 (2001-05-01), Zenchelsky et al.
patent: 6289013 (2001-09-01), Lakshman et al.
patent: 6341130 (2002-01-01), Lakshman et al.
patent: 6347376 (2002-02-01), Attwood et al.
patent: 6404752 (2002-06-01), Allen, Jr. et al.
patent: 6449256 (2002-09-01), Varghese et al.
patent: 6460120 (2002-10-01), Bass et al.
patent: 6473434 (2002-10-01), Araya et al.
patent: 6505192 (2003-01-01), Godwin et al.
Lakshman et al, High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching, 1998, ACM Press, 203-214.*
Suri et al, Packet Filtering in High Speed Networks, 1999, ACM Press, 969-970.
Corl, Jr. Everett Arthur
Jeffries Clark Debs
Verilli Colin Beaton
Bracewell & Patterson
Chang Jung-won
International Business Machines - Corporation
Maung Zarni
LandOfFree
Method and apparatus for processing frames using static and... 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 apparatus for processing frames using static and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for processing frames using static and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3216536