Improving the efficiency of the OSI checksum calculation

ABSTRACT

It is known that using larger byte--sizes to access memory usually results in faster computations of checksum algorithms. This paper proposes two different ways to use larger byte--sizes to improve the performance of the OSI checksum. First, an algorithm is presented that computes the 8--bit checksum using 16-bit integers. It is shown that this algorithm yields a 5 to 20 percent performance improvement on many architectures. Second, the benefits of expanding the basic computation unit of the OSI checksum algorithm to 16--bits integers is considered. This change can yield an additional performance improvement of up to 50% and greatly extended error detection properties, although it is incompatible with the current standard. The measurements of these algorithms are compared with some taken of checksums in common use, such as IP and XNS†.

REFERENCES

• 1: [DE81] Digital Equipment Corporation, VAX Architecture Handbook, Digital Press, 1981.
• 2: [Xe81] Xerox Corporation, Internet Transport Protocols, Xerox System Integration Standard 028112, 1981.
• 3: [Fl82] Fletcher, J., "An Arithmetic Checksum for Serial Transmissions" IEEE Trans Commun. , Vol. COM-30, No. 1, January, 1982, pp. 247-252.
• 4: [IS86] International Organization for Standardization, "Connection oriented transport protocol specification", International Standard ISO 8073-1986 (E).
• 5: Riccardo Gusella, The Analysis of Diskless Workstation Traffic on an Ethernet, University of California at Berkeley, Berkeley, CA, 1987
• 6: [Ha87] Harris Corporation, HCX-7 and HCX-9 Architecture, Reference Manual, Pub. No. 0830022-100, Change 2, reissue 1.
• 7: [IS87] International Organization for Standardization, "Protocol for providing the connectionless-mode network service", Draft International Standard ISO 8473, ISO/TC 97/SC 6 N4542.
• 8: A. Cockburn, Efficient implementation of the OSI transport protocol checksum algorithm using 8/16-bit arithmetic, ACM SIGCOMM Computer Communication Review, v.17 n.3, p.13-20, July/Aug. 1987 [doi>10.1145/36727.36730]
• 9: W. McCoy, Implementation guide for the ISO Transport Protocol, RFC Editor, 1987
• 10: Anastase Nakassis, Fletcher's error detection algorithm: how to implement it efficiently and how toavoid the most common pitfalls, ACM SIGCOMM Computer Communication Review, v.18 n.5, p.63-88, October 1988 [doi>10.1145/53644.53648]
• 11: R. Braden , D. Borman , C. Partridge, Computing the internet checksum, ACM SIGCOMM Computer Communication Review, v.19 n.2, p.86-94, April 1, 1989 [doi>10.1145/378444.378453]
• 12: William W. Plummer, TCP checksum function design, ACM SIGCOMM Computer Communication Review, v.19 n.2, p.95-101, April 1, 1989 [doi>10.1145/378444.378454]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Open Systems Interconnection reference model (OSI)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Verification