Published in Volume XXV, Issue 1, 2015, pages 133-154, doi: 10.7561/SACS.2015.1.133

Authors: G. Istrate

Abstract

Associate to each sequence A of integers (intending to model packet IDs in a TCP/IP stream) a sequence of positive integers of the same length M(A). The i’th entry of M(A) is the size (at time i) of the smallest buffer needed to hold out-of-order packets, where space is accounted for unreceived packets as well. Call two sequences A, B equivalent (written A≡FB B) if M(A) = M(B).

For a sequence of integers A define SUS(A) to be the shuffled-up-sequences reordering measure defined as the smallest possible number of classes in a partition of the original sequence into increasing subsequences. We prove the following result: any two permutations A, B of the same length with SUS(A), SUS(B) ≤ 3 such that A ≡FB B are identical. The result is no longer valid if we replace the upper bound 3 by 4.

We also consider a similar problem for permutations with repeats. In this case the uniqueness of the preimage is no longer true, but we obtain a characterization of all the preimages of a given sequence, which in particular allows us to count them in polynomial time.

The results were motivated by explaining the behavior and engineering RESTORED, a receiver-oriented model of traffic we introduced and experimentally validated in earlier work.

Full Text (PDF)

References

[1] D. Aldous and P. Diaconis. Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bulletin of the American Mathematical Society 36, pages 413-432, 1999. doi:10.1090/S0273-0979-99-00796-X.

[2] J. Bennett, C. Partridge, and N. Shectman. Packet reordering is not pathological network behavior. IEEE/ACM Transactions on Networking, 7(6):789-798, 1999. doi:10.1109/90.811445.

[3] J. Bellardo and S. Savage. Measuring packet reordering. In Proceedings of the 2nd ACM Workshop on Internet Measurement, pages 97–105, 2002. doi:10.1145/637201.637216.

[4] V. Estivill-Castro and D. Wood. A survey of adaptive sorting algorithms. ACM Computing Surveys, 24(4):441–476, 1992. doi:10.1145/146370.146381.

[5] W. Fulton. Young tableaux: with applications to representation theory and geometry. Cambridge University Press, 1997.

[6] A. Hansson, G. Istrate, and S. Kasiviswanathan. Combinatorics of TCP reordering. Journal of Combinatorial Optimization, 12(1–2):57– 70, 2006. doi:10.1007/s10878-006-8904-0.

[7] A. Hansson, G. Istrate, and G. Yan. Packet reordering metrics: Some methodological considerations. In Proceedings of the Second International Conference on Networking and Services (ICNS’06). IEEE Computer Society Press, 2006. doi:10.1109/ICNS.2006.80.

[8] G. Istrate and A. Hansson. Counting preimages of TCP reordering patterns. Discrete Applied Mathematics, 156(17):3187–3193, 2008. doi:10.1016/j.dam.2008.05.011.

[9] G. Istrate, A. Hansson, S. Thulasidasan, M. Marathe, and C. Barrett. Semantic compression of TCP traces. In Proceedings of the IFIP NETWORKING Conference, volume 3976 of Lecture Notes in Computer Science, pages 123–135. Springer Verlag, 2006. doi:10.1007/11753810_11.

[10] A. P. Jayasumana, N. M. Piratla, A. A. Bare, T. Banka, and R. Whitner. Improved packet reordering metrics. RFC 5236, 2008.

[11] J. Kurose and K. Ross. Computer Networking: A Top-Down Approach Featuring the Internet, Second Edition. Addison Wesley, 2003.

[12] M. Laor and L. Gendel. The effect of packet reordering in a backbone link on application throughput. IEEE Network 16(5), pp. 28–36, 2002. doi:10.1109/MNET.2002.1035115.

[13] C. Levcopoulos and O. Petersson. Sorting shuffled monotone sequences. Information and Computation, 112(1):37–50, 1994. doi:10.1006/inco.1994.1050.

[14] A. Morton, L. Ciavattone, G. Ramachandran, S. Shalunov, and J. Perser. Packet reordering metric for IPPM. IETF RFC 4737, 2006.

[15] N. M. Piratla, A. P. Jayasumana, and A. A. Bare. Reorder Density (RD): A formal, comprehensive metric for packet reordering. In Proceedings of the IFIP Networking Conference 2005, volume 3462 of Lecture Notes in Computer Science, pages 78–89. Springer Verlag, 2005. doi:10.1007/11422778_7.

[16] N. Piratla, A. Jayasumana, A. Bare, and T. Banka. Reorder bufferoccupancy density and its applications for measurement and evaluation of packet reordering. Computer Communications, 30(9):1980–1993, 2007. doi:10.1016/j.comcom.2007.03.001.

[17] W.R. Stevens. TCP/IP Illustrated. Addison Wesley, 1994.

Bibtex

@article{sacscuza:istrate2015iaspftbd,
  title={Identifying Almost Sorted Permutations from TCP Buffer Dynamics},
  author={G. Istrate},
  journal={Scientific Annals of Computer Science},
  volume={25},
  number={1},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2015},
  pages={133--154},
  doi={10.7561/SACS.2015.1.133},
  publisher={``A.I. Cuza'' University Press}
}