Multiplex communications – Diagnostic testing – Fault detection
Reexamination Certificate
1999-05-26
2003-04-01
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Diagnostic testing
Fault detection
C370S389000, C714S758000
Reexamination Certificate
active
06542470
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data communications systems and more particularly relates to a system for expanding a packet's length while preserving its original CRC value.
BACKGROUND OF THE INVENTION
More and more reliance is being placed on data communication networks to carry increasing amounts of data. In a data communications network, data is transmitted from end to end in groups of bits called packets, frames, cells, messages, etc. depending on the type of data communication network. For example, Ethernet networks transport frames, X.25 and TCP/IP networks transport packets and ATM networks transport cells. Regardless of what the data unit is called, each data unit is defined as part of the complete message that the higher level software application desires to send from a source to a destination. Alternatively, the application may wish to send the data unit to multiple destinations.
In many communication systems it is desirable to add one or more data items to the received data packet. The data appended to the packet in some instances is referred to as a tag and may comprise various information elements such as the packet's priority, associated VLAN, etc.
A problem arises, however, when the packets are transmitted with a CRC check field. If data were to be added to the packet, either at the head or the tail, the CRC value becomes invalid. Changing the length of the packet by the addition of bits, invalidates the CRC. When the packet with the appended data passes through the CRC machine in the receiver, a CRC error indication will be generated since the CRC field in the original packet will not match that generated for the received packet. This is cause the original CRC was generated before the tag was appended to the packet. Thus, simple attachment of the tag to the packet will not work.
This problem is illustrated using the following example. A block diagram illustrating an example prior art interface card comprising a packet expander and MAC processor is shown in FIG.
1
. The example is illustrated in the context of a communication system, generally referenced
10
, that comprises a transmitter MAC processor
12
, packet expander
14
and receiver MAC processor
16
. Packets
18
generated by the transmitter MAC processor
12
comprise data and an original CRC field. Somewhere between the transmitter and the receive a tag
13
is appended to the packet by a packet expander
14
. Ultimately the packets are received by the receiver MAC processor
16
that comprises a CRC machine. The CRC indication result of the CRC calculation will be an error indication since the original CRC does not consider the appended tag data. The output of the receiver MAC processor
16
comprises a packet
22
including data and some or all portions of the original CRC and the tag data.
Thus, as described above, the simple attachment of the tag data to the received packet is not a valid solution. One solution to this problem is to calculate the CRC anew with the appended tag data. This requires a CRC generator to calculate the new CRC value. In addition, calculating a new CRC wipes out any benefit of validating the original CRC to determine the occurrence of transmission errors after the received packet traveled over the communication link.
Another solution is to provide a custom MAC processor that has knowledge of the tag appended and is adapted to perform a CRC only on the original packet content before the tag was appended. Another solution is to provide circuitry that functions to strip out the tag from the packet and create two streams: the original packet and the stripped tag. The packet is then processed normally and a valid CRC indication results. After MAC processing the tag is re-appended to the packet. Both these solutions preserve the original CRC check sum but they required either special custom MAC processors or the creation of additional circuitry before and after the MAC processor. In addition, both cases do not provide for CRC error checking for the tag data itself.
SUMMARY OF THE INVENTION
The present invention is a system for appending data to a packet whereby the original CRC calculated by the transmitter station is not modified and is still utilized to determine the occurrence of transmission errors. The invention is applicable in any communication system whereby a data tag representing the data to be appended to the packet is a fixed length. The invention appends the data tag to the tail of the packet after the original CRC and, in addition, determines and appends a tag CRC to the tail of the packet after the tag data. The tag CRC having a value whereby the CRC machine in the receiver generates the constant CRC value even though the packet length was expanded.
The invention utilizes the principle of CRC generation that a constant CRC is generated when a packet with no errors including the original CRC are passed through the CRC machine in the receiver. A tag CRC is generated that when appended to the packet will produce the same result as if the packet was processed through the CRC machine without any data appended.
In accordance with the invention, all possible values of the tag data are passed through a CRC machine that has been initialized to the constant CRC value. The results are placed in a lookup table for use when appending the tag data to received packets. The lookup is performed every time tag data is to be appended to a packet. The advantage of the invention is that a new CRC result is not required to be generated for the expanded packet. In fact, it is not desirable to do so, as this would eliminate the benefit of using the original CRC that was received with the packet to detect transmission errors.
There is provided in accordance with the present invention an apparatus for appending a data tag to a packet having a data field and an original Cyclic Redundancy Check (CRC) field calculated by a transmitting station comprising a lookup table comprising a plurality of entries, each entry including a tag and a corresponding tag CRC, the tag CRC calculated to permit an appended packet to avoid generating a CRC error due solely to the lengthening of the packet and a tag processor operative to append the tag and the tag CRC to the tail of the packet following the original CRC field.
The apparatus further includes a tag CRC generator initialized with a constant CRC value and adapted to calculate a set of tag CRC values in response to all possible tag values input thereto. The apparatus further includes tag capture means adapted to separate and process the tag from the packet.
There is also provided in accordance with the present invention, in a packet transmission system, the packets having a data field and an original Cyclic Redundancy Check (CRC) field calculated by a transmitting station, a method of appending a data tag to a packet, the method comprising the steps of looking up a tag CRC in a tag CRC lookup table in accordance with a tag value, each entry in the CRC lookup table including a tag and a corresponding tag CRC, the tag CRC calculated to permit an appended packet to avoid generating a CRC error due solely to the lengthening of the packet and appending the tag data and the tag CRC to the tail of the packet following the original CRC.
REFERENCES:
patent: 5594702 (1997-01-01), Walkeman et al.
patent: 6014380 (2000-01-01), Hendel et al.
patent: 6034963 (2000-03-01), Minami et al.
patent: 6128666 (2000-10-01), Muller et al.
patent: 6172990 (2001-01-01), Deb et al.
Halpern Ari
Honig Yoav
Mann Eytan
Schzukin Golan
3Com Corporation
Hsu Alpus H.
Nguyen Toan D.
Zaretsky Howard
LandOfFree
Packet expansion with preservation of original cyclic... 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 expansion with preservation of original cyclic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet expansion with preservation of original cyclic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3011480