Packet reordering in networks with heavy-tailed delays

An important characteristic of any TCP connection is the sequencing of packets within that connection. Out-of sequence packets indicate that the connection suffers from loss, duplication or reordering. More generally, in many distributed applications information integrity requires that data exchanges between different nodes of a system be performed in a specific order. However, due to random delays over different paths in a system, the packets may arrive at the receiver in a different order than their chronological order. In such a case, a resequencing buffer at the receiver has to store disordered packets temporarily. We analyze both the waiting time of a packet in the resequencing buffer and the size of this resequencing queue. We derive the exact asymptotics for the large deviation of these quantities under heavy-tailed assumptions. In contrast with results obtained for light-tailed distributions, we show that there exists several “typical paths” that lead to the large deviation. We derive explicitly these different “typical paths” and give heuristic rules for an optimal balancing. Copyright Springer-Verlag 2008