Subject: RE: [ippm] New metric for packet reordering

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

Stanislav,
Please find the link of C code for reorder density computation:

http://www.engr.colostate.edu/ece/Research/cnrl/code/RD.c

Feel free to send any more comments.
- Nischal

-------- Original Message --------
 >Subject: Re: [ippm] New metric for packet reordering.
 >Date: 18 Feb 2003 01:07:27 -0500
 >From: stanislav shalunov <[email-masked]>
 >To: Nischal M Piratla <[email-masked]>
 >CC: [email-masked]
 >References: <[email-masked]>
 >
 >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: stanislav shalunov <[email-masked]>
Date: 20 Feb 2003 11:11:54 -0500

Nischal,

It seems that:

* When `late' packets are encountered, your metric behaves like
  N-reordering;

* When `early' packets are encountered, your metric reports same
  degree of reordering as N-reordering, but larger number of packets
  are reported as reordered;

* When there are any missing packets, it reports high degrees of
  reordering for a whole bunch of packets.

This last is a show-stopper as far as I am concerned.

A fanatic is one who can't change his mind and won't change the
subject.                                   -- Winston Churchill
_______________________________________________
ippm mailing list
[email-masked]
http://mailhost.advanced.org/mailman/listinfo/ippm

---

From: Nischal Piratla <[email-masked]>
Date: Fri, 28 Feb 2003 17:08:34 -0700

Stanislav,
Thank you for the comments. Here are the clarifications.

>  are reported as reordered;
RD algorithm does not behave like N-reordering. Here are just  a couple 
of simple  examples:

Example 1:
For the sequence <1,4,5,2,3>
RD output:
displacement absolute normalized
0 2 0.400
1 1 0.200
2 2 0.400
3 0 0.000
4 0 0.000

N-reordering output:
1-reordering = 25.000000%
2-reordering = 33.333333%
no 3-reordering

1-reordering = 1
2-reordering = 1
no 3-reordering

In this sequence, RD shows that there are two packets with F[D=2] namely 
seq #s: 5 and 2. N-reordering treats only packet 2 as 1-reordered and 
2-reordered. According to RD, even after seq # 2 arrives the buffer 
requirement is '2' as seq #. 3 has not yet arrived. However, this 
conclusion cannot be derived from N-reordering.
   
    Example 2:
For the sequence <1,2,3,4,5,2,1>
RD output:
displacement absolute normalized
0 7 1.000
1 0 0.000
2 0 0.000
3 0 0.000

N-reordering output:
1-reordering = 33.333333%
2-reordering = 40.000000%
3-reordering = 50.000000%
4-reordering = 33.333333%
5-reordering = 50.000000%
no 6-reordering

1-reordering = 2
2-reordering = 2
3-reordering = 2
4-reordering = 1
5-reordering = 1
no 6-reordering

In this example, the N-reordering algo shows that there is 5-reordering. 
If you look at the sequence there are two duplicate packets namely, 
seq#s 2 & 1. In RD, the F[D] does not exist for D>0 i.e., there is no 
reordering. As one can see, the sequence has no reordering.

**************************************

> This last is a show-stopper as far as I am concerned.
RD has a concept of DT i.e., threshold after which the packet is assumed 
lost. This  takes care of the above issue. Moreover, we compared it with 
existing N-reordering for a sequence where the seq #2 comes after 40 
packets, then N-reordering shows very high reordering. Here is the sequence

Sequence: 
<1,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,2> 

RD output with DT = 5:
displacement absolute normalized
0 36 0.878
1 1 0.024
2 1 0.024
3 1 0.024
4 1 0.024
5 1 0.024

N-reordering output:

1-reordering = 2.500000%
2-reordering = 2.564103%
3-reordering = 2.631579%
4-reordering = 2.702703%
5-reordering = 2.777778%
6-reordering = 2.857143%
7-reordering = 2.941176%
8-reordering = 3.030303%
9-reordering = 3.125000%
10-reordering = 3.225806%
11-reordering = 3.333333%
12-reordering = 3.448276%
13-reordering = 3.571429%
14-reordering = 3.703704%
15-reordering = 3.846154%
16-reordering = 4.000000%
17-reordering = 4.166667%
18-reordering = 4.347826%
19-reordering = 4.545455%
20-reordering = 4.761905%
21-reordering = 5.000000%
22-reordering = 5.263158%
23-reordering = 5.555556%
24-reordering = 5.882353%
25-reordering = 6.250000%
26-reordering = 6.666667%
27-reordering = 7.142857%
28-reordering = 7.692308%
29-reordering = 8.333333%
30-reordering = 9.090909%
31-reordering = 10.000000%
32-reordering = 11.111111%
33-reordering = 12.500000%
34-reordering = 14.285714%
35-reordering = 16.666667%
36-reordering = 20.000000%
37-reordering = 25.000000%
38-reordering = 33.333333%
39-reordering = 50.000000%
no 40-reordering

This example clearly shows that N-reordering is much more susceptible to 
delayed packets as it cannot treat them as lost when their useful life 
is over, whereas with RD this is taken care of.  So we have to disagree 
with the above statement That certainly eliminates RD metric from 
show-stopper's list.

Please feel free to send more comments so that we can make this metric 
more useful for everyone. 
Thank You,
Nischal

***********************************************
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/ece/Research/cnrl
***********************************************