Debian Codegraph @

rfc1071.html

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