Reliable Transmission of Data Over a Semi-FIFO Routing Layer

In computer networks there is usually a trade-off between the performance and implementation complexity of the routing protocol, and those of the protocol for reliable transmission of data. Often, the routing protocol can perform better if it is not required to retain the FIFO order of the routed data units. However, in such a case the protocol for reliable transmission of data has to maintain many logical timers and to have accurate estimate of the round trip delay. The paper introduces a new notion: semi-FIFO service, which means that the routing layer retains the FIFO order in part. The paper shows that sometimes a non-FIFO routing layer may provide for semi-FIFO service, without substantial changes in the routing concept. Then, the paper proposes a new protocol for reliable transmission of data over an unreliable semi-FIFO routing layer. The protocol uses only one logical timer and does not require an estimate of the round trip delay in order to operate with full capacity. Therefore, the contribution of the paper is eliminating the deficiencies associated with non-FIFO routing schemes that may offer semi-FIFO service.