dwh@cfcl.UUCP (Dave Hamaker) (05/15/88)
Trick Question for the Day: Using ordinary asynchronous RS-232 full-duplex serial communications, is an error-detecting/correcting file-transfer protocol possible which is as fast as or faster than non-protocol transfer? If not, why not? If so, how? This is not a question about data compression or contrived circumstances. -Dave Hamaker ...!ucbvax!ucsfcgl!hoptoad!cfcl!dwh
mikep@lakesys.UUCP (Mike Pluta) (05/23/88)
In article <303@cfcl.UUCP> dwh@cfcl.UUCP (Dave Hamaker) writes: > >Using ordinary asynchronous RS-232 full-duplex serial communications, is an >error-detecting/correcting file-transfer protocol possible which is as fast >as or faster than non-protocol transfer? If not, why not? If so, how? I dont think it's possible to obtain the speed you ask on the host CPU, but with the addition of a "black box" dedicated to doing the error detection and correction it may be achieved. Multitech offeres MNP level V in their modems as I'm sure other manufacturers do- if you arent going through a modem, there are manufacturers of such devices for direct connect lines (Black Box Corp, etc). -- Michael J Pluta (mikep@lakesys.UUCP) c/o | {ihnp4,uwvax}! Tri-Sys Computer Corp., Inc. | uwmcsd1!lakesys! 207 East Buffalo Street, Suite 600 | mikep Milwaukee, WI 53202 |
jbs@fenchurch.MIT.EDU (Jeff Siegal) (05/23/88)
In article <303@cfcl.UUCP> dwh@cfcl.UUCP (Dave Hamaker) writes: >Trick Question for the Day: > >Using ordinary asynchronous RS-232 full-duplex serial communications, is an >error-detecting/correcting file-transfer protocol possible which is as fast >as or faster than non-protocol transfer? If not, why not? If so, how? No; at the very least, you need to send some error checking/correcting information (checksum, CRC, RS ECC, etc.) along with the data so you can detect or correct the errors. This will make it take longer. Jeff Siegal
cavanaug@ncrcce.StPaul.NCR.COM (John David Cavanaugh) (05/24/88)
In article <303@cfcl.UUCP> dwh@cfcl.UUCP (Dave Hamaker) writes: >Using ordinary asynchronous RS-232 full-duplex serial communications, is an >error-detecting/correcting file-transfer protocol possible which is as fast >as or faster than non-protocol transfer? If not, why not? If so, how? It depends on the error rate of your transmission medium. A reliable protocol will require the transmission of more characters than just sending the bare data stream. However, the correcting protocol will generally do retransmission of fairly small chunks of data. To figure what is more efficient, you have to consider the error rate and the amount of data that would have to be retransmitted when you have an error. For example, if you want to send a 1 meg file and you average 1 error every 5 million characters, you expect to send 1.2 characters for every character that ends up in the destination file (the first four times, the file made it OK, but the fifth, you had an error and had to retransmit the whole thing). A protocol that used 1k blocks with 10 bytes of ack/checksum/etc. would expect to get the file across at a rate of 1.01 characters (roughly) per character in the file. On the other hand, if your files are usually so small that they fit into a single block, you wouldn't gain much. And if your error rate is zero, you only lose. Note that one major gain in using a reliable protocol is that you _know_ your file is intact at the destination. It's frustrating to send a big file somewhere and have a single-character error make the whole thing worthless. John Cavanaugh John.Cavanaugh@StPaul.NCR.COM NCR Comten, Inc. 2700 Snelling Ave N. The opinions expressed ... St. Paul, MN 55113 (612) 638-2822
jk3k+@ANDREW.CMU.EDU (Joe Keane) (05/27/88)
In article <303@cfcl.UUCP> dwh@cfcl.UUCP (Dave Hamaker) writes: >Using ordinary asynchronous RS-232 full-duplex serial communications, is an >error-detecting/correcting file-transfer protocol possible which is as fast >as or faster than non-protocol transfer? If not, why not? If so, how? Sure, why not? Assuming no errors (otherwise the question is really stupid), the only overhead is acks from the receiver (`block 0 OK', `block 1 OK', ...) Assuming the protocol has a reasonable window and the acks are smaller than the data, this doesn't slow anything down. Of course most protocols delimit the blocks. --Joe
daver@daver.UUCP (Dave Rand) (05/28/88)
In article <8WbMLYy00Vs8EzltB4@andrew.cmu.edu> jk3k+@ANDREW.CMU.EDU (Joe Keane) writes: >In article <303@cfcl.UUCP> dwh@cfcl.UUCP (Dave Hamaker) writes: >>Using ordinary asynchronous RS-232 full-duplex serial communications, is an >>error-detecting/correcting file-transfer protocol possible which is as fast >>as or faster than non-protocol transfer? If not, why not? If so, how? > >Sure, why not? Assuming no errors (otherwise the question is really >stupid), the only overhead is acks from the receiver (`block 0 OK', >`block 1 OK', ...) Assuming the protocol has a reasonable window and >the acks are smaller than the data, this doesn't slow anything down. >Of course most protocols delimit the blocks. Incorrect. In order for a windowed protocol to work, a CRC/checksum and packet number must be attached to the data. For example, in the uucico g protocol (the "standard"), the format is 6 bytes of header, and 58 bytes of data per packet. There is normally up to three windows outstanding, and you are correct in assuming that if the ACKS take less time to transmit than the data outstanding, you will achieve maximum transmission rate. However, as may be obvious, if you cannot use every byte of transmitted data for the file, then you are not using 100 % of the channel capacity. In the g protocol, each packet is 64 bytes. The ACTUAL file occupies 58 of these bytes, thus the maximum throughput of a standard uucp connection is 58/64, or 90.625% of channel capacity. The following table summarizes this: bps rate throughput with g protocol 300 27 cps (characters per second) 1200 109 cps 2400 218 cps 9600 870 cps 19200 1740 cps Even if you limit the "error checking" information to a few bytes at the end of the file, the full channel capacity cannot be used. If you compress the data, or otherwise alter it during transmission, you can, of course, increase the transfer rate. But with any error checking protocol, you must ADD information to the file, to ensure that it was received correctly. When you add information, it takes longer to transmit, and thus cannot achieve full utilization of a channel. Summary: It is not possible to implement an error-detecting/correcting file transfer protocol which is as fast as a non-protocol transfer, due to the fact that additional information must be added to the file to ensure that the received data is correct. If the data is compressed or altered as part of the protocol, it is possible, but this was specifically ruled out in the original posting. Dave Rand
dwh@cfcl.UUCP (Dave Hamaker) (05/31/88)
<303@cfcl.UUCP> <698@lakesys.UUCP> <692@ncrcce.StPaul.NCR.COM> <9295@eddie.MIT.EDU> <8WbMLYy00Vs8EzltB4@andrew.cmu.edu> In article <303@cfcl.UUCP> I ask the trick question: > >Using ordinary asynchronous RS-232 full-duplex serial communications, is an >error-detecting/correcting file-transfer protocol possible which is as fast >as or faster than non-protocol transfer? If not, why not? If so, how? In article <698@lakesys.UUCP> mikep@lakesys.UUCP (Mike Pluta) suggests the use of MNP modems and the like. This is a pretty good answer. MNP modems can, in fact, outperform non-protocol transfer. However, they do this by using synchronous communications, saving enough in start/stop bits to more than offset the added protocol overhead. This violates the stipulation in my question for asynchronous communications. To restore a raw speed advantage to non-protocol transfer, just allow it the use of synchronous communications. In article <692@ncrcce.StPaul.NCR.COM> cavanaug@ncrcce.StPaul.NCR.COM (John David Cavanaugh) writes that non-protocol transfers are slower when there are errors because it takes so much time to send the whole thing over. This was also the message of two people who sent me email. It's a good point, but it does not answer the question I was trying to communicate. In article <9295@eddie.MIT.EDU> jbs@fenchurch.MIT.EDU (Jeff Siegal) answers no, because additional error-checking/correcting information must accompany the data for error-detection/correction to be possible. Another person who sent me email came to the same conclusion. This is the answer I expected. Jeff Siegal deserves credit for putting it forward; there was a hint I had something up my sleeve. In article <8WbMLYy00Vs8EzltB4@andrew.cmu.edu> jk3k+@ANDREW.CMU.EDU (Joe Keane) answers yes, because a windowed protocol can overlap returning ACK's with forward transmission. Maybe he interpreted "as fast as" to mean sending characters at the same rate. He does not mention the need for additional checking information, and thus provides the receiver no way to determine the correctness of the data. Yet it is supposed to send back "block n OK" messages. Protocol transfers and non-protocol transfers have no speed advantage over each other in terms of the raw data to be sent. Since the non-protocol transfer sends nothing else, protocol transfers cannot be faster. If it is true that additional information must be communicated for checking to be possible, and it is, how can protocol transfers avoid being slower? THE CHECKING INFORMATION CAN TAKE THE FORM OF FEEDBACK; IT CAN TRAVEL IN THE OTHER DIRECTION (full duplex, remember?)! This by itself will not quite reach "as fast as" performance. Some "attention" signal is needed which is distinct from data. Asynchronous RS-232 even provides this, in the form of the "break." An example protocol should make this clear: The data is sent non-stop. It is divided, conceptually, into packets of some specific size. Packets are numbered consecutively modulo 256. A 16-bit CRC is calculated for each packet, prefixed by its sequence number (the sequence number byte is pumped into the CRC generator before the first data byte). As each packet is received, four bytes of check infor- mation are returned in the opposite direction (overlapping the receipt of the next packet). The first byte of the check sequence is something specific (like SOH) for framing. The second byte is the sequence number of the associated packet. The third and fourth bytes are the CRC. A break signal causes the receiver to return the check information for the current short packet (if any), return its own break signal, and react to the next input character. It will either be another break, signaling the end of the transmission; or a sequence-number byte followed by two CRC bytes on the sequence number, followed by retransmitted data (at this point the receiver is back to normal). If the CRC of the sequence number received is wrong, the receiver sends back a break and ignores data until another break is received. A break is also the receiver's final response to the break which marks the end of the transmission. A "transmission window" is also needed. This extends some number of packets beyond the first packet which is waiting for check information to be returned. The window is advanced as check information is verified. The sender may not send data outside the window and the receiver may deduce from the highest packet received which earlier packets may be presumed correct (and written to disk, etc.). There is no framing information with the data, and the receiver should actually act as if the window is a little larger that it actually is. This prevents things like phantom characters caused by line noise from advancing the receiver's view of the window to the point where the receiver would be misled to accept an unverified packet. The window needs to be large enough to smooth out the effect of transmission delays. I'm sure everyone will agree that this protocol meets the "as fast as" requirement, although it is possible to quibble. A non-protocol transfer doesn't need the two break signals at the end. For that matter, the sender has to wait for all outstanding check data before sending the final break (as was pointed out in email from a person who knew more or less what I was up to, from prior contact with my ideas). But, then, how DO you tell when a non-protocol transfer is finished? How long does THAT process take? The example protocol makes a point, but I wouldn't propose it as a practical protocol. Facilities for handling break signals are often deficient, for one thing. There's no flow control, no timeout for lost data, and so forth. Why bring the subject up then? Well, I had two reasons: 1. I think it's good to be reminded that looking at problems in unconventional ways can result in solutions for the seemingly impossible problem. 2. I wanted to give some publicity to my design for a file-transfer protocol which takes advantage of these ideas, but which is intended for real world use. I'll email the specification document to anyone who asks (I'm reluctant to post it: it's about fifty pages long, would require a multi-part posting, and I'm not sure there is a good place to post something like it). Ideally, I'm hoping to hook up with anyone out there in netland who might be interested in prototyping the design. -Dave Hamaker ...!ucbvax!ucsfcgl!hoptoad!cfcl!dwh
jbs@fenchurch.MIT.EDU (Jeff Siegal) (06/01/88)
In article <304@cfcl.UUCP> dwh@cfcl.UUCP (Dave Hamaker) writes: >[How an error-controlled protocol transfer CAN be as fast as a > non-controlled transfer] I'm impressed. Good stumper, and a good protocol idea. Anyone know if this has been implemented and/or used? Jeff Siegal
caf@omen.UUCP (06/02/88)
While reading Dave's comments on file transfers I thought I'd pass on some
of the lessons I learned while developing ZMODEM and some of its antecedents.
In article <304@cfcl.UUCP> dwh@cfcl.UUCP (Dave Hamaker) writes:
....
:Protocol transfers and non-protocol transfers have no speed advantage over
:each other in terms of the raw data to be sent. Since the non-protocol
:transfer sends nothing else, protocol transfers cannot be faster. If it
:is true that additional information must be communicated for checking to
:be possible, and it is, how can protocol transfers avoid being slower?
:THE CHECKING INFORMATION CAN TAKE THE FORM OF FEEDBACK; IT CAN TRAVEL IN
:THE OTHER DIRECTION (full duplex, remember?)! This by itself will not
Some modems are more full duplex than others. The current crop of
v.29 and PEP based high speed modems cannot handle too frequent
ACKs without a severe throughput loss. At best, it costs as much
to send a CRC in one direction as the other when using these modems.
:quite reach "as fast as" performance. Some "attention" signal is needed
:which is distinct from data. Asynchronous RS-232 even provides this, in
:the form of the "break."
Since many systems cannot pass a "break" signal, a real world
protocol must reserve a code combination instead. This adds
some overhead.
:A break signal causes the receiver to return the check information for the
:current short packet (if any), return its own break signal, and react to
:the next input character. It will either be another break, signaling the
As a practical matter, there's no guarantee what a break
signal will look like at the other end. It depends on the
receiving UART and the transmission medium. On some devices
it looks like simple null characters. Break generation hasn't
progressed much beyond the break key on a Teletype ASR33.
Protocolwise, a break is somewhere between a cherry bomb and a
nuke.
:end of the transmission; or a sequence-number byte followed by two CRC
:bytes on the sequence number, followed by retransmitted data (at this
:point the receiver is back to normal). If the CRC of the sequence number
:received is wrong, the receiver sends back a break and ignores data until
:another break is received. A break is also the receiver's final response
:to the break which marks the end of the transmission.
:
:A "transmission window" is also needed. This extends some number of
:packets beyond the first packet which is waiting for check information to
:be returned. The window is advanced as check information is verified. The
:sender may not send data outside the window and the receiver may deduce
:from the highest packet received which earlier packets may be presumed
:correct (and written to disk, etc.). There is no framing information with
:the data, and the receiver should actually act as if the window is a little
:larger that it actually is. This prevents things like phantom characters
:caused by line noise from advancing the receiver's view of the window to
:the point where the receiver would be misled to accept an unverified packet.
The one thing I've learned for certain is that *nothing* can
be presumed in a protocol transfer. There is no guarantee the
receiver will receive the first, second, or third break signal
from the sender signifying bad data has been received. Then
again, if you're lucky you won't have to send a break, the
line disturbance might do it for you. Dat's da breaks, chum.
There isn't much of an upper bound on the number of extra
characters that might be inserted into the stream. Would you
believe several hours' worth of "UUUUUUUUUUUUUUUU" at 1200
bps? (I enhanced error recovery procedures after that one.)
That's one modem's rendition of dial tone.
In the absence of independently validated segments in the file
transmission, the receiver must buffer the entire file to be
very sure its been received intact unless the operating system
can trucate files on the fly. And of course the message the
sender sends to the receiver to indicate the end of file must
be difficult for noise to mimic.
:The window needs to be large enough to smooth out the effect of transmission
:delays.
:
:I'm sure everyone will agree that this protocol meets the "as fast as"
:requirement, although it is possible to quibble. A non-protocol transfer
We haven't even started on network protection, provisions for
multiple streams, and adaptive error control procedures.
In the case of ZMODEM transmitting with 1k subpacket length,
the overhead for sending the CRC is about one half per cent.
On a binary file, the overhead for network protection is
several times more.
ZMODEM actually uses feedback a bit like PROTDH. In the
absence of errors, ZMODEM in full streaming mode transmits but
one data header for the entire file. Each subpacket contains
only two protocol overhead characters (not counting CRC).
:doesn't need the two break signals at the end. For that matter, the sender
:has to wait for all outstanding check data before sending the final break
With CRC's in the forward direction, the ZMODEM sender doesn't
have to wait before sending the EOT. With the Relay protocol,
the sender may actually be several FILES ahead of the
receiver.
.....
: 1. I think it's good to be reminded that looking at problems in
: unconventional ways can result in solutions for the seemingly
: impossible problem.sirbu@GAUSS.ECE.CMU.EDU.UUCP (06/03/88)
The notion of a protocol which is "as fast" as non-protocol transfer is certainly interesting from a theoretical point of view. However, from a practical point of view, typical overhead in a protocol like HDLC is less than 10% (at least for file transfers where frames are near maximum size). Moreover, there are many silicon implementations of the HDLC standard. I doubt that there will be a great deal of commercial interest in a protocol which promises to offer--at most-- a 10% improvement in performance, lacks acceptance as a standard, and would require a substantial front end investment in chip to design in order to be provided at as low a cost (or as low a burden on the main CPU) as HDLC. Marvin Sirbu CMU
dwh@cfcl.UUCP (Dave Hamaker) (06/05/88)
In article <686@omen.UUCP> caf@omen.UUCP (Chuck Forsberg WA7KGX) applies
his experiences with ZMODEM and its predecessors as a basis for criticizing
a protocol which we both agree is not suitable for practical use. Note
that the entire article is a series of criticisms, with the exception of
a possible tacit approval of my first reason for bringing the subject up.
It doesn't sound like he wants any response from me, but I think the
average reader would come away with the impression that my "real"
protocol does not provide for modems which are not true full-duplex,
does nothing about "network protection," has no "provisions for multiple
streams," and ignores "adaptive error control procedures." All of these
are, in fact, dealt with in my "real" protocol (there is even a way the
receiver can get FILES ahead, but that's not obvious). I don't want to
get involved in an argumentative tit-for-tat exchange with Chuck, so
I'll leave things at that.
-Dave Hamaker
...!ucbvax!ucsfcgl!hoptoad!cfcl!dwhdwh@cfcl.UUCP (Dave Hamaker) (06/05/88)
In article <8806031410.AA26679@gauss.ece.cmu.edu> sirbu@GAUSS.ECE.CMU.EDU
(Marvin Sirbu) asserts that the at most 10% improvement in performance that
a "100%" protocol offers over HDLC is not interesting from a practical point
of view.
I am not aware of any significant penetration into the asynchronous RS-232
realm by HDLC, mostly due to cost and complexity factors. My design efforts
have not been at all targeted at the areas where HDLC use is significant
(although it doesn't follow that some of the ideas might not be fruitfully
applied there).
But I don't want to duck the real question about the practical significance
of the theoretical result. By itself, it's not all that significant now,
really. But, if it isn't forgotten, it may help make future protocols better.
And remember, while I have designed a protocol which incorporates the insight,
it does not follow that that is the only thing my protocol has going for it.
If you want to consider the significance of the whole, you should probably
send for the specs.
-Dave Hamaker
...!ucbvax!ucsfcgl!hoptoad!cfcl!dwhgoldfarb%hcx9@ucf.CSNET ("Benjamin I. Goldfarb") (06/06/88)
>There isn't much of an upper bound on the number of extra >characters that might be inserted into the stream. Would you >believe several hours' worth of "UUUUUUUUUUUUUUUU" at 1200 >bps? (I enhanced error recovery procedures after that one.) >That's one modem's rendition of dial tone. ------ --- ------- --------- -- ---- ---- OH YEAH? More likely the "UUUUUUUUUUU" was an erroneously initiated test mode in the modem in question. Racal-Vadics are notorious for this but the feature can be disabled by either a dip switch or a strap option. A stream of ASCII U's makes for a good digital test because U is 01010101, so a stream of them creates a nice, big, fat square wave on a scope. Sorry to be so picky, but I never saw a modem "render" a dial tone. Ben Goldfarb University of Central Florida goldfarb@ucf-cs.ucf.edu {decvax,peora,uflorida,codas}!ucf-cs!goldfarb
caf@omen.UUCP (Chuck Forsberg WA7KGX) (06/09/88)
In article <8806061401.AA04016@hcx9.ucf.edu> goldfarb%hcx9@ucf.CSNET ("Benjamin I. Goldfarb") writes:
:>There isn't much of an upper bound on the number of extra
:>characters that might be inserted into the stream. Would you
:>believe several hours' worth of "UUUUUUUUUUUUUUUU" at 1200
:>bps? (I enhanced error recovery procedures after that one.)
:>That's one modem's rendition of dial tone.
: ------ --- ------- --------- -- ---- ----
:
:OH YEAH? More likely the "UUUUUUUUUUU" was an erroneously
:initiated test mode in the modem in question. Racal-Vadics are
:notorious for this but the feature can be disabled by either
:a dip switch or a strap option. A stream of ASCII U's makes for a
:good digital test because U is 01010101, so a stream of them
:creates a nice, big, fat square wave on a scope.
:
:Sorry to be so picky, but I never saw a modem "render" a
:dial tone.
:
: Ben Goldfarb
: University of Central Florida
: goldfarb@ucf-cs.ucf.edu
: {decvax,peora,uflorida,codas}!ucf-cs!goldfarb
Come to think of it, the dialtone rendition might not have
been a string of U's, typically seen when one of the loopback
modes is activated. However, the point still stands, the
modem would emit a stream of characters if a caller
disconnected in just the right way, without any dead time
between loss of carrier and the onset of dial tone. This
was on a stepper switch, the "precision" dial tone on DTMF
lines would be less likely to do this.
I didn't mention, however, several other ways that a large
number of characters may be "invented" by the modem or other
parts of the transmission medium, including buffer pointer
errors and scramblers losing sync.
So, yes, I have seen a modem "render" a dial tone. More to
the point, the observation of the effect of that and related
impairments remains valid in respect to protocol discussions.