Data processing: structural design – modeling – simulation – and em – Emulation – Of peripheral device
Reexamination Certificate
1999-05-18
2002-07-23
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Emulation
Of peripheral device
C703S026000, C370S389000, C709S238000
Reexamination Certificate
active
06424934
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
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 or so forth 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 Ethernet, 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 all but 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 unlikely.
Current state of the art integrated memory devices achieve performance in the area of 5 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 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 would be advantageous to provide a state-machine for classification of bits in a data stream requiring only one memory access to program memory per state transition.
It has been found that a programmable state machine for use in packet classification of high-speed data communications wherein program memory requirements are reduced over program memory requirements of prior art implementations would be highly advantageous.
In order to overcome these and other limitations of the prior art, it is an object of the invention to provide a state machine architecture for supporting implementation of high speed packet classification and providing for reduced memory requirements over those necessary in the prior art.
It is another object of the present invention to provide state machine architecture for supporting implementation of high-speed packet classification and requiring only one memory access to program memory for each state transition.
It is another object of the present invention to provide state machine architecture for supporting programmable high-speed packet classification.
STATEMENT OF THE INVENTION
Accordingly, the invention provides a packet classification state machine for classifying data from a data stream. The state machine comprises:
a) a programmable memory for storing information relating to states within the state machine, the states including a first group of states and a second group of states, the first group of states each represented by a table of data at a table address and including a first plurality of table elements addressable at an offset from the table address, each of the table elements indicative of a next state within the state machine, and the second group of states each represented by a table of data including a table element and occupying less memory than a table of data representing a state of the first group of states; and,
b) a processor for determining a next state based on contents of a table element of a present state at an offset from the table address, the offset determined during a table address load portion of an instruction cycle in dependence upon the bits in the data stream, the processor also for switching the state machine into the next state so determined.
According to another embodiment, the invention provides a packet classification state machine for classifying data from a data stream. The state machine comprises:
a) a programmable memory for storing information relating to states within the state machine, the states including three groups of states;
the first group of states each represented by a table of data including 2
n
table elements addressable at an offset from the table address, the table elements indicative of a next state within the state machine, n bits in the data stream for determining the offset,
the second group of states each represented by a table of data including 2
n
table elements having a size smaller than that of table elements of the first group of states, the table elements addressable at an offset from the table address, the table elements indicative of a next state within the state machine, n bits in the data stream for determining the offset; and
the third group of states each represented by data indicative of a single possible next state; and,
c) a processor for storing for a table address of the first group a current state address and a plurality of bits from the data stream together to form an address, for a table address of the second group a current state address and a plurality of bits from the data stream together to form an address, and for a table address of the third group a current state address; for retrieving from that address in the programmab
Freedman & Associates
Phan Thai
Solidum Systems Corp.
Teska Kevin J.
LandOfFree
Packet classification state machine having reduced memory... 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 having reduced memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet classification state machine having reduced memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2904570