home *** CD-ROM | disk | FTP | other *** search
/ norge.freeshell.org (192.94.73.8) / 192.94.73.8.tar / 192.94.73.8 / pub / computers / pcjr / comm / GT1403_1.LZH / MEGALINK.DOC < prev    next >
Text File  |  1988-05-04  |  20KB  |  423 lines
  1.  
  2.                                    MEGAlink
  3.                            A File Transfer Protocol
  4.  
  5.                                 Specifications
  6.  
  7.                                By: Paul Meiners
  8.  
  9.                              P&M Software Company
  10.                              9350 Country Creek #30
  11.                              Houston, Texas 77036
  12.  
  13.                                 April 18, 1987
  14.  
  15.                                Revision history:
  16.                                -----------------
  17.                     August 9, 1987 ... Forsberg's CRC Variation
  18.  
  19.  
  20. Acknowledgements
  21. ----------------
  22. I would like to acknowledge the work of those who have done this before me.
  23. First, Chuck Forsberg, for his never ending quest for speed and reliability.
  24. Second, Ward Christensen, whose ideas are the genesis of this whole branch
  25. of file transfer technology.  Third, Peter Boswell, for showing me the way
  26. to a network friendly protocol.  Last, Tom Jennings, for the work he did
  27. on Fido and the Telink protocol, which introduced the "link" style header
  28. record, now in use by all "link" type protocols.
  29.  
  30. For those that are not aware, these pioneers are responsible for the following
  31. work:
  32.  
  33.                   Ward Christensen ___ Xmodem.
  34.                   Tom Jennings _______ Fido, Telink.
  35.                   Chuck Forsberg _____ Ymodem, Ymodem Batch, Zmodem.
  36.                   Peter Boswell ______ WXmodem.
  37.  
  38. Why Another Protocol?
  39. ---------------------
  40. In many respects, the design of a protocol has become a discussion between
  41. the above mentioned pioneers, each building on the work of the other.  Each
  42. has perceived a weakness in the protocols that have gone before and sought
  43. to improve the art.  And that is the most elegant reason for a new protocol,
  44. to advance the art.
  45.  
  46. I won't bother with a discussion of the merits of Xmodem.  Others have done
  47. that far better than I could.  Let me address the more modern variations.
  48. These are my opinions, based on experience and reading the literature.
  49.  
  50.    Zmodem  - The ideal protocol.  Highly reliable and fast.  Only failing
  51.              is that the cost of implementation is high.
  52.  
  53.    Ymodem  - Very fast, but not network friendly.  Also leaves something
  54.              to be desired on the reliability front.  Error correction is
  55.              slow.
  56.  
  57.    WXmodem - Fast and network friendly.  However, several questions exist
  58.              with regard to reliability.
  59.  
  60. So, it our goal to design and implement a protocol that meets or exceeds
  61. the following criteria:
  62.  
  63.    1.  Fast.  Efficency must exceed 95% on average basis.
  64.    2.  Reliable.  Known defects in prior protocols must be corrected.
  65.    3.  Inexpensive.  Implementation cost must be low.
  66.  
  67.  
  68. How Do We Do It?
  69. ----------------
  70. Let us address these issues in reverse sequence.
  71.  
  72.     COST OF IMPLEMENTATION
  73.     ----------------------
  74.     By closely modeling the protocol after Xmodem, we hope to reduce cost
  75.     of implementation.  This may be a vain effort, because implementation
  76.     of any high performance protocol requires a certain degree of complexity.
  77.  
  78.     RELIABILITY
  79.     -----------
  80.     To improve the reliability of the protocol, we have choosen to use the
  81.     new CRC-32 technology.  The algorithm for this procedure will be given
  82.     later in this document.  Also, the Ack/Nak packets will be composed of
  83.     3 bytes, as was done in the SEAlink protocol.  Like WXmodem we will
  84.     honor all network XOFF signals at the transmitter end.
  85.  
  86.     SPEED
  87.     -----
  88.     Several things are going to be done to improve speed.  First, the block
  89.     size will be increased from 128 to 512 bytes.  This reduces the number
  90.     of envelope characters.  Like Zmodem, MEGAlink will be a full streaming
  91.     protocol, thus eliminating the turn-around time involved with Xmodem
  92.     and Ymodem.
  93.  
  94.  
  95. Some definitions
  96. ----------------
  97.  
  98.      Description             Character           Decimal     Control Char
  99.      -----------             ---------           -------     ------------
  100.      XON ................... DC1 ............... 17 ............ ^Q
  101.      XOFF .................. DC3 ............... 19 ............ ^S
  102.      Acknowledge ........... ACK ............... 6 ............. ^F
  103.      Negative Acknowledge .. NAK ............... 21 ............ ^U
  104.      End of File ........... EOT ............... 4 ............. ^D
  105.      Start of Header ....... SOH ............... 1 ............. ^A
  106.      MegaLink Block Id ..... EM ................ 25 ............ ^Y
  107.      Request Status ........ RS ................ 30 ............ ^^
  108.      Cancel ................ CAN ............... 24 ............ ^X
  109.      Synchronize ........... SYN ............... 22 ............ ^V
  110.      Data Link Escape ...... DLE ............... 16 ............ ^P
  111.      CP/M EOF .............. SUB ............... 26 ............ ^Z
  112.  
  113.  
  114. Receiver discipline
  115. -------------------
  116. The receive side of a MEGAlink transfer has three possible packets it can
  117. use.  Each is three characters in length as follows:
  118.  
  119.       Byte No.          Content
  120.       --------          -------
  121.          1              Ack/Nak/'C'.  No other character may appear.
  122.          2              Packet number.  0 thru 255.
  123.          3              Complement of packet number, i.e. (Pkt# XOR 255).
  124.  
  125. The 'C' packet is sent only at the start of each file transfer.  It is sent
  126. by the receiver at 5 second intervals, until the transmitter begins.  After
  127. that it is not used again until the next file is begun, or the next session
  128. is begun, if only 1 file is transmitted.
  129.  
  130. The Nak packet is used to request the retransmission of the specified packet.
  131.  
  132. The Ack packet is used to indicate the highest packet received without error.
  133.  
  134. Normally, the receiver remains quiet.  The only time packets are required of
  135. the receiver are at the beginning of the transfer, as outlined below, and upon
  136. receipt of an RS character, the Request Status character.  The receiver must
  137. respond to the RS character with an Ack packet, reflecting the highest block
  138. received in without error.  Of course, the receiver should send a Nak packet
  139. whenever a block is received with an error condition.
  140.  
  141. Note, that to maintain network friendliness, no packet may contain a XON or
  142. XOFF character.  These characters must be sent as two characters, first a
  143. DLE, followed by the folded XON or XOFF.  Characters are folded by XOR'ing
  144. them with decimal 64.  This scheme requires that the DLE character is
  145. escaped and folded in the same manner.
  146.  
  147. Transmitter discipline
  148. ----------------------
  149. The transmitter can do four different things:
  150.  
  151.     1)  Send a header block.  Contains file name and other information
  152.         about the file.
  153.  
  154.     2)  Send a data block.  A data block contains 512 bytes of data.
  155.  
  156.     3)  Send an RS character, forces receiver to Ack the highest packet
  157.         he has received without error.
  158.  
  159.     4)  Send an EOT character, signals end-of-file to the receiver.
  160.  
  161.  
  162. Data blocks are sent without pause.  The transmitter should have enough
  163. buffers to cover the turn-around delay, so that any block the receiver
  164. may Nak will still be available in memory for retransmission.
  165.  
  166. Note, that to maintain network friendliness, no packet may contain a XON or
  167. XOFF character.  These characters must be sent as two characters, first a
  168. DLE, followed by the folded XON or XOFF.  Characters are folded by XOR'ing
  169. them with decimal 64.  This scheme requires that the DLE character is
  170. escaped and folded in the same manner.
  171.  
  172. Typical transmit/receive dialog:
  173. --------------------------------
  174.  
  175. Transmitter                           Receiver     Description
  176. -----------                           --------     -----------
  177.                                       C   00 FF    opening Nak.
  178.  
  179. SOH 00 FF  header[128]  CRC CRC                    header block sent,
  180.                                                    using CRC-16.
  181.  
  182.                                       ACK 00 FF    Ack of header block.
  183.  
  184. EM  01 FE  data[512]  CRC CRC CRC CRC              file transmitted in one
  185. EM  02 FD  data[512]  CRC CRC CRC CRC              or more data blocks,
  186. EM  03 FC  data[512]  CRC CRC CRC CRC              using CRC-32.
  187. EM  04 FB  data[512]  CRC CRC CRC CRC
  188.  
  189. RS                                                 transmit requests status.
  190.  
  191.                                       ACK 04 FB    receive replies to RS.
  192.  
  193. EOT                                                end-of-file sent.
  194.  
  195.                                       ACK 04 FB    Ack sent for end-of-file.
  196.  
  197.                                       C   00 FF    opening Nak.
  198.  
  199. EOT                                                end-of-batch sent.
  200.  
  201.                                       ACK 04 FB    Ack sent for end-of-batch.
  202.  
  203. If necessary, the last data block can be padded with CP/M EOF characters.
  204.  
  205. Note: all CRC bytes are transmitted from high to low order, NOT in the
  206.       more usual byte-reversed format.
  207.  
  208. At the end of the transaction, the "opening Nak" is repeated by the receiver.
  209. This is to allow for batch transmission, if more than one file were to be sent
  210. the transmitter would pick-up and start by sending the next header block and
  211. the transaction would continue from that point as shown.
  212.  
  213. The format of the header block conforms to the standard "link" format.
  214. Established by Tom Jennings when he designed the Telink protocol, also
  215. used by the SEAlink protocol.
  216.  
  217.      Byte Offset     Length       Content
  218.      -----------     ------       -------
  219.           0             4         Original file length. Integer in byte
  220.                                   reversed format.
  221.  
  222.           4             4         Date and time file was last mofified, in
  223.                                   seconds since 1979.  Same format DOS uses
  224.                                   in the directory entry.
  225.  
  226.           8            16         Original file name, as a null terminated
  227.                                   string.
  228.  
  229.          24             1         Binary version number.
  230.                                       0 ... Original MegaLink.
  231.                                       1 ... Forsberg's CRC Variation.
  232.  
  233.          25            15         Name of transmitting program, as a null
  234.                                   terminated string.
  235.  
  236.          40            88         Null filler and expansion area.
  237.  
  238. CRC Calculator
  239. --------------
  240. The following routines demonstrate the technique used to calculate CRC's,
  241. both 16 & 32 bit varieties, used in MEGAlink.  The code is written in
  242. Turbo PASCAL.
  243.  
  244. Thanks to Mr. Chuck Forsberg, "Forsberg's CRC Variation" can be introduced.
  245. It involves initializing the CRC Register to $FFFFFFFF instead of the normal
  246. zero.  The use of this variation is signaled by a handshake between transmitter
  247. and receiver.  The receiver sends an opening nak packet containing a 'C' and 2
  248. bytes of 00 and FF hex.  If the receiver desires to use  "Forsberg's CRC
  249. Variation", he should code the bytes following the 'C' as 01 and FE.  If the
  250. transmitter is capable of using "Forsberg's CRC Variation" he will signal this
  251. in the header block, see offset 24 above.  The transmitter will adjust to use
  252. whichever CRC is requested by receiver, thus maintaining downward compatibility.
  253.  
  254.    {  Global Variables  }
  255.  
  256.    TYPE
  257.       ARRAY512       = RECORD
  258.                           Len        : INTEGER;
  259.                           LongString : ARRAY[1..512] OF CHAR;
  260.                        END;
  261.       STRING128      = STRING[128];
  262.    VAR
  263.       crc_input        : INTEGER;      { 2 byte integer format }
  264.       crc_reg_lo       : INTEGER;
  265.       crc_reg_hi       : INTEGER;
  266.       forsberg_variant : BOOLEAN;
  267.  
  268.    PROCEDURE
  269.       ccitt_crc16_calc;                {  CRC-16  }
  270.    BEGIN
  271.       inline( $8B/$1E/crc_reg_hi );    {        mov     bx,crc_reg_hi    }
  272.       inline( $B9/>$08 );              {        mov     cx,8             }
  273.       inline( $A1/crc_input );         {        mov     ax,crc_input     }
  274.       inline( $D0/$D0 );               {  u1:   rcl     al,1             }
  275.       inline( $D1/$D3 );               {        rcl     bx,1             }
  276.       inline( $73/$04 );               {        jnc     u2               }
  277.       inline( $81/$F3/$1021 );         {        xor     bx,1021h         }
  278.       inline( $E2/$F4 );               {  u2:   loop    u1               }
  279.       inline( $89/$1E/crc_reg_hi );    {        mov     crc_reg_hi,bx    }
  280.    END;
  281.  
  282.    PROCEDURE
  283.       ccitt_crc32_calc;                {  CRC-32  }
  284.    BEGIN
  285.       inline( $8B/$1E/crc_reg_lo );    {       mov     bx,crc_reg_lo     }
  286.       inline( $8B/$16/crc_reg_hi );    {       mov     dx,crc_reg_hi     }
  287.       inline( $B9/>$08 );              {       mov     cx,8              }
  288.       inline( $A1/crc_input );         {       mov     ax,crc_input      }
  289.       inline( $D0/$D8 );               {  u1:  rcr     al,1              }
  290.       inline( $D1/$DA );               {       rcr     dx,1              }
  291.       inline( $D1/$DB );               {       rcr     bx,1              }
  292.       inline( $73/$08 );               {       jnc     u2                }
  293.       inline( $81/$F3/$8320 );         {       xor     bx,8320h          }
  294.       inline( $81/$F2/$EDB8 );         {       xor     dx,EDB8h          }
  295.       inline( $E2/$EE );               {  u2:  loop    u1                }
  296.       inline( $89/$1E/crc_reg_lo );    {       mov     crc_reg_lo,bx     }
  297.       inline( $89/$16/crc_reg_hi );    {       mov     crc_reg_hi,dx     }
  298.    END;
  299.  
  300.    PROCEDURE
  301.       calc_crc32(VAR cs : ARRAY512);
  302.    VAR
  303.       i  : INTEGER;
  304.    BEGIN
  305.    (*
  306.         Note: this routine calculates a 32 bit CRC based on the CCITT
  307.               polynomial.  The result is stored in the crc register,
  308.               variables crc_reg_hi & crc_reg_lo.
  309.    *)
  310.       IF (forsberg_variant) THEN BEGIN
  311.          crc_reg_hi:=$FFFF;
  312.          crc_reg_lo:=$FFFF;
  313.       END
  314.       ELSE BEGIN
  315.          crc_reg_hi:=0;
  316.          crc_reg_lo:=0;
  317.       END;
  318.       WITH cs DO BEGIN
  319.          FOR i:=1 TO Len DO BEGIN
  320.             crc_input:=ORD(LongString[i]);
  321.             ccitt_crc32_calc;
  322.          END;
  323.       END;
  324.       crc_input:=0;
  325.       ccitt_crc32_calc;
  326.       ccitt_crc32_calc;
  327.       ccitt_crc32_calc;
  328.       ccitt_crc32_calc;
  329.    END;
  330.  
  331.    PROCEDURE
  332.       calc_crc16(VAR cs : STRING128);
  333.    VAR
  334.       i  : INTEGER;
  335.    BEGIN
  336.    (*
  337.         Note: this routine calculates a 16 bit CRC based on the CCITT
  338.               polynomial.  The result is stored in the crc register,
  339.               variable crc_reg_hi.
  340.    *)
  341.       crc_reg_hi:=0;
  342.       crc_reg_lo:=0;
  343.       FOR i:=1 TO Length(cs) DO BEGIN
  344.          crc_input:=ORD(cs[i]);
  345.          ccitt_crc16_calc;
  346.       END;
  347.       crc_input:=0;
  348.       ccitt_crc16_calc;
  349.       ccitt_crc16_calc;
  350.    END;
  351.  
  352.  
  353. Buffer Management
  354. -----------------
  355. It is the responsibility of the transmitter to have enough buffer space
  356. to cover the Nak turn-around time at a particular baud rate.  Otherwise,
  357. in full stream mode, the receiver may Nak for a block that is not available.
  358. For example, at 2400 baud, assuming a turn-around delay of 6 seconds, the
  359. transmitter should have at least room for 4 blocks in his buffer area.  This
  360. in my opinion, would be cutting it TOO CLOSE, I would recommend a margin of
  361. at least 2 times or more.  In GT PowerComm, the first program to implement
  362. MEGAlink, we have a ring buffer of 32 blocks.  This is very easy to use,
  363. because the the Nak'ed block numbers can be AND'ed with $1F to produce the
  364. buffer number.  At 2400 baud, 32 blocks in the buffer amounts to more than
  365. 60 seconds.  This gives the receive side ample time to turn-around any Nak.
  366.  
  367. Notice that at higher baud rates, the time margin shrinks.  For example,
  368. at 9600 baud, the time margin for 32 blocks shrinks to about 14 seconds.
  369. This would probably be fine for a direct connect, but would not be good
  370. over a network such as PC Pursuit.  (This is not very important now, PC
  371. Pursuit is barely scratching the surface of 2400 baud at this time, 4/20/87.)
  372. At these higher baud rates, the transmitter must use flow control techniques to
  373. insure that an adequate time margin is maintained.  This can be done by issuing
  374. an RS, Request Status, command to the receive side.  The receiver should reply
  375. with an Ack packet indicating the last good packet received.  The transmitter
  376. should wait for reception of this Ack prior to continuing the dialog.  In
  377. effect this is a self-imposed flow control.  The transmitter must be smart
  378. enough to recognize the need for such, based on the baud rate and available
  379. buffer space.  Theoretically, if enough buffer space was available to the
  380. transmitter, it could continue to stream at any baud rate.
  381.  
  382. Error Corrections Procedure
  383. ---------------------------
  384. When the receiver detects an error, it must immediately send a Nak packet
  385. with the offending packet # within.  Then the receiver dumps the contents
  386. of the serial port input buffer and waits for the requested packet.  The
  387. transmitter will not usually be able to respond immediately, so the receiver
  388. must expect packets with higher than expected packet #'s, until the requested
  389. packet arrives.  These extra packets should be disgarded without comment by
  390. receiver.
  391.  
  392. The transmitter, upon receipt of a Nak, will immediately dump the contents of
  393. the serial port output buffer and resend the requested packet.  At this point,
  394. due to the probability of a loss-of-sync error, which cannot be recovered, the
  395. send and receive side now drop to start-stop mode to correct the error.  In
  396. other words, the receiver must Ack a packet that he receives in good shape
  397. after a prior Nak has been sent for the packet.  The sender will not restart
  398. the stream of packets until this Ack has been received.  This prevents any
  399. chance for loss-of-sync at this juncture.  Also important to recognize is
  400. that the receive side of the transfer must have good code to find the start
  401. of a packet.  It will have a fairly unique signature, i.e. the character EM
  402. followed by two characters that are the complements of each other.  Especially
  403. considering the fact that the receiver is looking for a particular packet at
  404. this point, the occurence of a false signature is unlikely.
  405.  
  406. The question of how to handle packets arriving from the receiver that are them-
  407. selves in error has not been addressed.  It is true however, that the trans-
  408. mitter will respond to any Nak.  If the transmitter fails to get a good Nak
  409. the receiver will continue to Nak, until the requested block is received.
  410. This procedure works in practice, however there may well be a more elegant
  411. solution.  For example, the transmitter, upon receipt of a faulty Nak, could
  412. simply wait for the receiver to resend the Nak.  Of course, the transmitter
  413. could also send an RS, request status, command to the receiver, which could
  414. be interpreted in a Nakking situation as a "nak" to the "nak".  This should
  415. cause the receiver to resend the Nak.
  416.  
  417. GT implements the "resend-and-see" approach, this is the most direct and
  418. usually the best.  Even if the Nak is faulty, GT will choose from the 32
  419. buffers and send a block.  If the block is too high or too low, the receiver
  420. will Nak again.  This type of dialog usually leads to a resolution of the
  421. error condition, on all but the worst lines.  Naturally, even the best
  422. protocols fail on the worst lines!
  423.