An End-to-End Approach to the Resequencing Problem

The resequencing or serialization problem is of basic interest in distributed systems and computer communication systems. This is because a flow of packets, messages, or updates entering a communication system in chronological order from the same port or from different ports may be disordered. The receiving port must then ensure that these objects are resequenced in the appropriate order before they are fed to the output of the system. In this paper we analyze the end-to-end delay recurred by objects traversing such a system, including the d~sordering delay, the delay introduced by the resequencing algorithm, and the delay due to the output server at the receiving port. The analysis is carded out via factorization methods.