Article ID Journal Published Year Pages File Type
419828 Discrete Applied Mathematics 2008 7 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,