2007/03/05 by Anders Hansson, Hansson, Anders, Gabriel Istrate +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Network Packet Processing and Optimization #Network Security and Intrusion Detection #Network Traffic and Congestion Control #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.cs/0703020
arxiv created 2007/03/05 · openalex publication_date 2007/03/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Packet reordering is an important property of network traffic that should be captured by analytical models of the Transmission Control Protocol (TCP). We study a combinatorial problem motivated by RESTORED, a TCP modeling methodology that incorporates information about packet dynamics. A significant component of this model is a many-to-one mapping B that transforms sequences of packet IDs into buffer sequences, in a manner that is compatible with TCP semantics. We show that the following hold: 1. There exists a linear time algorithm that, given a buffer sequence W of length n, decides whether there exists a permutation A of 1,2,..., n such that A∈ B-1(W) (and constructs such a permutation, when it exists). 2. The problem of counting the number of permutations in B-1(W) has a polynomial time algorithm. We also show how to extend these results to sequences of IDs that contain repeated packets.