Programmable data packet parser

Details Programmable data packet parser Programmable data packet parser

1999-06-30

2003-08-26

Kizou, Hassan (Department: 2662)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S474000

Reexamination Certificate

active

06611524

ABSTRACT:

The present invention relates to an apparatus and method for parsing data packets having different formats and in particular to parsing which is programmable, e.g. to accommodate new or different formats, but which can be provided without the need for using a microprocessor for parsing.
BACKGROUND INFORMATION
A number of electronic devices can receive data packets which may be in any of a plurality of different formats, which may not be known in advance. Examples include network routers, gateways, bridges, hubs and the like. Typically, information is included in the packets which is useful in determining how to handle or process the packets. For example, packets may include information regarding the destination of the packet, the size of the packet (or various fields therein) and the like. There are, however, a plurality of different formats for data packets and the location of information within various data packets may differ in the various formats. For example, one format may provide destination information in bytes
30
through
33
of a packet while another may provide destination information in bytes
38
through
41
. Accordingly, in order to properly handle a data packet, it is typically necessary to determine the format of the data packet. The process of determining the format, and using such determination to identify the location of various data (e.g. to facilitate handling of the packet), is known as parsing the packet.
The parsing of network data packets presents certain challenges which are believed substantially unique compared to other types of parsing. For example, typically the time available for parsing a packet is driven by the rate at which packets arrive, i.e. a given packet typically must be fully parsed before the next packet arrives. In a typical situation it is substantially infeasible to predict the format of the next packet, i.e. packets may arrive in substantially random formats. In many situations, a given type of data, although positioned in different locations for different formats, nevertheless may be used in substantially the same way for different formats. For example, although destination information may be located at different places for differently formatted packets, the destination information is used in substantially the same way for handling many, if not all, of the differently-formatted packets.
Various devices and procedures have been used for packet parsing. In one approach, a microprocessor, or an embedded microcoded engine, executes microcode which performs a plurality of (typically sequential) tests or comparisons on various data and/or fields of the packet to determine the packet format. An advantageous aspect of this approach is that the system can be configured to accommodate new packet formats by revising the microcode, i.e. substantially without the need for redesigning hardware (such as without the need for redesigning the microprocessor). Unfortunately, this approach can be relatively expensive. If a microprocessor is used for parsing packets, the cost of the microprocessor can undesirably increase the cost of the network router or other apparatus. If the microprocessor is also being used for other purposes, there can still be substantial expense involved because it is necessary to provide a processor which has a sufficiently high performance that it can perform both parsing functions and other functions and can perform such functions quickly enough to accommodate the data rates or data speeds of the incoming packets. Thus, providing a microprocessor for packet parsing functions can involve providing a processor which has higher performance (and typically higher cost) than would otherwise be necessary. Accordingly, it would be useful to provide a packet parser which can be implemented in an economic fashion preferably without the need to use a microprocessor or an embedded microcoded engine for packet parsing functions.
Another approach for handling data packets has been using partly or fully hardwired logic. For example, hardwired logic may be configured to test a first predefined field or bit of each incoming packet and, depending on the result of the comparison, branching to a next comparison for a second field or bit of the packet. This procedure is repeated recursively until the packet is parsed. Each test, in this configuration, is performed by hardwired logic and, accordingly, one disadvantageous aspect of such an approach is that new or different formats cannot be accommodated with a change in programming or software. Rather, when the hardwired logic is implemented, e.g., in an application specific integrated circuit (ASIC), a new or different format for packets requires redesigning the hardwired logic and generating a new ASIC, typically at substantial expense. Typically, redesigning and refabricating an ASIC requires months of time and relatively high expense in nonrecurring engineering (NRE) charges. Moreover, because of the nature of the “tree” logic typically used for hardwired parsing, there is no guarantee that a new or different format can be accommodated by a minor change in the hardwired logic. Thus, accommodating a new or changed format may often involve substantial redesign of the logic tree, possibly at relatively high expense. Another generally disadvantageous aspect of hardwired parsers is that in-service parsers are not easily upgraded e.g. to accommodate new or different formats. Typically, the owner of a router or similar device with hardwired parsers must acquire, and have installed, new hardware in order to accommodate new or changed packet formats. There may be substantial network down time involved in such hardware installation. Accordingly it would be desirable to provide a packet parser which can accommodate new or different packet formats by way of upgrading in-service routers or similar devices, without requiring the installation of new hardware.
In general, it would be useful to provide a data packet parser which can accommodate new or changed data packet formats without the need for changing or redesigning hardwired logic or other hardware, preferably by merely making software or programming changes and preferably in a way such that a new or changed packet format can be accommodated without the need for redesigning an entire logic tree.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for parsing data packets without the need for using a microprocessor to achieve such parsing, yet which can accommodate new or different packet formats without the need for changing hardwired logic or other circuitry or hardware (such as by changing programming or software). According to one embodiment, a database is stored, e.g. such as storing in a plurality of registers, which is used in providing a signature word for each packet, with the signature words being indicative of particular packet formats. New or different formats can be accommodated by changing the data stored in the database, e.g. to generate a new signature in response to a new or different packet format.
The signature can be used to directly control or determine processing for the data packet or handling. If desired, however, the signature can also be used to output other data such as using the signature as (all or part of) a key to a content-addressable memory (CAM) which outputs a pointer to an entry point in microcode. In this way, it is possible to avoid the need for reconfiguring hardwired logic or other hardware in order to accommodate new or different packet formats, but without needing to provide a microprocessor for packet parsing purposes.
In one embodiment, the database includes a plurality of registers, with each register being used for setting (or clearing) one or more bits of the signature word. For example, each register may define a word offset and/or bit field defining the bits of the packet to be compared, a data field defining the data to which the “masked” data from the packet is to be compared and an indication of which bit or bits in the signature word should be set (or cleared) as a resu

Affiliated with

Also associated with

Rating

Programmable data packet parser does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Programmable data packet parser, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable data packet parser will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3130252