Gabriel Istrate. Identifying almostsorted permutations from TCP buffer dynamics. Scientific Annals of Computer Science (special issue dedicated to professor Sergiu Rudeanu' s 80th birthday), XXV (1), pp. 133154, 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 outoforder 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 shuffledupsequences 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 receiveroriented 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
