Skip to Main content Skip to Navigation

Packet Reordering in Networks with Heavy-Tailed Delays

Marc Lelarge 1
1 TREC - Theory of networks and communications
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt
Abstract : 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. It is thus of interest to study the magnitude of out-of sequence packets within Internet TCP connection and to identify their causes. More generally, in many distributed applications (e.g., remote computations, database manipulations, or data transmission over a computer network), 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 or updates 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.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 7:37:24 PM
Last modification on : Wednesday, October 14, 2020 - 4:11:32 AM
Long-term archiving on: : Tuesday, February 22, 2011 - 11:38:40 AM


  • HAL Id : inria-00070238, version 1



Marc Lelarge. Packet Reordering in Networks with Heavy-Tailed Delays. [Research Report] RR-5783, INRIA. 2005, pp.31. ⟨inria-00070238⟩



Record views


Files downloads