US20060039372A1 - Method and apparatus for providing multi-protocol, multi-stage, real-time frame classification - Google Patents

Abstract

A multi-protocol, multi-stage, real-time frame classifier is disclosed. A preliminary multi-protocol frame composition analyzer is provided for performing preliminary multi-protocol frame classification for incoming frames. A parsing instruction generator is provided for processing at least the incoming frame and the preliminary multi-protocol frame classification to provide parsing instructions. A multi-stage parsing engine provides multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame. An advanced level of data extraction is provided across various frame protocols without imposing a performance penalty. Longest prefix match searches and/or direct lookup searches are supported. Moreover, conditional extractions, instruction branching, multi-stage processing are all performed in real time.

Description

CROSS-REFERENCE TO OTHER PATENT APPLICATIONS
• The following co-pending patent applications of common assignee contains some common disclosure:
• “System And Method For Providing Transformation Of Multi-Protocol Packets In A Data Stream,” Attorney Docket No. 1305.1-US-01, filed concurrently herewith, which is incorporated herein by reference in its entirety;
• “System And Method For Policing Multiple Data Flows And Multi-Protocol Data Flows,” Attorney Docket No. 1305.6-US-01, filed concurrently herewith, which is incorporated herein by reference in its entirety;
• “System And Method For Hierarchical Policing Of Flows And Subflows Of A Data Stream,” Attorney Docket No. 1305.10-US-01, filed concurrently herewith, which is incorporated herein by reference in its entirety.
BACKGROUND OF THE INVENTION
• 1. Field of the Invention
• This invention relates in general to a method and apparatus for handling packets, and more particularly to a method and apparatus for providing multi-protocol, multi-stage, real-time frame classification.
• 2. Description of Related Art
• Standards-based LAN systems work reasonably well at transfer rates up to about 100 Mbps. At transfer rates above 100 Mbps, providing the processing power required by a packet switch interconnecting a group of networks becomes economically challenging for the performance levels desired. This difficulty in economically “scaling up” performance is beginning to cause restrictions in some user's planned network expansions. Also, today's data networks do not provide network managers with enough control over bandwidth allocation and user access.
• Next generation networks are expected to support “multimedia” applications with their much greater bandwidth and real-time delivery requirements. The next generation networks should also have the ability to dynamically adjust the network so that it can guarantee a predetermined amount of bandwidth for the requested service level agreement. Additionally, it is desirable to provide access, performance, fault tolerance and security between any specified set of end systems as directed by the network's manager.
• One of the biggest opportunities for service providers today is to provide IP-based internetworking services to meet the exponential growth in demand from both business and residential customers. For example, voice and video based multimedia applications are expected to become a significant portion of the Internet. However, support for multimedia applications in the current Internet is at its initial stages. To fulfill the promise of remote work styles and B2C (Business-to-Consumer) e-commerce, broadband access for small offices, home offices and residences is critical. In today's information-based society, many individuals desire remote data connectivity to an office or remote data site. Remote individuals desire remote and transparent connectivity to the corporate office or a remote data site, including connectivity to the corporate office local area network (LAN).
• Broadband systems are being developed and implemented to provide higher capacities, more efficient use of bandwidth, and the ability to integrate voice, data, and video communications. The number and type of communication services has also been rapidly expanding, including the above-mentioned “multimedia” services such as video teleconferencing, video/movies on demand and the like.
• While broadband access is becoming more common, there are many competing technologies for delivering broadband access. For example, there are a number of standards used in digital telecommunications, including TCP/IP, Ethernet, HDLC, ISDN, ATM, X.25, Frame Relay, Digital Data Service, FDDI (Fiber Distributed Data Interface), T1, xDSL, Wireless, Cable Modems, and Satellite among others. Many of these standards employ different packet and/or frame formats. The term “frame” generally refers to encapsulated data atOSI layer 2, including a destination address, control bits for flow control, the data or payload, and CRC (cyclic redundancy check) data for error checking. The term “packet” generally refers to encapsulated data atOSI layer 3. However, in the present application, the term packet and frame and cell will be used interchangeably.
• In general, a packet format or frame format refers to how data is encapsulated with various fields and headers for transmission across a network. For example, a data packet typically includes an address destination field, a length field, an error correcting code (ECC) field or cyclic redundancy check (CRC) field, as well as headers and trailers to identify the beginning and end of the packet. The terms “packet format” and “frame format”, also referred to as “cell format”, are generally synonymous.
• In order for a router or gateway to be able to interface between communication systems employing different packet or frame formats, the node element, such as the router or gateway, is required to perform a packet conversion to convert the data from a first packet format used by the first communication system to a second packet format used by the second communication system. As the number of possible packet formats or types increases, the amount of logic required to convert between these different packet formats also increases.
• Furthermore, the emergence of high speed networking technologies, e.g., ATM cell-based technology, xDSL, cable modem technology and Gigabit Ethernet, makes possible the integration of multiple types of traffic like speech, video and data over the same communication network. The communication circuits which may be shared in such network include transmission lines, program controlled processors, nodes or links, and data or packet buffers. An access node in such network should thus be designed for supporting the access of the user existing communication equipment with their corresponding protocols as well as for accommodating new equipment. Accordingly, it is essential to know the different requirements of each traffic in order to optimize the different processes.
• Real-time traffic has more constraining requirements than non-real-time ones, i.e., end-to-end delay and jitter. It is necessary to be able to give priority to the real-time packets in order to minimize these delays. Meanwhile, the packet loss must be guaranteed both for real-time and non-real-time applications that have reserved bandwidth in the network while it is not mandatory for non-reserved type of traffic.
• Therefore, it is important to provide the network components (i.e. nodes or links) with mechanisms that control the priority of the packets and process them so that the desired quality of service (QOS) to their corresponding connections is guaranteed. It is also important to offer the same service to connections having the same QOS requirements by providing them with a fair share of the network transmission capacities.
• As can be seen, the technological convergence of computer and communication networks has led to more complex transmission of data, voice, images etc. Depending on the network, various protocols are hierarchically ordered, resulting in a vertical stack of protocols. Each of these protocols interact with the adjacent ones to organize the information exchange and transmission between remote systems, such as host computers. If an application program, for example, which runs on a first system requires the use of data of a second system, an exchange of information takes place. When the second system receives a request to send specific information, this information has to be transmitted from the highest protocol level, e.g., the application layer, down through all lower protocol levels prior to being sent along the physical link. Each protocol layer adds its own layer-specific connection information to data packets containing the request information that are received from the higher layer.
• Thus, a communication connection between two systems is defined in a packet header, hereinafter referred to as protocol header, by the aggregate of fields carrying connection information of the vertical protocol stack. Nevertheless, when receiving a data stream made up of data packets at a receiver site, prior to forwarding, routing, multiplexing or compressing the data packets, the protocol header has to be scanned to extract information to at least identify the connection information.
• A fundamental function in processing packets in networking communications is filtering. Filtering is the process of applying a set of rules to an incoming packet in order to determine its forwarding characteristics. Advanced frame identification and/or marking may be used to identify the entire frame composition layer by layer. The rules that are applied to perform the filtering can vary. For example, plural criteria may be used in a given table lookup. Another example uses the results of a one table lookup with certain packet protocol criteria to generate subsequent table lookups. Current methods used to obtain this type of filtering are implemented in software and thereby do not scale with the bandwidth in today's networks. Furthermore, these operations consume a considerable amount of time in the protocol processing, in particular when dealing with many connections, e.g., in a server, or when processing multimedia data streams. The result of this is cumbersome and conventional filtering applied to the high-speed networks leads to network degradation.
• Hardware implementation of a routing table for the translation of packet identifiers into an appropriate physical output link has been described in “Putting Routing Tables in Silicon”, T.-B. Pei and C. Zukowski, IEEE Network Magazine, January 1992, pp. 42-50. This approach is mainly characterized in that a Content Addressable Memory (CAM) is employed to match connection information in the header of a single protocol. In addition, the advantages and disadvantages of CAMs versus conventional Random Access Memories (RAM), used to store routing information, have been evaluated by Pei and Zukowski.
• In addition to the above-mentioned problems, another problem associated with using a CAM to match connection information in the header. To make filtering decisions, a CAM table is built. The CAM table contains search words. The table may contain fields for the IP source, the type of service, the TCP source port, etc. However, as search words are built, the amount of memory required explodes exponentially.
• Neither of the two systems above, both of them relating to the solution of sub-problems, nor the known software approaches allow fast processing of multiple protocols. A wide variety of communication protocols exist, but all tend to fall into one of the following groups: LAN protocols, WAN protocols, network protocols, and routing protocols. LAN protocols operate at the network and data link layers of the OSI model and define communication over the various LAN media. WAN protocols operate at the lowest three layers of the OSI model and define communication over the various wide-area media. Routing protocols are network-layer protocols that are responsible for path determination and traffic switching. Finally, network protocols are the various upper-layer protocols that exist in a given protocol suite. The processing of protocol headers and the recognition of different protocol types in real time is a very complicated and difficult undertaking. In almost all network systems, header processing is still a major CPU-cycle (Central Processor Unit) consuming activity. It can be seen that there is a need for a method and apparatus for providing multi-protocol, multi-stage, real-time frame classification.
SUMMARY OF THE INVENTION
• To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method and apparatus for providing multi-protocol, multi-stage, real-time frame classification.
• The present invention solves the above-described problems by providing an advanced level of data extraction across various frame protocols. Longest prefix match searches and/or direct lookup searches are supported. Moreover, conditional extractions, instruction branching, and multi-stage processing are all performed in real time.
• A method in accordance with the principles of the present invention includes performing preliminary multi-protocol frame classification for incoming frames, processing at least the incoming frame and the preliminary multi-protocol frame classification to provide parsing instructions, and providing multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame.
• Other embodiments of a method in accordance with the principles of the invention may include alternative or optional additional aspects. One such aspect of the present invention is that the performing preliminary multi-protocol frame classification further includes resolving a composition for the incoming frame.
• Another aspect of the present invention is that the processing further includes storing an incoming frame in a frame buffer, generating the parsing instructions for the incoming frame based upon the multi-protocol frame classification and aligning the generated parsing instructions with a frame selected from the incoming frames stored in the frame buffer.
• Another aspect of the present invention is that the providing multi-stage parsing of the incoming frame further includes reading at least a portion of the incoming frame from a frame buffer, interpreting the parsing instructions and executing macros for performing parsing functions on at least the portion of the incoming frame using the interpreted parsing instructions.
• Another aspect of the present invention is that the providing multi-stage parsing of the incoming frame further includes generating extraction instructions in response to the at least incoming frame and the preliminary multi-protocol frame classification, using the extraction instructions to produce search queries, and applying the search queries against a memory to produce the search results.
• Another aspect of the present invention is that the using the extraction instructions further comprises conditional extraction.
• Another aspect of the present invention is that conditional extraction comprises determining whether extracted bits of data from the packet meet a predetermined criteria.
• Another aspect of the present invention is that the providing multi-stage parsing of the incoming frame further includes reprocessing the search results to generate refined parsing instructions and parsing of the incoming frame according to the refined parsing instructions to generate refined search results, the refined search results providing greater information about the incoming frame.
• Another aspect of the present invention is that the processing at least the incoming frame and the preliminary multi-protocol frame classification further includes processing the search results, the incoming frame and the preliminary multi-protocol frame classification to provide refined parsing instructions.
• Another aspect of the present invention is that the parsing instructions includes a location identifier and an associated instruction to be applied to the frame at the position identified by the location identifier.
• Another aspect of the present invention is that the frame includes one of a plurality of frame protocols, the performing preliminary multi-protocol frame classification further including classifying a protocol identity.
• Another aspect of the present invention is that the performing preliminary multi-protocol frame classification further includes identifying each layer protocol and writing the frame into memory along with a protocol layer code.
• Another aspect of the present invention is that providing multi-stage parsing of the incoming frame further includes using the protocol layer code as a start vector into an instruction memory, the instruction memory containing instructions for parsing the frame and pointers to access selected words of the frame in a frame buffer.
• Another aspect of the present invention is that the performing preliminary multi-protocol frame classification further includes identifying each layer protocol and writing the frame into memory along with a protocol layer code, the method further including processing the instructions from the instruction memory, resolving the pointers according to the protocol layer table and aligning the frame data with the instruction words.
• Another aspect of the present invention is that the search results are fed back to an instruction controller to be used as data that a parsing engine can parse through a data pipe.
• Another aspect of the present invention is that the memory includes a content addressable memory and the search queries are used to search the content addressable memory.
• Another aspect of the present invention is that the memory includes a static random access memory and the search queries are indexed directly to a static random access memory.
• Another aspect of the present invention is that the method further includes providing a parser instruction set in the instruction memory to define microcode used for generating the parser instructions.
• Another aspect of the present invention is that the method further includes forwarding the frame and the search results.
• Another aspect of the present invention is that the search results include the frame classification.
• Another aspect of the present invention is that the search results are fed back to an instruction controller to be used as a start vector for subsequent processing stages.
• Another aspect of the present invention is that providing multi-stage parsing of the incoming frame further comprises performing conditional branching, the conditional branching allowing specific instructions to be performed based upon satisfaction of a predetermined criteria.
• In another embodiment of the present invention, a multi-protocol, multi-stage, real-time frame classifier is provided. The multi-protocol, multi-stage, real-time frame classifier includes a preliminary multi-protocol frame composition analyzer for performing preliminary multi-protocol frame classification for incoming frames, a parsing instruction generator for processing at least the incoming frame and the preliminary multi-protocol frame classification to provide parsing instructions and a multi-stage parsing engine for providing multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame.
• Another aspect of the present invention is that the preliminary multi-protocol frame classifier resolves a composition for the incoming frame.
• Another aspect of the present invention is that the parsing instructions generator processing further includes a frame buffer for storing an incoming frame, an instruction generator for creating the parsing instructions for the incoming frame based upon the multi-protocol frame classification and a data pipe for aligning the generated parsing instructions with a frame selected from the incoming frames stored in the frame buffer.
• Another aspect of the present invention is that the multi-stage parsing engine reads at least a portion of the incoming frame from a frame buffer, interprets the parsing instructions and executes macros for performing parsing functions on at least the portion of the incoming frame using the interpreted parsing instructions.
• Another aspect of the present invention is that the multi-stage parsing engine generating extractions instructions in response to the at least incoming frame and the preliminary multi-protocol frame classification.
• Another aspect of the present invention is that the multi-stage parsing engine performs conditional extractions using the extraction instructions.
• Another aspect of the present invention is that conditional extraction comprises determining whether extracted bits of data from the packet meet a predetermined criteria.
• Another aspect of the present invention is that the multi-stage parsing engine further includes an extractor for using the extraction instructions to produce search queries and a memory for applying the search queries against to produce the search results.
• Another aspect of the present invention is that the multi-protocol, multi-stage, real-time frame classifier further includes a feedback path for allowing the search results to be reprocessed to generate refined parsing instructions that are used by the parsing engine to generate refined search results, the refined search results providing greater information about the incoming frame.
• Another aspect of the present invention is that the parsing instructions generator processes the search results, the incoming frame and the preliminary multi-protocol frame classification to provide refined parsing instructions.
• Another aspect of the present invention is that the parsing instructions include a location identifier and an associated instruction to be applied to the frame at the position identified by the location identifier.
• Another aspect of the present invention is that the frame includes one of a plurality of frame protocols, the preliminary multi-protocol frame classifier classifying the incoming frame to identify a protocol identity.
• Another aspect of the present invention is that the preliminary multi-protocol frame classifier identifies each layer protocol and writes the frame into memory along with a protocol layer code.
• Another aspect of the present invention is that the multi-stage parsing engine uses the protocol layer code as a start vector for an instruction memory, the instruction memory containing instructions for parsing the frame and pointers to access selected words of the frame in a frame buffer.
• Another aspect of the present invention is that the parsing instructions generator identifies each layer protocol and writes the frame into memory along with a protocol layer code and wherein the multi-stage parsing engine processes the instructions from the instruction memory, resolves the pointers according to the protocol layer table and aligns the frame data with the instruction words.
• Another aspect of the present invention is that the search results are fed back to the parsing instructions generator to be used as data that a parsing engine can parse through a data pipe.
• Another aspect of the present invention is that the memory includes a content addressable memory and the search queries are used to search the content addressable memory.
• Another aspect of the present invention is that the memory includes a static random access memory and the search queries are indexed directly to a static random access memory.
• Another aspect of the present invention is that the parsing instructions generator provides a parser instruction set in an instruction memory to define microcode used for generating the parser instructions.
• Another aspect of the present invention is that the multi-stage parsing engine forwards the frame and the search results.
• Another aspect of the present invention is that the search results include the frame classification.
• Another aspect of the present invention is that the parsing instructions generator further includes an instruction controller and wherein the search results are fed back to the instruction controller to be used as a start vector for subsequent processing stages.
• Another aspect of the present invention is that the multi-stage parsing engine performs conditional branching, the conditional branching allowing specific instructions to be performed based upon satisfaction of a predetermined criteria.
• In another embodiment of the present invention, an article of manufacture comprising a program storage medium readable by a computer is provided. The medium tangibly embodies one or more programs of instructions executable by the computer to perform a method for parsing frames in a network flow, wherein the method includes performing preliminary multi-protocol frame classification for incoming frames, processing at least the incoming frame and the preliminary multi-protocol frame classification to provide parsing instructions and providing multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame.
• In another embodiment of the present invention, another method for handling packets is provided. The method including performing preliminary multi-protocol frame classification for incoming frames, processing at least the incoming frame and the preliminary multi-protocol frame classification to provide parsing instructions and providing parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame.
• In another embodiment of the present invention, another method for handling packets is provided. The method includes processing at least the incoming frame to provide parsing instructions and providing multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame.
• In another embodiment of the present invention, another article of manufacture comprising a program storage medium readable by a computer is provided. The medium tangibly embodies one or more programs of instructions executable by the computer to perform a method for parsing frames in a network flow, wherein the method includes performing preliminary multi-protocol frame classification for incoming frames, processing at least the incoming frame and the preliminary multi-protocol frame classification to provide parsing instructions and providing parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame.
• In another embodiment of the present invention, another article of manufacture comprising a program storage medium readable by a computer is provided. The medium tangibly embodies one or more programs of instructions executable by the computer to perform a method for parsing frames in a network flow, wherein the method includes processing at least the incoming frame to provide parsing instructions and providing multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame.
• In another embodiment of the present invention, another multi-protocol, multi-stage, real-time frame classifier is provided. The multi-protocol, multi-stage, real-time frame classifier including a preliminary multi-protocol frame composition analyzer for performing preliminary multi-protocol frame classification for incoming frames, a parsing instruction generator for processing at least the incoming frame and the preliminary multi-protocol frame classification to provide parsing instructions and a parsing engine for providing multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame.
• In another embodiment of the present invention, another multi-protocol, multi-stage, real-time frame classifier is provided. The multi-protocol, multi-stage, real-time frame classifier includes a parsing instruction generator for processing an incoming frame to provide parsing instructions and a multi-stage parsing engine for providing multi-stage parsing of the incoming frame according to the parsing instructions to generate search results presenting information about the incoming frame.
• These and various other advantages and features of novelty which characterize the invention are pointed out with particularity in the claims annexed hereto and form a part hereof. However, for a better understanding of the invention, its advantages, and the objects obtained by its use, reference should be made to the drawings which form a further part hereof, and to accompanying descriptive matter, in which there are illustrated and described specific examples of an apparatus in accordance with the invention.
BRIEF DESCRIPTION OF THE DRAWINGS
• Referring now to the drawings in which like reference numbers represent corresponding parts throughout:
• FIG. 1 illustrates a block diagram for a network device that includes a multi-protocol route/flow classifier with sophisticated policing engines and packet transformation capability;
• FIG. 2 is a block diagram of an input frame device according to the present invention;
• FIG. 3 illustrates a block diagram of an apparatus for providing multi-protocol, multi-stage, real-time frame classification according to the present invention;
• FIG. 4 illustrates a detailed block diagram of an apparatus for providing multi-protocol, multi-stage, real-time frame classification according to the present invention;
• FIG. 5 illustrates a flow chart representing the processes performed by the apparatus for providing multi-protocol, multi-stage, real-time frame classification;
• FIG. 6 illustrates the arrangement of the dual port frame buffer; and
• FIG. 7 illustrates a flow chart showing the processes of the detailed block diagram of the apparatus for providing multi-protocol, multi-stage, real-time frame classification with reference toFIG. 4 according to the present invention.
DETAILED DESCRIPTION OF THE INVENTION
• In the following description of the exemplary embodiment, reference is made to the accompanying drawings which form a part hereof, and in which is shown by way of illustration the specific embodiment in which the invention may be practiced. It is to be understood that other embodiments may be utilized as changes may be made without departing from the scope of the present invention.
• The present invention provides a method and apparatus for providing multi-protocol, multi-stage, real-time frame classification. Advanced level of data extraction is provided across various frame protocols without imposing a performance penalty. Longest prefix match searches and/or direct lookup searches are supported. Moreover, conditional extractions, instruction branching, and multi-stage processing are all performed in real time.
• FIG. 1 illustrates a block diagram for anetwork device100 that includes a multi-protocol route/flow classifier with sophisticated policing engines and packet editing capability. Thenetwork device100 provides advanced services at 10 Gbps, at least, by tightly coupling parsing, policing, and packet editing. This coupling allows the device to perform dynamic packet editing for QoS based on the current flow state and also effectively handles dynamic header processing such as required by MPLS routers. Aphysical layer interface110 provides access to aframer112 on the ingress. Ainput frame device120 includes a parsing engine for handling differentiated services and providing packet analysis, a rate policing engine, and editor functionality. Tightly coupled parsing, policing, and packet editing allows the collective device to perform dynamic packet editing for quality of service based on the current flow state and also effectively handles dynamic header processing such as required by MPLS routers. A session or flow is defined as a series of IP datagrams that share a common destination IP address and traffic-engineering characteristics.
• Theinput frame device120 provides differentiated services, routing, and policing and provides them to a switch fabric andinterface130. On the egress side, theegress frame device140 provides differentiated services traffic management. The egress frames are then provided to theframer112 and then onto thephysical layer interface110. Aprocessor150 controls at least theinput120 andegress140 frame devices.
• FIG. 2 is a block diagram of aninput frame device200 according to the present invention. InFIG. 2, the input frame device includes aclassifier210 that receivesincoming frames212. The classifier builds queries (search words) to be search against either aCAM214 or indexed directly to aSRAM216. Apolicer220 is provided to ensure flow conformance to a maximum allowed peak rate and a contractually obliged committed rate for flows, e.g., DiffServ IP and MPLS. Thepolicer220 includes anSRAM222 for storing a drop policy for each connection. Aneditor230 performs the last operations to the packet before being forwarded asoutgoing frames232. Theeditor230 may fetch editor instructions and support policing results. Anexternal SRAM234 is provided for storing editor instructions. A processor interface allows for control of theclassifier210,policer220 andeditor230 via theprocessor242. In addition, amemory244 may be provided to theprocessor interface240 also.
• FIG. 3 illustrates a block diagram300 of an apparatus for providing multi-protocol, multi-stage, real-time frame classification according to the present invention. InFIG. 3, a preliminaryframe composition analyzer310 is provided to produce the preliminarymulti-protocol frame classification312 forincoming frames314. A parsinginstructions generator320 is provided for processing at least theincoming frame314 and the preliminarymulti-protocol frame classification312 to provide parsinginstructions322. Amultistage parsing engine330 receives at least a portion of theincoming frame314 and the parsinginstructions322 to produce the search results332.
• The task of packet parsing involves identification of the fields in the packet. Field identification does not present a problem in the case ofLayer 2/Layer 3/Layer 4 applications where the field offsets are known either with respect to the start of the packet or are dependent on the contents of another field. However, content-aware classification rules often require fields located within the data packet payload. In this case, the off-sets of fields may not be known apriori and the rule must encode the parsing and classification information.
• Themultistage parsing engine330 provides multi-stage parsing of theincoming frame314 according to the parsinginstructions322 to generate search results that presents information about theincoming frame314. The search results332 may be fedback350 to the parsinginstructions generator320 for reprocessing of the search results332 to generate parsinginstructions322 that are refined. Then, themultistage parsing engine330 parses at least a portion of the incoming frame according to therefined parsing instructions322 to generatesearch results330 that are refined. Therefined search results330 provided greater information about theincoming frame314.
• Accordingly, the parsingengine330 performs layer classification and tagging via a search/lookup engine. Theparser330 includes bitwise extraction from layer and offset and limited operators and masks. The entire frame is available for parsing and extraction. The parser generates, for example, up to four 72-bit search keys that can be concatenated for up to 288 bit searches and is capable, for example, of 2 stage lookup. For example, the parsingengine330 may perform512 programmed extractions on the first search and512 for second stage extractions.
• A microcode controlled programmable sequencer implementation drives the parsing engine. The parsingengine330 is programmable to build search words. Theincoming frame314 is parsed to flexibly generate the search words from data anywhere within the frame or cell. The microcode instruction set contains specialized instructions defined to perform powerful and flexible operations such as EXTRACT, MASK, NOT, AND, OR, XOR, and Range. The instructions and associated data are executed from a dynamically loadable code space.
• To prevent table explosion, a bit may be set as a key to indicate whether a field in a packet is within a predetermined range. For example, when a packet is analyzed, if the TCP source port is within a predetermined range, a bit is set to represent the TCP source port rather than building a search word having the typical 16 bits for the TCP source port. Accordingly, the CAM is used more effectively because less memory is needed to build the search words. The results of the CAM search are applied to the SRAM and returned to the result buffer. Theparser330 builds a search word by extracting bits of data from the packet and prepending bits representing the search type.
• The parsingengine330 parses theincoming frame314 by extracting data into search words having various combinations of bits, e.g., 32, 64, 128, or 256 bits. Multiple searches may be performed, e.g., up to four searches may be issued to the CAM for Longest Prefix Matching or Direct SRAM Lookup (SRAM). For the Direct SRAM Lookup searches, the upper bits are truncated to match the width of the SRAM address space. The two words within the search word also have a corresponding eight bit search type. Given a specified extraction criteria, the appropriate microcode for the parser is provided. The protocol layer, extract data start offset, bits to be extracted, search word and location for extracted bits, N Bits of search type and SRAM or CAM Lookup parameters must be specified before the appropriate microcode can be generated. Optional parameters include data operations, e.g., greater than, less than, equal, NOT, AND, OR, XOR, and Range, that returns a single true/false bit that can be inserted into the search word. The true/false bit can also be used as a conditional branch, as will be explained with reference toFIG. 4. Optional parameters also includes a bit mask and operand(s) and branch instructions. Multiple microcode instructions can be concatenated into the same search words. The last instruction of a multiple instruction operation must indicate the extraction is complete.
• The parsingengine330 supports at least Longest Prefix Matching (LPM) lookups for forwarding table entries, MPLS label-based routing using direct lookup SRAM tables, ATM cell Virtual Path Identifier(VPI)Vertical Connector Identifier (VCI) mapping using direct lookup SRAM tables andLayer 3 lookups of source address (SA), destination address (DA), and type-of-service (TOS) fields. The parsingengine330 may perform accesses to CAM or direct lookup SRAM. The parsingengine330 supports a multi-stage memory lookup where the Connection ID resulting from one lookup is utilized to create the query word for a subsequent lookup.
• FIG. 4 illustrates a detailed block diagram400 of an apparatus for providing multi-protocol, multi-stage, real-time frame classification according to the present invention. Apreprocessor410 classifies the type offrame412 received. Thepreprocessor410 may be programmed to identify any protocol in any OSI layer. Thepreprocessor410 identifies each layer protocol using a multistage algorithm coupled with a CAM/SRAM414 for resolving protocols, etc.
• FIG. 6aillustrates the arrangement of the dualport memory buffer600. InFIG. 6a, the memory buffer contains afirst frame610 and2-N frames620. Thefirst frame610 is shown having several segments. The first segment is theprotocol header632 followed by theLayer 2header634, the Layer 2.5header636, thelayer 3header638 and thelayer 4header640. The layer address table650 inFIG. 6bprovides the layer base addresses653 which provide an indication of the address for each layer along with the search results656, the end-of-frame654, andother programming658.
• Referring again toFIG. 4, the frame is then written into the dualport memory buffer416 along with the result of the preprocessor, the protocol layer code. The protocol layer code andlayer653 are stored in theprotocol header632. The dualport memory buffer416 includes port A418 andport B420. Each layer boundary is marked as to where it resides, e.g., an N-bit code is stored with the frame. A parserinstruction start vector422 is provided from theframe memory controller424 to theinstruction memory controller460. Theinstruction memory controller460 controls the instruction memory based upon the frame data from theframe memory controller424.
• Theinstruction memory430 contains both instructions for theparsing engine440 and layer offsets to access selected words in the dualport memory buffer416. Each protocol layer within each frame is identified and its location in the memory buffer is stored in a table. The layer offset is added to the layer base address resulting in amemory pointer426 which selectsframe data434 used for parsing. As each instruction from theinstruction memory430 is processed, the pointers are resolved by linking the layer address table650 and layer offsets. Theinstruction pipe432 anddata pipe434 serve to align the frame data with the instruction words.
• The parsingengine440 receives theinstruction436 anddata438 and performs the functions, e.g., relative compare482, fixed compare484,mask486, register488, andALU490, selected by the opcode in theparser instruction436. Theparser instruction set436 defines the microcode used by the parsingengine440. Branching474 is provided to allow theinstruction memory controller460 to instruct theinstruction memory430 to generate instructions for theparsing engine440 and layer offsets to access selected words in the dualport memory buffer416. The branching474 may be conditional branching, wherein a field in a packet is analyzed and instructions are executed based upon whether the field meets a predetermined condition.
• Theresults442 of the functions are passed to theextractor444 which builds queries (search words)446 to be search against either theCAM448 or indexed directly to theSRAM450. These results contain the frame classification or can be fed back to theinstruction memory controller460 to be used as either the start vector for subsequent processing stages or as data theparsing engine440 can parse through thedata pipe434. When processing is complete, the frame is read out470 and forwarded with the CAM/SRAM data, i.e., the search results472. The search results472 are provided as an output, for example, as a start instruction pointer for the editor, as a connection ID for policing, or as a different type of instruction for the editor such as for filtering.
• The parsingengine440 may also provide anupdate480 to the search results472, for example, to provide a pointer and other bits that the editor can interpret, to perform custom bit modifications, or to provide for a more dynamic configuration. The parsingengine440 executes a new instruction each clock cycle. Because of the preprocessing by thepreprocessor410, the blueprint of the frame is known before execution of parsing instructions is initiated.
• In addition, the detailed block diagram400 may be concatenated to process the incoming frame/packet input412 to provide scalability of multi-protocol, multi-stage, real-time frame classification. Theoutputs470,472 are interleaved and are not all valid at the same time. By concatenating the block diagram400, the bandwidth provided may be scaled to meet the needs of the network.
• FIG. 5 illustrates aflow chart500 representing the processes performed by the apparatus for providing multi-protocol, multi-stage, real-time frame classification. First a frame is received asinput510. The frame is provided to the preprocessor forclassification512. The frame is then stored in thememory buffer514 as described above. The protocol layer code is used as a start vector into theinstruction memory516. Extraction instructions are provided for building search queries520. A decision is made whether there are additional searches to perform522. If yes524, then additional extraction instructions are provided for building search queries. If not526, then the processing continues. A search latency is provided530. A decision is made whether multi-stage parsing is to be performed540. If yes542, then the search results are fed back to the instruction controller to be used as the start vector for subsequent processing stages. If not544, the frame and the search results are provided as anoutput550.
• FIG. 7 illustrates a flow chart700 showing the processes of the detailed block diagram of the apparatus for providing multi-protocol, multi-stage, real-time frame classification with reference toFIG. 4 according to the present invention. First, preliminary multi-protocol frame classification for incoming frames is performed by resolving a composition for theincoming frame710. Then, at least the incoming frame and the preliminary multi-protocol frame classification is processed to provide parsing instructions by storing an incoming frame in a memory buffer, generating the parsing instructions for the incoming frame based upon the multi-protocol frame classification and aligning the generated parsing instructions with a frame selected from the incoming frames stored in thememory buffer712. At least a portion of the incoming frame is read from thememory buffer714. The parsing instructions are interpreted716. Macros are executed for performing parsing functions on at least the portion of the incoming frame using the interpreted parsinginstructions718. The parsing instructions may use conditional branching. Conditional branching involves analyzing a field in a packet and executing instructions based upon whether the field meets a predetermined condition. For example, if a field in the packet meets a predetermined criteria, a first instruction is performed. Otherwise, a second instruction is performed.
• Extractions instructions are generated in response to the at least incoming frame and the preliminarymulti-protocol frame classification722. The extraction instructions may invoke conditional extractions. The extraction instructions are used to produce search queries724. The search queries are applied against a memory to produce the search results726. The search results may be used by theinstruction memory controller460 and/orframe memory controller424 to generated further refined parsinginstructions740. The refined parsing instructions provide greater information about the incoming frame.
• The process illustrated with reference toFIG. 7 may be tangibly embodied in a computer-readable medium or carrier, e.g. one or more of the fixed and/or removabledata storage devices260 illustrated inFIG. 2, or other data storage or data communications devices. Thecomputer program262 may be loaded into theclassifier210 or into thememory244 to configure theclassifier210 ofFIG. 2, for execution. Thecomputer program262 comprise instructions which, when read and executed by theclassifier210 ofFIG. 2, causes theclassifier210 to perform the steps necessary to execute the steps or elements of the present invention.
• The foregoing description of the exemplary embodiment of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention be limited not with this detailed description, but rather by the claims appended hereto.

