Inscriere cercetatori

Premii Ad Astra

premii Ad Astra

Asociația Ad Astra a anunțat câștigătorii Premiilor Ad Astra 2022: Proiectul și-a propus identificarea și popularizarea modelelor de succes, a rezultatelor excepționale ale cercetătorilor români din țară și din afara ei.

Asociatia Ad Astra a cercetatorilor romani lanseaza BAZA DE DATE A CERCETATORILOR ROMANI DIN DIASPORA. Scopul acestei baze de date este aceea de a stimula colaborarea dintre cercetatorii romani de peste hotare dar si cu cercetatorii din Romania. Cercetatorii care doresc sa fie nominalizati in aceasta baza de date sunt rugati sa trimita un email la

Combinatorics of TCP Reordering

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

Autori: Anders Hansson, Gabriel Istrate and Shiva Prasad Kasiviswanathan

Editorial: Springer Verlag, Journal of Combinatorial Optimization, 12 (1-2), p.57-70, 2006.


We study a combinatorial problem motivated by a receiver-oriented model of TCP traffic, that incorporates information on both arrival times and the dynamics of packet IDs. An important component of this model is a many-to-one mapping FB from sequences of IDs into a sequence of buffer sizes. We show that:

i) Given a buffer sequence B, constructing a sequence A of IDs that belongs to the preimage of B can be accomplished by a cubic time algorithm.

ii) Counting the number of sequences A of packet IDs that belong to the preimage of B can be done in linear time in the special case when there exists a constant upper bound on the maximum entry in B.

iii) This problem also has a fully polynomial randomized approximation scheme when we have a constant upper bound on the number of repeats in the packet sequences in the preimage. We also provide experimental evidence that the two previous results suffice to efficiently count the number of preimages for buffer sequences observed in real TCP data.

A preliminary version of this paper can be freely downloaded from

Cuvinte cheie: packet reordering, TCP, generalized matchings