Browse Prior Art Database

Computing the Internet checksum (RFC1071)

IP.com Disclosure Number: IPCOM000001880D
Original Publication Date: 1988-Sep-01
Included in the Prior Art Database: 2000-Sep-12
Document File: 19 page(s) / 50K

Publishing Venue

Internet Society Requests For Comment (RFCs)

Related People

R.T. Braden: AUTHOR [+3]

Abstract

This memo discusses methods for efficiently computing the Internet checksum that is used by the standard Internet protocols IP, UDP, and TCP.

This text was extracted from a ASCII Text document.
This is the abbreviated version, containing approximately 6% of the total text.

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

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.

(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.

(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.

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] [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 ca...