Claims (40)

1-75. (canceled)

76. A system for adaptively parsing received frames that include data units having multiple field values formatted according to at least one of a set of network protocols used in a communication network, the system comprising:

a memory storing information suited to resolve the at least one of the set of network protocols;

a preprocessor configured to interact with the memory to provide a type classification for a first frame and generate a layer code based upon said type classification wherein said layer code delineates selected field values in said first frame corresponding to a protocol format of a resolved one of the set of network protocols;

a dual-port memory coupled to said preprocessor and operative to concurrently receive said first frame and said layer code;

an instruction memory operatively coupled to said dual-port memory, said instruction memory storing layer offsets associated with said selected field values delineated by said layer code and at least one instruction that is selected based upon the type classification of said first frame;

a parsing engine communicatively coupled to said instruction memory and said dual-port memory in a feed-forward data flow connection and a feed-back dataflow connection, the feed-forward dataflow connection operative to provide said parsing engine with the at least one instruction and with said layer offsets for accessing the selected field values in said first frame, said parsing engine being adapted to parse said first frame according to said at least one instruction and generate an output indicative of a classification of said first frame, said feed-back dataflow connection affecting communication between said parsing engine and at least one of said instruction memory and said dual-port memory by forwarding at least a portion of said output to said instruction memory for use in refining of said at least one instruction targeted for execution on and to said dual-port memory for re-inputting to said parsing engine through said feed-forward dataflow connection.

