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

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

Order of spatial and computation complexity for n-reordering are O(N) and 
O(N^2) respectively.

This is true for almost all IPPM metrics due to the absence of any robust 
mechanism to detect and remove duplicate packets. You will have to either 
store the early arrivals or the missing numbers. The worst case scenario for 
both could be order of N. This is what we all said about the RBD in the 
initial stages, before we explained the offset concept to all. 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.

- 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

---

From: stanislav shalunov <[email-masked]>
Date: 08 Mar 2005 14:08:43 -0500

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

---

From: Henk Uijterwaal <[email-masked]>
Date: Wed, 09 Mar 2005 02:41:53 +0100

At 19:34 08/03/2005, Nischal M Piratla wrote:

>Also, everytime

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

> >complexity is O(N) rather than O(N^2) (as the table in Nischal's

------------------------------------------------------------------------------
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)