Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> Românã
 
   
 

Gabriel Istrate. Identifying almost-sorted permutations from TCP buffer dynamics. Scientific Annals of Computer Science (special issue dedicated to professor Sergiu Rudeanu' s 80th birthday), XXV (1), pp. 133-154, 2015.

Abstract: Associate to each sequence A of integers (intending to model packet IDs in a TCP/IP stream) a sequence of positive integers of the same length M(A). The iíth entry of M(A) is the size (at time i) of the smallest buffer needed to hold out-of-order packets, where space is accounted for unreceived packets as well. Call two sequences A, B equivalent (written A =_{FB} B) if M(A) = M(B).

For a sequence of integers A define SUS(A) to be the shuffled-up-sequences reordering measure, defined as the smallest possible number of classes in a partition of the original sequence into increasing subsequences.

We prove the following result: any two permutations A, B of the same length with SUS(A), SUS(B) <= 3 such that A =_ {FB} B are identical. The result is no longer valid if we replace the upper bound 3 by 4.

We also consider a similar problem for permutations with repeats. In this case the uniqueness of the preimage is no longer true, but we obtain a characterization of all the preimages of a given sequence, which in particular allows us to count them in polynomial time.

The results were motivated by explaining the behavior and engineering Restored, a receiver-oriented model of traffic we introduced
and experimentally validated in earlier work.

Keywords: SUS, permutations

URL: http://www.info.uaic.ro/bin/download/Annals/XXV1/XXV1_5.pdf

Posted by Gabriel Istrate

Back

   
© Ad Astra 2001-2013