Counting preimages of TCP reordering patterns

Details Counting preimages of TCP reordering patterns Counting preimages of TCP reordering patterns

2007-03-05

arxiv.org/abs/cs/0703020v1

Computer Science

Data Structures and Algorithms

Scientific paper

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 $A\in 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.

Affiliated with

Also associated with

No associations

Rating

Counting preimages of TCP reordering patterns does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting preimages of TCP reordering patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting preimages of TCP reordering patterns will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-113732