Subject: [ippm] New metric for packet reordering.

From: Nischal M Piratla <[email-masked]>
Date: Fri, 14 Feb 2003 10:00:52 -0700

Dear ippm Members,
We have come up with a new metric to measure packet reordering. We have 
posted a ID and here is the link:

http://www.ietf.org/internet-drafts/draft-jayasumana-reorder-density-00.txt

This draft may interest you all. Please feel free to send any 
comments/suggestions.
Thanks,
Nischal Piratla

_______________________________________________
ippm mailing list
[email-masked]
http://mailhost.advanced.org/mailman/listinfo/ippm

---

From: "Henk Uijterwaal (RIPE-NCC)" <[email-masked]>
Date: Mon, 17 Feb 2003 11:57:03 +0100 (CET)

Nischal,

> This draft may interest you all. Please feel free to send any

1. If I understand the algorithm correctly, then it needs an array
   in_buffer[N] with N the number of packets in a stream. This is not
   very practical, when I make a VoIP phonecall, then I never know how
   long it is going to last in advance and thus how I should dimension
   this array.

2. Can you include the same examples as in the other reordering metrics
   so one can compare the algorithms?

Henk

------------------------------------------------------------------------------
Henk Uijterwaal                             Email: [email-masked]
RIPE Network Coordination Centre            WWW: http://www.ripe.net/home/henk
P.O.Box 10096          Singel 258           Phone: +31.20.5354414
1001 EB Amsterdam      1016 AB Amsterdam    Fax: +31.20.5354445
The Netherlands        The Netherlands      Mobile: +31.6.55861746
------------------------------------------------------------------------------

That problem that we weren't having yesterday, is it better? (Big ISP NOC)

---

From: Al Morton <[email-masked]>
Date: Mon, 17 Feb 2003 09:27:27 -0500

At 11:57 AM 02/17/2003 +0100, Henk Uijterwaal (RIPE-NCC) wrote:
>...

Case b, packet loss (1,2,4,5,6,7) is sufficient for comparison.
No reordered packets arrive, yet this metric reports reordering
density.  The existing metrics maintain orthogonality between
loss and reordering. Perhaps this algorithm would be better
characterized as a receiver buffer occupation function.

Al

---

From: Nischal M Piratla <[email-masked]>
Date: Mon, 17 Feb 2003 16:14:14 -0700

Dear Henk Uijterwaal,

Please find the answers below:

   this array

in_buffer (N): The dimension of this array is DT. DT is the threshold 
after which the packet is considered useless or lost. This array 
dimension can be chosen based on the application. . For example in VoIP, 
if a packet arrives after 150msec (in theory) it can be discarded. Based 
on the codec selection, we can determine the packet size, max delay and 
in turn the value of DT after which the packet is rendered useless. For 
a TCP connection this DT value would not exceed the number of packets in 
the TCP send queue. Thus, it is not necessary to know the number of 
packets before hand. Dt imposes a limit on when one should consider a 
packet to be lost.

I have picked one example from Al Morton's draft on reorder metric here. 
I hope it is ok to use the text from the draft 
<draft-ietf-ippm-reordering-01.txt>

"...Table 1 Example with Packet 4 Reordered,
   Sending order(SrcNum@Src): 1,2,3,4,5,6,7,8,9,10
   SrcNum       Src     Dst                     Dst     Posit.  Late
   @Dst NextExp Time    Time    Delay   IPDV    Order   Offset  Time	 
   1     1       0      68      68              1				
    2     2      20      88      68       0      2
    3     3      40     108      68       0      3
    5     4      80     148      68     -82      4
    6     6     100     168      68       0      5
    7     7     120     188      68       0      6
    8     8     140     208      68       0      7
    4     9      60     210     150      82      8      4       62
    9     9     160     228      68       0      9
   10    10     180     248      68       0     10

   Each column gives the following information:

   SrcNum   Packet sequence number at the Source.
   NextExp   The value of NextExp when the packet arrived(before
   update).
   SrcTime  Packet time stamp at the Source, ms.
   DstTime  Packet time stamp at the Destination, ms.
   Delay    1-way delay of the packet, ms.
   IPDV     IP Packet Delay Variation, ms
            IPDV = Delay(SrcNum)-Delay(SrcNum-1)..."

Reorder Density for the above example:

  SrcNum       
   @Dst NextExp  Displacement	 Frequency
   1     1          0              F[0] = 1				
    2     2          0              F[0]++
    3     3          0              F[0]++
    5     4          1              F[1] = 1
    6     4          2              F[2] = 1
    7     4          3              F[3] = 1
    8     4          4              F[4] = 1
    4     4          0              F[0]++  
    9     9          0              F[0]++
   10    10          0              F[0]++

