Identifying almost sorted permutations from TCP buffer dynamics

Details Identifying almost sorted permutations from TCP buffer dynamics Identifying almost sorted permutations from TCP buffer dynamics

2008-10-09

arxiv.org/abs/0810.1639v1

Computer Science

Data Structures and Algorithms

Scientific paper

Associate to each sequence $A$ of integers (intending to represent packet IDs) a sequence of positive integers of the same length ${\mathcal M}(A)$. The $i$'th entry of ${\mathcal 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$ {\em equivalent} (written $A\equiv_{FB} B$) if ${\mathcal M}(A)={\mathcal M}(B)$. We prove the following result: any two permutations $A,B$ of the same length with $SUS(A)$, $SUS(B)\leq 3$ (where SUS is the {\em shuffled-up-sequences} reordering measure), and such that $A\equiv_{FB} B$ are identical. The result (which is no longer valid if we replace the upper bound 3 by 4) was motivated by RESTORED, a receiver-oriented model of network traffic we have previously introduced.

Affiliated with

Also associated with

No associations

Rating

Identifying almost sorted permutations from TCP buffer dynamics 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 Identifying almost sorted permutations from TCP buffer dynamics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Identifying almost sorted permutations from TCP buffer dynamics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-460886