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