Subject: RE: [ippm] spatial complexity of n-reordering

From: Nischal M Piratla <[email-masked]>
Date: Tue, 8 Mar 2005 19:23:22 -0700

Henk,
What I presented is a worst case scenario's order of computation ( as I did 
mention in during my presentation). 
Also, with arrivals the formula of N(N+1)/2 is put approximately (rather 
erronously). However, it doesn't affect the result. The exact formula can be 
computed as follows

With second arrival, we make 1 comparison, with 3rd arrival we make two 
comparions, i.e., to first and second, with fourth arrival, we compare the 
packet number to first, second and third arrivals. Thus, by 4th arrival, we 
have
1 comparison (at second arrival)
2 comparisons (at third arrival)
3 comparisons (at fourth arrival)
..
..

The formula is (N-1)*(N)/2.  The example that you mentioned depends on a 
property of an arrival sequence, i.e., hoping previous arrivals are in order. 
We will hit the above limit as in the formula, if things are not in order. To 
implement these metrics, it is important to know the worst case complexities

Thanks,
Nischal

>===== Original Message From Henk Uijterwaal <[email-masked]> =====
>At 19:34 08/03/2005, Nischal M Piratla wrote:
>
>
>>Also, everytime
>>you receive a packet, you are required to match them against this stored
>>arrivals.. i.e., 1, 2, 3, 4, 5, .... = N(N+1)/2 comparisons. Thus, leading 
to
>>O(N^2) complexities.
>
>Mainly for my own understanding: if I have a sequence of 3 packets: 1 
arrives,
>2 arrives. I now have to compare 1 against 2 to check if they are in order.
>Then 3 arrives.  I have to compare 3 against 1 and 2.  That is 3 comparisons.
>However, you say N(N+1)/2 = 3*4/2 = 6 comparisons.
>
>If a 4th packet arrives, I have to compare it against 1, 2 and 3.  That
>is 6 comparisons.  You say N(N+1)/2 = 4*5/2= 10 comparisons.
>
>(And I'd actually do this in a smarter way: first compare against the
>previous packet: 1 arrive, 2 arrives, compare 1 and 2.  Then 3 arrives,
>compare against 2 first, if (1,2) are in order and (2,3) are in order,
>then (1,2,3) must be in order too.
>
>Henk
>
>
>
>>- Nischal
>>
>>
>>
>> >===== Original Message From stanislav shalunov <[email-masked]>
>> =====
>> >stanislav shalunov <[email-masked]> writes:
>> >
>> >> O(N) for n-reordering, [...]  The actual complexity is O(1).
>> >
>> >It was pointed out to me that I forgot to mention that the temporal
>> >complexity is O(N) rather than O(N^2) (as the table in Nischal's
>> >slides had it).
>> >
>> >--
>> >Stanislav Shalunov             http://www.internet2.edu/~shalunov/
>> >
>> >Clothes make the man.  Naked people have little or no influence on
>> >society.                                             -- Mark Twain
>> >
>> >_______________________________________________
>> >ippm mailing list
>> >[email-masked]
>> >https://www1.ietf.org/mailman/listinfo/ippm
>>
>>****************************************************
>>Research Assistant
>>Computer Networking Research Laboratory (CNRL)
>>C203,Dept. of Electrical & Computer Eng.
>>Colorado State University,
>>Fort Collins, CO 80523
>>Voice: 970-491-7067/7794
>>Fax:   970-491-2249
>>http://www.cnrl.colostate.edu
>>http://lamar.colostate.edu/~nischal
>>****************************************************
>>
>>
>>_______________________________________________
>>ippm mailing list
>>[email-masked]
>>https://www1.ietf.org/mailman/listinfo/ippm
>
>-----------------------------------------------------------------------------
-
>Henk Uijterwaal                           Email: henk.uijterwaal(at)ripe.net
>RIPE Network Coordination Centre          http://www.amsterdamned.org/~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
>-----------------------------------------------------------------------------
-
>
>Look here junior, don't you be so happy.
>And for Heaven's sake, don't you be so sad.                 (Tom Verlaine)

****************************************************
Research Assistant
Computer Networking Research Laboratory (CNRL)
C203,Dept. of Electrical & Computer Eng.
Colorado State University,
Fort Collins, CO 80523
Voice: 970-491-7067/7794
Fax:   970-491-2249
http://www.cnrl.colostate.edu
http://lamar.colostate.edu/~nischal
****************************************************

_______________________________________________
ippm mailing list
[email-masked] 
https://www1.ietf.org/mailman/listinfo/ippm

---

From: Nischal M Piratla <[email-masked]>
Date: Tue, 8 Mar 2005 23:18:25 -0700

Unless you are claiming that n-reordering considers duplicate packets as 
reordered, I do not see how the order of computation complexity is less than 
O(N^2).

Let us consider the sequence (1,3,2,4,2). Here packet 2 is a duplicate. Given, 
this sequence, following is step-thru of n-reordering program "example 1 of 
appendix A"

Ring:: (empty)

Read packet s = 1
Ring::1
Increment frequency of none

Read packet s = 3
Ring::1 3
Increment frequency of none

Read packet s = 2
Previous packet 3 > s
Increment frequency of 1-reordering by 1 (now 1)
Still previous packet 1 < s, so stop.

1-reordering = 1
Ring::1 3 2

Read packet s = 4
Previous packet 3 < s
Increment frequency of none
1-reordering = 1
Ring::1 3 2 4

Read packet s = 2
Previous packet 4 > s
Increment frequency of 1-reordering by 1 (now 2)
Still previous packet 2 = s, so stop

1-reordering = 2

But, *the duplicate of 2 is considered reordered*!

- Nischal

>===== Original Message From stanislav shalunov <[email-masked]> =====
>Nischal M Piratla <[email-masked]> writes:
>
>> Order of spatial and computation complexity for n-reordering are
>> O(N) and O(N^2) respectively.
>
>Look at the program of example 1 of appendix A of
>draft-ietf-ippm-reordering-09.txt.  It computes n-reordering (for all
>n<=100) of a sample of size N in O(N) time and O(1) space.
>
>P.S. Even if what you said about spatial complexity were true, the
>temporal complexity would remain O(N).  Hint: put sequence numbers in
>a hash table of size 2N.
>
>--
>"The power of accurate observation is commonly called cynicism by
>those who have not got it."			-- G. B. Shaw
>