The Intractability of Bounded Protocols for On-Line Sequence Transmission over Non-FIFO Channels

The efficiency of data-link protocols for reliable transmission of a sequence of messages over non-FIFO physical channels is discussed. The transmission has to be on-line; i.e., a message cannot be accessed by the transmitting station before the preceding message has been received. Three resources are considered: The number of packets that have to be sent, the number of headers, and the amount of space required by the protocol. Three lower bounds are proved. First, the space required by any protocol for delivering n messages that uses less than n headers cannot be bounded by any function of n. Second, the number of packets that have to be sent by any protocol that uses a fixed number of headers in order to deliver a message is linear in the number of packets that are delayed on the channel at the time the message is sent. Finally, the notion of a probabilistic physical channel, in which a packet can be delayed on the channel with probability q, is introduced. An exponential lower bound, with overwhelming probability, is proved on the number of packets that have to be sent by any data-link protocol using a fixed number of headers when it is implemented over a probabilistic physical channel.