この文書はRFC1071の日本語訳（和訳）です。 この文書の翻訳内容の正確さは保障できないため、 正確な知識や情報を求める方は原文を参照してください。 翻訳者はこの文書によって読者が被り得る如何なる損害の責任をも負いません。 この翻訳内容に誤りがある場合、訂正版の公開や、 誤りの指摘は適切です。 この文書の配布は元のＲＦＣ同様に無制限です。
Network Working Group R. Braden
Request for Comments: 1071 ISI
D. Borman
Cray Research
C. Partridge
BBN Laboratories
September 1988
Computing the Internet Checksum
インターネットチェックサムの計算
Status of This Memo
この文書の状態
This memo summarizes techniques and algorithms for efficiently
computing the Internet checksum. It is not a standard, but a set of
useful implementation techniques. Distribution of this memo is
unlimited.
このメモは効率的にインターネットチェックサムを計算する技術とアルゴリ
ズムを要約します。これは標準ではなく、有用な実装技術です。このメモの
配布は無制限です。
1. Introduction
1. はじめに
This memo discusses methods for efficiently computing the Internet
checksum that is used by the standard Internet protocols IP, UDP, and
TCP.
このメモは効率的に標準インターネット・プロトコルＩＰとＵＤＰとＴＣＰ
で使われるインターネットチェックサムを計算する方法を論じます。
An efficient checksum implementation is critical to good performance.
As advances in implementation techniques streamline the rest of the
protocol processing, the checksum computation becomes one of the
limiting factors on TCP performance, for example. It is usually
appropriate to carefully hand-craft the checksum routine, exploiting
every machine-dependent trick possible; a fraction of a microsecond
per TCP data byte can add up to a significant CPU time savings
overall.
効率的なチェックサムの実装は良い性能に重大です。実装技術の進歩がプロ
トコル処理の残りを合理化するので、チェックサム計算は、例えば、ＴＣＰ
性能を制限する要素の１つになります。慎重にチェックサムルーチンを作り、
すべてのマシン依存の可能性のある方法を採用するのは、通常適切です；Ｔ
ＣＰデータバイト毎に全体に対する重要なＣＰＵ時間の１マイクロ秒の何分
の１かが追加されます。
In outline, the Internet checksum algorithm is very simple:
インターネットチェックサムアルゴリズムの概要は非常に単純です：
(1) Adjacent octets to be checksummed are paired to form 16-bit
integers, and the 1's complement sum of these 16-bit integers is
formed.
(1) チェックサムを行うオクテットは１６ビット整数になるように対にされ、
これら１６ビット整数の１の補数の合計が生成されます。
(2) To generate a checksum, the checksum field itself is cleared,
the 16-bit 1's complement sum is computed over the octets
concerned, and the 1's complement of this sum is placed in the
checksum field.
(2) チェックサムを生成するために、チェックサムフィールド自身はクリア
され、１６ビットの１の補数の合計は関連したオクテット上で計算され、
そして合計の１の補数がチェックサムフィールドに置かれます。
(3) To check a checksum, the 1's complement sum is computed over the
same set of octets, including the checksum field. If the result
is all 1 bits (-0 in 1's complement arithmetic), the check
succeeds.
(3) チェックサムををチェックするために、１の補数の合計はチェックサム
を含む同じオクテット上で計算されます。もし結果がすべての１のビッ
トであるなら（１の補数の演算で−０）、検査は成功です。
Suppose a checksum is to be computed over the 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, then the 16-bit 1's
complement sum of these bytes is given by one of the following:
オクテットA, B, C, D, ... , Y, Zの列上でチェックサムを計算すると
考えてください。表記[a,b]をaとbをバイトとした場合の１６ビットの
整数a*256+bとして、与えられたバイトの１６ビットの１の補数の合計
は以下の通りです：
[A,B] +' [C,D] +' ... +' [Y,Z] [1]
[A,B] +' [C,D] +' ... +' [Z,0] [2]
where +' indicates 1's complement addition. These cases
correspond to an even or odd count of bytes, respectively.
ここで+'は１の補数の加算です。これらの場合はそれぞれバイト数が偶
数か奇数かに対応します。
On a 2's complement machine, the 1's complement sum must be
computed by means of an "end around carry", i.e., any overflows
from the most significant bits are added into the least
significant bits. See the examples below.
２の補数のマシンで、１の補数の合計は「エンドアラウンドキャリー」
の意味で計算しなければなりません、すなわち、最上位ビットの桁あふ
れは最下位ビットに加算されます。下記の例を見てください。
Section 2 explores the properties of this checksum that may be
exploited to speed its calculation. Section 3 contains some
numerical examples of the most important implementation
techniques. Finally, Section 4 includes examples of specific
algorithms for a variety of common CPU types. We are grateful
to Van Jacobson and Charley Kline for their contribution of
algorithms to this section.
２章がその計算を速めるために利用されるかもしれないこのチェックサ
ムの性質を調べます。３章がある重要な実装技術の数値例を含んでいま
す。最後に４章が、いろいろな一般的ＣＰＵタイプに固有のアルゴリズ
ムの例を含みます。我々はこの章のアルゴリズムの貢献に対しVan
JacobsonとCharley Klineに感謝します。
The properties of the Internet checksum were originally
discussed by Bill Plummer in IEN-45, entitled "Checksum Function
Design". Since IEN-45 has not been widely available, we include
it as an extended appendix to this RFC.
インターネットチェックサムの性質は元々Bill Plummerにより「チェッ
クサム機能デザイン」と題を付けられたＩＥＮ−４５で論じられました。
ＩＥＮ−４５が広く利用可能ではなかったので、我々はこのＲＦＣの拡
張付録としてこれを含みます。
2. Calculating the Checksum
2. チェックサム計算
This simple checksum has a number of wonderful mathematical
properties that may be exploited to speed its calculation, as we
will now discuss.
この単純なチェックサムは、我々が今論じるように、計算を速めるため
に利用されるかもしれない多くの素晴らしい数学的な特性を持っていま
す。
(A) Commutative and Associative
(A) 可換で結合
As long as the even/odd assignment of bytes is respected, the
sum can be done in any order, and it can be arbitrarily split
into groups.
バイトの奇数／奇数の割当てが間違わない限り、合計はどんな順序でも
可能で、任意にグループに分けることができます。
For example, the sum [1] could be split into:
例えば、[1]の合計は以下に分けられます：
( [A,B] +' [C,D] +' ... +' [J,0] )
+' ( [0,K] +' ... +' [Y,Z] ) [3]
(B) Byte Order Independence
(B) バイト順独立
The sum of 16-bit integers can be computed in either byte order.
Thus, if we 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! To see why this is so, observe that in both orders the
carries are the same: from bit 15 to bit 0 and from bit 7 to bit
8. In other words, consistently swapping bytes simply rotates
the bits within the sum, but does not affect their internal
ordering.
結果は合計でバイトが交換される以外[1]と同じです！なぜこうなるか
を見るために、両方の順でキャリーが同じ事を観察してください：ビッ
ト１５からビット０までそしてビット７からビット８まで。言い換えれ
ば、全てのバイトを交換することは単純に合計のビットを回転させます
が、内部の順序に影響を与えません。
Therefore, the sum may be calculated in exactly the same way
regardless of the byte order ("big-endian" or "little-endian")
of the underlaying hardware. For example, assume a "little-
endian" machine summing data that is stored in memory in network
("big-endian") order. Fetching each 16-bit word will swap
bytes, resulting in the sum [4]; however, storing the result
back into memory will swap the sum back into network byte order.
それ故に、合計はハードウェアのバイト順（「ビッグエンディアン」あ
るいは「リトルエンディアン」）に関係なく同じ方法で計算できるかも
しれません。例えば、メモリにネットワーク順（「ビッグエンディアン」）
で記憶するデータを合計する「リトルエンディアン」マシンを想定して
ください。それぞれの１６ビットのワードを読み取るとバイトが入れ替
わり合計[4]を生成します；しかしながら、メモリの中に結果を置くと順
序が入れ替わりネットワーク順に戻るでしょう。
Byte swapping may also be used explicitly to handle boundary
alignment problems. For example, the second group in [3] can be
calculated without concern to its odd/even origin, as:
バイト交換が境界整列問題を処理するために明示的に使われるかもしれ
ません。例えば[3]の第２グループが偶数／奇数の始まりを気にしない
で計算できます：
[K,L] +' ... +' [Z,0]
if this sum is byte-swapped before it is added to the first
group. See the example below.
もしこの合計が前にバイト交換をされてるなら、最初のグループに加算
されます。下記の例を見てください。
(C) Parallel Summation
(C) 平行合計
On machines that have word-sizes that are multiples of 16 bits,
it is possible to develop even more efficient implementations.
Because addition is associative, we do not have to sum the
integers in the order they appear in the message. Instead we
can add them in "parallel" by exploiting the larger word size.
１６ビット倍数のワードサイズを持つ機械で、更に効率的な実装を作る
ことは可能です。加算が結合性があるので、我々はメッセージに見える
順序で整数を合計しなくてもよいです。その代わりに大きいワードサイ
ズを採用することで「平行」に加算ができます。
To compute the checksum in parallel, simply do a 1's complement
addition of the message using the native word size of the
machine. For example, on a 32-bit machine we can add 4 bytes at
a time: [A,B,C,D]+'... When the sum has been computed, we "fold"
the long sum into 16 bits by adding the 16-bit segments. Each
16-bit addition may produce new end-around carries that must be
added.
チェックサムを平行に計算するために、単純にマシンのネイティブのワー
ドサイズでメッセージの１の補数の加算をします。例えば、３２ビット
マシン上で我々は一度に４バイトを加算できます：[A,B,C,D]+'...。合
計が計算された時、我々は１６ビット毎に加算し１６ビットにすること
で長い合計を「折ります」。それぞれの１６ビットは加算が必要な新し
いエンドアラウンドキャリーを起こすかもしれません。
Furthermore, again the byte order does not matter; we could
instead sum 32-bit words: [D,C,B,A]+'... or [B,A,D,C]+'... and
then swap the bytes of the final 16-bit sum as necessary. See
the examples below. Any permutation is allowed that collects
all the even-numbered data bytes into one sum byte and the odd-
numbered data bytes into the other sum byte.
さらにバイト順は問題ではありません；その代わりに３２ビットワード
を合計することができます：[D,C,B,A]+'... または [B,A,D,C]+'...と
最後の１６ビット合計の交換が必要なだけです。下記の例を見てくださ
い。奇数バイトを１つの合計バイトに集め、偶数バイトを他の合計バイ
トに集めるすべての配列が許されます。
There are further coding techniques that can be exploited to speed up
the checksum calculation.
チェックサム計算を速めるために利用できる他のコーディング技術があります。
(1) Deferred Carries
(1) 延期キャリー
Depending upon the machine, it may be more efficient to defer
adding end-around carries until the main summation loop is
finished.
機械依存ですが、合計ループが終了するまで、エンドアラウンドキャリー
の加算を延期することはより効率的かもしれません。
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 approach
typically avoids a carry-sensing instruction but requires twice
as many additions as would adding 32-bit segments; which is
faster depends upon the detailed hardware architecture.
１つの方法は３２ビット加算器で１６ビットワードを合計することで、
あふれは上位１６ビットに蓄積されます。この方法は一般にキャリー検
出処理を避けますが、３２ビットセグメントの加算に２倍の数の加算演
算を要求します；どちらがより速いかは詳細なハードウェアアーキテク
チャに依存します。
(2) Unwinding Loops
(2) ループをほどく
To reduce the loop overhead, it is often useful to "unwind" the
inner sum loop, replicating a series of addition commands within
one loop traversal. This technique often provides significant
savings, although it may complicate the logic of the program
considerably.
ループの冗長性を減らすために、内部の加算ループをほどいて一連の加
算コマンドを繰り返す事はしばしば有用です。この技術はかなりプログ
ラムロジックを複雑にするかもしれないが、しばしば重要な利益を供給
します。
(3) Combine with Data Copying
(3) データコピーの結合
Like checksumming, copying data from one memory location to
another involves per-byte overhead. In both cases, the
bottleneck is essentially the memory bus, i.e., how fast the
data can be fetched. On some machines (especially relatively
slow and simple micro-computers), overhead can be significantly
reduced by combining memory-to-memory copy and the checksumming,
fetching the data only once for both.
合計検査のように、１つのメモリから他にデータをコピーすることはバ
イト毎のオーバーヘッドを生じます。両方の場合に、ボトルネックは本
質的にメモリバスです、すなわち、速くデータを読む方法です。あるマ
シン（特に比較的遅くて単純なマイクロ・コンピュータ）で、メモリ間
コピーと合計検査を組み合わせて、両方のデータを読むのを一度に行う
とオーバーヘッドを減らすことができます。
(4) Incremental Update
(4) 逐次更新
Finally, one can sometimes avoid recomputing the entire checksum
when one header field is updated. The best-known example is a
gateway changing the TTL field in the IP header, but there are
other examples (for example, when updating a source route). In
these cases it is possible to update the checksum without
scanning the message or datagram.
最後に、１つのヘッダフィールドを更新する時に、全部のチェックサム
を再計算するのを避けることができます。最もよく知られた例はＩＰヘッ
ダでＴＴＬフィールドを変えるゲートウェイですが、他の例もあります
（例えば、ソースルート更新時）。これらの場合メッセージあるいはデー
タグラムを走査しないでチェックサムを更新することは可能です。
To update the checksum, simply add the differences of the
sixteen bit integers that have been changed. To see why this
works, observe that every 16-bit integer has an additive inverse
and that addition is associative. From this it follows that
given the original value m, the new value m', and the old
checksum C, the new checksum C' is:
チェックサムを更新するために、１６のビット整数の差分だけを加算し
ます。なぜこれでいいかを知るには、すべての１６ビット整数が加算の
逆元を持ち、そして加算が結合性を持つ事からわかります。これから元
の値mと新しい値m'と古いチェックサムCという条件で、新しいチェック
サムC'が以下の通りです：
C' = C + (-m) + m' = C + (m' - m)
3. Numerical Examples
3. 数値例
We now present explicit examples of calculating a simple 1's
complement sum on a 2's complement machine. The examples show the
same sum calculated byte by bye, by 16-bits words in normal and
swapped order, and 32 bits at a time in 3 different orders. All
numbers are 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 ddf2
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 ddf2
Finally, here an example of breaking the sum into two groups, with
the second group starting on a odd boundary:
最後に、この例で合計を２つのグループに分けて、２番目のグループが奇数
境界で始めます：
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: ddf2
4. Implementation Examples
4. 実装例
In this section we show examples of Internet checksum implementation
algorithms that have been found to be efficient on a variety of
CPU's. In each case, we show the core of the algorithm, without
including environmental code (e.g., subroutine linkages) or special-
case code.
この章で我々はいろいろなＣＰＵのの上に効率的であるインターネットチェッ
クサム実装アルゴリズムの例を示します。それぞれの事例で、環境のコード
（例えば、サブルーチンリンク）や特別な事例のコードは含まず、アルゴリ
ズムの核心を見せます。
4.1 "C"
4.1 「Ｃ」
The following "C" code algorithm computes the checksum with an inner
loop that sums 16-bits at a time in a 32-bit accumulator.
次の「Ｃ」コードアルゴリズムは内部ループで３２ビットの加算器で一度に
１６ビットを合計計算します。
in 6
{
/* Compute Internet Checksum for "count" bytes
* beginning at location "addr".
* "addr"から開始する"count"バイトのインターネット
* チェックサムを計算
*/
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
4.2 モトローラ６８０２０
The following algorithm is given in assembler language for a Motorola
68020 chip. This algorithm performs the sum 32 bits at a time, and
unrolls the loop with 16 replications. For clarity, we have omitted
the logic to add the last fullword when the length is not a multiple
of 4. The result is left in register d0.
次のアルゴリズムはモトローラ６８０２０チップのためのアセンブラ言語で
与えられます。このアルゴリズムは３２ビットを一度に合計し、ループを
１６の反復に開きます。明快さのために、我々は、長さが４の倍数ではない
時に、最後の全ワードを加算する論理を除きました。結果はレジスタd0に残
されます。
With a 20MHz clock, this routine was measured at 134 usec/kB summing
random data. This algorithm was developed by Van Jacobson.
２０ＭＨｚクロックで、このルーティンはランダムデータの合計が
１３４ｕｓｅｃ／ｋＢと測られました。このアルゴリズムは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,d0
4.3 Cray
4.3 クレイ
The following example, in assembler language for a Cray CPU, was
contributed by Charley Kline. It implements the checksum calculation
as a vector operation, summing up to 512 bytes at a time with a basic
summation unit of 32 bits. This example omits many details having to
do with short blocks, for clarity.
次の例は、アセンブラ言語でクレイＣＰＵのために、Charley Klineによって
提供されました。これは、３２ビットの基本的加算単位で一度に５１２バイ
トの加算をするベクトル演算として、チェックサム計算をします。この例は
明快さのために、一部の詳細を除きます。
Register A1 holds the address of a 512-byte block of memory to
checksum. First two copies of the data are loaded into two vector
registers. One is vector-shifted right 32 bits, while the other is
vector-ANDed with a 32 bit mask. Then the two vectors are added
together. Since all these operations chain, it produces one result
per clock cycle. Then it collapses the result vector in a loop that
adds each element to a scalar register. Finally, the end-around
carry is performed and the result is folded to 16-bits.
レジスタA1がチェックサムをする５１２バイトメモリブロックのアドレスを
持ちます。データの最初の２つのコピーが２つのベクトルレジスタにロード
されます。１つはベクトル変換された右の３２ビットで、他はベクトルＡＮ
Ｄされた３２ビットマスクです。２つのベクトルは共に加えられます。オペ
レーションが連結されるので、クロックサイクル毎に１つの結果を作り出し
ます。それでスカラレジスタにそれぞれの要素を加えるループを結果方向に
たたみます。最終的に、エンドアラウンドキャリーが行われ、そして結果は
１６ビットにたたまれます。
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
4.4 ＩＢＭ３７０
The following example, in assembler language for an IBM 370 CPU, sums
the data 4 bytes at a time. For clarity, we have omitted the logic
to add the last fullword when the length is not a multiple of 4, and
to reverse the bytes when necessary. The result is left in register
RCARRY.
次の例は、アセンブラ言語でＩＢＭ３７０のＣＰＵのために、一度に４バイ
トデータを合計します。明快さのために、長さが４の倍数ではない時、最後
に全ワードを加えて、必要な時、バイトを反転するロジックを除きました。
結果はレジスタRCARRYに残されます。
This code has been timed on an IBM 3090 CPU at 27 usec/KB when
summing all one bits. This time is reduced to 24.3 usec/KB if the
trouble is taken to word-align the addends (requiring special cases
at both the beginning and the end, and byte-swapping when necessary
to compensate 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 1978
Internet Experiment Note 45 5 June 1978
TCP Checksum Function Design William W. Plummer
1. Introduction
1. はじめに
Checksums are included in packets in order that errors
encountered during transmission may be detected. For Internet
protocols such as TCP [1,9] this is especially important because
packets may have to cross wireless networks such as the Packet
Radio Network [2] and Atlantic Satellite Network [3] where
packets may be corrupted. Internet protocols (e.g., those for
real time speech transmission) can tolerate a certain level of
transmission errors and forward error correction techniques or
possibly no checksum at all might be better. The focus in this
paper is on checksum functions for protocols such as TCP where
the required reliable delivery is achieved by retransmission.
チェックサムは送信時に発生したエラーを検出するためにパケットに含め
られます。ＴＣＰ[1,9]のようなインターネット・プロトコルで、パケッ
トがパケットラジオネットワーク[2]や大西洋人工衛星ネットワーク [3]
のような誤りの多い無線ネットワークを通過するかもしれないので、これ
は特に重要です。インターネット・プロトコル（例えば、リアルタイムス
ピーチ送信で）はあるレベルのエラーと前方エラー訂正によりエラーに寛
大か、あるいはチェックサムが良くないかもしれません。この文書の焦点
は、信頼性が高い配達が再送によって成し遂げられるＴＣＰのようなプロ
トコルのためのチェックサム機能にあります。
Even if the checksum appears good on a message which has been
received, the message may still contain an undetected error. The
probability of this is bounded by 2**(-C) where C is the number
of checksum bits. Errors can arise from hardware (and software)
malfunctions as well as transmission errors. Hardware induced
errors are usually manifested in certain well known ways and it
is desirable to account for this in the design of the checksum
function. Ideally no error of the "common hardware failure" type
would go undetected.
たとえチェックサムが受信メッセージ上で正しく見えるとしても、メッセー
ジはまだ見つけられていないエラーを含んでいるかもしれません。これの
可能性はCをチェックサムビット数とすると2**(-C)になります。エラーは
ハードウェア（とソフトウェア）故障でも、転送誤りでも生ずることがで
きます。ハードウェアによって誘発されたエラーが通常ある特定の既知の
方法で検出されます、そしてチェックサム機能の設計でこれを説明するこ
とは望ましいです。理想的には検出されない「一般ハードウェア障害」タ
イプのエラーがないことでしょう。
An example of a failure that the current checksum function
handles successfully is picking up a bit in the network interface
(or I/O buss, memory channel, etc.). This will always render the
checksum bad. For an example of how the current function is
inadequate, assume that a control signal stops functioning in the
network interface and the interface stores zeros in place of the
real data. These "all zero" messages appear to have valid
checksums. Noise on the "There's Your Bit" line of the ARPANET
Interface [4] may go undetected because the extra bits input may
cause the checksum to be perturbed (i.e., shifted) in the same
way as the data was.
現在のチェックサム機能が処理に成功する故障の例は、ネットワークイン
タフェース（あるいはＩ／Ｏバス、メモリチャネルなど）で１ビットです。
これは常にチェックサムを正しくなくします。現在の機能が不適当である
例は、制御信号がネットワークインタフェースで動作をやめ、そしてイン
タフェースが真のデータの代わりにゼロを保管すると想定してください。
これらの「すべてのゼロ」メッセージは正当なチェックサムを持つように
思われます。ＡＲＰＡＮＥＴインタフェース[4]の「あなたのビットがあ
る」線上のノイズは、入力された余分のビットがデータと同じくチェック
サム自体も混乱させる（つまりビットずれをする）かもしれないから、見
つけられないかもしれません。
Although messages containing undetected errors will occasionally
be passed to higher levels of protocol, it is likely that they
will not make sense at that level. In the case of TCP most such
messages will be ignored, but some could cause a connection to be
aborted. Garbled data could be viewed as a problem for a layer
of protocol above TCP which itself may have a checksuming scheme.
見つけられないエラーを含んでいるメッセージが時折より上位レベルプロ
トコルに渡されるであろうけれども、そのレベルで意味をなさないであろ
うことはありそうです。ＴＣＰの場合、ほとんどのこのようなメッセージ
が無視され、いくらかが接続を中止させるでしょう。自身でチェックサム
計画を持っているかもしれないＴＣＰ上のプロトコルレイヤで、要領を得
ないデータが問題と見なすことができます。
This paper is the first step in design of a new checksum function
for TCP and some other Internet protocols. Several useful
properties of the current function are identified. If possible
these should be retained in any new function. A number of
plausible checksum schemes are investigated. Of these only the
"product code" seems to be simple enough for consideration.
この文書はＴＣＰや他のインターネット・プロトコルのための新しいチェッ
クサム機能の設計の第一歩です。現在の機能のいくつかの有用な特性が認
識されています。もし可能であるなら、これらは新しい機能ででも維持さ
れるべきです。多くの正しそうなチェックサム案が調査されます。これら
で「掛算コード」だけが考慮に十分なほど単純であるように思われます。
2. The Current TCP Checksum Function
2. 現在のＴＣＰチェックサム機能
The current function is oriented towards sixteen-bit machines
such as the PDP-11 but can be computed easily on other machines
(e.g., 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. It is the one's
complement of this sum which is stored in the checksum field of
the TCP header. Before computing the checksum value, the sender
places a zero in the checksum field of the packet. If the
checksum value computed by a receiver of the packet is zero, the
packet is assumed to be valid. This is a consequence of the
"negative" number in the checksum field exactly cancelling the
contribution of the rest of the packet.
現在の機能はＰＤＰ−１１のような１６ビットのマシンに向きですが、他
の機械上で容易に計算できます（例えばＰＤＰ−１０）。パケットが１６
ビットバイトの列と考えられ、そしてチェックサム機能はこれらのバイト
の１の補数の合計です（エンドアラウンドキャリーと共に加算）。ＴＣＰ
ヘッダのチェックサムフィールドにしまっておかれるものはこの合計の１
の補数です。チェックサム値を計算する前に、送信者はゼロをパケットの
チェックサムフィールドに置きます。もしパケットの受信者によって計算
されたチェックサムがゼロであるなら、パケットは正当と考えられます。
これはパケット残りに関係なく、チェックサムフィールドの「負の」数が
取り消しを行った結果です。
Ignoring the difficulty of actually evaluating the checksum
function for a given packet, the way of using the checksum
described above is quite simple, but it assumes some properties
of the checksum operator (one's complement addition, "+" in what
follows):
上で記述されたチェックサムの方法で、実際にあるパケットのチェックサ
ム機能を評価することの困難さを無視することは非常に簡単ですが、ある
のチェックサム演算子（１の補数の加算、以下の「+」）の特性を仮定し
ます：
(P1) + is commutative. Thus, the order in which
the 16-bit bytes are "added" together is
unimportant.
(P1) + は可換です。それで、１６ビットバイトの「合計」
順序は重要でありません。
(P2) + has at least one identity element (The
current function has two: +0 and -0). This
allows the sender to compute the checksum
function by placing a zero in the packet checksum
field before computing the value.
(P2) + が少なくとも１つの単位元を持ちます（現在の機能
は２つ：+0と-0）。これは値を計算する前にゼロをパケッ
トチェックサムフィールドに置くことによって送信者が
チェックサム機能を計算することを許します。
(P3) + has an inverse. Thus, the receiver may
evaluate the checksum function and expect a zero.
(P3) + が逆元を持っています。それで、受信者はチェック
サム機能を評価し、ゼロを期待してもよいです。
(P4) + is associative, allowing the checksum field
to be anywhere in the packet and the 16-bit bytes
to be scanned sequentially.
(P4) + が結合性を持ちます、チェックサムフィールドがパ
ケットのどこにもおけ、１６ビットバイトが連続的に走
査できます。
Mathematically, these properties of the binary operation "+" over
the set of 16-bit numbers forms an Abelian group [5]. Of course,
there are many Abelian groups but not all would be satisfactory
for use as checksum operators. (Another operator readily
available in the PDP-11 instruction set that has all of these
properties is exclusive-OR, but XOR is unsatisfactory for other
reasons.)
数学的に、これらの１６ビットの数の上の２項演算子「+」の性質は、アー
ベル群を生成します[5]。もちろん、多くのアーベル群がありますが、すべ
てがチェックサム演算子として使用するのに満足であるわけではありませ
ん。（他のこれらすべての特性を持つＰＤＰ−１１の命令セットで利用可
能な演算は排他的論理和ですが、ＸＯＲは他の理由で不十分です）。
Albeit imprecise, another property which must be preserved in any
future checksum scheme is:
不正確かもしれないが、将来のチェックサムでも維持されているに違いな
いもう１つの特性は以下です：
(P5) + is fast to compute on a variety of machines
with limited storage requirements.
(P5) + が限定されたメモリのいろいろなマシン上で計算が高速です。
The current function is quite good in this respect. On the
PDP-11 the inner loop looks like:
現在の機能はこの点に関して非常に良いです。ＰＤＰ−１１で内部ループ
は以下の様です：
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 are exploited further and two
16-bit bytes per loop are processed:
ＰＤＰ−１０の特性で、Ｐ１〜４がさらに利用でき、ループ毎に２つの１６
ビットバイトが処理されます：
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" instruction in the loops above are required to
convert the two's complement ADD instruction(s) into a one's
complement add by making the carries be end-around. One's
complement arithmetic is better than two's complement because it
is 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 affecting the value of the checksum. It is just this
property that makes some sort of addition preferable to a simple
exclusive-OR which is frequently used but permits an even number
of drops (pick ups) in any bit channel. 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.
(P6) パケットにチェックサムを加えても情報バイトを変え
ません。Peterson[6]はこれを「体系的」コードと呼び
ます。
This property allows intermediate computers such as gateway
machines to act on fields (i.e., the Internet Destination
Address) without having to first decode the packet. Cyclical
Redundancy Checks used for error correction are not systematic
either. However, most applications of CRCs tend to emphasize
error detection rather than correction and consequently can send
the message unchanged, with the CRC check bits being 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.
この特性はゲートウェイマシンのような中間コンピュータが最初にパケッ
トを解読せずにフィールド（すなわち、インターネット宛先アドレス）に
対して行動することを可能にします。エラー訂正のために使われた循環冗
長検査は体系的ではありません。しかしながら、たいていのＣＲＣのアプ
リケーションがどちらかと言うと訂正よりエラー発見を強調する傾向があ
り、従ってメッセージを変えずにＣＲＣ検査ビットを追加できます。ＡＲ
ＰＡＮＥＴのＩＭＰと超遠距離ホストインタフェース[4]で使われた２４
ビットＣＲＣと（[11]で記述された）８００と６２５０ビット/インチの
磁気テープのＡＮＳＩ標準はこのモードを使います。
Note that the operation of higher level protocols are not (by
design) affected by anything that may be done by a gateway acting
on possibly invalid packets. It is permissible for gateways to
validate the checksum on incoming packets, but in general
gateways will not 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.
(P7) 検査合計は少しずつ修正されるかもしれません。
This property permits an intermediate gateway to add information
to a packet, for instance a timestamp, and "add" an appropriate
change to the checksum field of the packet. Note that the
checksum will still be end-to-end since it was not fully
recomputed.
この特性は中間ゲートウェイがパケット、例えばタイムスタンプにような
情報を加えて、そしてパケットのチェックサムフィールドに適切な変更を
「加える」のを許します。チェックサムが完全再計算されてはいないので、
まだエンドエンドである事に注意してください。
3. Product Codes
3. 掛算コード
Certain "product codes" are potentially useful for checksuming
purposes. The following is a brief description of product codes
in the context of TCP. More general treatment can be found in
Avizienis [7] and probably other more recent works.
ある特定の「掛算コード」は潜在的にチェックサムの目的に役立ちます。
次はＴＣＰ環境での製品コードの短い記述です。より一般的な扱いが
Avizienis[7]と恐らく他のより最近の仕事で見つかります。
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 if 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 Reconstructed
With 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 will yield Mr as the quotient and
0 as the remainder if Mr is to be considered the same as Mo .
掛算コードで転送形式はMs = K * Moです。すなわち送信メッセージは単純
に元のメッセージMoとある既知の定数Kの掛算です。解読時に、受信MsをK
で割ってMrが商で、もしMrがMoと同じなら余りが0を生成します。
The first problem is selecting 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.)
最初の問題は「良い」K、「検査因子」の選択です。Kがメッセージを表現
するために選ばたベースと互いに素に違いありません。（例：バイナリメッ
セージと間違って選ばれた８のK。これは、３つのゼロが追加された以外、
Msが正確にMoと同じに見えることを意味します。メッセージ受信者が８で
割ることで見える唯一の誤りは、エラーがそれらの３ビットの１つで起こっ
た場合です。）
For TCP the base R will be chosen to be 2**16. That is, every
16-bit byte (word on the PDP-11) will be considered as a digit of
a big number and that number is the message. Thus,
ＴＣＰでベースRは2**16と選ばれるでしょう。すなわち、すべての１６ビッ
トのバイト（ＰＤＰ−１１上のワード）が、メッセージを数と見て、大き
い数の桁として考えられるでしょう。それで、
Mo = SIGMA [ Bi * (R**i)] , Bi is i-th byte
i=0 to N
Ms = K * Mo
Corrupting 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)/K. Since 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" which controls the degree of detection to be had for
burst errors which affect 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 so that arithmetic operations will be 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:
Msのひと桁の誤りはある基数位置ｊに対しMs' = Ms±C*(R**j)を生じます。
受信者はMs'/K = Mo±C(R**j)/Kを計算します。RとKが互いの素なので、
C*(R**j)がKの倍数ではありません。それ故に、割算は０でない余りを生じ、
Ms'がMsと異なる事を示します。見ての通り、Kのよい選択はあるbに対して
(R**b - 1)で、bは「検査長」でメッセージの桁列（つまり１６ビットバイ
ト）のバースト誤りの検出精度を制御します。実際は、算数オペレーショ
ンが単純であるであろうように、bが１と選ばれ、それでKが2**16 - 1であ
るでしょう。これは１５ビット以下のバーストが検出されることを意味し
ます。[7]によればこのbの選択は見つけられない２重誤りの割合の次の式
をもたらします：
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.
大きいメッセージで、ｋが無限になる時、fは３.１２５パーセントに近づ
きます。
Multiple precision multiplication and division are normally quite
complex operations, especially on small machines which typically
lack even single precision multiply and divide operations. The
exception to this is exactly the case being dealt with here --
the factor is 2**16 - 1 on machines with a word length of 16
bits. The reason for this is due to the following identity:
多精度乗算と除算は通常、特に典型的に単精度に欠ける小さい機械上で、
非常に複雑な演算です。この例外はここで扱われる場合です−因数は１６
ビットワード長の機械上で2**16 - 1です。これの理由は次の恒等式のため
です：
Q*(R**j) = Q, mod (R-1) 0 <= Q < R
That 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.
すなわち、基の内で選択された任意の数値Qに対し、(0, 1, ... R-1)掛け
る基数の任意の乗数は、基数引く１で割った時、Qの余りを与えます。
Example: In decimal R = 10. Pick Q = 6.
例：数R = 10で、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
= 5
So, 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 2**16 and the check
factor is 2**16 - 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!
それで、数を基数引く１で割った余りは桁分割された数を合計することで
わかります。ＴＣＰケース場合に基数が2**16で、検査因数は2**16 - 1で、
メッセージは１６ビットワード（ＰＤＰ−１１上で）を合計し、キャリー
をエンドアラウンドすすことで検査できます。もし結果がゼロなら、メッ
セージは正当と思うことができます。それで、掛算コード化メッセージの
検査は、現在のＴＣＰチェックサムと正確に同じ複雑さです！
In order to form Ms, the sender must multiply the multiple
precision "number" Mo by 2**16 - 1. Or, Ms = (2**16)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.
Msを生成するために、送信者は多精度「数」Moと2**16 - 1を掛けるか、あ
るいは、Ms = (2**16)Mo - Moです。これはMo全体を１ワードシフトし、精
度値を変えて、Moを引くことによって行われます。キャリーが桁間で伝播
しなければなりませんが、現在の桁だけの問題なので、１の補数演算が使
われます。
(2**16)Mo = Mo0 + Mo1 + Mo2 + ... + MoX + 0
- Mo = - ( Mo0 + Mo1 + ......... + MoX)
--------- ----------------------------------
Ms = Ms0 + Ms1 + ... - MoX
A 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 byte
Note 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.
体系的でないのでコーディング手順が決まった場所でされないことに注意
してください。一般に、原本、Mo、は再送の目的で送信者側で保管されな
ければならないので、読み込み可能でしょう。それでMOV R0,(R3)+はルー
プ毎に８メモリサイクルの２つを必要とします。
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.
Ms < (2**16)Moなので、コーディング手順はメッセージに正確に１つの
１６ビットワードを加えるでしょう。この追加の１６ビットがメッセージ
の最後にあるでしょう、しかし送信前のＴＣＰヘッダで定義された場所に
されるかもしれません。受信者はメッセージを解読する前に標準的なフォー
マットに戻すためにMsを元どおりにしなければならないでしょう。
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.
完全にメッセージを解読する受信者のコードは、Msの任意のワードはMoの
連続する２つのワードの差分から前ワードのキャリーを引いたもので、下
位ワードはMoのマイナス下位ワードを含むと推論されるかもしれません。
それでMrの下位（すなわち、最右）ワードはMsの下位バイトのマイナスで
す。Mrの次のワードはMsの次のワード足すMrの計算されたワード足す前の
計算のキャリーです。
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. Chosing C = 1 is sufficient in most
cases.
宛先へのすべてゼロのメッセージから保護するために手順のわずかな改善
が要求されます。Ms'/K = 0/K = 0は余りがゼロなので、これは正当なチェッ
クサムを持つように見えます。コードの改善はCを既知の整数としたときに、
Ms = K*Mo + Cとする事です。この定数を加えることはメッセージの上に第
２パスを必要としますが、しかしこれはキャリーの増加が止まれば終わる
ので、一般に小さいでしょう。C = 1を選ぶのはほとんどの場合に十分です。
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*(R**j) + 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,
掛算コードチェックサムは、手順がいくらか関係するが、追加のワードの
計算に徐々に更新できるので、Ｐ７が満たされます。元のメッセージが２
つの部分Ｈ１とＨ２からなると想像してください。それで、
Mo = H1*(R**j) + H2です。タイムスタンプワードがこれらの間に挿入され
ると形式は修正され、Mo' = H1*(R**(j+1)) + T*(R**j) + H2になります。
KがR-1と選ばれているので、転送メッセージはMs' = Mo'(R-1)です。それで、
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 - P2
Recalling 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 handle similarly.
Rが2**16、ＰＤＰ−１１上のワードサイズ、であるのでRで乗算する事はメ
モリ上で１ワード動かす事を意味します。それで、最初の項のMs'は単純に
メッセージの修正なしのコピーです。次の項は新しいデータTを(j+1)番ワー
ドから始まる様に修正したMs'と加算したものです。Tの加算は左からのキャ
リーの伝播を起こすがキャリーが生成されないと停止するので、加算は簡
単です。他の項は同様に簡単に扱えます。
4. More Complicated Codes
4. より複雑なコード
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.
誤り検出とコード修正についてたくさんの理論が存在します。Peterson
[6]はよい参考文献です。これらの「ＣＲＣ」案の大部分が排他的論理和で
構成されたフィードバックネットワークとシフトレジスタを使って実行さ
れるよう意図されます。プログラムでこのようなロジック回路をシミュレー
トすることは、何らかのプログラムトリックが発見されないなら、実用上
遅すぎるでしょう。
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 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.
１つのそのようなトリックがKirstein[8]によって提案されました。基本的
に、現在のシフトレジスタ状態の少ないビット（４か８）は（Moからの）
入力列と混合され、結果は新しいシフトレジスタ状態と、もしコードが体
系的でないなら出力列（Ms）のビット、から生じる表のインデックスとし
て使用されます。４ビットバイトを使っている特に「良い」ＣＲＣ関数の
コーディングの試験が、このテクニックが現在のチェックサム機能と比べ
ておよそ４倍遅いことを示しました。これはＰＤＰ−１０とＰＤＰ−１１
の両方で真実でした。上でリストアップされた望ましい特性について、Ｃ
ＲＣ案はＰ３（逆元を持つ）とＰ６（体系的である）だけを満たします。
パケット中のチェックサムフィールドの配置は重要で、そしてＣＲＣは徐
々に変更することができません。
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.
コーディング理論の大部分がバイナリコードを扱うけれども、qを素数のべ
き乗として、もしアルファベットがq個の記号からなるなら、理論の大部分
が適用できます。例えばqを2**16とすると、ワード毎で理論が有用です。
5. Outboard Processing
5. 船外処理
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.
複雑なチェックサムを計算するような機能が大規模な処理を必要とする時、
１つの解決策が外部プロセッサにその処理を委ねることです。このように
して「メッセージコード化」と「メッセージ解読」はメインホストプロセッ
サに負担をかけないひとつの命令になります。デジタル・イクイップメン
ト社のＶＡＸ／７８０コンピュータはＣＲＣ[13]の生成と検査に対する特
殊ハードウェアが搭載されています。一般にこれは、このようなプロセッ
サがＴＣＰメッセージを使うすべての異なるホストマシンに設置が必要な
ので、良い解決ではありません。
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.
大きいホストのゲートウェイ機能は「インターネットフロントエンドマシ
ン」で完全に処理されることは想像可能です。このマシンはネットワーク
かインターネットプロトコルモジュールから来たパケットの転送と、イン
ターネット分割をセグメントに再組み立てしホストに渡すに責任があるで
しょう。もう１つのこの機械の能力は、チェックサムを検査しホスト渡す
セグメントがフロントエンドを出る時点で正しいとすることです。コン
ピュータサイクルがフロントエンドでは高価でなくて利用可能であると考
えられるので、これは合理的と思われます。
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 that
information like which function is being performed and the
message reference numbers are 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 reduces the computing burden on the host
is that all that is required in order to validate the message
using the end-to-end checksum is to send it back to the frontend
machine. In the case of the PDP-10, this requires only 0.5
memory cycles per 16-bit byte of Internet message, and only a few
processor cycles to setup the required transfers.
この案がホストの計算負担を減らす理由は、エンドエンドチェックサムを
使うメッセージの検査に要求されるすべてがフロントエンド機械あるとい
うことです。ＰＤＰ−１０の場合に、これはインターネットメッセージの
１６ビットのバイト毎にただ０.５メモリサイクルだけが必要で、そして要
求の転送の設定には数プロセッササイクルだけを必要とします。
6. Conclusions
6. 結論
There is an ordering of checksum functions: first and simplest is
none at all which provides no error detection or correction.
Second, is sending a constant which is checked by the receiver.
This also is extremely weak. Third, the exclusive-OR of the data
may be sent. XOR takes the minimal amount of computer time to
generate and check, but is 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 is currently used by TCP. It is slightly more
expensive in terms of computer time. The next step is a product
code. The product code is strongly related to one's complement
sum, takes still more computer time to use, provides a bit more
protection against common hardware failures, but has some
objectionable properties. Next is a genuine CRC polynomial code,
used for checking purposes only. This is 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 suffers mainly in that messages must be (at least
partially) decoded by intermediate gateways in order that they
can be forwarded. Should product codes not be chosen as an
improved checksum, some slight modification to the existing
scheme might be possible. For instance the "add and rotate"
function used for paper tape by the PDP-6/10 group at the
Artificial Intelligence Laboratory at M.I.T. Project MAC [12]
could be useful if it can be proved that it is better than the
current scheme and that it can be computed efficiently on a
variety of machines.
ＴＣＰとインターネットアプリケーションで掛算コード案は実行可能です。
これは、メッセージを転送するには、（少なくとも部分的に）中間ゲート
ウェイで解読されなくてはならないという点で、主に問題です。もし掛算
コードが改善されたチェックサムとして選ばれなかったなら、ある既存の
案へのわずかな修正が可能であるかもしれません。例えばＭＩＴプロジェ
クトＭＡＣ[12]は人工知能試験所のＰＤＰ−６／１０グループにの紙テー
プで使われた「加算と回転」機能は、もしそれが現在の案より良くいろい
ろなマシン上で効率的に計算できることが証明できるなら、なら有用です。
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.