From: dwh@vaxeline.ftp.com (David W. Hamaker)
Subject: Re: New modem transfer protocol  (Long - protocol weenies only)
Organization: FTP Software, Inc., Wakefield, MA
Date: Sat, 4 Apr 1992 03:26:45 GMT

In article <1992Mar30.020533.22305@ksmith.uucp> keith@ksmith.uucp (Keith Smith)
writes:

>In article <5410.29d48008@hayes.com> tnixon@hayes.com writes:
>>In article <mzbjr+fgerg@netcom.com>, gerg@netcom.com (Greg Andrews)
>>writes: 
>>
>>Not necessarily, assume that the receiver has the ability to back up 
>>and overwrite portions of the file it has already received.

It's also possible to use windowing techniques: if the sender is not
allowed to send more than n packets beyond the last packet for which
the CRC has been verified, receipt of packet m implies packet m-n is
good to the receiver (modulo injected line noise, etc. - you need an
added safety margin).

>>Here's how I would design the protocol:
>>
>>(1) The file sender has a limited number of DLE-sequences that are 
>>used for control.  One of them says "what follows is the file 
>>header", another is "I'm done sending", another is "final ACK OK", 
>>and another is "back up to position 'x' in the file".

Looking ahead to your next point, I don't think you mean ASCII DLE
here, but Keith appears to have read it that way.  I argue that the
escape character/sequence should be printable, and that for the most
part the control-character part of ASCII is a legacy from the days
of discrete-logic, electro-mechanical communications devices where
there were good reasons for reserving specific codes for various
control purposes.  The main result of that legacy today is that
computer code spaces contain a bunch of unprintables.  A printable
escape sequence enhances transparency and makes ordinary terminals
easier to use for line monitoring.

>>(2) The sender transmit data continuously.  What it DOES need to do 
>>is scan for occurences of the "escape" character.  In V.42bis, 
>>whenever the escape character occurs, the character is "rotated" (by 
>>adding 51, mod 256), so that data including large numbers of a 
>>single escape character doesn't get doubled in size; I would propose 
>>a similar mechanism for this protocol.  With this randomization of 
>>the escape character, transparentization should add only about 1/2 
>>of 1 percent overhead (unless you also decide to transparentize XONs 
>>and XOFFs or something like that).

Clever, but I see several drawbacks to such rotation.  You need more
mechanisms to do the rotation, and, especially, to detect and recover
from hits on the escape character, than are needed for a fixed escape
character scheme.  As described, such rotation assumes the channel
is otherwise transparent; the mechanisms will be complicated further
if some codes must be avoided.  Worst of all, I think rotation will
INCREASE overhead ON THE AVERAGE and for TYPICAL data, compared to a
fixed escape code chosen with reasonable care.

By the way, for proof of concept purposes, in theory it is possible
to avoid the .5% escape overhead.  The BREAK signal can be used for
the escape.  The reason this is not a practical method is that BREAK
signal detection/generation is often deficient in the real world.
Often, a BREAK signal and the NUL character look the same by the time
they reach your program.  There are other reasons for using some sort
of escape, such as transparency encoding, where BREAK is a bad choice
because BREAK is a fixed-time signal that takes longer than a character
time to send (in some cases quite a bit longer).

>Sounds good.  I think XON/XOFF has to go by the wayside.  One would need
>to keep something like this as simple as possible.  A single DLE would
>do, also, one would need to engineer the file header, Perhaps with
>null terminated strings of TEXT like:

I think it's important NOT to punt transparency issues.  It's one of the
needs that Kermit has filled and a reason for its success.  It's one of
the most-common user difficulties with XMODEM.

><SOH>filename<NUL>size_in_HEX[<NUL>otherstuff]<ENQ>Hexcoded_DLE<STX>
>                                                   ^^^^^^^^^^^^

I like leading-zero-suppressed hexadecimal too.  It's printable, more
compact than decimal, and expresses small numbers (sizes, offsets, etc.)
compactly.  Plus, it's open-ended.

