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 B 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 W to be valid (i.e. A∈B⁻¹(W) for some permutation A of {1,2,…,n}), and a linear time algorithm that, given a valid buffer sequence W of length n, constructs a permutation A in the preimage of W.

•

We show that the problem of counting the number of permutations in B⁻¹(W) has a polynomial time algorithm.

•

We also show how to extend these results to sequences of IDs that contain repeated packets.