77. The system ofclaim 76 wherein said feed-back dataflow connection includes an extractor coupled to said parsing engine for receiving said output and constructing search words, said search words suitable for application against a contents-addressable memory (CAM) for obtaining search results embodying information about the first frame.

78. The system ofclaim 76 wherein said parsing engine is coupled to one or more of a mask unit, a compare unit, a register file and a arithmetic logic unit (ALU), wherein said mask unit is configured to mask a first portion of said first frame to provide masked frame data, said compare unit is adapted to compare the at least one selected field value in said masked frame data to a predetermined value to generate at least a partial identity of the protocol format of the resolved one of the set of network protocols, said ALU is adapted to process one or more of the at least one selected field, said partial identity of said protocol format to provide updated output indicative of the classification of said first frame.

79. The system ofclaim 76 wherein said parsing engine is provided with a data pipe and a instruction pipe disposed in said feed-forward dataflow connection in data communication with said dual-port memory and said instruction memory respectively that maintain said first frame and said at least one instruction substantially aligned with each other.

80. The system ofclaim 79 wherein said data units correspond to two or more frames and arrive in an interleaved sequence with said data pipe and said instruction pipe is operative to align said data units from the first frame with said at least one instruction that is selected responsive to the type classification of said first frame.

81. The system ofclaim 76 wherein said at least one instruction that is selected based upon the type classification of said first frame includes a first sequence of instructions having at least one branch instruction that enables said instruction memory to select a second sequence of instructions targeted for execution by said parsing engine, said second sequence of instructions being based on at least a partial parsing of the first frame using one or more of said first sequence of instructions.