>Might wanna throw 2 bits on front and back end (4 total) to make sure
>the DLE is in sync ? ? ?

How do you do this with normal serial interfaces?

>>
>>(3) Every received "n" characters (could be a fairly small number, 
>>to permit quick recovery, such as 32 bytes, or could simply be 
>>stated as "as frequently as possible, or as frequently as the 
>>receiver feels comfortable"), the receiver generates a frame going
>>back to the sender which says "over the range of characters 'n' to
>>'m', the CRC was 'p'".   If there are any problems with this (e.g., 

I'd rather imply position information by agreeing on the checking
interval.  The meat of the channel is the CRC's.  Everything else
adds to the communications load the sender has to deal with.

>How about:
><ACK>Current_Byte_count(in HEX)<NUL>Current_32bit_CRC(in HEX)<NAK>
>
>Can be sent at any point, even on every byte if need be (wasteful in
>real time).  Then the receiver can just keep track of the last good byte
>count, and if it's CRC doesn't match at that point re-start.
>
>No need to worry about file length, as the HEX strings get longer as the
>file get's bigger.
>
>>'n' is not the next unacknowledged character, or 'm' doesn't make 
>>sense [hasn't been sent yet, is lower than 'n', etc.], or 'p' 
>>doesn't match over that range], the sender would interrupt sending,
>>insert a "back up to position 'x'" command (x = the first
>>unacknowledged byte), and then resume sending at position 'x'.  
>>
>>Interestingly, this could be easily extended to permit restarting
>>failed transfers.  The receiver could send CRCs on, say, 1K chunks
>>of the file it already has, and the sender would pick up the
>>transmission at the point where the CRCs first failed to match. 
>>
>
>Not sure of this, logistically.  The reciever has no way of knowing
>where the last good byte was, since no header info. (what you are
>getting at right?)

The receiver just sends the CRC's on what it has of the file.  The
sender compares these to the CRC's of the file it still has.  The
first mismatch tells the sender where to start overwriting.  The
sender sends a "back up to position 'x'" command (only it now becomes
a "go forward to position 'x'" command).

>Perhaps it could ack ahead at header time by maintaining a table of
>previous acks as the file was transferred.  ie, at startup start acking
>CRC's out of your table until the first DLE comes along ? ? ? Or maybe
>maintain a table of the last n (n = 10?) acks and start from their,
>
>transmitter will start up on first bad ack packet.  in fact, use this to
>start the protocall, ack byte 0 with a 1 CRC:
>
><ACK>00<NUL>01<NAK>
>
>to start at byte F000:
>
><ACK>F000<NUL>CRC_val<NAK>
>
>Transmitter cranks up as soon as the first bad ACK packet hits.
>Make the file header part of the byte stream.
>
>>(4)  At the end of the file, the sender would include a sequence
>>indicating the end of the file.  The receiver would respond with the
>>CRC of the last "chunk". The sender would either respond with a
>>repetition of the last chunk (if the CRC was wrong) or some sort of
>>concluding sequence (or possibly the header of the next file). 
>
>Why wait?  The sender, can just keep plowing along ... <DLE> Next header
>... Oops tilt, backup if neccessary.

I came to the conclusion that the sender and receiver need to sync up
at the end of the file so they can agree they are done, and at the
beginning so they can agree about other things.  However, it's desirable
to somehow be able to do static or dynamic batching of files on top of
this.

>>Does what I've described above sound complex?  I'm just writing this 
>>off the top of my head, but it sounds pretty simple.  Maybe I should 
>>code it up so we can try it.
>
>Not at all,  KISS. :-)!
>
>>I don't know.  The "block identification" can be the absolute file 
>>position, with a 32-bit "identifier" (assuming you're sending files
>>of less than 4 gigabytes).  That's the way ZMODEM works, by the way; 
>>the ZRPOS frame specifies file position as a 32-bit number.
>
>Like I said above, encode the ACK packets in HEX.  Who cares about the
>extra time really on the back channel?

To emphasize this, zero-suppressed hexadecimal takes one byte to encode
0-15, two bytes to encode 16-255, three bytes to encode 256-4095, and
four bytes to encode 4096-65535.  A 32-bit number encodes ALL of these
in four bytes, NON-transparently.  By the time hexadecimal hits 4GB,
it only takes eight bytes, and can keep going (in these days of 1.2GB
disk drives).

>>
>>If the sender's "go back to n" sequence is corrupted or lost, the 
>>receiver will eventually indicate it because the CRC will be wrong 
>>on the data, and the sender will go back and try again.
>>
>
>Back to the last correct file position with <DLE>NEWPOS<STX> maybe.  I'm
>not really sure about the DLE coding though.
>
>>You don't need that if acknowledgements can be sent "asynchronously" 
>>(and random times) and cover a variable amount of the data.  In 
>>point-to-point dial-up connections, you might want to have very 
>>frequent (as often as possible) CRC checks, but on connections 
>>through packet-switched networks where you're paying by the byte, 
>>you might want to only ack every few hundred bytes.  In the method I 
>>described above, the receiver controls this.

I think it is pretty much of a wash as to who controls this.  Remember,
though, that the whole point of the protocol is that the receiver is
absorbing the data nonstop.  We can't be very sympathetic to a receiver
that can't keep up.  If the sender gets overrun, however, this will
mess up the data flow to the receiver too, which argues for giving the
sender control of this.  I chose to have them reach an agreement.

>Now figuring about 20 bytes in a large ack packet acking every 32-64
>bytes doesn't sound unreasonable.
>
>>
>>> I don't really think it's worth the effort to try to wring another 3.5%
>>> increase in throughput out of the transfer.  The gains are just too small.
>>> It's certainly fun to apply one's mind to an interesting challenge, but
>>> it's going to be very hard to outthink the creators of protocols like
>>> Kermit and Zmodem.
>>
>>You're right about whether it is "worth it" for another few percent
>>throughput. There's an awful lot of momentum for ZMODEM out there! 
>>It would be an interesting intellectual exercise to see if we could
>>make it work. 
>
>Also just goofing around for mental exercise. <G>

I've come to the conclusion that I probably wouldn't have bothered to do
my design if Zmodem had been around when I started.  But, I didn't find
Zmodem until I was almost finished.  This makes for a different "worth
it" question.  Do I toss an EXTENSIVELY thought-out design without
giving it a try?  I think not.  There's also a potential for other gains
besides the 3%.  Because error-checking granularity can be much finer,
performance on noisy lines could be much better.  It might also be nice
to get away from Zmodem's proprietary tendencies, or to at least give
Zmodem some competitive pressure about them.  Then there's the potential
of a single protocol with the performance of Zmodem and the generality
of Kermit, which I believe my design contains.

You might consider evaluating and discussing my design as mental
exercise (take new look at it Toby?).  It's pretty clear to me that my
spec document could be better and that absorbing it all is a bit of a
challenge (I love getting advice about improving it, but this is also
a very non-profit project and I have already spent hours and hours and
hours writing it).

If I do get around to implementing my design (and I have a terrible track
record in this regard), I plan to graft it into C-Kermit.

>>
>>-- 
>>Toby Nixon, Principal Engineer      | Voice   +1-404-840-9200  Telex 151243420
>>Hayes Microcomputer Products, Inc.  | Fax     +1-404-447-0178  CIS   70271,404
>>P.O. Box 105203                     | BBS     +1-404-446-6336  AT&T    !tnixon
>>Atlanta, Georgia  30348             | UUCP uunet!hayes!tnixon  Fido   1:114/15
>>USA                                 | Internet                tnixon@hayes.com
>
>-- 
>Just a (Not So) Humble UNIX GURU out in the Styx of North Carolina ...
>Keith Smith          uunet!ksmith!keith            5719 Archer Rd.
>Digital Designs      BBS 1-919-423-4216            Hope Mills, NC 28348-2201

-Dave Hamaker
 cfcl!dwh@apple.com
 dwh@ftp.com
Newsgroups: comp.dcom.modems