Counting preimages of TCP reordering patterns

DOI10.1016/J.DAM.2008.05.011MaRDI QIDQ1003463zbMATH OpenOpenAlexFDO

Authors J. Martínez

Publication date 4 March 2009

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0703020

zbMATH Keywords

matchingsTCPpacket reorderingdoubly convex bipartite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Network design and communication in computer systems (68M10) Network protocols (68M12)

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, 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 show that the following hold: 1. There exists a linear time algorithm that, given a buffer sequence W of length n, decides whether there exists a permutation A of 1,2,..., n such that $Ain{B}^{-1}(W)$ (and constructs such a permutation, when it exists). 2. 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.

Recommendations

• Combinatorics of TCP reordering
• Packet reordering in networks with heavy-tailed delays
• On the Large Deviations of Resequencing Queue Size: 2-M/M/1 Case
• Sorting reordered packets with interrupt coalescing
• On the higher moments of TCP

Cites work

• scientific article; zbMATH DE number 571346 (Why is no real title available?)
• Combinatorics of TCP reordering
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems

Cited in

(3)

• Combinatorics of TCP reordering
• Sorting reordered packets with interrupt coalescing
• Packet reordering in networks with heavy-tailed delays

This page was built for publication: Counting preimages of TCP reordering patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003463)