Counting preimages of TCP reordering patterns

DOI10.1016/J.DAM.2008.05.011zbMATH Open1170.68338arXivcs/0703020OpenAlexW2123916341MaRDI QIDQ1003463FDOQ1003463

Authors: J. Martínez 

Publication date: 4 March 2009

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

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.

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

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

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)

Cites Work

• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Title not available (Why is that?)
• Combinatorics of TCP reordering

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)