Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-05-18
2002-02-19
Dam, Tuan Q. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000, C711S103000, C712S231000, C713S160000
Reexamination Certificate
active
06349405
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to programmable state machines and more particularly to programmable packet classification state machines for use in high-speed communication.
BACKGROUND OF THE INVENTION
In the past, programmable state machines were provided with procedural programming. This permits flow from one state to another state upon certain conditions according to a desired sequence. Because a state machine effectively controls a sequence of processing steps, the concept of a truly non-procedural programming method for a state machine appears contradictory. To this end, many “non-procedural” methods of programming state machines have been proposed. Nevertheless, upon analysis these have been found to be procedural or somewhat procedural. The concept of branches and loops is common in these methods and a flow diagram of operation is often evident.
Until now because of the procedural nature of state machines, non-procedural methods of programming the state machines have been regarded as having few advantages. Some of the “non-procedural” methods of programming a state machine focus on reuse of programming code and modularity of the code. Therefore, procedural elements within each state are not only permitted, but are viewed as somewhat essential. Different states, however, are commonly easily reused or assembled into a whole classification description.
When reprogramming a state machine, it is important to consider a concept of a truly non-procedural method of implementing a programmable state machine. Changes to state machine programming are then added without concern for state flow, since the description of the state machine is non-procedural. Further, implementation of the state machine is performed by the compiler and does not require significant design by a state machine designer or, more importantly, an end user.
Reprogramming of a state machine having procedural programming is considered a straightforward task. State machine execution is paused, new programming is loaded into program memory and then the state machine is restarted. The process of pausing the state machine often involves halting data flow, which is undesirable. For use in firewalls and other security applications, a change in programming often results from a change in security procedures. As such, it is important to load the change as quickly as possible. Of course, it is evident to one skilled in the art that it is often impractical to shut down a system during reprogramming and, hence reprogramming of a system often only occurs at certain times. This is inconvenient.
Another problem is encountered with current reprogramming techniques for programmable state machines when several state machines share a common program memory. When upgrading the programming for any of the state machines, all state machines are paused. This is a significant problem that is possibly avoided by duplicating program memory in order to allow all but one state machine to remain operative during a reprogramming operation. Another method of avoiding this problem is to provide each state machine with dedicated state machine memory.
A current area of research in high-speed state machine design is the area of digital communications. Commonly, in digital communication networks, data is grouped into packets, cells, frames, buffers, and so forth. The packets, cells etc, contain data and classification information. It is important to classify packets, cells, etc. for routing and correctly responding to data communications. An approach to classifying data of this type uses a state machine.
For Gigabit Etheniet, it is essential that a state machine operate at very high speeds to process data in order to determine addressing and routing information as well as protocol-related information. Unfortunately, at those speeds, memory access is a significant bottleneck in implementing a state machine or any other type of real time data processor. This is driving researchers to search for innovative solutions to increase classification performance. An obvious solution is to implement a classification state machine completely in hardware. Non-programmable hardware state machines are known to have unsurpassed performance and are therefore well suited to these high data rates; however, the implementation of communication protocols is inherently flexible in nature. A common protocol today may be obsolete in a few months. Therefore, it is preferable that a state machine for use with Gigabit Ethernet is programmable. In the past, solutions for 10 Mbit and 100 Mbit Ethernet data networks required many memory access instructions per state in order to accommodate programmability. This effectively limits operating speeds of the prior art state machines.
A programmable state machine for classification of data can be implemented entirely in software. Of course, software state machines are often much slower than their hardware equivalents. In a software state machine, each operation is performed by a software instruction and state changes result in branch operations. As is evident to those of skill in the art, to implement a high-speed state machine in software for packet classification, requires many instructions per second—many more than a billion—requiring expensive parallel processors or technologies unknown at present. In fact, a severe limitation to performance is the speed of memory devices. For example, should a 7 ns memory device be used, less than one memory access per memory device is possible for each bit of a Gigabit Ethernet stream. Thus, if each byte—8 bits—of data is processed in a single state, only one memory access operations is possible for each state. To implement such a system as a purely software solution is impractical and unlikely.
Current state of the art integrated memory devices achieve performance in the area of 7 ns per memory access when timing and other factors are taken into account. Therefore, pure hardware implementations of state machines fast enough to implement a Gigabit Ethernet packet classifier are possible so long as only one memory access is required for every 8 bits within the Ethernet data stream. Prior art implementations of such a state machine use a branching algorithm to allow state transitions within the time frame of a predetermined number of bits. The address data for the branching algorithm is stored in program memory. When the predetermined number of bits is 8, each state transition occurs within 8 ns. One method of achieving this performance is to store a table of data having 256 entries for each possible state. The table address is then concatenated with 8 bits from the data stream to determine a next state address. This continues until a value indicative of a classification or a failure to classify is encountered.
Unfortunately, the amount of memory required to implement a system, such as that described above, is prohibitive. For example, using 8 bits at a time requires up to 256 entries per table, 16 bits at a time requires 65,536 entries. The exact number of tables also depends on a number of terminal states. Since integrated memory having a high storage capacity is not available, implementation of a prior art programmable packet classification state machines having large numbers of edges in integrated memory is currently not feasible.
It has been found that a programmable hardware state machine for use in packet classification of high-speed data communications wherein reprogramming of the state machine is performed according to a non-procedural method, would be advantageous.
It would also be advantageous to provide a method of programming a state machine such that easy modification of state machine programming is possible during operation of a plurality of state machines using, the same program memory.
OBJECT OF THE INVENTION
In order to overcome these and other limitations of the prior art, it is an object of the invention to provide state machine memory architecture for supporting a plurality of state machines simultaneously.
It is another object of the present invention to provide a
Dam Tuan Q.
Freedman & Associates
Solidum Systems Corp.
Vo Ted T.
LandOfFree
Packet classification state machine does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Packet classification state machine, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet classification state machine will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2976327