Processing of network data by parallel processing channels

Details Processing of network data by parallel processing channels Processing of network data by parallel processing channels

1998-06-22

2002-08-13

Ngo, Ricky (Department: 2661)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S366000, C370S535000

Reexamination Certificate

active

06434145

ABSTRACT:

CROSS REFERENCE TO RELATED APPLICATIONS
Not applicable.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH
Not applicable.
BACKGROUND OF THE INVENTION
The present invention relates to network data processing.
When data are transferred in networks, the data may have to be processed at intermediate or end transfer points. The data processing may involve address resolution, protocol transformations between different protocols, implementing connectivity restrictions imposed for security reasons or to reduce network congestion, and possibly other processing. Sometimes the data processing throughput does not keep up with data transmission rates. Therefore, systems are needed which can take advantage of high data transmission rates while still using data processing equipment having lower throughput.
SUMMARY
In some embodiments, the present invention allows one to take advantage of high data transmission rates while still using data processing equipment with lower throughput. In some embodiments, this is achieved by using multiple data processing channels in parallel to increase the total data processing throughput. In some embodiments, the data ordering is maintained as if the data were processed sequentially by a single processing channel.
More particularly, in some embodiments, a first flow of data is received on a first network port by a first circuit. The first circuit dispatches received data to different processing channels so that different channels process different pieces of data in parallel. A second circuit receives the data from the processing channels and dispatches the data to a second flow on a second network port. At least one of the first and second flows has a greater throughput than at least one of the processing channels. However, the processing throughput is high because different channels process the data in parallel.
In some embodiments, in at least one of the first and second flows data are transferred in frames. Each frame is processed by a single processing channel. The frames may emerge from the processing channels not necessarily in the order in which the frames were received on the first port. However, the second circuit reorders the frames received from the processing channels so that the data are transmitted on the second port in the same order in which they were received on the first port. This may be important for some applications in which a source station transmitting the data to the first port and a destination station receiving the data from the second port may want the frame ordering to be unchanged during transmission. In particular, the system of the present invention is suitable for connection oriented protocols which require the frame ordering to be preserved.
In some embodiments that preserve data ordering, it is desirable to minimize changes needed to be made to the processing channels when the processing channels are used in the system of the present invention. More particularly, in the system of the present invention, each processing channel processes a portion of a data flow between the first and second ports. However, each processing channel may have been designed to process an entire data flow. Therefore, the processing channels may have no mechanism to assist the first and second circuits to maintain frame ordering. Hence, in some embodiments, when the first circuit dispatches a frame to the processing channel, the first circuit does not modify the frame with any information that could be recognized by the second circuit or the processing channel and used to maintain the frame order. When the second circuit receives frames from the processing channels, the processing channels do not provide any information as to the order of the frame in the first data flow. Therefore, in some embodiments, the frame ordering information is provided by the first circuit directly to the second circuit.
Thus, some embodiments include an ordering FIFO between the first and second circuits. When the first circuit dispatches a frame to a processing channel, the first circuit pushes (i.e. queues) the processing channel ID (for example, the processing channel number) into the ordering FIFO. The second circuit pops, (dequeues) the channel IDs from the ordering FIFO, and dispatches the frames to the second flow from the channels in the order of the channel IDs. For example, if the first circuit pushed the channel IDs
1
,
2
,
4
,
1
, in that order, into the ordering FIFO, the second circuit will dispatch a frame received from channel
1
, then a frame received from channel
2
, then a frame received from channel
4
, then a frame received from channel
1
. Therefore, the frames will be dispatched to the second flow in the same order in which they were dispatched by the first circuit to the processing channels, which is the order of the frames in the first data flow.
In some embodiments, a processing channel may drop a frame due, for example, to a buffer-full condition in the channel. Then the frame ordering can be violated. To restore the frame ordering, the first circuit dispatches a “marker” frame on each channel once in a while. When the corresponding channel ID is pushed into the ordering FIFO, a “marker” bit is set in the ordering FIFO entry to indicate that the channel ID corresponds to a marker frame.
The marker frame itself is distinguished in some way that will allow the second circuit to recognize such frames. For example, in some embodiments, the marker frames are distinguished by a source address being a broadcast address or some other illegal address.
Each time the second circuit pops a channel ID from the ordering FIFO, the second circuit also pops the corresponding marker bit. If the marker bit indicates a marker frame but the corresponding frame from the channel is not a marker frame, the marker frame was possibly dropped by the channel. Perhaps, other frames have also been dropped. Therefore, the frame received from,the channel is not transmitted at least until another channel ID is popped corresponding to the same channel. Further, the second circuit requests the first circuit to send another marker frame on the same channel.
If the marker bit from the ordering FIFO indicates a non-marker frame but the frame received from the corresponding channel is a marker frame, one or more non-marker frames have possibly been dropped by the channel. Therefore, no frames are transmitted from the channel until another channel ID identifying the same channel and accompanied by a marker bit set is popped from the ordering FIFO. In this way, the frame ordering is restored.
In some embodiments, the channels also process traffic flowing from the second port to the first port. A separate ordering FIFO is provided for this traffic.
Some embodiments include multiple first ports and/or multiple second ports. The second circuit reorders the frames as needed so that the frames are transmitted on one or more second ports in the same order in which they arrived on one or more first ports. In some embodiments, only frames received on the same first port are transmitted in the order in which they arrived, and/or only frames transmitted on the same second port are transmitted in the order in which they arrived on one or more first ports. In some embodiments, a separate ordering FIFO is provided for each first port for the traffic from the first ports to the second ports, and a separate ordering FIFO is provided for each second port for the traffic from the second ports to the first ports. Each processing channel processes traffic from only one first port and/or only one second port, and the ordering in the data flow between each pair of the first and second ports is maintained, i.e., data are transmitted on one of the first and second ports in the same order in which the data were received on the other one of the first and second ports.
In some embodiments, multiple flows are transferred through a single port, so that the port is treated as a plurality of logical sub-ports with each sub-port handling a single data flow.
Other features and advantages of the invention are

Affiliated with

Also associated with

Rating

Processing of network data by parallel processing channels does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Processing of network data by parallel processing channels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing of network data by parallel processing channels will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2911880