82. The system ofclaim 76 wherein said at least one instruction comprises instructions drawn from the group consisting of EXTRACT, MASK, NOT, AND, OR, XOR, and Range.

83. A method for classifying a frame composed of data-fields formatted according to protocol layers used in a communication network, the method comprising:

storing predetermined data in a first memory wherein said predetermined data enables at least a partial resolution of said protocol layers;

operating a preprocessor in interactive communication with the first memory to correlate at least a portion of the predetermined data with one or more data-fields to obtain class information for the frame, said class information including indicia pointing to boundaries between said protocol layers;

concurrently transferring said data-fields and said class information to be stored in a second memory;

selectively loading an instruction memory with a sequence of program instructions for subsequent processing of said frame responsive to said data-fields and said class information;

parsing said frame by operating on said data-fields, pointed to by said indicia, using said sequence of program instructions to output a first set of search words indicative of an identification of said data-fields at a first resolution;

iteratively refining said sequence of program instructions responsive to said first set of search words and causing said refined sequence of program instructions to operate on one or more of said data-fields and said first set of search words to generate a second set of search words indicative of the identification of said data-fields at a second resolution greater than said first resolution; and

outputting said data-fields and said second set of search words when said second resolution meets predefined criteria.

84. The method ofclaim 83 further including aligning said data-fields with the sequence of program instructions before said program instructions operate on said data-fields.

