Re: [DNA] Info: Computation Time/Space requirements for LinkIdentification schemes

[Greg Daley <Greg.Daley@eng.monash.edu.au>]

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