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: 2019-Feb-15
Document File: 24 page(s) / 33K

Publishing Venue

Internet Society Requests For Comment (RFCs)

Related People

R.T. Braden: AUTHOR [+2]

Related Documents

10.17487/RFC1071: DOI

Abstract

This RFC summarizes techniques and algorithms for efficiently computing the Internet checksum. It is not a standard, but a set of useful implementation techniques.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% 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

Braden, Borman, & Partridge [Page 1]

RFC 1071 Computing the Internet Checksum September 1988

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

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.

2...

Processing...
Loading...