85. The method ofclaim 84 wherein said data-fields include two or more sets of data-fields corresponding to two or more arriving frames with each set of data-fields embodying differing protocol layers, said step of aligning said data-fields with the sequence of program instructions including aligning said a first set of data-fields with an associated first sequence of program instructions and a second set of data-fields with an associated second sequence of program instructions.

86. The method ofclaim 85 wherein said step of parsing said frame includes interleaving operation of both said first sequence of program instructions on said first data-fields and said second sequence of program instructions on said second data-fields during a single time span.

87. The method ofclaim 83 wherein said frame ingresses at a first bit-rate and egresses at a second bit-rate that is substantially equal to said first bit-rate.

88. The method ofclaim 83 wherein said predefined criteria corresponds to identification of all protocol layers for said frame.

89. The method ofclaim 83 wherein said step of outputting said first set of search results further includes:

using an extractor with an output of said parsing engine to build search keys; and

applying said search keys against a contents-addressable memory (CAM) to generate said first set of search results that contain a frame classification.

90. The method ofclaim 83 wherein parsing said frame includes the steps of:

receiving predetermined data corresponding to at least one protocol layer;

extracting said frame into a plurality of bit fragments of varying length using at least one data mask;

comparing said predetermined data with at least one bit fragment to generate at least one comparison result;

