2008/10/09 by Gabriel Istrate, Istrate, Gabriel
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Network Traffic and Congestion Control #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.0810.1639
arxiv created 2008/10/09 · openalex publication_date 2008/10/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Associate to each sequence A of integers (intending to represent packet IDs) a sequence of positive integers of the same length \mathcal M(A). The i'th entry of \mathcal 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 \em equivalent (written A≡FB B) if \mathcal M(A)=\mathcal M(B). We prove the following result: any two permutations A,B of the same length with SUS(A), SUS(B)≤ 3 (where SUS is the \em shuffled-up-sequences reordering measure), and such that A≡FB B are identical. The result (which is no longer valid if we replace the upper bound 3 by 4) was motivated by RESTORED, a receiver-oriented model of network traffic we have previously introduced.