info-kermit@ucbvax.ARPA (08/01/85)
From: Frank da Cruz <SY.FDC@CU20B.ARPA> Info-Kermit Digest Thu, 1 Aug 1985 Volume 3 : Number 11 SPECIAL SLIDING WINDOWS ISSUE -- Comments on Comments on Lurching Windows Sliding Windows -- When to Write to Disk? Mutual Exclusivity of Sliding Windows and Long Packets? Implied ACKs, Half Duplex Windows Full-Duplex Windowing vs CP/M, et al Proposal for Half Duplex Windows Examination of Proposals Full Duplex Sliding Windows -- Let's Give Them a Try ---------------------------------------------------------------------- Date: Sun, 28 Jul 85 21:32:40 pdt From: "Scott Weikart; Community Data Processing; 415-322-9069" <cdp!scott@Glacier> Subject: Comments on Comments on Lurching Windows > Date: Fri 26 Jul 85 16:50:48-EDT > From: Leslie Spira <OC.SOURCE@CU20B.ARPA> > Subject: KERMIT Windowing Questions and Answers...continued. > > The intent of windowing is to try to keep the sender continuously > sending data. Obviously, this is not possible on a half-duplex > channel. A better solution for half-duplex channels would be to use > an extended packet length. > > An attempt to use windowing on half-duplex really is just a way of > doing extended packet lengths. The sender would send out a group of > packets, then wait and get a group of ACKS. It would be better to > simply send out a large packet, which would have less overhead. Actually, this is not quite true. If the channel is noisy, then longer packets won't increase the data rate. Tha advantage of a lurching window scheme is that the receiver could NAK all the small packets that didn't make it, and then the sender could resend the NAKed packets plus some new packets in the next bundle. I think that lurching windows would be a good idea. -scott ------------------------------ Date: Thu, 850725 15:11:20-EDT From: Peter Marshall <21-111@uwo-d10.UWO> Subject: Sliding Windows -- When to Write to Disk? I would like to add a question to the group produced by John Mulligan produced in a recent Kermit-digest. I wonder if someone could explain why it would be so much more difficult to write a received packet to disk, when you have correctly received it? His explaination does not make sense to me. Just because you write a packet to disk does not mean that you have to clear it from the receive table at that time. When you actually clear the oldest message from the receive table for a new message, then you can be assured that the sender has received the ACK. So I don't see his argument about keeping things synchronized. The ACKed flag in the table could also act as a "written to disk" flag. Is it not a little unsafe to assume that you have received a packet correctly (and send off an ACK to that effect) until you have actually got it safely to disk? ------------------------------ Date: Tue, 30 Jul 85 20:41:16 EDT From: RAF@UMDC.BITNET Subject: Mutual Exclusivity of Sliding Windows and Long Packets? I'm not sure that I understand what was meant by long packets and sliding windows being mutually exclusive. If it means that both would not be used at the same time, that seems fairly reasonable (although packets a bit longer than 96 characters wouldn't seem to be especially harmful). If it means that only one of the two proposals should be adopted, I disagree. They are not technically incompatible and each solves some problems that the other does not. Sliding windows are best if the environment can support them. However, some major systems, such as the IBM 370 (TSO and, I think, CMS), do not support the necessary full duplex channel. TSO, at least, will support long packets. The UCLA File Transfer Package sucessfully uses a 1K packet size on TSO and CMS (using their own protocol). We very much want improved Kermit performance, but will never be able to support sliding windows on our TSO system. On the other hand, we also have a DECsystem-10, which can support sliding windows. Those users would benefit from the extra performance of sliding windows over long packets. Lurching windows for half duplex channels were not addressed in the sliding windows proposal. It seems like sender and receiver would have to agree on how many packets would be sent before the receiver would acknowledge. The sender would have to know not to try to send more packets until the previous group was acknowledged. I suppose that this number could be the window size. Also, in a lurching windows environment, a way to acknowledge multiple packets would be beneficial, as acknowledgements are not overlapped with data. The main difference between lurching windows and long packets seems to be that lurching windows have more overhead bytes and that less data might be retransmitted in case of an error. One further point on lurching windows: I'm pretty sure that TSO would require a delay of a charcater time or more between packets so that they would be recognized as separate "lines" of input. Otherwise, I think that everything after the carriage return at the end of the first packet would be lost. Also, when TSO detects a parity error it sends out a transmission error message, which means that it would not be listening for the following packet, so it would be lost too. All in all, I think long packets are better for half duplex channels and sliding windows are better for full duplex. In the sliding windows proposal, I do not understand why the sending of the end of file packet is delayed until all previous packets have been acknowledged. It seems to introduce an unnecessary delay. Both proposals are optional -- no one would have to implement either, if they don't care about the improved performance or want to defer the additional complexity to a later version of their Kermit. ------------------------------ Date: Sat, 27 Jul 85 18:18:19 pdt From: hpl-opus!poulton%hplabs.csnet@csnet-relay.arpa Subject: Implied ACKs, Half Duplex Windows I have two comments on Leslie's Q+A in info-kermit #9. On implied-ACKing: Leslie states that getting a NAK forces the protocol to stop sending. I don't agree. There's no reason for the sender to stop sending just because a NAK came. The retry for the NAK'ed packet can be inserted (ASAP) into the stream of first-try packets. ACK's for packets successfully received after the NAK'ed packet will have to wait until the NAK'ed packet is successfully received. But this does *not* change window requirements: the window has to be long enough to cover the time for NAK and retransmission of packets anyway. Note that although ACK's must wait until all packets up to that point have been received correctly, NAK's for unsuccessful packets can be sent as soon as they are detected as being unsuccessful, i.e. upon successful receipt of the following packet. This will help keep the protocol running smoothly. The only penalty is that since ACKs will be bunched by the receiver, the window must be longer by the number of packets implied by each ACK to keep the window from filling. On windows in a half-duplex environment: This is dismissed as being just long packets, with the implication that one should just use long packets in a half-duplex environment. This is not true! Half-duplex connections have exaclty the same problem: how to get good efficiency over long-delay + moderate error rate connections. I would like to have half-duplex sliding windows seriously considered! Ken Poulton hplabs!poulton I know it's dumb, but half-duplex is the way many systems work... ------------------------------ Date: 27 Jul 1985 1334-EDT From: B.Eiben LCG Ext 617-467-4431 <EIBEN at DEC-MARLBORO.ARPA> Subject: Full-Duplex Windowing vs CP/M, et al Since KERMIT-protocol has been invented and is successfully used in data transfer between "micro's" and larger machines, let me take a look at the "windowing" proposal as seen from the "micro's". As is probably known, none of our current 'Van Neuman' machines can handle more than one task at any given instant of time. The illusion of 'time-sharing' and 'multi-tasking' or even 'multi-processing' are only possible with the existence of a sophisticated interrupt-structure [typically combined with 'hardware assisted' context-switching] and software delivering the book-keeping services. The currently most 'popular' micro-systems [CP/M and MSDOS or derivatives] are SINGLE-tasking systems. Although the used micro-processors typically support a basic interrupt-structure, the lack of buffered and hardware assisted I/O devices limits the interrupt-structure basically to ERROR intercepts and clock-service. -- Or in laymans terms, "A typical micro CANNOT accept characters on the Input-port, as long as its reading or writing to the floppy". How, might You ask, did MODEM or KERMIT survive this basic flaw at higher communication speeds ?? -- Very easily with a "trick" in ACKing a received packet ONLY AFTER it had been written to storage [ - thereby making sure, that NOTHING {except NOISE} could arrive at the input-port - and therefore nothing could be lost ]. In view of these "basics", I would like to treat a "Window of Packets" as one Very Large Packet, which just happens to be sliced into smaller packets for ease of error-recovery. And the micro only has to make sure, that it can store the combined DATA-content of the Window in a buffer. Following Frank's concerns of portability, I would like to propose "fixed" windows ["fixed" in their "agreed upon" starting packet-Nr and their size - in contrast to "sliding windows" , where an ACK for the first packet in a window of packets can slide the starting-point downwards]. In comparison to the "large packet" proposal this technique is probably of more immediate interest to micro-users since: a. Most Communication media are NOT totally error-free b. Most micros are quite limited in sustaining any baud-rate above 4800 Baud between Communication-Port and File-storage [ infact some have even problems to sustain above rates between Comm-Port and terminal]. Here the "changes" in detail: 1. Extend current KERMIT-Heuristic that "A NAK for the current packet is an implied ACK for the previous one" to "A NAK for the current packet is an implied ACK for all previous packets inside the current window". 2. Introduce a rule, that the next [ fixed ] window of packets can ONLY be sent, AFTER receipt of the LAST packet of the previous window has been ACKed. [This will guarantee the needed "silence on the input-port" during 'buffer-write to file-storage' on the micro.] 3. Change the proposed Error-Recovery rule to "On a receipt of a NAK the SENDER will re-send packets starting with the NAKed one". [This will remove the need to keep a "transfer-table" AND make re-synchonisation possible for the micro without hefty recoding]. I believe, that with above changes, we only encounter a minimal "extra overhead" in case of error-retransmission - probably NO extra overhead time-wise at all , if the MAIN-Kermit can be written to be effectively "interrupted" by receipt of a NAK from the micro - if he only can check for NAK's between sending of packets, we'll incur a slight degradation timewise as compared to the current protocol - since the NAK probably will arrive in the middle of a not fully sent packet, which has to be re-sent again according to the above changed rules. We will however enjoy even "faster" transmission in the more prevailing case of having NO ERRORS, since the single ACKs for each packet collapse into a single ACK per window - and we will enjoy the same savings [or better] on packet-based channels. Rgds, Bernie. ------------------------------ Date: Sat, 27 Jul 85 18:18:41 pdt From: hpl-opus!poulton%hplabs.csnet@csnet-relay.arpa Subject: Proposal for Half Duplex Windows A quick proposal for half-duplex sliding windows: Kermit negotiates both packet size and super-packet size (i.e., N packets per super-packet, where N should be less than half the window size). The sender then sends <=N packets, then the end-of-line character to delimit end-of-super-packet (NO end-of-line chars inside the super packet - this is a must for half-duplex receivers). The receiver sends back a super packet of ACKs and NAKs. This could use either the implied-ACK scheme discussed above, or an explicit ACK or NAK for each packet in the super-packet. The implied-ACK scheme has the advantage that, on clean lines, the returning super-packet consists of just one ACK packet. The sender then sends the next super-packet, starting with the outstanding NAK'ed packets, and filled up (to N packets max) with new (first-time) packets. This kind of protocol can't obtain the efficiency of the full-duplex sliding window protocol, since it must incur an overhead of one round-trip delay per super-packet. This can, however, still gain a factor of 2 or 3 over the current situation with 1200 baud lines with 2 second round trip delays. It's *essential* for improvement over poor half-duplex connections where the error rates preclude getting long packets to work at all. I think what I have outlined is close enough to the full-duplex sliding windows to allow them to coexist in the same code. All the full-duplex version needs to do is: 1) negotiate half-duplex status and super-packet size along with window size (maybe we can negotiate handshake at the same time?) 2) bunch packets without end-of-lines to form a super-packet 3) wait for the replying super-packet before sending the next. Another advantage to allowing this half-duplex option is that this opens up greater flexibility for the implementation of sliding window Kermits, since this protocol can be implemented without multiprocessing. This might make it a good choice for non-multi-processing systems or systems which make that difficult. Ken Poulton hplabs!poulton ------------------------------ Date: Thu 1 Aug 85 12:44:55-EDT From: Leslie Spira <OC.SOURCE@CU20B.ARPA> Subject: Examination of Proposals Dear Frank, Hugh Matlock and I sat down last night and studied in detail the discussion about the proposed extensions. It seemed to us once again that there is a fundamental difference between full-duplex environments and half-duplex environments. Looking at it, it appears that the problems in half-duplex can best be solved by a large packet size with smaller sub-units that can be NAKed and retransmitted as necessary. The attempts to modify windowing all ended coming around to this concept. We looked at three things that indicated this: 1. Ken Poulton's suggestion of a way to do "super-packet" half-duplex (message dated July 27). This is a effectively a super-packet with segmentation. Hugh agrees with Ken Poulton that the coding on this suggestion would parallel well with the full-duplex coding. 2. Bernie Eiben's "rewritten" reply dated 27 July. As he notes: "... I would like to treat a 'Window of Packets" as one Very Large Packet, which just happens to be sliced into smaller packets for ease of error-recovery." 3. The original extended packet length proposal, which could be modified so that checksums are placed after every 94 characters. If you look at that definition, MAXLX1 simply becomes the number of sub-units in this view. Note what happened as people looked at "windowing" in the half-duplex environment: the choice of terminology was confusing at first, but gradually sorted itself out into the fact that true sliding windows only works in a full-duplex environment, and the equivalent in half-duplex is a long packet with sub-units for ease of error-recovery. This suggests that the extended packet length proposal can be modified to include sub-units. I believe there is something of a philosophical turning point in KERMIT's development appearing. The Sliding Windows proposal provides "high-end" performance for those higher capability environments (operating system and communications channel) that are truly able to be full-duplex. This "high-end" situation generally reflects the capabilities of later systems on the market, which deserve to have their power taken advantage of. On the other hand, I think that a Super-Packet with segmentation proposal could reflect Classic KERMIT's concern with being able to operate in all environments. This proposal would need to take more enviroments into account. In some ways it is harder to define, because it may require more changes to the existing KERMIT definition since it is more dependent on KERMIT and less dependent on the operating system environment for performance gains. This philosophical difference is just a way of analyzing the fact that the two proposals have somewhat different intents, both of which I think are valid. With this in mind, I think it might be helpful to change the name of our proposal to "Full-Duplex Windowing Extension", in order to make it's intent clear. This definition is more dependent on the operating environment, but its changes to the KERMIT definition are limited, in that windowing is only in effect during transfer of data packets, there are no new packet types, and the ACK and NAK stay pretty much the same. The criticisms of our proposal have been with our underlying decision to operate in a full-duplex environment, rather than with the internal consistency of the proposal. I'm putting the following points forward in our favor: 1. We have a complete, usable definition. 2. We have a working implementation for the IBM PC, and it is based on CKERMIT. We are about to finish the PRIME implementation. 3. We will be making the code available to Columbia, and will be actively distributing it to communications software producers. 4. We have put lots of hard work into this. (Does that count??) 5. We have some unfortunate, but real, deadlines. 6. The sliding window definition can starting making some very great improvements in transfer times over the public data networks, where there currently is no other good solution to the throghput problem. 7. We (at The Source) currently have a chance to build additional momentum for KERMIT. In a lot of ways, this opportunity (or window?) is much better now than it will be later. We would like to have the definition approved this week. In addition, we would then like to continue to contribute to the definition of "super-packets with segmentation". I also would like to apologize for not having more time to approve this; it was not our intent. This is not a casual proposal however; it has been pretty carefully thought through (indeed, the refinement of the definition delayed it). Sincerely, John Mulligan ------------------------------ Date: Thu 1 Aug 85 14:17:00-EDT From: Frank da Cruz <SY.FDC@CU20B> Subject: Full Duplex Sliding Windows -- Let's Give Them a Try To: OC.SOURCE@CU20B, OC.Jordan@CU20B, Info-Kermit@CU20B John, Hugh, Leslie, Larry... Your arguments are persuasive. You've clearly done a lot of work (in a project like Kermit, that's usually what counts most!). I'd like to state my misgivings for the record, and then go ahead grant you permission to use Bit #4 in the CAPAS field to indicate Full Duplex Sliding Window Capability, and the field immediately after the CAPAS field (remembering that the CAPAS field can grow) to designate window size, as you have proposed. My biggest misgiving is that we (you, I, and the Info-Kermit community) have not had sufficient time to consider the proposal, and I will always have nagging doubts that there may have been ways to improve it that would have made more people happy. As proposed, this capability requires true full duplex operation. In order for any computer to support this style of i/o, it must be capable of EITHER multiprocessing OR fully interrupt-driven i/o (or both). Multiprocessing is something most micros can't do; it requires certain hardware features like memory protection. On the other hand, almost any operating system allows access to its interrupt structure by the programmer. Unfortunately, the mechanisms for getting at interrupts vary considerably among machines, operating systems, and even operating system versions. So a Kermit program that manages to "steal" the system's interrupt vector in order to work correctly under version x of the operating system might suddenly stop working when the user installs version y... To make matters worse, information about interrupt programming tends to be hard to come by -- it's missing from the manuals, it's proprietary, or whatever -- so when this is true, it makes it tough for even the motivated programmer to do the work. It's unfortunate that you have such pressing deadlines, and that I will be gone for a month. It may well be that your proposal is exactly what is needed to kick Kermit protocol into the big leagues, but it might have been possible to refine it in such a way that continuous full duplex transmission would be possible for those systems capable of it, while provision was made for those systems (CP/M-80 springs to mind) that have to turn their backs on the communication port from time to time in order to write to the disk. As you suggest, systems like CP/M along with the systems that really have half duplex communication channels might be accommodated by the long-packet extension, especially if modified to allow segmented long packets (this reminds me of SMTP vs BSMTP...). But it would be a lot cleaner if a single Kermit extension could take care of everyone. A final misgiving is that allocation of a CAPAS bit and Send-Init field is irrevocable. Once Kermit programs are out in the world that use them, they can never be used for anything else. Therefore, I'd like to emphasize that the full duplex sliding window feature specified in Info-Kermit V3 #7 should still be considered EXPERIMENTAL. The group at The SOURCE will be tuning it as they work on their new implementations, and I'm sure that some of the comments and suggestions from Info-Kermit will be in the back of their minds. I expect that all this activity will settle down in a month or two, and a "final" copy of the sliding window specification will be available then. Until then, no one should attempt to work from the current specification without first contacting the people at The SOURCE (mail to OC.SOURCE@CU20B). Since the CAPAS bit and the window size field will be allocated to their windowing method, it is essential that the protocol invoked by them is clearly, completely, and unambiguously specified before any programs using them are distributed to the public. - Frank ------------------------------ End of Info-Kermit Digest ************************* -------