Inscriere cercetatori

Daca aveti cont Ad Astra si de Facebook, intrati pe pagina de profil pentru a da dreptul sa va logati pe site doar cu acest buton.

Site nou !

Daca nu va puteti recupera parola (sau aveti alte probleme), scrieti-ne la pagina de contact. Situl vechi se gaseste la adresa


Counting preimages of TCP reordering patterns

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în revistã ştiinţificã

Autori: Anders Hansson, Gabriel Istrate

Editorial: Discrete Applied Mathematics, 156(17), p.3187-3193, 2008.


Want create site? Find Free WordPress Themes and plugins.

Packet reordering is an important property of network traffic that
should be captured by analytical models of the Transmission Control
Protocol (TCP). We study a combinatorial problem motivated by RESTORED, a TCP modeling methodology that
incorporates information about packet dynamics. A significant
component of this model is a many-to-one mapping $B$ that transforms
sequences of packet IDs into buffer sequences, in a manner that
is compatible with TCP semantics. We show that the following hold:

1. There exists a linear time algorithm that, given a buffer
sequence W of length n, decides whether there exists a permutation
A of 1,2,…,n such that $Ain B^{-1}(W)$ (and constructs
such a permutation, when it exists).

2. The problem of counting the number of permutations in $B^{-1}(W)$ has a polynomial time algorithm.

3. We also show how to extend these results to sequences of IDs
that contain repeated packets.

A preliminary version of this paper can be freely consulted at

Did you find apk for android? You can find new Free Android Games and apps.

Cuvinte cheie: TCP, packet reordering, linear algorithms, matchings