Text 359, 264 rader
Skriven 2005-05-31 22:32:59 av Michiel Broek (2:280/2802)
Ärende: Corrected FSP-1020
==========================
Hello,
a corrected version of the FSP-1020. I added the references to the CRC32
algorithm. The changed lines are marked with a | as first character.
**********************************************************************
FTSC FIDONET TECHNICAL STANDARDS COMMITTEE
**********************************************************************
Publication: FSP-1020
Revision: final draft.
Title: Binkp optional protocol extension CRC Checksum.
Authors: Tobias Ernst (publisher of this protocol),
Michiel Broek (documentation for FTSC).
Issue Date: 31 May 2005
Review Date: 31 May 2007
----------------------------------------------------------------------
Contents:
1. Definitions
2. Binkp CRC Checksum Mode
2.1 Introduction
2.2 Protocol specification
2.3 Further thoughts
2.4 CRC-32 Algorithm
3. Compatibility issues
A. References
B. History
----------------------------------------------------------------------
Status of this document
-----------------------
This document is a Fidonet Standard Proposal (FSP), issued by the
FTSC for the benefit of the Fidonet community.
This document specifies an optional Fidonet standard protocol for
the Fidonet community, and requests discussion and suggestions for
improvements.
This document is released to the public domain, and may be used,
copied or modified for any purpose whatever.
This document describes the binkp CRC option published by Tobias
Ernst on 12 januari 2000 (Paragraph 2). This paragraph has some
changes for use in ftsc documentation.
The original document can be found at:
http://www.physcip.uni-stuttgart.de/tobi/binkd/BINKP_CRC_PROPOSAL
1. Definitions
--------------
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL
NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL"
in this document are to be interpreted as described in [FTA-1006].
2. Binkp CRC Checksum Mode
--------------------------
2.1 Introduction
----------------
Binkp originally was designed to work on top of a reliable
transmission layer, i.E. a transmission layer that has its own
checksums, like TCP. Therefore, the Binkp specification does not
provide a way for controlling correct data transfer, because
it is assumed that the underlying TCP transport layer does the
necessary data integrity checks.
However, I have seen TCP connections trashing data at random, and
actually have suffered from mail loss because a file received by
binkd was not identical with the file that the sender has
transmitted.
Therefore, this document specifies an extension to the Binkp
protocol which allows data integrity checks by means of CRC32
checksums. It is intended as an *optional* feature in Binkp for
those nodes that live in places with an unreliable TCP routing
structure (like I seem to do), and it is fully backwards
compatible.
2.2 Protocol specification
--------------------------
During session handshake, a mailer that knows the CRC protocol
extension MAY send an "M_NUL OPT CRC" message. This indicates
that the mailer is able to process the CRC-extended "M_FILE"
messages described below, nothing more.
The other end which receives the OPT CRC message will switch to
CRC-secure mode (probably only if CRC-secure mode has been
allowed by the sysop for the particluar other end). Note that
even if this end previously has sent a M_NUL OPT CRC on its own,
it is not forced to switch to CRC mode, it is just an option.
In the following, the "sending end" is the Binkp mailer which is
transmitting a file, and the "receiving end" is the mailer which
is receiving it. Of course, in a Binkp session, both sides can
become both sending and the receiving ends.
When the sending end is in CRC-secure mode, it will send an
extended M_FILE message with an additional fifth argument,
specifying a CCITT CRC32 checksum for the file that is following.
This means that the mailer has to calculate the checksum before
transmitting the file.
The checksum is pre-conditioned and postconditioned. This means
that the initial CRC-value is 0xFFFFFFFF (preconditioning), and
after the final value has been computed, all bits must be in-
verted (postconditioning).
The format of the fifth M_FILE argument is a sequence of up to
eight hexadecimal digits in ASCII. Leading digits may be omitted,
trailing digits must not be omitted.
The receiving end, if it has sent an "M_NUL OPT CRC", MUST be
able to process M_FILE messages with either four or five
arguments. If it receives a M_FILE message with five arguments,
it will treat the fifth argument as a checksum and, after
receiving the file, will compare this checksum with the checksum
it has computed from the data that has been received.
If the checksums disagree, the receiving end has two options. It
can either send a M_SKIP for this file. This will cause a
non-destructive reject of the file, so that the session goes on,
but the remote site will mark the file as not sent successfully
and retransmit it in the next session. Or it can send a M_ERR,
indicating a fatail failure, which will terminate the session,
and also cause a non-destructive reject of this and all following
files. It is suggested that on the first CRC failure, a M_SKIP
is sent, but if the next file also has an error, indicating that
the session is completely faulty, a M_ERR could be transmitted
instead.
2.3 Further thoughts
--------------------
There are some disadvantages of this way of implementing CRC:
1. The CRC checksum must be computed before the file
transmission STARTS, instead of during the transmission.
2. The protocol will fail if errors don't occur spontaneous, but
regularly with an error rate greater than 1 error per file.
In this case, transmission will be impossible because all
files will always be rejected.
Why then implement it this way? It is the easiest way to
implement CRC fully backwards compatible, and it is the way that
requries the least amount of changes in the code of existing
binkp mailers. Even given the mentioned disadvantages, the
extension is good enough for detecting spontaneous transmission
errors, so that sysops will not loose valuable data, and so that
they can see that there is a problem in the network infrastructure
and fix it. That is, this extension is intended as a safeguard
against rare error conditions on a transport layer that still,
basically, is reliable.
This extension, however, is not suitable for transmission over a
transport layer which is unreliable by definition, as a standard
modem connection. But that was not the goal of binkp from the
beginning.
In the future, it might be worth considering an extension to the
binkp protocol which goes furhter. For example, one CRC32
checksum could be transmitted at the end of each frame, and a
mechanism for directly resending frames
2.4 CRC-32 Algorithm
--------------------
| The checksum algorithm that is used is CRC-32 following ITU-T's
specifications. For further information refer to the literature
list given below. The following pseudocode shows how to
calculate such a checksum for a file of N bytes indexed from 0 to
N-1 and stored in BUFFER. The XOR, AND and NOT logical
operations are to be executed bit-wise. In C, for instance, XOR
equals ^, AND equals &, and NOT equals ~.
// CRC, I, J, K are unsigned integers of at least 32 bits.
UNSIGNED LONG CRC, I, J, K
// Preconditioning
CRC = FFFFFFFF
// Loop through all bytes in the file
FOR J = 0 TO N-1
K = (CRC XOR BYTE#J) & 000000FF // (*)
FOR I = 8 DOWNTO 1
IF K AND 1 <> 0
THEN K = (K SHR 1) XOR EDB88320
ELSE
K = K SHR 1
ENDIF
END FOR // (**)
CRC = ((CRC SHR 8) AND 00FFFFFF) XOR K
END FOR
// Postconditioning: Flip all bits
CRC = NOT CRC;
Note that as in the line marked as (*), K can initially only get
values in the range from 0 to 255. Therefore it is a good idea
to replace the inner loop over I with a lookup table routine,
i.E. generate a lookup table for the outcomes of K after the loop
with initial values of K from 0 to 255, and then replace lines
(*) up to and including (**) with something like
K = LOOKUPTABLE [ (CRC XOR BYTE#J) XOR 000000FF ]
Author: Tobias Ernst
3. Compatibility issues
-----------------------
The CRC option cannot be used together with some other options
which also use extra parameters with the M_FILE messages.
A. References
-------------
[FSP-1018]
Binkp 1.0 Protocol specification.
[FTA-1006]
Key words to indicate requirement levels, Fidonet Technical
Standards Committee administrative. FTA-1006.
| [ITU-T V.42]
| International Telecommunications Union, Error-correcting
| Procedures for DCEs Using Asynchronous-to-Synchronous
| Conversion, ITU-T Recommendation V.42, 1994, Rev. 1.
|
| [ISO 3309]
| International Organization for Standardization,
| "Information Processing Systems--Data Communication
| High-Level Data Link Control Procedure--Frame Structure",
| ISO 3309, October 1984, 3rd Edition.
B. History
----------
Rev.1, 20050531:
First release, protocol extension published by Tobias Ernst
on 12 januari 2000 imported.
Greetings, Michiel Broek
Email: mbse@mbse.dds.nl
Fidonet: Michiel Broek at 2:280/2802
... A hunch is creativity trying to tell you something.
--- MBSE BBS v0.71.2 (GNU/Linux-i386)
* Origin: MBSE Linux BBS. Made in the Netherlands (2:280/2802)
|