storing said at least one comparison result in a first register;

concatenating said comparison results from said register to obtain a search key; and

indexing a memory using said search key to generate a classification of said frame.

91. The method ofclaim 90 further comprising the steps of:

providing a content-addressable memory (CAM);

storing a plurality of instructions for handling said frame in said CAM;

receiving said search key at said CAM and outputting a set of instructions from said stored plurality of instructions responsive to said search key; and

reparsing said frame using said outputted set of instructions.

92. A method of filtering data packets in a network device, said method comprising:

receiving an incoming packet from a port; extracting packet fields of the incoming packet; classifying the incoming packet and generating action instructions based on values contained in the extracted packet fields; and modifying the incoming packet based on the action instructions and a predetermined criteria set for the network device.

93. A data filter for data packets in a network device, said data filter comprising:

receiving means for receiving an incoming packet from a port; extracting means for extracting packet fields of the incoming packet; classifying means for classifying the incoming packet and generating action instructions based on values contained in the extracted packet fields; and modifying means for modifying the incoming packet based on the action instructions and a predetermined criteria set for the network device.

94. A data filter as recited inclaim 93, wherein said network device comprises one of a switch and a router and the modifying means comprises processing means for discarding the incoming packet, forwarding the incoming packet, modifying the incoming packet or modifying a forwarding control message for the incoming packet.

