Hey folks, It always bugged me back in the day that ZModem (and even Ymodem-G) left some performance on the table. For a 14.4 kbps modem with a theoretical perfect transfer rate of 1800 characters per second (assume no data compression, flawless connection, etc) -- ZModem would give you something like 1650-1660 cps and Ymodem-G would give you up to 1730 cps under ideal conditions. Ymodem-G of course had no error recovery (though it did send CRCs to help indicate whether or not there was a problem). In the interest of trying to use 100% of "upload" bandwidth, I always wanted to write a protocol that used the back channel to send CRCs from the 'download' computer to the upload source computer. (Even on asymmetrical protocols like USRobotics standards, 450 bps 'back channel' should be enough for this..) This protocol would operate like ZModem or YModem-G where the uploader just keeps streaming, but no CRCs would be sent with the transfer. Instead, the 'sender' computer would simply pre-calculate CRCs for every 1K or so; the receiver computer would calculate after receiving that 1K, and send back to the uploader. The uploader would go back and verify that it was getting the right CRCs in the right order (you could pre-calculate these and store in RAM before the transfer starts to reduce CPU load during transfer). If no problems were encountered - you might hit that theoretical 1800 cps. If problems were encountered - you'd either pause for some period of time and then re-send the last 3-4 good sets of CRCs to alert the 'receiver' computer that the transfer had to resume from an earlier state and would start after those 3-4 CRC sets were sent. Anyway just some thoughts. Something I might try in C sometime with a couple of modems... John
On Mon, Oct 14, 2019 at 7:55 PM John Heritage via vcf-midatlantic < vcf-midatlantic@lists.vcfed.org> wrote:
This protocol would operate like ZModem or YModem-G where the uploader just keeps streaming, but no CRCs would be sent with the transfer. Instead, the 'sender' computer would simply pre-calculate CRCs for every 1K or so; the receiver computer would calculate after receiving that 1K, and send back to the uploader. The uploader would go back and verify that it was getting the right CRCs in the right order (you could pre-calculate these and store in RAM before the transfer starts to reduce CPU load during transfer). If no problems were encountered - you might hit that theoretical 1800 cps.
You will probably want to at least mark block boundaries, so that the sender and receiver can stay in sync if any bytes are dropped in transmission. Otherwise a single dropped byte could cause every successive block to be sent again. With a 1K block size, a 2-byte 'frame boundary' marker would give you an efficiency of 1024/1026 (99.8%), assuming the block doesn't contain embedded markers that need to be escaped. For random data you could guess that you'll get about 4 such bytes on average per block, so call it 1024/1034 (99.0%) efficient. I chose 2 bytes as the size of the frame marker so that a single escape byte could handle all of these cases: ESC n (n=0-63) - frame (x mod 64) follows (numbered starting from 0) ESC n (n=64-127) - current frame contains n-63 literal ESC bytes here ESC n (n=128-191) - end of file, file size should be (x mod 64) frames ESC n (n=192-255) - please send the CRC for frame (x mod 64) again The first 3 cases should be self-explanatory, the last case allows the receiver to send a 'frame' CRC in addition to the 'payload' CRC, so the sender can detect corrupt CRCs (or corrupt frame numbers). -ken
You will probably want to at least mark block boundaries
Hello Ken. Looks like that's your first post here. Please introduce yourself as is our tradition. How you found us, what are your interests in vintage computing, where you live, etc. -Evan K. (list admin) On Tue, Oct 15, 2019, 2:34 PM Kenneth Gober via vcf-midatlantic < vcf-midatlantic@lists.vcfed.org> wrote:
On Mon, Oct 14, 2019 at 7:55 PM John Heritage via vcf-midatlantic < vcf-midatlantic@lists.vcfed.org> wrote:
This protocol would operate like ZModem or YModem-G where the uploader just keeps streaming, but no CRCs would be sent with the transfer. Instead, the 'sender' computer would simply pre-calculate CRCs for every 1K or so; the receiver computer would calculate after receiving that 1K, and send back to the uploader. The uploader would go back and verify that it was getting the right CRCs in the right order (you could pre-calculate these and store in RAM before the transfer starts to reduce CPU load during transfer). If no problems were encountered - you might hit that theoretical 1800 cps.
You will probably want to at least mark block boundaries, so that the sender and receiver can stay in sync if any bytes are dropped in transmission. Otherwise a single dropped byte could cause every successive block to be sent again. With a 1K block size, a 2-byte 'frame boundary' marker would give you an efficiency of 1024/1026 (99.8%), assuming the block doesn't contain embedded markers that need to be escaped. For random data you could guess that you'll get about 4 such bytes on average per block, so call it 1024/1034 (99.0%) efficient.
I chose 2 bytes as the size of the frame marker so that a single escape byte could handle all of these cases: ESC n (n=0-63) - frame (x mod 64) follows (numbered starting from 0) ESC n (n=64-127) - current frame contains n-63 literal ESC bytes here ESC n (n=128-191) - end of file, file size should be (x mod 64) frames ESC n (n=192-255) - please send the CRC for frame (x mod 64) again
The first 3 cases should be self-explanatory, the last case allows the receiver to send a 'frame' CRC in addition to the 'payload' CRC, so the sender can detect corrupt CRCs (or corrupt frame numbers).
-ken
Interesting Ken - thank you; Ahh interesting - is that because a one byte slip/drop might not allow the CRC algorithm to work properly? I guess alternatively if you had a truly symmetrical connection you could send the entire file back on the other channel as a brute force method of ensuring 100% correct and 100% efficiency? On Tue, Oct 15, 2019 at 2:33 PM Kenneth Gober <kgober@gmail.com> wrote:
On Mon, Oct 14, 2019 at 7:55 PM John Heritage via vcf-midatlantic < vcf-midatlantic@lists.vcfed.org> wrote:
This protocol would operate like ZModem or YModem-G where the uploader just keeps streaming, but no CRCs would be sent with the transfer. Instead, the 'sender' computer would simply pre-calculate CRCs for every 1K or so; the receiver computer would calculate after receiving that 1K, and send back to the uploader. The uploader would go back and verify that it was getting the right CRCs in the right order (you could pre-calculate these and store in RAM before the transfer starts to reduce CPU load during transfer). If no problems were encountered - you might hit that theoretical 1800 cps.
You will probably want to at least mark block boundaries, so that the sender and receiver can stay in sync if any bytes are dropped in transmission. Otherwise a single dropped byte could cause every successive block to be sent again. With a 1K block size, a 2-byte 'frame boundary' marker would give you an efficiency of 1024/1026 (99.8%), assuming the block doesn't contain embedded markers that need to be escaped. For random data you could guess that you'll get about 4 such bytes on average per block, so call it 1024/1034 (99.0%) efficient.
I chose 2 bytes as the size of the frame marker so that a single escape byte could handle all of these cases: ESC n (n=0-63) - frame (x mod 64) follows (numbered starting from 0) ESC n (n=64-127) - current frame contains n-63 literal ESC bytes here ESC n (n=128-191) - end of file, file size should be (x mod 64) frames ESC n (n=192-255) - please send the CRC for frame (x mod 64) again
The first 3 cases should be self-explanatory, the last case allows the receiver to send a 'frame' CRC in addition to the 'payload' CRC, so the sender can detect corrupt CRCs (or corrupt frame numbers).
-ken
On Tue, Oct 15, 2019 at 7:42 PM John Heritage <john.heritage@gmail.com> wrote:
Ahh interesting - is that because a one byte slip/drop might not allow the CRC algorithm to work properly?
Yes. There are 2 kinds of failures that you need to handle: 1. a byte is corrupted during transmission, and is received incorrectly. 2. a byte is dropped during transmission, and is never received. The CRC will handle the first case with no trouble, but in the second case it won't be obvious to the receiver that the 1024 bytes they got was actually 1023 bytes from the first block (with 1 byte missing), plus the first byte of the second block. So the receiver will calculate the CRC and it will be wrong, which is fine because the first block needs to be retransmitted anyway. But then, the receiver will calculate the CRC for the second block, starting with the second byte (because the receiver doesn't know that the last byte of the first block was actually supposed to be the first byte of the second), which will also end up wrong, and this will continue to happen for every successive block. Sending the entire file back the other way would work as a confirmation of success, but if there are any errors (in either direction) you still need a way to figure out which parts of the file need to be retransmitted and communicate that information to the receiver, which is kind of the same problem all over again. -ken
That’s what timeouts are for. The receiver should time out because it’s waiting too long for the missing byte. The transmit side has a timeout to re-transmit, so the receive side should also have a timeout to discard the current incomplete message. Ideally, the dropped byte would generate a framing or other error at the receiving hardware (UART?ACIA/etc) which can also be used to flag the current frame as potentially corrupted. Or, do as synchronous protocols do and have a unique character that only appears at the start of a frame, never in the data stream. That way if the character is ever seen, it allows the receiver to re-sync and know exactly where it is in terms of frames coming in. If a byte is dropped, the receiver will see the reserved character and know to throw away the incomplete frame and just receive the new one that is arriving. Synchronous protocols are so much easier than asynchronous ones. Bob
On Oct 16, 2019, at 2:07 PM, Kenneth Gober via vcf-midatlantic <vcf-midatlantic@lists.vcfed.org> wrote:
On Tue, Oct 15, 2019 at 7:42 PM John Heritage <john.heritage@gmail.com> wrote:
Ahh interesting - is that because a one byte slip/drop might not allow the CRC algorithm to work properly?
Yes. There are 2 kinds of failures that you need to handle: 1. a byte is corrupted during transmission, and is received incorrectly. 2. a byte is dropped during transmission, and is never received.
The CRC will handle the first case with no trouble, but in the second case it won't be obvious to the receiver that the 1024 bytes they got was actually 1023 bytes from the first block (with 1 byte missing), plus the first byte of the second block. So the receiver will calculate the CRC and it will be wrong, which is fine because the first block needs to be retransmitted anyway.
But then, the receiver will calculate the CRC for the second block, starting with the second byte (because the receiver doesn't know that the last byte of the first block was actually supposed to be the first byte of the second), which will also end up wrong, and this will continue to happen for every successive block.
Sending the entire file back the other way would work as a confirmation of success, but if there are any errors (in either direction) you still need a way to figure out which parts of the file need to be retransmitted and communicate that information to the receiver, which is kind of the same problem all over again.
-ken
Serial communication always scared me. I wish I understood it better. On Wed, Oct 16, 2019 at 5:13 PM Bob Applegate via vcf-midatlantic < vcf-midatlantic@lists.vcfed.org> wrote:
That’s what timeouts are for. The receiver should time out because it’s waiting too long for the missing byte. The transmit side has a timeout to re-transmit, so the receive side should also have a timeout to discard the current incomplete message.
Ideally, the dropped byte would generate a framing or other error at the receiving hardware (UART?ACIA/etc) which can also be used to flag the current frame as potentially corrupted.
Or, do as synchronous protocols do and have a unique character that only appears at the start of a frame, never in the data stream. That way if the character is ever seen, it allows the receiver to re-sync and know exactly where it is in terms of frames coming in. If a byte is dropped, the receiver will see the reserved character and know to throw away the incomplete frame and just receive the new one that is arriving.
Synchronous protocols are so much easier than asynchronous ones.
Bob
On Oct 16, 2019, at 2:07 PM, Kenneth Gober via vcf-midatlantic < vcf-midatlantic@lists.vcfed.org> wrote:
On Tue, Oct 15, 2019 at 7:42 PM John Heritage <john.heritage@gmail.com> wrote:
Ahh interesting - is that because a one byte slip/drop might not allow the CRC algorithm to work properly?
Yes. There are 2 kinds of failures that you need to handle: 1. a byte is corrupted during transmission, and is received incorrectly. 2. a byte is dropped during transmission, and is never received.
The CRC will handle the first case with no trouble, but in the second case it won't be obvious to the receiver that the 1024 bytes they got was actually 1023 bytes from the first block (with 1 byte missing), plus the first byte of the second block. So the receiver will calculate the CRC and it will be wrong, which is fine because the first block needs to be retransmitted anyway.
But then, the receiver will calculate the CRC for the second block, starting with the second byte (because the receiver doesn't know that the last byte of the first block was actually supposed to be the first byte of the second), which will also end up wrong, and this will continue to happen for every successive block.
Sending the entire file back the other way would work as a confirmation of success, but if there are any errors (in either direction) you still need a way to figure out which parts of the file need to be retransmitted and communicate that information to the receiver, which is kind of the same problem all over again.
-ken
participants (5)
-
Bob Applegate -
Chris Fala -
Evan Koblentz -
John Heritage -
Kenneth Gober