home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / rfc / rfc1071 < prev    next >
Text File  |  1991-04-21  |  54KB  |  1,418 lines

  1.  
  2.  
  3.  
  4.  
  5. Network Working Group                                         R.  Braden
  6. Request for Comments: 1071                                           ISI
  7.                                                               D.  Borman
  8.                                                            Cray Research
  9.                                                             C. Partridge
  10.                                                         BBN Laboratories
  11.                                                           September 1988
  12.  
  13.  
  14.                     Computing the Internet Checksum
  15.  
  16.  
  17. Status of This Memo
  18.  
  19.    This memo summarizes techniques and algorithms for efficiently
  20.    computing the Internet checksum.  It is not a standard, but a set of
  21.    useful implementation techniques.  Distribution of this memo is
  22.    unlimited.
  23.  
  24. 1.  Introduction
  25.  
  26.    This memo discusses methods for efficiently computing the Internet
  27.    checksum that is used by the standard Internet protocols IP, UDP, and
  28.    TCP.
  29.  
  30.    An efficient checksum implementation is critical to good performance.
  31.    As advances in implementation techniques streamline the rest of the
  32.    protocol processing, the checksum computation becomes one of the
  33.    limiting factors on TCP performance, for example.  It is usually
  34.    appropriate to carefully hand-craft the checksum routine, exploiting
  35.    every machine-dependent trick possible; a fraction of a microsecond
  36.    per TCP data byte can add up to a significant CPU time savings
  37.    overall.
  38.  
  39.    In outline, the Internet checksum algorithm is very simple:
  40.  
  41.    (1)  Adjacent octets to be checksummed are paired to form 16-bit
  42.         integers, and the 1's complement sum of these 16-bit integers is
  43.         formed.
  44.  
  45.    (2)  To generate a checksum, the checksum field itself is cleared,
  46.         the 16-bit 1's complement sum is computed over the octets
  47.         concerned, and the 1's complement of this sum is placed in the
  48.         checksum field.
  49.  
  50.    (3)  To check a checksum, the 1's complement sum is computed over the
  51.         same set of octets, including the checksum field.  If the result
  52.         is all 1 bits (-0 in 1's complement arithmetic), the check
  53.         succeeds.
  54.  
  55.         Suppose a checksum is to be computed over the sequence of octets
  56.  
  57.  
  58.  
  59. Braden, Borman, & Partridge                                     [Page 1]
  60.  
  61. RFC 1071            Computing the Internet Checksum       September 1988
  62.  
  63.  
  64.         A, B, C, D, ... , Y, Z.  Using the notation [a,b] for the 16-bit
  65.         integer a*256+b, where a and b are bytes, then the 16-bit 1's
  66.         complement sum of these bytes is given by one of the following:
  67.  
  68.             [A,B] +' [C,D] +' ... +' [Y,Z]              [1]
  69.  
  70.             [A,B] +' [C,D] +' ... +' [Z,0]              [2]
  71.  
  72.         where +' indicates 1's complement addition. These cases
  73.         correspond to an even or odd count of bytes, respectively.
  74.  
  75.         On a 2's complement machine, the 1's complement sum must be
  76.         computed by means of an "end around carry", i.e., any overflows
  77.         from the most significant bits are added into the least
  78.         significant bits. See the examples below.
  79.  
  80.         Section 2 explores the properties of this checksum that may be
  81.         exploited to speed its calculation.  Section 3 contains some
  82.         numerical examples of the most important implementation
  83.         techniques.  Finally, Section 4 includes examples of specific
  84.         algorithms for a variety of common CPU types.  We are grateful
  85.         to Van Jacobson and Charley Kline for their contribution of
  86.         algorithms to this section.
  87.  
  88.         The properties of the Internet checksum were originally
  89.         discussed by Bill Plummer in IEN-45, entitled "Checksum Function
  90.         Design".  Since IEN-45 has not been widely available, we include
  91.         it as an extended appendix to this RFC.
  92.  
  93.      2.  Calculating the Checksum
  94.  
  95.         This simple checksum has a number of wonderful mathematical
  96.         properties that may be exploited to speed its calculation, as we
  97.         will now discuss.
  98.  
  99.  
  100.    (A)  Commutative and Associative
  101.  
  102.         As long as the even/odd assignment of bytes is respected, the
  103.         sum can be done in any order, and it can be arbitrarily split
  104.         into groups.
  105.  
  106.         For example, the sum [1] could be split into:
  107.  
  108.            ( [A,B] +' [C,D] +' ... +' [J,0] )
  109.  
  110.                   +' ( [0,K] +' ... +' [Y,Z] )               [3]
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118. Braden, Borman, & Partridge                                     [Page 2]
  119.  
  120. RFC 1071            Computing the Internet Checksum       September 1988
  121.  
  122.  
  123.    (B)  Byte Order Independence
  124.  
  125.         The sum of 16-bit integers can be computed in either byte order.
  126.         Thus, if we calculate the swapped sum:
  127.  
  128.            [B,A] +' [D,C] +' ... +' [Z,Y]                   [4]
  129.  
  130.         the result is the same as [1], except the bytes are swapped in
  131.         the sum! To see why this is so, observe that in both orders the
  132.         carries are the same: from bit 15 to bit 0 and from bit 7 to bit
  133.         8.  In other words, consistently swapping bytes simply rotates
  134.         the bits within the sum, but does not affect their internal
  135.         ordering.
  136.  
  137.         Therefore, the sum may be calculated in exactly the same way
  138.         regardless of the byte order ("big-endian" or "little-endian")
  139.         of the underlaying hardware.  For example, assume a "little-
  140.         endian" machine summing data that is stored in memory in network
  141.         ("big-endian") order.  Fetching each 16-bit word will swap
  142.         bytes, resulting in the sum [4]; however, storing the result
  143.         back into memory will swap the sum back into network byte order.
  144.  
  145.         Byte swapping may also be used explicitly to handle boundary
  146.         alignment problems.  For example, the second group in [3] can be
  147.         calculated without concern to its odd/even origin, as:
  148.  
  149.               [K,L] +' ... +' [Z,0]
  150.  
  151.         if this sum is byte-swapped before it is added to the first
  152.         group.  See the example below.
  153.  
  154.    (C)  Parallel Summation
  155.  
  156.         On machines that have word-sizes that are multiples of 16 bits,
  157.         it is possible to develop even more efficient implementations.
  158.         Because addition is associative, we do not have to sum the
  159.         integers in the order they appear in the message.  Instead we
  160.         can add them in "parallel" by exploiting the larger word size.
  161.  
  162.         To compute the checksum in parallel, simply do a 1's complement
  163.         addition of the message using the native word size of the
  164.         machine.  For example, on a 32-bit machine we can add 4 bytes at
  165.         a time: [A,B,C,D]+'... When the sum has been computed, we "fold"
  166.         the long sum into 16 bits by adding the 16-bit segments.  Each
  167.         16-bit addition may produce new end-around carries that must be
  168.         added.
  169.  
  170.         Furthermore, again the byte order does not matter; we could
  171.         instead sum 32-bit words: [D,C,B,A]+'... or [B,A,D,C]+'... and
  172.         then swap the bytes of the final 16-bit sum as necessary.  See
  173.         the examples below.  Any permutation is allowed that collects
  174.  
  175.  
  176.  
  177. Braden, Borman, & Partridge                                     [Page 3]
  178.  
  179. RFC 1071            Computing the Internet Checksum       September 1988
  180.  
  181.  
  182.         all the even-numbered data bytes into one sum byte and the odd-
  183.         numbered data bytes into the other sum byte.
  184.  
  185.  
  186.    There are further coding techniques that can be exploited to speed up
  187.    the checksum calculation.
  188.  
  189.    (1)  Deferred Carries
  190.  
  191.         Depending upon the machine, it may be more efficient to defer
  192.         adding end-around carries until the main summation loop is
  193.         finished.
  194.  
  195.         One approach is to sum 16-bit words in a 32-bit accumulator, so
  196.         the overflows build up in the high-order 16 bits.  This approach
  197.         typically avoids a carry-sensing instruction but requires twice
  198.         as many additions as would adding 32-bit segments; which is
  199.         faster depends upon the detailed hardware architecture.
  200.  
  201.    (2)  Unwinding Loops
  202.  
  203.         To reduce the loop overhead, it is often useful to "unwind" the
  204.         inner sum loop, replicating a series of addition commands within
  205.         one loop traversal.  This technique often provides significant
  206.         savings, although it may complicate the logic of the program
  207.         considerably.
  208.  
  209.    (3)  Combine with Data Copying
  210.  
  211.         Like checksumming, copying data from one memory location to
  212.         another involves per-byte overhead.  In both cases, the
  213.         bottleneck is essentially the memory bus, i.e., how fast the
  214.         data can be fetched. On some machines (especially relatively
  215.         slow and simple micro-computers), overhead can be significantly
  216.         reduced by combining memory-to-memory copy and the checksumming,
  217.         fetching the data only once for both.
  218.  
  219.    (4)  Incremental Update
  220.  
  221.         Finally, one can sometimes avoid recomputing the entire checksum
  222.         when one header field is updated.  The best-known example is a
  223.         gateway changing the TTL field in the IP header, but there are
  224.         other examples (for example, when updating a source route).  In
  225.         these cases it is possible to update the checksum without
  226.         scanning the message or datagram.
  227.  
  228.         To update the checksum, simply add the differences of the
  229.         sixteen bit integers that have been changed.  To see why this
  230.         works, observe that every 16-bit integer has an additive inverse
  231.         and that addition is associative.  From this it follows that
  232.         given the original value m, the new value m', and the old
  233.  
  234.  
  235.  
  236. Braden, Borman, & Partridge                                     [Page 4]
  237.  
  238. RFC 1071            Computing the Internet Checksum       September 1988
  239.  
  240.  
  241.         checksum C, the new checksum C' is:
  242.  
  243.                 C' = C + (-m) + m' = C + (m' - m)
  244.  
  245.  
  246. 3. Numerical Examples
  247.  
  248.    We now present explicit examples of calculating a simple 1's
  249.    complement sum on a 2's complement machine.  The examples show the
  250.    same sum calculated byte by bye, by 16-bits words in normal and
  251.    swapped order, and 32 bits at a time in 3 different orders.  All
  252.    numbers are in hex.
  253.  
  254.                   Byte-by-byte    "Normal"  Swapped
  255.                                     Order    Order
  256.  
  257.         Byte 0/1:    00   01        0001      0100
  258.         Byte 2/3:    f2   03        f203      03f2
  259.         Byte 4/5:    f4   f5        f4f5      f5f4
  260.         Byte 6/7:    f6   f7        f6f7      f7f6
  261.                     ---  ---       -----     -----
  262.         Sum1:       2dc  1f0       2ddf0     1f2dc
  263.  
  264.                      dc   f0        ddf0      f2dc
  265.         Carrys:       1    2           2         1
  266.                      --   --        ----      ----
  267.         Sum2:        dd   f2        ddf2      f2dd
  268.  
  269.         Final Swap:  dd   f2        ddf2      ddf2
  270.  
  271.  
  272.         Byte 0/1/2/3:  0001f203     010003f2       03f20100
  273.         Byte 4/5/6/7:  f4f5f6f7     f5f4f7f6       f7f6f5f4
  274.                        --------     --------       --------
  275.         Sum1:         0f4f7e8fa    0f6f4fbe8      0fbe8f6f4
  276.  
  277.         Carries:              0            0              0
  278.  
  279.         Top half:          f4f7         f6f4           fbe8
  280.         Bottom half:       e8fa         fbe8           f6f4
  281.                           -----        -----          -----
  282.         Sum2:             1ddf1        1f2dc          1f2dc
  283.  
  284.                            ddf1         f2dc           f2dc
  285.         Carrys:               1            1              1
  286.                            ----         ----           ----
  287.         Sum3:              ddf2         f2dd           f2dd
  288.  
  289.         Final Swap:        ddf2         ddf2           ddf2
  290.  
  291.  
  292.  
  293.  
  294.  
  295. Braden, Borman, & Partridge                                     [Page 5]
  296.  
  297. RFC 1071            Computing the Internet Checksum       September 1988
  298.  
  299.  
  300.    Finally, here an example of breaking the sum into two groups, with
  301.    the second group starting on a odd boundary:
  302.  
  303.  
  304.                    Byte-by-byte    Normal
  305.                                     Order
  306.  
  307.         Byte 0/1:    00   01        0001
  308.         Byte 2/ :    f2  (00)       f200
  309.                     ---  ---       -----
  310.         Sum1:        f2   01        f201
  311.  
  312.         Byte 4/5:    03   f4        03f4
  313.         Byte 6/7:    f5   f6        f5f6
  314.         Byte 8/:     f7  (00)       f700
  315.                     ---  ---       -----
  316.         Sum2:                      1f0ea
  317.  
  318.         Sum2:                       f0ea
  319.         Carry:                         1
  320.                                    -----
  321.         Sum3:                       f0eb
  322.  
  323.         Sum1:                       f201
  324.         Sum3 byte swapped:          ebf0
  325.                                    -----
  326.         Sum4:                      1ddf1
  327.  
  328.         Sum4:                       ddf1
  329.         Carry:                         1
  330.                                    -----
  331.         Sum5:                       ddf2
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345.  
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353.  
  354. Braden, Borman, & Partridge                                     [Page 6]
  355.  
  356. RFC 1071            Computing the Internet Checksum       September 1988
  357.  
  358.  
  359. 4.  Implementation Examples
  360.  
  361.    In this section we show examples of Internet checksum implementation
  362.    algorithms that have been found to be efficient on a variety of
  363.    CPU's.  In each case, we show the core of the algorithm, without
  364.    including environmental code (e.g., subroutine linkages) or special-
  365.    case code.
  366.  
  367. 4.1  "C"
  368.  
  369.    The following "C" code algorithm computes the checksum with an inner
  370.    loop that sums 16-bits at a time in a 32-bit accumulator.
  371.  
  372.    in 6
  373.        {
  374.            /* Compute Internet Checksum for "count" bytes
  375.             *         beginning at location "addr".
  376.             */
  377.        register long sum = 0;
  378.  
  379.         while( count > 1 )  {
  380.            /*  This is the inner loop */
  381.                sum += * (unsigned short) addr++;
  382.                count -= 2;
  383.        }
  384.  
  385.            /*  Add left-over byte, if any */
  386.        if( count > 0 )
  387.                sum += * (unsigned char *) addr;
  388.  
  389.            /*  Fold 32-bit sum to 16 bits */
  390.        while (sum>>16)
  391.            sum = (sum & 0xffff) + (sum >> 16);
  392.  
  393.        checksum = ~sum;
  394.    }
  395.  
  396.  
  397.  
  398.  
  399.  
  400.  
  401.  
  402.  
  403.  
  404.  
  405.  
  406.  
  407.  
  408.  
  409.  
  410.  
  411.  
  412.  
  413. Braden, Borman, & Partridge                                     [Page 7]
  414.  
  415. RFC 1071            Computing the Internet Checksum       September 1988
  416.  
  417.  
  418. 4.2  Motorola 68020
  419.  
  420.    The following algorithm is given in assembler language for a Motorola
  421.    68020 chip.  This algorithm performs the sum 32 bits at a time, and
  422.    unrolls the loop with 16 replications.  For clarity, we have omitted
  423.    the logic to add the last fullword when the length is not a multiple
  424.    of 4.  The result is left in register d0.
  425.  
  426.    With a 20MHz clock, this routine was measured at 134 usec/kB summing
  427.    random data.  This algorithm was developed by Van Jacobson.
  428.  
  429.  
  430.        movl    d1,d2
  431.        lsrl    #6,d1       | count/64 = # loop traversals
  432.        andl    #0x3c,d2    | Then find fractions of a chunk
  433.        negl    d2
  434.        andb    #0xf,cc     | Clear X (extended carry flag)
  435.  
  436.        jmp     pc@(2$-.-2:b,d2)  | Jump into loop
  437.  
  438.    1$:     | Begin inner loop...
  439.  
  440.        movl    a0@+,d2     |  Fetch 32-bit word
  441.        addxl   d2,d0       |    Add word + previous carry
  442.        movl    a0@+,d2     |  Fetch 32-bit word
  443.        addxl   d2,d0       |    Add word + previous carry
  444.  
  445.            | ... 14 more replications
  446.    2$:
  447.        dbra    d1,1$   | (NB- dbra doesn't affect X)
  448.  
  449.        movl    d0,d1   | Fold 32 bit sum to 16 bits
  450.        swap    d1      | (NB- swap doesn't affect X)
  451.        addxw   d1,d0
  452.        jcc     3$
  453.        addw    #1,d0
  454.    3$:
  455.        andl    #0xffff,d0
  456.  
  457.  
  458.  
  459.  
  460.  
  461.  
  462.  
  463.  
  464.  
  465.  
  466.  
  467.  
  468.  
  469.  
  470.  
  471.  
  472. Braden, Borman, & Partridge                                     [Page 8]
  473.  
  474. RFC 1071            Computing the Internet Checksum       September 1988
  475.  
  476.  
  477. 4.3  Cray
  478.  
  479.    The following example, in assembler language for a Cray CPU, was
  480.    contributed by Charley Kline.  It implements the checksum calculation
  481.    as a vector operation, summing up to 512 bytes at a time with a basic
  482.    summation unit of 32 bits.  This example omits many details having to
  483.    do with short blocks, for clarity.
  484.  
  485.    Register A1 holds the address of a 512-byte block of memory to
  486.    checksum.  First two copies of the data are loaded into two vector
  487.    registers.  One is vector-shifted right 32 bits, while the other is
  488.    vector-ANDed with a 32 bit mask. Then the two vectors are added
  489.    together.  Since all these operations chain, it produces one result
  490.    per clock cycle.  Then it collapses the result vector in a loop that
  491.    adds each element to a scalar register.  Finally, the end-around
  492.    carry is performed and the result is folded to 16-bits.
  493.  
  494.          EBM
  495.          A0      A1
  496.          VL      64            use full vectors
  497.          S1      <32           form 32-bit mask from the right.
  498.          A2      32
  499.          V1      ,A0,1            load packet into V1
  500.          V2      S1&V1            Form right-hand 32-bits in V2.
  501.          V3      V1>A2            Form left-hand 32-bits in V3.
  502.          V1      V2+V3            Add the two together.
  503.          A2      63            Prepare to collapse into a scalar.
  504.          S1      0
  505.          S4      <16           Form 16-bit mask from the right.
  506.          A4      16
  507.    CK$LOOP S2    V1,A2
  508.          A2      A2-1
  509.          A0      A2
  510.          S1      S1+S2
  511.          JAN     CK$LOOP
  512.          S2      S1&S4           Form right-hand 16-bits in S2
  513.          S1      S1>A4           Form left-hand 16-bits in S1
  514.          S1      S1+S2
  515.          S2      S1&S4           Form right-hand 16-bits in S2
  516.          S1      S1>A4           Form left-hand 16-bits in S1
  517.          S1      S1+S2
  518.          S1      #S1            Take one's complement
  519.          CMR            At this point, S1 contains the checksum.
  520.  
  521.  
  522.  
  523.  
  524.  
  525.  
  526.  
  527.  
  528.  
  529.  
  530.  
  531. Braden, Borman, & Partridge                                     [Page 9]
  532.  
  533. RFC 1071            Computing the Internet Checksum       September 1988
  534.  
  535.  
  536. 4.4  IBM 370
  537.  
  538.    The following example, in assembler language for an IBM 370 CPU, sums
  539.    the data 4 bytes at a time.  For clarity, we have omitted the logic
  540.    to add the last fullword when the length is not a multiple of 4, and
  541.    to reverse the bytes when necessary.  The result is left in register
  542.    RCARRY.
  543.  
  544.    This code has been timed on an IBM 3090 CPU at 27 usec/KB when
  545.    summing all one bits.  This time is reduced to 24.3 usec/KB if the
  546.    trouble is taken to word-align the addends (requiring special cases
  547.    at both the beginning and the end, and byte-swapping when necessary
  548.    to compensate for starting on an odd byte).
  549.  
  550.    *      Registers RADDR and RCOUNT contain the address and length of
  551.    *              the block to be checksummed.
  552.    *
  553.    *      (RCARRY, RSUM) must be an even/odd register pair.
  554.    *      (RCOUNT, RMOD) must be an even/odd register pair.
  555.    *
  556.    CHECKSUM  SR    RSUM,RSUM       Clear working registers.
  557.              SR    RCARRY,RCARRY
  558.              LA    RONE,1          Set up constant 1.
  559.    *
  560.              SRDA  RCOUNT,6        Count/64 to RCOUNT.
  561.              AR    RCOUNT,RONE       +1 = # times in loop.
  562.              SRL   RMOD,26         Size of partial chunk to RMOD.
  563.              AR    RADDR,R3        Adjust addr to compensate for
  564.              S     RADDR,=F(64)      jumping into the loop.
  565.              SRL   RMOD,1          (RMOD/4)*2 is halfword index.
  566.              LH    RMOD,DOPEVEC9(RMOD) Use magic dope-vector for offset,
  567.              B     LOOP(RMOD)          and jump into the loop...
  568.    *
  569.    *             Inner loop:
  570.    *
  571.    LOOP      AL    RSUM,0(,RADDR)   Add Logical fullword
  572.              BC    12,*+6             Branch if no carry
  573.              AR    RCARRY,RONE        Add 1 end-around
  574.              AL    RSUM,4(,RADDR)   Add Logical fullword
  575.              BC    12,*+6             Branch if no carry
  576.              AR    RCARRY,RONE        Add 1 end-around
  577.    *
  578.    *                    ... 14 more replications ...
  579.    *
  580.              A     RADDR,=F'64'    Increment address ptr
  581.              BCT   RCOUNT,LOOP     Branch on Count
  582.     *
  583.     *            Add Carries into sum, and fold to 16 bits
  584.     *
  585.              ALR   RCARRY,RSUM      Add SUM and CARRY words
  586.              BC    12,*+6              and take care of carry
  587.  
  588.  
  589.  
  590. Braden, Borman, & Partridge                                    [Page 10]
  591.  
  592. RFC 1071            Computing the Internet Checksum       September 1988
  593.  
  594.  
  595.              AR    RCARRY,RONE
  596.              SRDL  RCARRY,16        Fold 32-bit sum into
  597.              SRL   RSUM,16            16-bits
  598.              ALR   RCARRY,RSUM
  599.              C     RCARRY,=X'0000FFFF' and take care of any
  600.              BNH   DONE                     last carry
  601.              S     RCARRY,=X'0000FFFF'
  602.    DONE      X     RCARRY,=X'0000FFFF' 1's complement
  603.  
  604.  
  605.  
  606.  
  607.  
  608.  
  609.  
  610.  
  611.  
  612.  
  613.  
  614.  
  615.  
  616.  
  617.  
  618.  
  619.  
  620.  
  621.  
  622.  
  623.  
  624.  
  625.  
  626.  
  627.  
  628.  
  629.  
  630.  
  631.  
  632.  
  633.  
  634.  
  635.  
  636.  
  637.  
  638.  
  639.  
  640.  
  641.  
  642.  
  643.  
  644.  
  645.  
  646.  
  647.  
  648.  
  649. Braden, Borman, & Partridge                                    [Page 11]
  650.  
  651. RFC 1071            Computing the Internet Checksum       September 1988
  652.  
  653.  
  654.      IEN 45
  655.      Section 2.4.4.5
  656.  
  657.  
  658.  
  659.  
  660.  
  661.  
  662.  
  663.  
  664.  
  665.  
  666.  
  667.  
  668.  
  669.  
  670.  
  671.  
  672.                        TCP Checksum Function Design
  673.  
  674.  
  675.  
  676.                             William W. Plummer
  677.  
  678.  
  679.                        Bolt Beranek and Newman, Inc.
  680.                              50 Moulton Street
  681.                            Cambridge MA   02138
  682.  
  683.  
  684.                                 5 June 1978
  685.  
  686.  
  687.  
  688.  
  689.  
  690.  
  691.  
  692.  
  693.  
  694.  
  695.  
  696.  
  697.  
  698.  
  699.  
  700.  
  701.  
  702.  
  703.  
  704.  
  705.  
  706.  
  707.  
  708. Braden, Borman, & Partridge                                    [Page 12]
  709.  
  710. RFC 1071            Computing the Internet Checksum       September 1988
  711.  
  712.  
  713.      Internet Experiment Note  45                          5 June 1978
  714.      TCP Checksum Function Design                   William W. Plummer
  715.  
  716.      1.      Introduction
  717.  
  718.      Checksums  are  included  in  packets  in   order   that   errors
  719.      encountered  during  transmission  may be detected.  For Internet
  720.      protocols such as TCP [1,9] this is especially important  because
  721.      packets  may  have  to cross wireless networks such as the Packet
  722.      Radio Network  [2]  and  Atlantic  Satellite  Network  [3]  where
  723.      packets  may  be  corrupted.  Internet protocols (e.g., those for
  724.      real time speech transmission) can tolerate a  certain  level  of
  725.      transmission  errors  and  forward error correction techniques or
  726.      possibly no checksum at all might be better.  The focus  in  this
  727.      paper  is  on  checksum functions for protocols such as TCP where
  728.      the required reliable delivery is achieved by retransmission.
  729.  
  730.      Even if the checksum appears good on a  message  which  has  been
  731.      received, the message may still contain an undetected error.  The
  732.      probability of this is bounded by 2**(-C) where  C  is the number
  733.      of  checksum bits.  Errors can arise from hardware (and software)
  734.      malfunctions as well as transmission  errors.   Hardware  induced
  735.      errors  are  usually manifested in certain well known ways and it
  736.      is desirable to account for this in the design  of  the  checksum
  737.      function.  Ideally no error of the "common hardware failure" type
  738.      would go undetected.
  739.  
  740.      An  example  of  a  failure  that  the  current checksum function
  741.      handles successfully is picking up a bit in the network interface
  742.      (or I/O buss, memory channel, etc.).  This will always render the
  743.      checksum bad.  For an example of  how  the  current  function  is
  744.      inadequate, assume that a control signal stops functioning in the
  745.      network  interface and the interface stores zeros in place of the
  746.      real data.  These  "all  zero"  messages  appear  to  have  valid
  747.      checksums.   Noise  on the "There's Your Bit" line of the ARPANET
  748.      Interface [4] may go undetected because the extra bits input  may
  749.      cause  the  checksum  to be perturbed (i.e., shifted) in the same
  750.      way as the data was.
  751.  
  752.      Although messages containing undetected errors will  occasionally
  753.      be  passed  to  higher levels of protocol, it is likely that they
  754.      will not make sense at that level.  In the case of TCP most  such
  755.      messages will be ignored, but some could cause a connection to be
  756.      aborted.   Garbled  data could be viewed as a problem for a layer
  757.      of protocol above TCP which itself may have a checksuming scheme.
  758.  
  759.      This paper is the first step in design of a new checksum function
  760.      for TCP  and  some  other  Internet  protocols.   Several  useful
  761.      properties  of  the current function are identified.  If possible
  762.  
  763.                                    - 1 -
  764.  
  765.  
  766.  
  767. Braden, Borman, & Partridge                                    [Page 13]
  768.  
  769. RFC 1071            Computing the Internet Checksum       September 1988
  770.  
  771.  
  772.      Internet Experiment Note  45                          5 June 1978
  773.      TCP Checksum Function Design                   William W. Plummer
  774.  
  775.      these should be retained  in  any  new  function.   A  number  of
  776.      plausible  checksum  schemes are investigated.  Of these only the
  777.      "product code" seems to be simple enough for consideration.
  778.  
  779.      2.      The Current TCP Checksum Function
  780.  
  781.      The current function is  oriented  towards  sixteen-bit  machines
  782.      such  as  the PDP-11 but can be computed easily on other machines
  783.      (e.g., PDP-10).  A packet is thought of as  a  string  of  16-bit
  784.      bytes  and the checksum function is the one's complement sum (add
  785.      with  end-around  carry)  of  those  bytes.   It  is  the   one's
  786.      complement  of  this sum which is stored in the checksum field of
  787.      the TCP header.  Before computing the checksum value, the  sender
  788.      places  a  zero  in  the  checksum  field  of the packet.  If the
  789.      checksum value computed by a receiver of the packet is zero,  the
  790.      packet  is  assumed  to  be  valid.  This is a consequence of the
  791.      "negative" number in the checksum field  exactly  cancelling  the
  792.      contribution of the rest of the packet.
  793.  
  794.      Ignoring  the  difficulty  of  actually  evaluating  the checksum
  795.      function for a given  packet,  the  way  of  using  the  checksum
  796.      described  above  is quite simple, but it assumes some properties
  797.      of the checksum operator (one's complement addition, "+" in  what
  798.      follows):
  799.  
  800.        (P1)    +  is commutative.  Thus, the  order  in  which
  801.              the   16-bit   bytes   are  "added"  together  is
  802.              unimportant.
  803.  
  804.        (P2)    +  has  at  least  one  identity  element  (The
  805.              current  function  has  two:  +0  and  -0).  This
  806.              allows  the  sender  to  compute   the   checksum
  807.              function by placing a zero in the packet checksum
  808.              field before computing the value.
  809.  
  810.        (P3)    +  has an  inverse.   Thus,  the  receiver  may
  811.              evaluate the checksum function and expect a zero.
  812.  
  813.        (P4)    +  is associative, allowing the checksum  field
  814.              to be anywhere in the packet and the 16-bit bytes
  815.              to be scanned sequentially.
  816.  
  817.      Mathematically, these properties of the binary operation "+" over
  818.      the set of 16-bit numbers forms an Abelian group [5].  Of course,
  819.      there  are  many Abelian groups but not all would be satisfactory
  820.      for  use  as  checksum  operators.   (Another  operator   readily
  821.  
  822.                                    - 2 -
  823.  
  824.  
  825.  
  826. Braden, Borman, & Partridge                                    [Page 14]
  827.  
  828. RFC 1071            Computing the Internet Checksum       September 1988
  829.  
  830.  
  831.      Internet Experiment Note  45                          5 June 1978
  832.      TCP Checksum Function Design                   William W. Plummer
  833.  
  834.      available  in  the  PDP-11  instruction set that has all of these
  835.      properties is exclusive-OR, but XOR is unsatisfactory  for  other
  836.      reasons.)
  837.  
  838.      Albeit imprecise, another property which must be preserved in any
  839.      future checksum scheme is:
  840.  
  841.        (P5)    +  is fast to compute on a variety of  machines
  842.              with limited storage requirements.
  843.  
  844.      The  current  function  is  quite  good  in this respect.  On the
  845.      PDP-11 the inner loop looks like:
  846.  
  847.              LOOP:   ADD (R1)+,R0    ; Add the next 16-bit byte
  848.                      ADC R0          ; Make carry be end-around
  849.                      SOB R2,LOOP     ; Loop over entire packet.
  850.  
  851.               ( 4 memory cycles per 16-bit byte )
  852.  
  853.      On the PDP-10 properties  P1-4  are  exploited  further  and  two
  854.      16-bit bytes per loop are processed:
  855.  
  856.      LOOP: ILDB THIS,PTR   ; Get 2 16-bit bytes
  857.            ADD SUM,THIS    ; Add into current sum
  858.            JUMPGE SUM,CHKSU2  ; Jump if fewer than 8 carries
  859.            LDB THIS,[POINT 20,SUM,19] ; Get left 16 and carries
  860.            ANDI SUM,177777 ; Save just low 16 here
  861.            ADD SUM,THIS    ; Fold in carries
  862.      CHKSU2: SOJG COUNT,LOOP ; Loop over entire packet
  863.  
  864.      ( 3.1 memory cycles per 16-bit byte )
  865.  
  866.      The  "extra"  instruction  in  the  loops  above  are required to
  867.      convert the two's complement  ADD  instruction(s)  into  a  one's
  868.      complement  add  by  making  the  carries  be  end-around.  One's
  869.      complement arithmetic is better than two's complement because  it
  870.      is  equally  sensitive  to errors in all bit positions.  If two's
  871.      complement addition were used, an even number  of  1's  could  be
  872.      dropped  (or  picked  up)  in  the  most  significant bit channel
  873.      without affecting the value of the checksum.   It  is  just  this
  874.      property  that makes some sort of addition preferable to a simple
  875.      exclusive-OR which is frequently used but permits an even  number
  876.      of drops (pick ups) in any bit channel.  RIM10B paper tape format
  877.      used  on PDP-10s [10] uses two's complement add because space for
  878.      the loader program is extremely limited.
  879.  
  880.                                    - 3 -
  881.  
  882.  
  883.  
  884.  
  885. Braden, Borman, & Partridge                                    [Page 15]
  886.  
  887. RFC 1071            Computing the Internet Checksum       September 1988
  888.  
  889.  
  890.      Internet Experiment Note  45                          5 June 1978
  891.      TCP Checksum Function Design                   William W. Plummer
  892.  
  893.      Another property of the current checksum scheme is:
  894.  
  895.        (P6)    Adding the checksum to a packet does not change
  896.              the information bytes.  Peterson [6] calls this a
  897.              "systematic" code.
  898.  
  899.      This property  allows  intermediate  computers  such  as  gateway
  900.      machines  to  act  on  fields  (i.e.,  the  Internet  Destination
  901.      Address) without having to first  decode  the  packet.   Cyclical
  902.      Redundancy  Checks  used  for error correction are not systematic
  903.      either.  However, most applications of  CRCs  tend  to  emphasize
  904.      error  detection rather than correction and consequently can send
  905.      the message unchanged, with the CRC check bits being appended  to
  906.      the  end.   The  24-bit CRC used by ARPANET IMPs and Very Distant
  907.      Host Interfaces [4] and the ANSI standards for 800 and 6250  bits
  908.      per inch magnetic tapes (described in [11]) use this mode.
  909.  
  910.      Note  that  the  operation  of higher level protocols are not (by
  911.      design) affected by anything that may be done by a gateway acting
  912.      on possibly invalid packets.  It is permissible for  gateways  to
  913.      validate  the  checksum  on  incoming  packets,  but  in  general
  914.      gateways will not know how to  do  this  if  the  checksum  is  a
  915.      protocol-specific feature.
  916.  
  917.      A final property of the current checksum scheme which is actually
  918.      a consequence of P1 and P4 is:
  919.  
  920.        (P7)    The checksum may be incrementally modified.
  921.  
  922.      This  property permits an intermediate gateway to add information
  923.      to a packet, for instance a timestamp, and "add"  an  appropriate
  924.      change  to  the  checksum  field  of  the  packet.  Note that the
  925.      checksum  will  still  be  end-to-end  since  it  was  not  fully
  926.      recomputed.
  927.  
  928.      3.      Product Codes
  929.  
  930.      Certain  "product  codes"  are potentially useful for checksuming
  931.      purposes.  The following is a brief description of product  codes
  932.      in  the  context  of TCP.  More general treatment can be found in
  933.      Avizienis [7] and probably other more recent works.
  934.  
  935.      The basic concept of this coding is that the message (packet)  to
  936.      be sent is formed by transforming the original source message and
  937.      adding  some  "check"  bits.   By  reading  this  and  applying a
  938.      (possibly different) transformation, a receiver  can  reconstruct
  939.  
  940.                                    - 4 -
  941.  
  942.  
  943.  
  944. Braden, Borman, & Partridge                                    [Page 16]
  945.  
  946. RFC 1071            Computing the Internet Checksum       September 1988
  947.  
  948.  
  949.      Internet Experiment Note  45                          5 June 1978
  950.      TCP Checksum Function Design                   William W. Plummer
  951.  
  952.      the  original  message  and  determine  if  it has been corrupted
  953.      during transmission.
  954.  
  955.               Mo              Ms              Mr
  956.  
  957.              -----           -----           -----
  958.              | A |  code     | 7 |   decode  | A |
  959.              | B |    ==>    | 1 |     ==>   | B |
  960.              | C |           | 4 |           | C |
  961.              -----           |...|           -----
  962.                              | 2 | check     plus "valid" flag
  963.                              ----- info
  964.  
  965.              Original        Sent            Reconstructed
  966.  
  967.      With product codes the transformation is  Ms = K * Mo .  That is,
  968.      the message sent is simply the product of  the  original  message
  969.      Mo   and  some  well known constant  K .  To decode, the received
  970.      Ms  is divided by  K  which will yield  Mr  as the  quotient  and
  971.      0   as the remainder if  Mr is to be considered the same as  Mo .
  972.  
  973.      The first problem is selecting a "good" value for  K, the  "check
  974.      factor".   K  must  be  relatively  prime  to  the base chosen to
  975.      express  the  message.   (Example:  Binary   messages   with    K
  976.      incorrectly  chosen  to be 8.  This means that  Ms  looks exactly
  977.      like  Mo  except that three zeros have been appended.   The  only
  978.      way  the message could look bad to a receiver dividing by 8 is if
  979.      the error occurred in one of those three bits.)
  980.  
  981.      For TCP the base  R  will be chosen to be 2**16.  That is,  every
  982.      16-bit byte (word on the PDP-11) will be considered as a digit of
  983.      a big number and that number is the message.  Thus,
  984.  
  985.                      Mo =  SIGMA [ Bi * (R**i)]   ,   Bi is i-th byte
  986.                           i=0 to N
  987.  
  988.                      Ms = K * Mo
  989.  
  990.      Corrupting a single digit  of   Ms   will  yield   Ms' =  Ms +or-
  991.      C*(R**j)  for some radix position  j .  The receiver will compute
  992.      Ms'/K = Mo +or- C(R**j)/K. Since R  and  K  are relatively prime,
  993.      C*(R**j) cannot be any exact  multiple  of   K.   Therefore,  the
  994.      division will result in a non-zero remainder which indicates that
  995.      Ms'   is  a  corrupted  version  of  Ms.  As will be seen, a good
  996.      choice for  K  is (R**b - 1), for some  b  which  is  the  "check
  997.      length"  which  controls  the  degree  of detection to be had for
  998.  
  999.                                    - 5 -
  1000.  
  1001.  
  1002.  
  1003. Braden, Borman, & Partridge                                    [Page 17]
  1004.  
  1005. RFC 1071            Computing the Internet Checksum       September 1988
  1006.  
  1007.  
  1008.      Internet Experiment Note  45                          5 June 1978
  1009.      TCP Checksum Function Design                   William W. Plummer
  1010.  
  1011.      burst errors which affect a string of digits (i.e., 16-bit bytes)
  1012.      in the message.  In fact  b  will be chosen to be  1, so  K  will
  1013.      be  2**16 - 1 so that arithmetic operations will be simple.  This
  1014.      means  that  all  bursts  of  15  or fewer bits will be detected.
  1015.      According to [7] this choice for  b   results  in  the  following
  1016.      expression for the fraction of undetected weight 2 errors:
  1017.  
  1018.       f =  16(k-1)/[32(16k-3) + (6/k)]  where k is the message length.
  1019.  
  1020.      For  large messages  f  approaches  3.125 per cent as  k  goes to
  1021.      infinity.
  1022.  
  1023.      Multiple precision multiplication and division are normally quite
  1024.      complex operations, especially on small machines which  typically
  1025.      lack  even  single precision multiply and divide operations.  The
  1026.      exception to this is exactly the case being dealt  with  here  --
  1027.      the  factor  is  2**16  - 1  on machines with a word length of 16
  1028.      bits.  The reason for this is due to the following identity:
  1029.  
  1030.              Q*(R**j)  =  Q, mod (R-1)     0 <= Q < R
  1031.  
  1032.      That is, any digit  Q  in the selected  radix  (0,  1,  ...  R-1)
  1033.      multiplied  by any power of the radix will have a remainder of  Q
  1034.      when divided by the radix minus 1.
  1035.  
  1036.      Example:  In decimal R = 10.  Pick  Q = 6.
  1037.  
  1038.                      6  =   0 * 9  +  6  =  6, mod 9
  1039.                     60  =   6 * 9  +  6  =  6, mod 9
  1040.                    600  =  66 * 9  +  6  =  6, mod 9   etc.
  1041.  
  1042.         More to the point, rem(31415/9) = rem((30000+1000+400+10+5)/9)
  1043.            = (3 mod 9) + (1 mod 9) + (4 mod 9) + (1 mod 9) + (5 mod 9)
  1044.            = (3+1+4+1+5) mod 9
  1045.            = 14 mod 9
  1046.            = 5
  1047.  
  1048.      So, the remainder of a number divided by the radix minus one  can
  1049.      be  found  by simply summing the digits of the number.  Since the
  1050.      radix in the TCP case has been chosen to be  2**16 and the  check
  1051.      factor is  2**16 - 1, a message can quickly be checked by summing
  1052.      all  of  the  16-bit  words  (on  a  PDP-11),  with carries being
  1053.      end-around.  If zero is the result, the message can be considered
  1054.      valid.  Thus, checking a product coded  message  is  exactly  the
  1055.      same complexity as with the current TCP checksum!
  1056.  
  1057.                                    - 6 -
  1058.  
  1059.  
  1060.  
  1061.  
  1062. Braden, Borman, & Partridge                                    [Page 18]
  1063.  
  1064. RFC 1071            Computing the Internet Checksum       September 1988
  1065.  
  1066.  
  1067.      Internet Experiment Note  45                          5 June 1978
  1068.      TCP Checksum Function Design                   William W. Plummer
  1069.  
  1070.      In  order  to  form   Ms,  the  sender must multiply the multiple
  1071.      precision "number"  Mo  by  2**16 - 1.  Or,  Ms = (2**16)Mo - Mo.
  1072.      This is performed by shifting  Mo   one  whole  word's  worth  of
  1073.      precision  and  subtracting   Mo.   Since  carries must propagate
  1074.      between digits, but it is only the  current  digit  which  is  of
  1075.      interest, one's complement arithmetic is used.
  1076.  
  1077.              (2**16)Mo =  Mo0 + Mo1 + Mo2 + ... + MoX +  0
  1078.                  -  Mo =    - ( Mo0 + Mo1 + ......... + MoX)
  1079.              ---------    ----------------------------------
  1080.                 Ms     =  Ms0 + Ms1 + ...             - MoX
  1081.  
  1082.      A  loop  which  implements  this  function on a PDP-11 might look
  1083.      like:
  1084.              LOOP:   MOV -2(R2),R0   ; Next byte of (2**16)Mo
  1085.                      SBC R0          ; Propagate carries from last SUB
  1086.                      SUB (R2)+,R0    ; Subtract byte of  Mo
  1087.                      MOV R0,(R3)+    ; Store in Ms
  1088.                      SOB R1,LOOP     ; Loop over entire message
  1089.                                      ; 8 memory cycles per 16-bit byte
  1090.  
  1091.      Note that the coding procedure is not done in-place since  it  is
  1092.      not  systematic.   In general the original copy, Mo, will have to
  1093.      be  retained  by  the  sender  for  retransmission  purposes  and
  1094.      therefore  must  remain  readable.   Thus  the  MOV  R0,(R3)+  is
  1095.      required which accounts for 2 of the  8  memory cycles per  loop.
  1096.  
  1097.      The  coding  procedure  will  add  exactly one 16-bit word to the
  1098.      message since  Ms <  (2**16)Mo .  This additional 16 bits will be
  1099.      at the tail of the message, but may be  moved  into  the  defined
  1100.      location  in the TCP header immediately before transmission.  The
  1101.      receiver will have to undo this to put  Ms   back  into  standard
  1102.      format before decoding the message.
  1103.  
  1104.      The  code  in  the receiver for fully decoding the message may be
  1105.      inferred  by  observing  that  any  word  in   Ms   contains  the
  1106.      difference between two successive words of  Mo  minus the carries
  1107.      from the previous word, and the low order word contains minus the
  1108.      low word of Mo.  So the low order (i.e., rightmost) word of Mr is
  1109.      just  the negative of the low order byte of Ms.  The next word of
  1110.      Mr is the next word of  Ms  plus the just computed  word  of   Mr
  1111.      plus the carry from that previous computation.
  1112.  
  1113.      A  slight  refinement  of  the  procedure is required in order to
  1114.      protect against an all-zero message passing to  the  destination.
  1115.      This  will  appear to have a valid checksum because Ms'/K  =  0/K
  1116.  
  1117.                                    - 7 -
  1118.  
  1119.  
  1120.  
  1121. Braden, Borman, & Partridge                                    [Page 19]
  1122.  
  1123. RFC 1071            Computing the Internet Checksum       September 1988
  1124.  
  1125.  
  1126.      Internet Experiment Note  45                          5 June 1978
  1127.      TCP Checksum Function Design                   William W. Plummer
  1128.  
  1129.      = 0 with 0 remainder.  The refinement is to make  the  coding  be
  1130.      Ms  =  K*Mo + C where  C  is some arbitrary, well-known constant.
  1131.      Adding this constant requires a second pass over the message, but
  1132.      this will typically be very short since it can stop  as  soon  as
  1133.      carries  stop propagating.  Chosing  C = 1  is sufficient in most
  1134.      cases.
  1135.  
  1136.      The product code checksum must  be  evaluated  in  terms  of  the
  1137.      desired  properties  P1 - P7.  It has been shown that a factor of
  1138.      two more machine cycles are consumed in computing or verifying  a
  1139.      product code checksum (P5 satisfied?).
  1140.  
  1141.      Although the code is not systematic, the checksum can be verified
  1142.      quickly   without   decoding   the   message.   If  the  Internet
  1143.      Destination Address is located at the least  significant  end  of
  1144.      the packet (where the product code computation begins) then it is
  1145.      possible  for  a  gateway to decode only enough of the message to
  1146.      see this field without  having  to  decode  the  entire  message.
  1147.      Thus,   P6  is  at  least  partially  satisfied.   The  algebraic
  1148.      properties P1 through P4 are not  satisfied,  but  only  a  small
  1149.      amount  of  computation  is  needed  to  account  for this -- the
  1150.      message needs to be reformatted as previously mentioned.
  1151.  
  1152.      P7  is  satisfied  since  the  product  code  checksum   can   be
  1153.      incrementally  updated to account for an added word, although the
  1154.      procedure is  somewhat  involved.    Imagine  that  the  original
  1155.      message  has two halves, H1 and  H2.  Thus,  Mo = H1*(R**j) + H2.
  1156.      The timestamp word is to be inserted between these halves to form
  1157.      a modified  Mo' = H1*(R**(j+1)) + T*(R**j) + H2.  Since   K   has
  1158.      been  chosen to be  R-1, the transmitted message  Ms' = Mo'(R-1).
  1159.      Then,
  1160.  
  1161.       Ms' =  Ms*R + T(R-1)(R**j) + P2((R-1)**2)
  1162.  
  1163.           =  Ms*R + T*(R**(j+1))  + T*(R**j) + P2*(R**2) - 2*P2*R - P2
  1164.  
  1165.      Recalling that  R   is  2**16,  the  word  size  on  the  PDP-11,
  1166.      multiplying  by   R   means copying down one word in memory.  So,
  1167.      the first term of  Ms' is simply the  unmodified  message  copied
  1168.      down  one word.  The next term is the new data  T  added into the
  1169.      Ms' being formed beginning at the (j+1)th word.  The addition  is
  1170.      fairly  easy  here  since  after adding in T  all that is left is
  1171.      propagating the carry, and that can stop as soon as no  carry  is
  1172.      produced.  The other terms can be handle similarly.
  1173.  
  1174.                                    - 8 -
  1175.  
  1176.  
  1177.  
  1178.  
  1179.  
  1180. Braden, Borman, & Partridge                                    [Page 20]
  1181.  
  1182. RFC 1071            Computing the Internet Checksum       September 1988
  1183.  
  1184.  
  1185.      Internet Experiment Note  45                          5 June 1978
  1186.      TCP Checksum Function Design                   William W. Plummer
  1187.  
  1188.      4.      More Complicated Codes
  1189.  
  1190.      There exists a wealth of theory on error detecting and correcting
  1191.      codes.   Peterson  [6]  is an excellent reference.  Most of these
  1192.      "CRC" schemes are  designed  to  be  implemented  using  a  shift
  1193.      register  with  a  feedback  network  composed  of exclusive-ORs.
  1194.      Simulating such a logic circuit with a program would be too  slow
  1195.      to be useful unless some programming trick is discovered.
  1196.  
  1197.      One  such  trick has been proposed by Kirstein [8].  Basically, a
  1198.      few bits (four or eight) of the current shift register state  are
  1199.      combined with bits from the input stream (from Mo) and the result
  1200.      is  used  as  an  index  to  a  table  which yields the new shift
  1201.      register state and, if the code is not systematic, bits  for  the
  1202.      output  stream  (Ms).  A trial coding of an especially "good" CRC
  1203.      function using four-bit bytes showed showed this technique to  be
  1204.      about  four times as slow as the current checksum function.  This
  1205.      was true for  both  the  PDP-10  and  PDP-11  machines.   Of  the
  1206.      desirable  properties  listed  above, CRC schemes satisfy only P3
  1207.      (It has an inverse.), and P6 (It is systematic.).   Placement  of
  1208.      the  checksum  field in the packet is critical and the CRC cannot
  1209.      be incrementally modified.
  1210.  
  1211.      Although the bulk of coding theory deals with binary codes,  most
  1212.      of  the theory works if the alphabet contains   q  symbols, where
  1213.      q is a power of a prime number.  For instance  q  taken as  2**16
  1214.      should  make  a great deal of the theory useful on a word-by-word
  1215.      basis.
  1216.  
  1217.      5.      Outboard Processing
  1218.  
  1219.      When a function such as computing an involved  checksum  requires
  1220.      extensive processing, one solution is to put that processing into
  1221.      an  outboard processor.  In this way "encode message" and "decode
  1222.      message" become single instructions which do  not  tax  the  main
  1223.      host   processor.   The  Digital  Equipment  Corporation  VAX/780
  1224.      computer is equipped with special  hardware  for  generating  and
  1225.      checking  CRCs [13].  In general this is not a very good solution
  1226.      since such a processor must be constructed  for  every  different
  1227.      host machine which uses TCP messages.
  1228.  
  1229.      It is conceivable that the gateway functions for a large host may
  1230.      be  performed  entirely  in an "Internet Frontend Machine".  This
  1231.      machine would be  responsible  for  forwarding  packets  received
  1232.  
  1233.                                    - 9 -
  1234.  
  1235.  
  1236.  
  1237.  
  1238.  
  1239. Braden, Borman, & Partridge                                    [Page 21]
  1240.  
  1241. RFC 1071            Computing the Internet Checksum       September 1988
  1242.  
  1243.  
  1244.      Internet Experiment Note  45                          5 June 1978
  1245.      TCP Checksum Function Design                   William W. Plummer
  1246.  
  1247.      either  from the network(s) or from the Internet protocol modules
  1248.      in the connected host, and for  reassembling  Internet  fragments
  1249.      into  segments and passing these to the host.  Another capability
  1250.      of this machine would be  to  check  the  checksum  so  that  the
  1251.      segments given to the host are known to be valid at the time they
  1252.      leave the frontend.  Since computer cycles are assumed to be both
  1253.      inexpensive and available in the frontend, this seems reasonable.
  1254.  
  1255.      The problem with attempting to validate checksums in the frontend
  1256.      is that it destroys the end-to-end character of the checksum.  If
  1257.      anything,  this is the most powerful feature of the TCP checksum!
  1258.      There is a way to make the host-to-frontend link  be  covered  by
  1259.      the  end-to-end  checksum.   A  separate,  small protocol must be
  1260.      developed to cover this link.  After having validated an incoming
  1261.      packet from the network, the frontend would pass it to  the  host
  1262.      saying "here is an Internet segment for you.  Call it #123".  The
  1263.      host  would  save  this  segment,  and  send  a  copy back to the
  1264.      frontend saying, "Here is what you gave me as #123.  Is it  OK?".
  1265.      The  frontend  would  then  do a word-by-word comparison with the
  1266.      first transmission, and  tell  the  host  either  "Here  is  #123
  1267.      again",  or "You did indeed receive #123 properly.  Release it to
  1268.      the appropriate module for further processing."
  1269.  
  1270.      The headers on the messages crossing the host-frontend link would
  1271.      most likely be covered  by  a  fairly  strong  checksum  so  that
  1272.      information  like  which  function  is  being  performed  and the
  1273.      message reference numbers are reliable.  These headers  would  be
  1274.      quite  short,  maybe  only sixteen bits, so the checksum could be
  1275.      quite strong.  The bulk of the message would not be checksumed of
  1276.      course.
  1277.      The reason this scheme reduces the computing burden on  the  host
  1278.      is  that  all  that  is required in order to validate the message
  1279.      using the end-to-end checksum is to send it back to the  frontend
  1280.      machine.   In  the  case  of  the PDP-10, this requires only  0.5
  1281.      memory cycles per 16-bit byte of Internet message, and only a few
  1282.      processor cycles to setup the required transfers.
  1283.  
  1284.      6.      Conclusions
  1285.  
  1286.      There is an ordering of checksum functions: first and simplest is
  1287.      none at all which provides  no  error  detection  or  correction.
  1288.      Second,  is  sending a constant which is checked by the receiver.
  1289.      This also is extremely weak.  Third, the exclusive-OR of the data
  1290.      may be sent.  XOR takes the minimal amount of  computer  time  to
  1291.      generate  and  check,  but  is  not  a  good  checksum.   A two's
  1292.      complement sum of the data is somewhat better and takes  no  more
  1293.  
  1294.                                   - 10 -
  1295.  
  1296.  
  1297.  
  1298. Braden, Borman, & Partridge                                    [Page 22]
  1299.  
  1300. RFC 1071            Computing the Internet Checksum       September 1988
  1301.  
  1302.  
  1303.      Internet Experiment Note  45                          5 June 1978
  1304.      TCP Checksum Function Design                   William W. Plummer
  1305.  
  1306.      computer  time  to  compute.   Fifth, is the one's complement sum
  1307.      which is what is currently used by  TCP.   It  is  slightly  more
  1308.      expensive  in terms of computer time.  The next step is a product
  1309.      code.  The product code is strongly related to  one's  complement
  1310.      sum,  takes  still more computer time to use, provides a bit more
  1311.      protection  against  common  hardware  failures,  but  has   some
  1312.      objectionable properties.  Next is a genuine CRC polynomial code,
  1313.      used  for  checking  purposes only.  This is very expensive for a
  1314.      program to implement.  Finally, a full CRC error  correcting  and
  1315.      detecting scheme may be used.
  1316.  
  1317.      For  TCP  and  Internet  applications  the product code scheme is
  1318.      viable.  It suffers mainly in that messages  must  be  (at  least
  1319.      partially)  decoded  by  intermediate gateways in order that they
  1320.      can be forwarded.  Should product  codes  not  be  chosen  as  an
  1321.      improved  checksum,  some  slight  modification  to  the existing
  1322.      scheme might be possible.  For  instance  the  "add  and  rotate"
  1323.      function  used  for  paper  tape  by  the  PDP-6/10  group at the
  1324.      Artificial Intelligence Laboratory at  M.I.T.  Project  MAC  [12]
  1325.      could  be  useful  if it can be proved that it is better than the
  1326.      current scheme and that it  can  be  computed  efficiently  on  a
  1327.      variety of machines.
  1328.  
  1329.  
  1330.  
  1331.  
  1332.  
  1333.  
  1334.  
  1335.  
  1336.  
  1337.  
  1338.  
  1339.  
  1340.  
  1341.  
  1342.  
  1343.  
  1344.  
  1345.  
  1346.  
  1347.  
  1348.  
  1349.                                   - 11 -
  1350.  
  1351.  
  1352.  
  1353.  
  1354.  
  1355.  
  1356.  
  1357. Braden, Borman, & Partridge                                    [Page 23]
  1358.  
  1359. RFC 1071            Computing the Internet Checksum       September 1988
  1360.  
  1361.  
  1362.      Internet Experiment Note  45                          5 June 1978
  1363.      TCP Checksum Function Design                   William W. Plummer
  1364.  
  1365.      References
  1366.  
  1367.      [1]  Cerf, V.G. and Kahn, Robert E., "A Protocol for Packet Network
  1368.           Communications," IEEE Transactions on Communications, vol.
  1369.           COM-22, No.  5, May 1974.
  1370.  
  1371.      [2]  Kahn, Robert E., "The Organization of Computer Resources into
  1372.           a Packet Radio Network", IEEE Transactions on Communications,
  1373.           vol. COM-25, no. 1, pp. 169-178, January 1977.
  1374.  
  1375.      [3]  Jacobs, Irwin, et al., "CPODA - A Demand Assignment Protocol
  1376.           for SatNet", Fifth Data Communications Symposium, September
  1377.           27-9, 1977, Snowbird, Utah
  1378.  
  1379.      [4]  Bolt Beranek and Newman, Inc.  "Specifications for the
  1380.           Interconnection of a Host and an IMP", Report 1822, January
  1381.           1976 edition.
  1382.  
  1383.      [5]  Dean, Richard A., "Elements of Abstract Algebra", John Wyley
  1384.           and Sons, Inc., 1966
  1385.  
  1386.      [6]  Peterson, W. Wesley, "Error Correcting Codes", M.I.T. Press
  1387.           Cambridge MA, 4th edition, 1968.
  1388.  
  1389.      [7]  Avizienis, Algirdas, "A Study of the Effectiveness of Fault-
  1390.           Detecting Codes for Binary Arithmetic", Jet Propulsion
  1391.           Laboratory Technical Report No. 32-711, September 1, 1965.
  1392.  
  1393.      [8]  Kirstein, Peter, private communication
  1394.  
  1395.      [9]  Cerf, V. G. and Postel, Jonathan B., "Specification of
  1396.           Internetwork Transmission Control Program Version 3",
  1397.           University of Southern California Information Sciences
  1398.           Institute, January 1978.
  1399.  
  1400.      [10] Digital Equipment Corporation, "PDP-10 Reference Handbook",
  1401.           1970, pp. 114-5.
  1402.  
  1403.      [11] Swanson, Robert, "Understanding Cyclic Redundancy Codes",
  1404.           Computer Design, November, 1975, pp. 93-99.
  1405.  
  1406.      [12] Clements, Robert C., private communication.
  1407.  
  1408.      [13] Conklin, Peter F., and Rodgers, David P., "Advanced
  1409.           Minicomputer Designed by Team Evaluation of Hardware/Software
  1410.           Tradeoffs", Computer Design, April 1978, pp. 136-7.
  1411.  
  1412.                                        - 12 -
  1413.  
  1414.  
  1415.  
  1416. Braden, Borman, & Partridge                                    [Page 24]
  1417.  
  1418.