RFC 1071
Computing the Internet checksum
RFC 1071: Computing the Internet Checksum 🎀
Okay bestie, this one is a classic 🌸 It's RFC 1071, titled Computing the Internet Checksum, and it was written in September 1988 by three people:
- R. Braden, from ISI
- D. Borman, from Cray Research
- C. Partridge, from BBN Laboratories
It doesn't say what category it's in, but the Status section makes it clear it's not a standard. It's a collection of useful implementation tricks 🧚 The title block doesn't list anything it obsoletes or updates, so it's standing on its own ✨
Status of This Memo ✨
This memo sums up techniques and algorithms for computing the Internet checksum efficiently. It's not a standard, just a set of handy implementation techniques. Distribution of this memo is unlimited 💖
1. Introduction 🦋
Okay so this memo is all about how to compute the Internet checksum quickly. That checksum is used by the standard Internet protocols IP, UDP, and TCP, so it shows up everywhere 👑
An efficient checksum implementation is critical for good performance. Once people sped up everything else in protocol processing, the checksum became one of the things holding TCP back. A fraction of a microsecond per TCP data byte adds up to a huge amount of CPU time, so it's totally normal to hand-craft the checksum routine and squeeze out every machine-specific trick you can 💅
The basic algorithm is honestly super simple:
- The octets being checksummed get paired up into 16-bit integers, and you take the 1's complement sum of those integers.
- To generate a checksum, you clear the checksum field first, compute the 16-bit 1's complement sum over the octets, and then put the 1's complement of that sum into the checksum field.
- To check a checksum, you compute the 1's complement sum over the same set of octets, this time including the checksum field. If the result is all 1 bits (that's -0 in 1's complement arithmetic), the check passes ✨
Let's say you're checksumming a sequence of octets A, B, C, D, ... , Y, Z. Using the notation [a,b] for the 16-bit integer a*256+b (where a and b are bytes), the 16-bit 1's complement sum comes out to one of these two forms, depending on whether you have an even or odd number of bytes:
[A,B] +' [C,D] +' ... +' [Y,Z] [1]
[A,B] +' [C,D] +' ... +' [Z,0] [2]Here, +' means 1's complement addition 🧁
On a 2's complement machine, you have to do the 1's complement sum with an "end around carry". Basically, any overflow out of the most significant bits gets added back into the least significant bits. There are examples below to make this click 🫶
Section 2 looks at the mathematical properties of this checksum that you can exploit to make it faster. Section 3 has numerical examples of the most important implementation techniques. And Section 4 has specific algorithms for a bunch of common CPU types. Huge thanks to Van Jacobson and Charley Kline for contributing those algorithms 💜
The properties of the Internet checksum were first discussed by Bill Plummer in IEN-45, which is called "Checksum Function Design". IEN-45 isn't really easy to find anymore, so it's included as an extended appendix to this RFC 📚
2. Calculating the Checksum 🧮
This simple checksum has a bunch of wonderful mathematical properties that you can use to speed up the calculation. Let's go through them 🌈
(A) Commutative and Associative 🔁
As long as the even/odd assignment of bytes is respected, you can do the sum in any order, and you can split it into groups however you like.
For example, the sum [1] could be split up like this:
( [A,B] +' [C,D] +' ... +' [J,0] )
+' ( [0,K] +' ... +' [Y,Z] ) [3](B) Byte Order Independence 🔄
You can compute the sum of 16-bit integers in either byte order. If you calculate the swapped sum:
[B,A] +' [D,C] +' ... +' [Z,Y] [4]the result is the same as [1], except the bytes are swapped in the sum! The reason this works is that in both orders the carries are the same: from bit 15 to bit 0, and from bit 7 to bit 8. So swapping bytes consistently just rotates the bits within the sum, without messing up their internal ordering 🦋
That means you can calculate the sum in exactly the same way no matter whether the hardware is "big-endian" or "little-endian". For instance, say a "little-endian" machine is summing data stored in memory in network ("big-endian") order. Fetching each 16-bit word swaps the bytes, which gives you the sum [4]. Storing the result back into memory then swaps it back into network byte order 🎀
You can also use byte swapping explicitly to deal with boundary alignment problems. For example, the second group in [3] can be calculated without worrying about whether it starts at an odd or even position, like this:
[K,L] +' ... +' [Z,0]As long as you byte-swap this sum before adding it to the first group. There's an example below too 👀
(C) Parallel Summation 🚀
On machines whose word sizes are multiples of 16 bits, you can build even faster implementations. Since addition is associative, you don't have to sum the integers in the order they appear in the message. You can add them "in parallel" by taking advantage of the bigger word size 💪
To compute the checksum in parallel, just do a 1's complement addition of the message using the machine's native word size. For example, on a 32-bit machine you can add 4 bytes at a time: [A,B,C,D]+'... Once the sum is computed, you "fold" the long sum down into 16 bits by adding up the 16-bit segments. Each of those 16-bit additions can produce new end-around carries, and those have to be added in too 🧠
Byte order doesn't matter here either. You could sum 32-bit words as [D,C,B,A]+'... or [B,A,D,C]+'... and then swap the bytes of the final 16-bit sum if needed. Check out the examples below! Any permutation is fine as long as it collects all the even-numbered data bytes into one sum byte and all the odd-numbered data bytes into the other sum byte 💖
There are a few more coding techniques that can speed up the checksum calculation too 😤
(1) Deferred Carries ⏳
Depending on the machine, it can be more efficient to delay adding end-around carries until the main summation loop is done.
One approach is to sum 16-bit words in a 32-bit accumulator, so the overflows build up in the high-order 16 bits. This usually avoids needing a carry-sensing instruction, but it takes twice as many additions as adding 32-bit segments would. Which one is faster depends on the detailed hardware architecture 🤷♀️
(2) Unwinding Loops 🔂
To cut down on loop overhead, it's often useful to "unwind" the inner sum loop, repeating a series of addition commands within a single loop pass. This can save a lot of time, although it can make the logic of the program a lot messier 😭
(3) Combine with Data Copying 🧃
Copying data from one memory location to another has per-byte overhead, just like checksumming does. In both cases the bottleneck is basically the memory bus, meaning how fast the data can be fetched. On some machines (especially slower, simpler microcomputers), you can cut overhead a lot by combining the memory-to-memory copy with the checksumming, so the data only gets fetched once for both jobs 🍓
(4) Incremental Update 🌟
Finally, you can sometimes avoid recomputing the whole checksum when just one header field changes. The best-known example is a gateway changing the TTL field in the IP header, but there are others too (for example, when updating a source route). In these cases, you can update the checksum without scanning the whole message or datagram ✨
To update the checksum, just add the differences of the sixteen-bit integers that changed. This works because every 16-bit integer has an additive inverse, and addition is associative. So if you have the original value m, the new value m', and the old checksum C, the new checksum C' is:
C' = C + (-m) + m' = C + (m' - m)3. Numerical Examples ✨
okay bestie, now for the fun part 🧮 we're doing worked examples of a simple 1's complement sum on a 2's complement machine 💅 Same sum, computed a few ways: one byte at a time, then 16-bit words in normal and swapped order, then 32 bits at a time in three different orders. Everything is in hex 🎀
Byte-by-byte "Normal" Swapped
Order Order
Byte 0/1: 00 01 0001 0100
Byte 2/3: f2 03 f203 03f2
Byte 4/5: f4 f5 f4f5 f5f4
Byte 6/7: f6 f7 f6f7 f7f6
--- --- ----- -----
Sum1: 2dc 1f0 2ddf0 1f2dc
dc f0 ddf0 f2dc
Carrys: 1 2 2 1
-- -- ---- ----
Sum2: dd f2 ddf2 f2dd
Final Swap: dd f2 ddf2 ddf2look at them all landing on ddf2 😭✨ Every column ends in the same answer, just reached by different routes. That's the whole vibe of 1's complement: the order you add in doesn't change the result 🌈
Next up, the 32-bit version, where the same bytes get grouped into longer chunks 🦋
Byte 0/1/2/3: 0001f203 010003f2 03f20100
Byte 4/5/6/7: f4f5f6f7 f5f4f7f6 f7f6f5f4
-------- -------- --------
Sum1: 0f4f7e8fa 0f6f4fbe8 0fbe8f6f4
Carries: 0 0 0
Top half: f4f7 f6f4 fbe8
Bottom half: e8fa fbe8 f6f4
----- ----- -----
Sum2: 1ddf1 1f2dc 1f2dc
ddf1 f2dc f2dc
Carrys: 1 1 1
---- ---- ----
Sum3: ddf2 f2dd f2dd
Final Swap: ddf2 ddf2 ddf2Last one, and it's a bit of a twist 👑 we split the sum into two groups, and the second group starts on an odd boundary, so there's a byte swap to deal with 🙈
Byte-by-byte Normal
Order
Byte 0/1: 00 01 0001
Byte 2/ : f2 (00) f200
--- --- -----
Sum1: f2 01 f201
Byte 4/5: 03 f4 03f4
Byte 6/7: f5 f6 f5f6
Byte 8/: f7 (00) f700
--- --- -----
Sum2: 1f0ea
Sum2: f0ea
Carry: 1
-----
Sum3: f0eb
Sum1: f201
Sum3 byte swapped: ebf0
-----
Sum4: 1ddf1
Sum4: ddf1
Carry: 1
-----
Sum5: ddf24. Implementation Examples 💻
okay so this section is where the algorithms get real 🔥 We're looking at Internet checksum implementations that people found to be efficient on a bunch of different CPUs 🌸 Each one shows just the core of the algorithm. We skip the environment code (like subroutine linkages) and the special-case stuff, so you're seeing the heart of it and nothing else 🫶
4.1 "C"
this one is in C 🎀 The inner loop adds up 16 bits at a time into a 32-bit accumulator, and the rest is just cleanup and folding 💖
in 6
{
/* Compute Internet Checksum for "count" bytes
* beginning at location "addr".
*/
register long sum = 0;
while( count > 1 ) {
/* This is the inner loop */
sum += * (unsigned short) addr++;
count -= 2;
}
/* Add left-over byte, if any */
if( count > 0 )
sum += * (unsigned char *) addr;
/* Fold 32-bit sum to 16 bits */
while (sum>>16)
sum = (sum & 0xffff) + (sum >> 16);
checksum = ~sum;
}4.2 Motorola 68020
now we're in assembler for a Motorola 68020 chip 👾 This one sums 32 bits at a time and unrolls the loop with 16 replications, so it's a whole lot of copy-paste energy 💅 For clarity, the logic for adding the last fullword when the length isn't a multiple of 4 has been left out. The result ends up in register d0.
the speed stat is iconic 😭 On a 20MHz clock, this routine was measured at 134 usec/kB summing random data. The algorithm was developed by Van Jacobson 🌟
movl d1,d2
lsrl #6,d1 | count/64 = # loop traversals
andl #0x3c,d2 | Then find fractions of a chunk
negl d2
andb #0xf,cc | Clear X (extended carry flag)
jmp pc@(2$-.-2:b,d2) | Jump into loop
1$: | Begin inner loop...
movl a0@+,d2 | Fetch 32-bit word
addxl d2,d0 | Add word + previous carry
movl a0@+,d2 | Fetch 32-bit word
addxl d2,d0 | Add word + previous carry
| ... 14 more replications
2$:
dbra d1,1$ | (NB- dbra doesn't affect X)
movl d0,d1 | Fold 32 bit sum to 16 bits
swap d1 | (NB- swap doesn't affect X)
addxw d1,d0
jcc 3$
addw #1,d0
3$:
andl #0xffff,d04.3 Cray
this one is a Cray CPU, and it's giving vector operations 🚀 It was contributed by Charley Kline, and it chews through up to 512 bytes at a time with a basic 32-bit summing unit 🦋 It skips a lot of the short-block stuff for clarity.
Here's the vibe: the 512-byte block gets loaded into two vector registers. One gets shifted right 32 bits, the other gets ANDed with a 32-bit mask, and then the two get added together. Everything chains, so you get one result per clock cycle 🔥 After that, the result vector collapses in a loop that adds each element into a scalar register. Finally there's an end-around carry and the result gets folded down to 16 bits ✨
EBM
A0 A1
VL 64 use full vectors
S1 <32 form 32-bit mask from the right.
A2 32
V1 ,A0,1 load packet into V1
V2 S1&V1 Form right-hand 32-bits in V2.
V3 V1>A2 Form left-hand 32-bits in V3.
V1 V2+V3 Add the two together.
A2 63 Prepare to collapse into a scalar.
S1 0
S4 <16 Form 16-bit mask from the right.
A4 16
CK$LOOP S2 V1,A2
A2 A2-1
A0 A2
S1 S1+S2
JAN CK$LOOP
S2 S1&S4 Form right-hand 16-bits in S2
S1 S1>A4 Form left-hand 16-bits in S1
S1 S1+S2
S2 S1&S4 Form right-hand 16-bits in S2
S1 S1>A4 Form left-hand 16-bits in S1
S1 S1+S2
S1 #S1 Take one's complement
CMR At this point, S1 contains the checksum.4.4 IBM 370
last up, an IBM 370 in assembler 🧚 This one sums 4 bytes at a time. For clarity, the logic for the last fullword (when the length isn't a multiple of 4) is left out, and so is the byte reversal for when it's needed. The result is left in register RCARRY 💜
the timing tea is spicy 🍓 This code was timed on an IBM 3090 CPU at 27 usec/KB when summing all one bits. It drops to 24.3 usec/KB if you go to the trouble of word-aligning the addends. That means special cases at both the beginning and the end, plus byte-swapping when needed to make up for starting on an odd byte 🙈
* Registers RADDR and RCOUNT contain the address and length of
* the block to be checksummed.
*
* (RCARRY, RSUM) must be an even/odd register pair.
* (RCOUNT, RMOD) must be an even/odd register pair.
*
CHECKSUM SR RSUM,RSUM Clear working registers.
SR RCARRY,RCARRY
LA RONE,1 Set up constant 1.
*
SRDA RCOUNT,6 Count/64 to RCOUNT.
AR RCOUNT,RONE +1 = # times in loop.
SRL RMOD,26 Size of partial chunk to RMOD.
AR RADDR,R3 Adjust addr to compensate for
S RADDR,=F(64) jumping into the loop.
SRL RMOD,1 (RMOD/4)*2 is halfword index.
LH RMOD,DOPEVEC9(RMOD) Use magic dope-vector for offset,
B LOOP(RMOD) and jump into the loop...
*
* Inner loop:
*
LOOP AL RSUM,0(,RADDR) Add Logical fullword
BC 12,*+6 Branch if no carry
AR RCARRY,RONE Add 1 end-around
AL RSUM,4(,RADDR) Add Logical fullword
BC 12,*+6 Branch if no carry
AR RCARRY,RONE Add 1 end-around
*
* ... 14 more replications ...
*
A RADDR,=F'64' Increment address ptr
BCT RCOUNT,LOOP Branch on Count
*
* Add Carries into sum, and fold to 16 bits
*
ALR RCARRY,RSUM Add SUM and CARRY words
BC 12,*+6 and take care of carry
AR RCARRY,RONE
SRDL RCARRY,16 Fold 32-bit sum into
SRL RSUM,16 16-bits
ALR RCARRY,RSUM
C RCARRY,=X'0000FFFF' and take care of any
BNH DONE last carry
S RCARRY,=X'0000FFFF'
DONE X RCARRY,=X'0000FFFF' 1's complement IEN 45
Section 2.4.4.5 TCP Checksum Function Design
William W. Plummer
Bolt Beranek and Newman, Inc.
50 Moulton Street
Cambridge MA 02138
5 June 1978IEN 45: TCP Checksum Function Design 📜
okay so this is the original Internet Experiment Note 45, and it's a whole vibe 🌈 Written by William W. Plummer at Bolt Beranek and Newman, Inc., in Cambridge MA, dated 5 June 1978. Here's the running header that goes with it:
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer1. Introduction
so checksums get stuck onto packets so that errors picked up during transmission can be detected 🦋 This matters a ton for Internet protocols like TCP [1,9], because packets might have to cross wireless networks like the Packet Radio Network [2] and the Atlantic Satellite Network [3], where packets can get corrupted 😭 Protocols that do real-time speech can handle a certain level of transmission errors, so forward error correction, or maybe no checksum at all, could work better for them 🎀 This paper focuses on checksum functions for protocols like TCP, where reliable delivery comes from retransmission 💖
here's the plot twist 🙈 Even when the checksum looks good on a message that's been received, there can still be an undetected error. The chance of that is bounded by 2**(-C), where C is the number of checksum bits. Errors can come from hardware (and software) malfunctions as well as from transmission. Hardware-induced errors tend to show up in certain well-known ways, so it's worth designing the checksum function with that in mind. The ideal is that no error of the "common hardware failure" type gets through undetected 🫶
An example of a failure that the current checksum function handles successfully is picking up a bit in the network interface (or I/O bus, memory channel, etc.). ✨ That will always make the checksum bad, which is iconic of it honestly. 💅
For an example of how the current function is inadequate, imagine a control signal stops working in the network interface, and the interface stores zeros in place of the real data. 💀 Those "all zero" messages look like they have valid checksums, which is so not it. 🙈 Noise on the "There's Your Bit" line of the ARPANET Interface [4] might also go totally undetected, because the extra bits that come in can shift the checksum in the same way they shifted the data. 😭
Undetected errors will sometimes get passed up to higher levels of protocol, but they probably won't make sense up there. 🌸 With TCP, most of those messages get ignored, but a few could cause a connection to be aborted. Garbled data could also be a problem for a protocol layer above TCP, which might have its own checksum scheme. 🦋
This paper is the first step toward designing a new checksum function for TCP and some other Internet protocols. 🎀 It identifies several useful properties of the current function, and if possible, these should be retained in any new function. ✨ A bunch of plausible checksum schemes were investigated, and of those, only the "product code" seems simple enough to consider. 👑
2. The Current TCP Checksum Function 🌈
The current function is oriented toward sixteen-bit machines like the PDP-11, but it can be computed pretty easily on other machines (like the PDP-10). 💖 A packet is thought of as a string of 16-bit bytes, and the checksum function is the one's complement sum (add with end-around carry) of those bytes. The one's complement of that sum is what gets stored in the checksum field of the TCP header. 🧚 Before computing the checksum value, the sender puts a zero in the checksum field of the packet. If the receiver computes a checksum value of zero, the packet is assumed to be valid. This works because the "negative" number in the checksum field exactly cancels out the contribution of the rest of the packet. 🔥
Ignoring how hard it actually is to evaluate the checksum function for a given packet, the way of using the checksum described above is pretty simple. 💅 It does assume some properties of the checksum operator (one's complement addition, written + below):
- (P1)
+is commutative. So the order in which the 16-bit bytes get "added" together doesn't matter. 🫶 - (P2)
+has at least one identity element. (The current function has two:+0and-0.) This lets the sender compute the checksum function by putting a zero in the packet's checksum field before computing the value. 🍓 - (P3)
+has an inverse. So the receiver can evaluate the checksum function and expect a zero. ✨ - (P4)
+is associative, which means the checksum field can be anywhere in the packet, and the 16-bit bytes can be scanned sequentially. 🦋
Mathematically, these properties of the binary operation "+" over the set of 16-bit numbers form an Abelian group [5]. 🤓 Of course, there are many Abelian groups, and not all of them would be satisfactory as checksum operators. (Another operator that's readily available in the PDP-11 instruction set and has all of these properties is exclusive-OR, but XOR is unsatisfactory for other reasons. 🙈)
Although it's imprecise, there's another property that any future checksum scheme must preserve:
- (P5)
+is fast to compute on a variety of machines with limited storage requirements. ⚡
The current function is really good in this respect. 👑 On the PDP-11, the inner loop looks like this:
LOOP: ADD (R1)+,R0 ; Add the next 16-bit byte
ADC R0 ; Make carry be end-around
SOB R2,LOOP ; Loop over entire packet.
( 4 memory cycles per 16-bit byte )On the PDP-10, properties P1-4 get exploited even further, and two 16-bit bytes get processed per loop:
LOOP: ILDB THIS,PTR ; Get 2 16-bit bytes
ADD SUM,THIS ; Add into current sum
JUMPGE SUM,CHKSU2 ; Jump if fewer than 8 carries
LDB THIS,[POINT 20,SUM,19] ; Get left 16 and carries
ANDI SUM,177777 ; Save just low 16 here
ADD SUM,THIS ; Fold in carries
CHKSU2: SOJG COUNT,LOOP ; Loop over entire packet
( 3.1 memory cycles per 16-bit byte )The "extra" instructions in the loops above are needed to turn the two's complement ADD instruction(s) into a one's complement add by making the carries end-around. 🔄 One's complement arithmetic is better than two's complement because it's equally sensitive to errors in all bit positions. 💜 If two's complement addition were used, an even number of 1's could be dropped (or picked up) in the most significant bit channel without changing the checksum value. That's exactly why some sort of addition beats a simple exclusive-OR, which is used a lot but allows an even number of drops (or pick ups) in any bit channel. 😭 The RIM10B paper tape format used on PDP-10s [10] uses two's complement add, because space for the loader program is extremely limited. 🥺
Another property of the current checksum scheme is:
- (P6) Adding the checksum to a packet does not change the information bytes. Peterson [6] calls this a "systematic" code. 🎀
This property lets intermediate computers, like gateway machines, act on fields (for example, the Internet Destination Address) without having to decode the whole packet first. 🧠 Cyclical Redundancy Checks used for error correction aren't systematic either. However, most applications of CRCs focus more on error detection than correction, so they can send the message unchanged with the CRC check bits appended to the end. 💌 The 24-bit CRC used by ARPANET IMPs and Very Distant Host Interfaces [4], and the ANSI standards for 800 and 6250 bits per inch magnetic tapes (described in [11]), use this mode. 📼
Also, the operation of higher level protocols is not (by design) affected by anything a gateway does with possibly invalid packets. 🙌 Gateways are allowed to validate the checksum on incoming packets, but in general they won't know how to do this if the checksum is a protocol-specific feature. 🤷♀️
A final property of the current checksum scheme, which is actually a consequence of P1 and P4, is:
- (P7) The checksum may be incrementally modified. 🦋
This lets an intermediate gateway add information to a packet, like a timestamp, and "add" an appropriate change to the packet's checksum field. ⏰ The checksum will still be end-to-end, since it wasn't fully recomputed. 💖
3. Product Codes 💅
Certain "product codes" are potentially useful for checksuming purposes. ✨ Here's a brief description of product codes in the context of TCP. A more general treatment can be found in Avizienis [7] and probably other, more recent works. 📚
The basic concept of this coding is that the message (packet) to be sent is formed by transforming the original source message and adding some "check" bits. 🎀 By reading this and applying a (possibly different) transformation, a receiver can reconstruct the original message and determine whether it has been corrupted during transmission. 🔍
Mo Ms Mr
----- ----- -----
| A | code | 7 | decode | A |
| B | ==> | 1 | ==> | B |
| C | | 4 | | C |
----- |...| -----
| 2 | check plus "valid" flag
----- info
Original Sent ReconstructedWith product codes, the transformation is Ms = K * Mo. 🧁 That is, the message sent is simply the product of the original message Mo and some well-known constant K. To decode, the received Ms is divided by K, which yields Mr as the quotient and 0 as the remainder if Mr is to be considered the same as Mo. 🌟
The first problem is picking a "good" value for K, the "check factor". 🧐 K must be relatively prime to the base chosen to express the message. 💫 (Example: binary messages with K incorrectly chosen to be 8. This means that Ms looks exactly like Mo except that three zeros have been appended. The only way the message could look bad to a receiver dividing by 8 is if the error occurred in one of those three bits. 😬)
For TCP, the base R is chosen to be 2**16. That is, every 16-bit byte (word on the PDP-11) is considered a digit of a big number, and that number is the message. 🔢 Thus,
Mo = SIGMA [ Bi * (R**i)] , Bi is i-th byte
i=0 to N
Ms = K * MoCorrupting a single digit of Ms will yield Ms' = Ms +or- C*(R**j) for some radix position j. The receiver will compute:
Ms'/K = Mo +or- C(R**j)/KSince R and K are relatively prime, C*(R**j) cannot be any exact multiple of K. Therefore, the division will result in a non-zero remainder, which indicates that Ms' is a corrupted version of Ms. 🚨 As will be seen, a good choice for K is (R**b - 1), for some b, which is the "check length" that controls the degree of detection to be had for burst errors affecting a string of digits (i.e., 16-bit bytes) in the message. 🎯 In fact, b will be chosen to be 1, so K will be 2**16 - 1, which keeps the arithmetic operations simple. ✨ This means that all bursts of 15 or fewer bits will be detected. 🎉 According to [7], this choice for b results in the following expression for the fraction of undetected weight 2 errors:
okay so the cost of the product code is basically this formula 🧮💅
f = 16(k-1)/[32(16k-3) + (6/k)] where k is the message length.For large messages f approaches 3.125 per cent as k goes to infinity 🦋
Multiple precision multiplication and division are normally quite complex operations, especially on small machines, which typically lack even single precision multiply and divide operations. ngl that's the vibe-killer 💀 The exception is exactly the case we're dealing with here: the factor is 2**16 - 1 on machines with a word length of 16 bits. The reason is this identity:
Q*(R**j) = Q, mod (R-1) 0 <= Q < RThat is, any digit Q in the selected radix (0, 1, ... R-1) multiplied by any power of the radix will have a remainder of Q when divided by the radix minus 1. ✨
Example: In decimal R = 10. Pick Q = 6.
6 = 0 * 9 + 6 = 6, mod 9
60 = 6 * 9 + 6 = 6, mod 9
600 = 66 * 9 + 6 = 6, mod 9 etc.More to the point, rem(31415/9) = rem((30000+1000+400+10+5)/9)
= (3 mod 9) + (1 mod 9) + (4 mod 9) + (1 mod 9) + (5 mod 9)
= (3+1+4+1+5) mod 9
= 14 mod 9
= 5So the remainder of a number divided by the radix minus one can be found by simply summing the digits of the number 🔥 Since the radix in the TCP case has been chosen to be 216 and the check factor is 216 - 1, a message can quickly be checked by summing all of the 16-bit words (on a PDP-11), with carries being end-around. If zero is the result, the message can be considered valid. Thus, checking a product coded message is exactly the same complexity as with the current TCP checksum! 👑
- 6 -
Internet Experiment Note 45 · 5 June 1978 TCP Checksum Function Design · William W. Plummer
In order to form Ms, the sender must multiply the multiple precision "number" Mo by 216 - 1. Or, Ms = (216)Mo - Mo. This is performed by shifting Mo one whole word's worth of precision and subtracting Mo. Since carries must propagate between digits, but it is only the current digit which is of interest, one's complement arithmetic is used. 🌸
(2**16)Mo = Mo0 + Mo1 + Mo2 + ... + MoX + 0
- Mo = - ( Mo0 + Mo1 + ......... + MoX)
--------- ----------------------------------
Ms = Ms0 + Ms1 + ... - MoXA loop which implements this function on a PDP-11 might look like:
LOOP: MOV -2(R2),R0 ; Next byte of (2**16)Mo
SBC R0 ; Propagate carries from last SUB
SUB (R2)+,R0 ; Subtract byte of Mo
MOV R0,(R3)+ ; Store in Ms
SOB R1,LOOP ; Loop over entire message
; 8 memory cycles per 16-bit byteNote that the coding procedure is not done in-place since it is not systematic. In general the original copy, Mo, will have to be retained by the sender for retransmission purposes and therefore must remain readable. Thus the MOV R0,(R3)+ is required, which accounts for 2 of the 8 memory cycles per loop. 🫶
The coding procedure will add exactly one 16-bit word to the message since Ms < (2**16)Mo. This additional 16 bits will be at the tail of the message, but may be moved into the defined location in the TCP header immediately before transmission. The receiver will have to undo this to put Ms back into standard format before decoding the message.
The code in the receiver for fully decoding the message may be inferred by observing that any word in Ms contains the difference between two successive words of Mo minus the carries from the previous word, and the low order word contains minus the low word of Mo. So the low order (i.e., rightmost) word of Mr is just the negative of the low order byte of Ms. The next word of Mr is the next word of Ms plus the just computed word of Mr plus the carry from that previous computation. 🧚
A slight refinement of the procedure is required in order to protect against an all-zero message passing to the destination. This will appear to have a valid checksum because Ms'/K = 0/K = 0 with 0 remainder. The refinement is to make the coding be Ms = K*Mo + C, where C is some arbitrary, well-known constant. Adding this constant requires a second pass over the message, but this will typically be very short since it can stop as soon as carries stop propagating. Choosing C = 1 is sufficient in most cases. 🙈
The product code checksum must be evaluated in terms of the desired properties P1 - P7. It has been shown that a factor of two more machine cycles are consumed in computing or verifying a product code checksum (P5 satisfied?).
Although the code is not systematic, the checksum can be verified quickly without decoding the message. If the Internet Destination Address is located at the least significant end of the packet (where the product code computation begins), then it is possible for a gateway to decode only enough of the message to see this field without having to decode the entire message. Thus, P6 is at least partially satisfied. The algebraic properties P1 through P4 are not satisfied, but only a small amount of computation is needed to account for this. The message needs to be reformatted as previously mentioned. 🍓
P7 is satisfied since the product code checksum can be incrementally updated to account for an added word, although the procedure is somewhat involved. Imagine that the original message has two halves, H1 and H2. Thus, Mo = H1*(Rj) + H2. The timestamp word is to be inserted between these halves to form a modified Mo' = H1*(R(j+1)) + T*(R**j) + H2. Since K has been chosen to be R-1, the transmitted message Ms' = Mo'(R-1). Then,
Ms' = Ms*R + T(R-1)(R**j) + P2((R-1)**2)
= Ms*R + T*(R**(j+1)) + T*(R**j) + P2*(R**2) - 2*P2*R - P2Recalling that R is 2**16, the word size on the PDP-11, multiplying by R means copying down one word in memory. So, the first term of Ms' is simply the unmodified message copied down one word. The next term is the new data T added into the Ms' being formed beginning at the (j+1)th word. The addition is fairly easy here since after adding in T all that is left is propagating the carry, and that can stop as soon as no carry is produced. The other terms can be handled similarly. 💜
- 8 -
Internet Experiment Note 45 · 5 June 1978 TCP Checksum Function Design · William W. Plummer
4. More Complicated Codes ✨
There exists a wealth of theory on error detecting and correcting codes. Peterson [6] is an excellent reference. Most of these "CRC" schemes are designed to be implemented using a shift register with a feedback network composed of exclusive-ORs. Simulating such a logic circuit with a program would be too slow to be useful unless some programming trick is discovered.
One such trick has been proposed by Kirstein [8]. Basically, a few bits (four or eight) of the current shift register state are combined with bits from the input stream (from Mo), and the result is used as an index to a table which yields the new shift register state and, if the code is not systematic, bits for the output stream (Ms). A trial coding of an especially "good" CRC function using four-bit bytes showed this technique to be about four times as slow as the current checksum function. This was true for both the PDP-10 and PDP-11 machines. Of the desirable properties listed above, CRC schemes satisfy only P3 (It has an inverse.) and P6 (It is systematic.). Placement of the checksum field in the packet is critical, and the CRC cannot be incrementally modified. 🌈
Although the bulk of coding theory deals with binary codes, most of the theory works if the alphabet contains q symbols, where q is a power of a prime number. For instance, q taken as 2**16 should make a great deal of the theory useful on a word-by-word basis. 🎀
5. Outboard Processing ✨
When a function such as computing an involved checksum requires extensive processing, one solution is to put that processing into an outboard processor. In this way "encode message" and "decode message" become single instructions which do not tax the main host processor. The Digital Equipment Corporation VAX/780 computer is equipped with special hardware for generating and checking CRCs [13]. In general this is not a very good solution, since such a processor must be constructed for every different host machine which uses TCP messages. 😭
It is conceivable that the gateway functions for a large host may be performed entirely in an "Internet Frontend Machine". This machine would be responsible for forwarding packets received either from the network(s) or from the Internet protocol modules in the connected host, and for reassembling Internet fragments into segments and passing these to the host. Another capability of this machine would be to check the checksum so that the segments given to the host are known to be valid at the time they leave the frontend. Since computer cycles are assumed to be both inexpensive and available in the frontend, this seems reasonable. 🧠
- 9 -
Internet Experiment Note 45 · 5 June 1978 TCP Checksum Function Design · William W. Plummer
The problem with attempting to validate checksums in the frontend is that it destroys the end-to-end character of the checksum. If anything, this is the most powerful feature of the TCP checksum! 🔥 There is a way to make the host-to-frontend link be covered by the end-to-end checksum. A separate, small protocol must be developed to cover this link. After having validated an incoming packet from the network, the frontend would pass it to the host saying "here is an Internet segment for you. Call it #123". The host would save this segment, and send a copy back to the frontend saying, "Here is what you gave me as #123. Is it OK?". The frontend would then do a word-by-word comparison with the first transmission, and tell the host either "Here is #123 again", or "You did indeed receive #123 properly. Release it to the appropriate module for further processing." 💖
The headers on the messages crossing the host-frontend link would most likely be covered by a fairly strong checksum 💅 so info like which function is being performed and the message reference numbers stays reliable ✨. These headers would be quite short, maybe only sixteen bits, so the checksum could be quite strong 🔥. The bulk of the message would not be checksumed, of course 🙈.
The reason this scheme takes pressure off the host is that all that is required to validate the message using the end-to-end checksum is to send it back to the frontend machine 🦋. On the PDP-10, this only takes 0.5 memory cycles per 16-bit byte of Internet message, plus a few processor cycles to set up the required transfers 💖.
6. Conclusions 👑
Okay, so there's an ordering of checksum functions 🌈. First and simplest is none at all, which provides no error detection or correction 💀. Second is sending a constant that the receiver checks, and this is also extremely weak 😭. Third, the exclusive-OR of the data may be sent. XOR takes the least computer time to generate and check, but it's not a good checksum 🙈. A two's complement sum of the data is somewhat better and takes no more computer time to compute. Fifth is the one's complement sum, which is what TCP currently uses 💜. It's slightly more expensive in terms of computer time. The next step is a product code 🦋. It's strongly related to the one's complement sum, takes still more computer time to use, and provides a bit more protection against common hardware failures, but it has some objectionable properties. Next is a genuine CRC polynomial code, used for checking purposes only, and it's very expensive for a program to implement 🥴. Finally, a full CRC error correcting and detecting scheme may be used ✨.
For TCP and Internet applications, the product code scheme is viable 🎀. It mainly suffers because messages have to be (at least partially) decoded by intermediate gateways so that they can be forwarded. If product codes aren't chosen as an improved checksum, some slight modification to the existing scheme might be possible 🌸. For instance, the "add and rotate" function that the PDP-6/10 group at the Artificial Intelligence Laboratory at M.I.T. Project MAC used for paper tape [12] could be useful, if it can be proved that it's better than the current scheme and that it can be computed efficiently on a variety of machines 🧚.
References 📚
[1] Cerf, V.G. and Kahn, Robert E., "A Protocol for Packet Network Communications," IEEE Transactions on Communications, vol. COM-22, No. 5, May 1974.
[2] Kahn, Robert E., "The Organization of Computer Resources into a Packet Radio Network", IEEE Transactions on Communications, vol. COM-25, no. 1, pp. 169-178, January 1977.
[3] Jacobs, Irwin, et al., "CPODA - A Demand Assignment Protocol for SatNet", Fifth Data Communications Symposium, September 27-9, 1977, Snowbird, Utah
[4] Bolt Beranek and Newman, Inc. "Specifications for the Interconnection of a Host and an IMP", Report 1822, January 1976 edition.
[5] Dean, Richard A., "Elements of Abstract Algebra", John Wyley and Sons, Inc., 1966
[6] Peterson, W. Wesley, "Error Correcting Codes", M.I.T. Press Cambridge MA, 4th edition, 1968.
[7] Avizienis, Algirdas, "A Study of the Effectiveness of Fault-Detecting Codes for Binary Arithmetic", Jet Propulsion Laboratory Technical Report No. 32-711, September 1, 1965.
[8] Kirstein, Peter, private communication
[9] Cerf, V. G. and Postel, Jonathan B., "Specification of Internetwork Transmission Control Program Version 3", University of Southern California Information Sciences Institute, January 1978.
[10] Digital Equipment Corporation, "PDP-10 Reference Handbook", 1970, pp. 114-5.
[11] Swanson, Robert, "Understanding Cyclic Redundancy Codes", Computer Design, November, 1975, pp. 93-99.
[12] Clements, Robert C., private communication.
[13] Conklin, Peter F., and Rodgers, David P., "Advanced Minicomputer Designed by Team Evaluation of Hardware/Software Tradeoffs", Computer Design, April 1978, pp. 136-7.
📦 where this page comes from
- ietf: rfc1071 1988-09
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms