Counting preimages of TCP reordering patterns

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 [G. Istrate, A. Hansson, S. Thulasidasan, M. Marathe, C. Barrett, Semantic compression of TCP traces, in: F. Boavida (Ed.), Proceedings of the Fifth IFIP NETWORKING Conference, in: Lecture Notes in Computer Science, vol. 3976, Springer-Verlag, 2006, pp. 123–135], a TCP modeling methodology that incorporates information about packet dynamics. A significant component of this model is a many-to-one mapping BB that transforms sequences of packet IDs into buffer sequences in a manner that is compatible with TCP semantics. We obtain the following results:
• We give an easy necessary and sufficient condition for an input sequence WW to be valid   (i.e. A∈B−1(W)A∈B−1(W) for some permutation AA of {1,2,…,n}{1,2,…,n}), and a linear time algorithm that, given a valid buffer sequence WW of length nn, constructs a permutation AA in the preimage of WW.
• We show that the problem of counting the number of permutations in B−1(W)B−1(W) has a polynomial time algorithm.
• We also show how to extend these results to sequences of IDs that contain repeated packets.