95. A data filter as recited inclaim 93, wherein said network device comprises a network co-processor and the classifying means comprises classifying means for classifying the incoming packet based on protocol type and data payload of the incoming packet.

96. A data filter as recited inclaim 93, wherein said network device comprises a network interface controller and the classifying means comprises classifying means for classifying the incoming packet based on one of a flow identification for packets having a particular source and a particular destination and a flow identification parameter.

97. A fast flexible filter processor for data packets in a network device, said fast flexible filter processor comprising: an inspection engine, configured to receive an incoming data packet and extract selected packet fields from the incoming data packet; a classification engine communicating with the inspection engine, configured to receive the extracted selected packet fields and generate action instructions based on the values contained in the extracted packet fields; a packet processing engine communicating with the classification engine, configured to receive the action instructions and the incoming data packet, modify the incoming packet and output the modified incoming data packet.

98. A network device for network communications, said network device comprising: a data port interface supporting at least one data port; a programmable interface, said programmable interface configured to communicate with a CPU or a programming source; a memory, said memory communicating with said data port interface; and a fast flexible filtering processor configured to receive packets coming into the data port interface, extract packet fields from said packets, determine action instructions from values contained in the extracted packet fields and take selective filter action based upon the action instructions and a predetermined criteria set for the network device.

99. A network switch as recited inclaim 98, wherein said fast flexible filtering processor is configured to be programmable by inputs from the CPU or the programming source through the programmable interface.

