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

From: Greg Daley <[email-masked]>
Date: Sat, 30 Jul 2005 22:53:25 +1000

Hi Subba,

Thanks for your analysis.  I've asked the draft authors
for further clarification on the points you've raised.

If you've got a reference to the text which indicates what
you meant, we may be able to clear it up ourselves.

----- Original Message -----
[cut]
> 
> I think, if we consider no. of routers on link, then for each RS
> 1. In Landmark method, all the routers in the link needs to 
> compare the
> landmark prefix
>    with the DNAPrefix List.
> 2. In LinkID method, routers just sends RAs, so no comaprision is 
> requiredat the router side.

Yes, this is the O(1) operation - hash table lookup for 
Landmark and for CompleteRA.  This is constant time.

It is also constant time to just send the RA in LinkID,
as it has to lookup the LinkID (one operartion or two
operations, if you include OldLinkID).

[cut]
> > Prefix Landmarks:
> > -----------------
> > Additional Storage: O(P) keep DNAprefixlist
> >
> > RA build time: O(1) comparison of landmark with DNAPrefixList.
> 
> I don't know, which complexity (best case or average case or worst 
> case?)you have considered.
> As per my understanding,
>        Best case complexity is O(1) as you have mentioned.
>        Average and Worst case complexities are O(P).

I'm looking at average case complexity.  With a fair sized hash
table, this is what you get.  Of course there are pathological
cases with badly built hashes, or small tables which are worse. 
Worst case therefore degenerates to linear, but you'd practically
never get it if there was a well distributed hash, and the
collision probabilities for a particular value were low enough.

This is fairly well known for hash tables.

[cut]
> >
> > Prefix LinkID  **** (Proposed Scheme):
> > ---------------------------------------
> > Additional Storage: O(1) keep LinkID and Old LinkID
> 
> I think storage requirement is O(P). If LinkID prefix is removed from
> the link, routers need to select the next smaller prefix from 
> prefix list.
> 
> I think, here also, if you have considered only the cases, where 
> LinkIDwill not change, O(1) is fine.

This is mentioned in the assumptions at the top.  I guess
that if there's only going to be one prefix removed in a period,
the next smaller prefix is all that's required. In the general
case though, O(P) is correct.

> >
> > RA Build time: O(1) selection of LinkID and Old LinkID
> >
> >
> > RA Processing: O(p_r) comparison of each prefix with LinkID
> >
> 
> I think, this is O(1) because, only linkID in the RA needs to be 
> comparedwith the LinkID at the host.

No actually, the learned component of the RA isn't inspected,
for robustness sake (described in the draft: Syam or JinHyeock may
also correct me on this).  This means all the PIOs need to be checked.

[cut]
> >
> > Prefix LinkID **** (Proposed Scheme  -- see below for CPL):
> > -------------------------------------
> > Storage: O(1) Prefix LinkID (minimum)
> >          O(N) set of linkIDs received recently on different IP 
> links.>
> 
> I think, here N is the number of different LinkIDs (if at all) 
> advertised in the last 1.5hrs on the link.

Actually, I think this is the number of prefixes known on the 
host:

From section 1.3:

Paragraph4:
"...the hosts track the list of linkid prefixes they've
   received in the last 1.5 hours to generate "the linkid prefix list
   (LinkidPrefixList)".

Perhaps, there is confusion, because in most cases, the 
LinkIDPrefixList
is cleared out by the host each time it moves link

Is this the current thinking?

In that case, then the maximum size is P, but the mean size
is much lower (typically 1).

I'll update the description of the assumptions  with the ideas
mentioned here.

Greg

---

From: Subba Reddy <[email-masked]>
Date: Sun, 31 Jul 2005 10:40:14 +0530

Hi Greg,

> operations, if you include OldLinkID).

ok.

> This is fairly well known for hash tables.

True. For a well distributed hash, O(1) is fine.

> case though, O(P) is correct.

fine.

> > comparedwith the LinkID at the host.

From Section 4.2 (4th paragraph) of the LinkID draft(00/01)

"
   When a host with a linkid prefix receives an RA, whether solicited or
   unsolicited, that includes a prefix with I-bit set, the host compares
   its LinkidPrefixList with the set of prefixes in the RA.
"

Host compares, its LinkID (stored in LinkIDPrefixList) with the LinkID
advertised in RA (i.e, the prefix with I bit set. This prefix can be
learned prefix or router's own prefix).
So, only one comarision is required if the LinkIDPrefixList consists of
only one prefix (Most of the time LinkIDPrefixList consists of only one
prefix).

So, I think it is O(1).

> also correct me on this).  This means all the PIOs need to be checked.

Routers will not consider the learned prefixes for the robustness sake, but
not the hosts.

From Section 3.2 (4th paragraph) of the LinkID draft(01),

"
   From the received RAs, the router extracts only the valid prefixes in
   PIO and generate the "learned prefix list (LearnedPrefixList)".
"

From Section 3.2 (last paragraph) of the LinkID draft(01),

"
   Take notice that, for prefix list generation, a router only takes the
   prefixes in PIO into consideratoin.
"

> Actually, I think this is the number of prefixes known on the

Most of the time LinkIDPrefixList consists of only one prefix i.e, LinkID.
If LinkID of the link changes, because of addition/deletion of prefixes,
then
LinkIDPrefixList can contain more than 1 prefix.

> Is this the current thinking?

True. If a host changes its link, it will clear the LinkIDPrefixList.

> is much lower (typically 1).

True. I also think O(1) is fine.

Thanks & Regards,
Subba Reddy