Name
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 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^-^1(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^-^1(W) has a polynomial time algorithm. *We also show how to extend these results to sequences of IDs that contain repeated packets. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.dam.2008.05.011 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
doubly convex bipartite graphs,packet reordering,tcp modeling methodology,matchings.,permutation a,combinatorial problem,tcp trace,tcp semantics,tcp,input sequence w,packet dynamic,tcp reordering pattern,buffer sequence,matchings,packet ids,bipartite graph,transmission control protocol | Journal | 156 |
Issue | ISSN | Citations |
17 | Discrete Applied Mathematics | 3 |
PageRank | References | Authors |
0.45 | 7 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anders Hansson | 1 | 7 | 0.95 |
| Gabriel Istrate | 2 | 99 | 24.96 |