HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 - ENS Paris, 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 Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 7:37:24 PM
Last modification on : Thursday, March 17, 2022 - 10:08: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