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

[Subba Reddy <subbareddy@samsung.com>]

Hi Greg,


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

ok.

>
> [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.
>

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

> [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.
>

fine.

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

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

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

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.
"

>
> [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:
>

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.

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

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

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

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

Thanks & Regards,
Subba Reddy