Subject: Re: [DNA] Info: Computation Time/Space requirements for Link Identification schemes

From: Greg Daley <[email-masked]>
Date: Mon, 01 Aug 2005 19:16:26 +1000

Hi Subba,

I think we've got one issue left.

[cut]
>>Thinking about it another way though, each PIO and LPIO has to be
>>checked for the LinkID flag, and then that LinkID has to be compared
>>with the stored LinkID.
>>
> 
> 
> If the first prefix in the RA is LinkID prefix (if any), then only one
> comparision is enough.  I feel, routers can maintain the LinkID prefix
 > as the first prefix, in their prefix list.  Because of this, routers
> can easily check (with O(1) complexity) the validity of LinkID at
 > various point of times (like prefix life time changes, new prefix is
> added, LinkID prefix is a learned prefix and it has not been advertised
 > in the last 1.5hrs). So, routers can easily include LinkID prefix as
 > the first prefix in the RA. Also, maintaining the LinkID prefix as
> the first entry in the prefix list will not add any additional complexity
 > (It is constant O(1)).
> 
> Though, whatever I have mentioned is more implementation specific, IMHO O(1)
> is fine.

RFC 2461 doesn't place any ordering requirements on options in transmitted
RAs.  This is deliberately stated in that document.  I'm not sure
existing implementations would necessarily be well served in requiring 
such ordering.

Additionally, the existing LinkID draft doesn't have this assumption.
So if an issue is adopted for LinkID, and there's agreement that this
transmission is required, it will be O(1).

Currently it is O(p_r), I think.  The difference is very small,
considering the number of advertised prefixes in any RA will be low.

Greg

---

From: Subba Reddy <[email-masked]>
Date: Mon, 01 Aug 2005 16:09:27 +0530

Hi Greg,

> I think we've got one issue left.

Yes.

> transmission is required, it will be O(1).

I agree with your point that there is no ordering requirements for options.
I feel it as more implementation specific. I think, optimistic way is
considered
in the analysis (like hash list for DNAPrefixList, one LinkID in the
LinkIDPrefixList).
Please correct me, if wrong.

So, it may be better to consider this also in the similar way.

>
> Currently it is O(p_r), I think.

Yes.

> The difference is very small,

Difference is small, but when we consider the complexity analysis, we feel
like
there is a difference between constant time and linear time.

Thanks & Regards,
Subba Reddy

---

From: Greg Daley <[email-masked]>
Date: Tue, 02 Aug 2005 03:03:56 +1000

Hi Subba,

[cut]
> considered in the analysis (like hash list for DNAPrefixList, one LinkID
 > in the LinkIDPrefixList).

You're not wrong.

Previously with hashing, that was the mean case - O(1), as based on
several existing hashing algorithms.   If there is no known ordering
on a list of options, then there has to be traversal of the list in
general.

While it is on average O(p_r/2), O(p_r/2) is also conventionally noted
O(p_r).

That's why I said it was linear...

Greg

---

From: Subba Reddy <[email-masked]>
Date: Tue, 02 Aug 2005 08:51:35 +0530

Hi Greg,

<cut>

> That's why I said it was linear...

If traversal is required, I agree with linear. 
What I am saying is, if implementations 
(router side, anyway they are changing RA) can take
advantage by putting LinkID as the first prefix, complexity will come 
down to constant. 
For general case, linear is fine.

Thanks & Regards,
Subba Reddy