Transit Note #6
RN1: Forward Checksum
Andre DeHon
Original Issue: May 1990
Last Updated: Tue Nov 9 12:31:53 EST 1993
Need
When using RN1 in a complete system, the system should
provide a forward checksum on data sent through the network. The routing
protocol at the level implemented on RN1 provides checksums on data back to
the sending processor to allow the source responsible protocol to be
implemented. However, at this level, no indication is provided to the
receiving node so that can establish the integrity of the data it
receives.
A forward checksum is needed to:
- detect bit errors in data occurring at any point between the
source and destination
- detect data stream splicing when using cascaded routers
(tn4)
Form
The forward checksum can be just about any simple checksum. A CRC checksum
would probably work well and can be easily implemented in hardware. The
checksum should probably be as wide as the data path so that it only requires
an additional cycle to transmit. Longer checksums are, of course,
feasible.
Mechanism
Since there is no other mechanism to inform the receiver of the validity of
the data it is receiving, it probably makes sense to implement the forward
checksum directly at the level of the network interface. That is, it
would probably be worthwhile to have this checksum automatically generated
by the hardware communicating with the network and automatically appended
to all outgoing data streams. Likewise, the hardware receiving the data
stream should automatically check the checksum.
We could either have the receiving hardware automatically deal with
errors or require intervention at a higher level. The receive could simply
inform the receiving node of the error. Alternately, it might be
preferable to have the receiver indicate the failure directly to the sender
without involving the receiving node.
The sending node could handle
this fault case as an extension of the source responsible protocol it is
implementing. For example, the source node could expect a status response
from the receiving hardware similar to that expected from network routers.
When the forward checksum detects an error, the receiver could then drop
the message and indicate the problem to the source in its status response.
The source would then retransmit the data as it does when a connection
fails at some routing component.
See Also...
References
- DeH90
-
Andre DeHon.
Shared Randomness.
Transit Note 4, MIT Artificial Intelligence Laboratory, May 1990.
[tn4 HTML link] [tn4 FTP link].
- Kni89
-
Thomas F. Knight Jr.
Technologies for Low-Latency Interconnection Switches.
In Symposium on parallel architecures and algorithms. ACM, June
1989.