Packet Reordering in Networks with Heavy-Tailed Delays

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.
Mots-clés :
Document type :
Reports
Domain :

https://hal.inria.fr/inria-00070238
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

Identifiers

• HAL Id : inria-00070238, version 1

Citation

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

Record views