Name
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 equivalent to(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 equivalent to(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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.7561/SACS.2015.1.133 | SCIENTIFIC ANNALS OF COMPUTER SCIENCE |
Keywords | DocType | Volume |
algorithms, packet reordering, shuffled up sequences | Journal | 25 |
Issue | ISSN | Citations |
1 | 1843-8121 | 1 |
PageRank | References | Authors |
0.37 | 7 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gabriel Istrate | 1 | 99 | 24.96 |
| V. Parvan | 2 | 1 | 0.37 |