Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-07-27
2002-08-27
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S252000
Reexamination Certificate
active
06442161
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the transmission of data packets in computer networks and in particular to the proper forwarding of such data packets the content of which may have been intentionally changed.
2. Prior Art
It is well known in computer networks for devices connected to the network to communicate with each other by sending data to each other in the form of data packets. The precise content of each packet will depend upon the communication protocol in operation but typically each data packet may contain a destination address identifying the intended recipient of the data packet, a source address identifying the sender of the packet, and the data itself Additionally, there may be protocol specific sections of the data packet, for instance in the Ethernet protocol each data packet typically contains a type identifier indicating for instance the type of packet which is being transmitted or the length of the data section of the packet. Finally, there is usually provided at the end of the data packet a sequence of bits enabling error detection to be carried out.
In particular, this sequence of bits, which is commonly known as a frame check sequence (FCS), is a sequence of bits generated by performing some mathematical algorithm or procedure on all of the bits forming the rest of the data packet. On receipt of the data packet, the receiving station can check for errors which may have occurred during transmission of the packet by performing the appropriate mathematical algorithm or procedure on the data packet as received and comparing this to the received FCS. If there is a difference in this comparison the received data packet is discarded as containing an error.
In computer networks the network devices are not connected directly to each other and the data packets which are sent as described above in fact travel via a number of communication hubs which function to receive and retransmit the packet to enable the packets to travel throughout the network. There are certain types of communications hub, such as bridges, switches and routers, which have a certain amount of intelligence such that the packets they receive are retransmitted only on the route or routes necessary to enable the received packet to reach its intended destination. To achieve this, such hubs have some memory to enable the data packet to be received into memory and held while the required analysis of the destination takes place before being retransmitted.
This temporary storage of the data packet enables the communications hub also to make modifications to the data packet if this is required. Such modifications may be made in circumstances where for instance the hub is at an interface between two network segments operating slightly different network protocols or supporting different network features. The modifications would generally not affect the data portion of the packet or probably the destination or source address of the packet. However, the type identifier mentioned above may be altered or additional sections may be inserted into the packet specific to the protocol via which the packet is to be transmitted. Equally, upon reaching the end of the particular network segment in question, the inserted data must be removed from the data packet or the data packet must be otherwise restored to its original condition. One particular circumstance in which data packets may be altered in this fashion is on being passed to a portion of a computer network which supports virtual LANs (VLANs) in which case it is necessary to insert a portion of data known as a VLAN tag into the data packet and to remove it when the packet leaves the portion of the network which supports this feature.
The present invention is not directly concerned with the reasons or mechanisms for altering the data packets in this way, although in the specific embodiment described later on a mechanism of inserting and removing a VLAN tag will be described. Rather, the present invention is related to the problems created in relation to the FCS when the packet is altered as outlined above.
It will be appreciated that whenever the overall content of the data packet changes the FCS at the end of the data packet must also be changed if it is to remain consistent with the content of the packet itself. However, in a circumstance where a packet is to be altered as outlined above it is also necessary to check the current FCS for correspondence with the existing data packet in order to detect any errors, before discarding the FCS and replacing it with the new one.
There have previously been proposed methods for dealing with the requirement to change the FCS when the content of the data packet changes but these have exhibited certain problems. For instance, it has been proposed simply to recalculate the FCS without checking the integrity of the received data and just transmitting the altered packet with a good FCS on the assumption that a packet containing an error would have been dropped before it reached the point at which the packet was altered. Such methods do not taken into account the possible corruption of a packet while it is being handled in the device performing the alteration to the packet. For instance, a good packet could be corrupted while being stored in the memory. A good FCS would then be appended to a bad packet and a receiving device would accept the packet and try to treat the corrupted data as valid data.
A second previously proposed method uses a multiplexer to control the flow of data to the transmission section of the communications hub and another data path to check the previous FCS. However, the generation in this scheme of two data paths raises the possibility that data corruption may occur on the transmit path which would not be detected on the checking path and this would result in the same difficulties as mentioned above. In this scheme, there is also a considerable delay introduced in the transmit path in the case that a section of the packet is being removed, for instance a VLAN tag. In this case, the FCS checker still needs to process the removed bits along with the original FCS before the transmission can be completed with the new FCS. Typically this introduces a requirement for 64 bits of delay into the transmission path, reflecting the sizes of the original FCS and VLAN tag being 32 bits.
A third general approach to the problem mentioned above is to use a mathematical algorithm to calculate the position of the change in the data in the packet and applying a corresponding offset to the existing FCS to correct it for the modified packet. This solution however requites complex mathematical calculation to be carried out on the asserted data and the existing packet and the additional results. This process involves calculating several FCSs using different parts of the packet along with various masks and is very gate intensive when implemented in hardware.
SUMMARY OF THE INVENTION
The present invention provides apparatus for the alteration and output of an input data packet in a computer network, the data packet comprising communication data, and check data, the check data bearing a predetermined relationship to the communication data whereby integrity of the data packet can be checked; the apparatus comprising:
means arranged to alter the communication data of an input data packet;
storage means arranged to store said data packet such that said communication data may be output from said storage means in either its un-altered or altered condition;
output means arranged to receive from said storage means said communication data in its altered condition, to determine new check data on the basis of said communication data in its altered condition, and to output said communication data in its altered condition and said new check data as an output data packet; and
checking means arranged to receive from said storage means said communication data in its unaltered condition and said check data of said input packet, to determine whether said received check data bears said predete
Drummond-Murray Justin
Law David
Parry Rob
3Com Corporation
McDonnell & Boehnen Hulbert & Berghoff
Olms Douglas
Vanderpuye Ken
LandOfFree
Data packet transmission does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data packet transmission, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data packet transmission will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2955906