RELIABLE COMMUNICATION OVER UNRELIABLE CHANNELS

Layered communication protocols frequently implement a FIFO message fa cility on top of an unreliable non-FIFO service such as that provided by a packet-switching network. This paper investigates the possibility of implementing a reliable message layer on top of an underlying laye r that can lose packets and deliver them out of order, with the additi onal restriction that the implementation uses only a fixed finite numb er of different packets. A new formalism is presented to specify commu nication layers and their properties, the notion of their implementati on by I/O automata, and the properties of such implementations. An I/O automaton that implements a reliable layer over an unreliable layer i s presented. In this implementation, the number of packets needed to d eliver each succeeding message increases permanently as additional pac ket-loss and reordering faults occur. A proof is given that no protoco l can avoid such performance degradation.