Counting Protocols for Reliable End-to-End Transmission

Authors: Richard E. Ladner, Anthony LaMarca, Ewan Tempero
Source: GZipped PostScript (0kb); Adobe PDF (372kb)

We introduce a new class of protocols, called counting protocols. These protocols provide a reliable virtual circuit for computer networks in which packets may be delivered out of order. Standard protocols use bounded sequence numbers to identify lost packets. In networks that do not remove very old packets, these protocols may experience wrap-around and fail. Counting protocols use a different approach.

Three counting protocols are presented:

1. the one-bit protocol which uses one bit header and sends one packet per message under ideal conditions, but performs poorly in networks with realistic loss rates,
2. the mode protocol which uses multiple-bit headers and behaves well in networks with a realistic loss rates, and
3. the mode-power protocol which also uses multiple-bit headers and performs better than the mode protocol on short sequences, but worse on very long sequences.

We give the derivations of the three counting protocols and prove the one-bit protocol correct. We do a careful performance analysis of both the one-bit and mode protocols and present the results of a simulation study to demonstrate the performance of the mode-power protocol.