100. A network switch as recited inclaim 98, wherein said data port interface, said programmable interface, said memory, and said fast flexible filtering processor are implemented on a common semiconductor substrate.

101. A network switch as recited inclaim 98, wherein the fast flexible filtering processor filters the packets independent of the programmable interface, and therefore without communicating with the CPU or the programming source.

102. A method for searching network messages for pre-defined regular expressions, the method comprising the steps of: storing a plurality of pre-defined regular expressions in a content-addressable memory (CAM); inputting a network message or selected portion thereof to the CAM for comparison with all of the regular expressions stored therein, the comparison with all CAM entries being done at the same time; returning an output from the CAM; and identifying, in response to the output, an action to be applied to the given network message or portion thereof that corresponds to a CAM entry matching the inputted network message or selected portion thereof.

103. The method ofclaim 102, further comprising: storing the pre-defined regular expressions in a memory storage device, and also storing one or more actions that are to be applied to network messages matching the respective regular expressions in the memory storage device; and operating the memory storage device in interaction with the CAM.

104. The method ofclaim 102, further comprising: using as the CAM a ternary content addressable memory (TCAM); storing the pre-defined regular expressions in a random access memory (RAM); and storing one or more actions that are to be applied to network messages matching the respective regular expressions in the random access memory (RAM).

105. The method ofclaim 102, further comprising: configuring a logic circuit to extract one or more selected fields from network messages and to append those selected fields to the respective network messages prior to inputting the messages to the CAM.

106. A pattern matching engine apparatus for use in searching network messages for pre-defined regular expressions, comprising: a content-addressable memory (CAM) having a plurality of entries containing the pre-defined regular expressions; a decoder circuit configured to control an input to the CAM, the input including a given network message or selected portion thereof for comparison with the regular expressions contained within the CAM; and an output from the CAM, and in response to the output from the CAM, identifying an action to be applied to the given network message or portion thereof, and the CAM configured such that each network message or portion thereof input to the CAM is compared against all CAM entries at the same time, allowing high-speed pattern matching of network messages.

107. The apparatus ofclaim 106, further comprising: a memory storage device to store the pre-defined regular expressions, and also to store one or more actions that are to be applied to network messages matching the respective regular expressions; and operating the memory storage device in interaction with the CAM.

108. A computer readable media, comprising: said computer readable media containing instructions for execution on a processor for the practice of a method for searching network messages for pre-defined regular expressions, the method having the steps of, storing a plurality of pre-defined regular expressions in a content-addressable memory (CAM); inputting a network message or selected portion thereof to the CAM for comparison with all of the regular expressions stored therein, the comparison with all CAM entries being done at the same time; returning an output from the CAM; and identifying, in response to the output, an action to be applied to the given network message or portion thereof that corresponds to a CAM entry matching the inputted network message or selected portion thereof.

109. Electromagnetic signals propagating on a computer network, comprising: said electromagnetic signals carrying instructions for execution on a processor for the practice of a method for searching network messages for pre-defined regular expressions, the method having the steps of, storing a plurality of pre-defined regular expressions in a content-addressable memory (CAM); inputting a network message or selected portion thereof to the CAM for comparison with all of the regular expressions stored therein, the comparison with all CAM entries being done at the same time; returning an output from the CAM; and identifying, in response to the output, an action to be applied to the given network message or portion thereof that corresponds to a CAM entry matching the inputted network message or selected portion thereof.

110. A processor configured to process contents of packets passing through a connection point on a computer network, the processor comprising: (a) a buffer for receiving at least some of the contents of each packet passing through the connection point; (b) a memory containing one or more instructions of an instruction set for the state processor; (c) an arithmetic logic unit (ALU) coupled to the buffer; (d) a control block coupled to the ALU and to the instruction memory for decoding instructions; and (e) a program counter coupled to the instruction memory and to the ALU for indicating the next state processor instruction in the memory to process, wherein the ALU includes a searching apparatus comprising one or more comparators for searching for a reference string in the contents of a packet.

111. In a packet switching network for relaying information in frames among nodes, a node comprising a combination of receiving means for acquiring incoming information frames including header portions designating format information, frame alteration commands for designating changes to data in a frame, and packets containing information data; alteration means responsive to said header portions for modifying information contained in said frames; and output means for relaying altered frames to another node.

112. The packet switching network ofclaim 111 further including offset means for determining locations of data to be transformed; pointer means for indicating locations of data passing through said node; comparator means for indicating locations from the offset means and the pointer means are equal; and means responsive to equality signals from said comparator means for controlling insertion and passage of data to the output means.

113. The combination ofclaim 111 further including deletion means responsive to the decoder means for inhibiting passage of data to said output means.

114. The combination inclaim 111 further including storage means for storing predetermined data patterns; selection means coupled to said storage means for selecting a desired predetermined data pattern; and application means responsive to the selection means for coupling a selected predetermined data pattern to the alteration means.

Images