Normalized F[i] for all i: F[0] = 0.6, F[1] = 0.1, F[2] = 0.1, F[3] = 0.1, F[4] = 0.1
we 
In this case, if we can set DT = 3, then the table will look like this:

  SrcNum       
   @Dst Expected  Displacement	 Frequency
   1     1          0              F[0] = 1				
    2     2          0              F[0]++
    3     3          0              F[0]++
    5     4          1              F[1] = 1
    6     4          2              F[2] = 1
    7     4          3              F[3] = 1
    8     4          0              F[0]++       { after the current packet's (8) arrival, packet '4' is rendered useless!}
    4     9          0              F[0]++       { should we count this as F[0] occurence?)
    9     9          0              F[0]++
   10    10          0              F[0]++

Normalized F[i] for all i: F[0] = 0.7, F[1] = 0.1, F[2] = 0.1, F[3] = 0.1

Other examples in current metrics are almost similar. However, there are 
no examples with packet duplication. Here is one for the metric 
proposed. (Note: Packet '5' is duplicated.)

  SrcNum       
   @Dst NextExp  Displacement	 Frequency
   1     1          0              F[0] = 1				
    2     2          0              F[0]++
    3     3          0              F[0]++
    5     4          1              F[1] = 1
    6     4          2              F[2] = 1
    7     4          3              F[3] = 1
    8     4          4              F[4] = 1
    4     4          0              F[0]++
    5    9          0              F[0]++    
    9     9          0              F[0]++

Normalized F[i] for all i: F[0] = 0.6, F[1] = 0.1, F[2] = 0.1, F[3] = 0.1, F[4] = 0.1. 

At the arrival of a duplicate packet the buffer occupancy is held the 
same as the duplicate packet will be discarded and the contents of the 
buffer remain.
If you need more examples or explanation, please feel free to send us an 
email.

Thanks,
Nischal Piratla

******************************************
Research Assistant
Computer Networking Research Laboratory
Department of Electrical and Computer Eng.
Colorado State University,
Fort Collins, CO 80523
Voice: +1 970-491-7974
Fax:   +1 970-491-2249
http://www.engr.colostate.edu/~nischal
*******************************************

---

From: stanislav shalunov <[email-masked]>
Date: 18 Feb 2003 01:07:27 -0500

Nischal,

I seem to be having a difficulty interpreting your algorithm as
presented in the internet-draft.

For example, I am looking at the following:

>             If (D < DT)
>             /*Store arrived packet in buffer.*/
>                D = D + 1;
>             Else
>                [...]

Is the comment an actual comment or a pseudocode statement?

Would it perhaps be convenient for you to provide some runnable C code
that we could play with to better understand your definition?

-- 
Stanislav Shalunov		http://www.internet2.edu/~shalunov/

"Which one is worse?  Both are worse."		-- V. I. Lenin
_______________________________________________
ippm mailing list
[email-masked]
http://mailhost.advanced.org/mailman/listinfo/ippm

---

From: Nischal M Piratla <[email-masked]>
Date: Wed, 19 Feb 2003 21:25:51 -0700

Dear Al Morton,

Your question gives rise to a very interesting issue - the orthogonality
of reordering and other phenomena, including losses and duplication of
packets.

1) Loss: With the sequence (1,2,4,5,6,7) it is possible to conclude that
packet 3 is lost only if we are not expecting any more packets in the
sequence. The key question here is "When should a packet be considered
lost?" When it does not arrive during a certain time threshold, or when
the packet does not arrive till measurements are completed? Stated
differently, is a packet considered lost if it does not arrive within
some useful time period, or is it considered lost until it arrives? From 
the point of view of higher level protocols or applications, the former
is desirable. Also, in case of continuous monitoring of reorder in a
network, latter is not possible. Considering a packet to be lost if it
does not arrive during the measurement period does not necessarily make
loss and reordering measurements orthogonal. After debating along these
lines and considering the usefulness of the metric, we decided to move
ahead of any packet that did not arrive within a given time or threshold
(DT). [ In fact, considering packets that do not arrive within the
measurement periods equivalent to starting with DT= no of packets
arriving in measurement period, and decreasing DT by 1 with each
arriving packet. ]

Another interesting question is whether we should  consider (arrived
but) dropped packets as lost packets ?

2) Duplication: These are the packets that are duplicated due to
whatever reason. Should we have a reorder metric that is orthogonal to
it as well? It is possible to argue that reordering has nothing to do 
with duplication and these packets should not be taken into 
consideration. If we consider duplicate packet as a reordered packet, 
the reorder metric is not the same for sequences with duplication and 
sequences without duplication.
Consider the example: (1,2,3,2,4,5,6)
If we consider packet '2' second occurrence as reordering then the
orthogonality between duplicate packet and reorder is not maintained.

When we were thinking about these issues, we also considered Van Paxson 
& etal.'s RFC 2330. I am quoting the requirements that they stated for 
the performance metrics

"+ The metrics must be concrete and well-defined,
+ A methodology for a metric should have the property that it is
repeatable: if the methodology is used multiple times under
identical conditions, the same measurements should result in the
same measurements.
+ The metrics must exhibit no bias for IP clouds implemented with
identical technology,
+ The metrics must exhibit understood and fair bias for IP clouds
implemented with non-identical technology,
+ The metrics must be useful to users and providers in understanding
the performance they experience or provide,
+ The metrics must avoid inducing artificial performance goals."

We thought of the usefulness as one important criteria. Till recently,
we had only % reordering and as the example in the draft indicated the
definition was not concrete (and ambiguous) and hence the usefulness was 
very limited.

Lack of a concrete definition also makes it difficult to reproduce the
results. I hope this answers your query. Please feel free to send any
additional comments/suggestions.
Thank you,
Nischal Piratla

---

From: "Henk Uijterwaal (RIPE-NCC)" <[email-masked]>
Date: Thu, 20 Feb 2003 12:01:45 +0100 (CET)

Nischal,

> the packet does not arrive till measurements are completed?

Time threshold, with the limit set by the application (and can be set to
infinite).  The problem is when an application asks for a resend, if this
happens after (say) 3 packets, then ( 1, 2, 4, 5, 6, 7, 3, 8) is as
interesting as (1, 2, 4, 5, 6, 7, 8).

> it as well?

Yes, duplication is different from reordering.  If packets are duplicated,
then most applications will ignore the second copy, this doesn't take any
CPU cycles.  Reordering means that the packets have to be put back into
order, this does require effort by the application.

Henk