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

[Subba Reddy <subbareddy@samsung.com>]

Hi Greg,

It is good to see all the time/space requirements at one place.

I have few questions and comments.

>
> Greg
>
> Parameters:
> -----------
>
> P   number of distinct prefixes on a link
> p_r number of distinct prefixes received in pios from router r
> l_r number 0of learned prefixes received in pios from router r
> N   number of links visited recently.
>
>
>
> Discussion of issues and assumptions:
> -------------------------------------
>
> Schemes are described with individual sub components,
> as well as when combined in compound solutions (as proposed
> in drafts).  This made building the analysis easier.
>
> Proposed schemes from the drafts are marked as: **** (Proposed Scheme)
>
> Ignores number of routers on link

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 required
at the router side.


<cut>
>
>
>
> Router Side storage and processing requirements.
> ================================================
>
> CompleteRA:
> -----------
> Additional Storage: O(P) keep DNAPrefixList
>
> RA build time: O(P) traverse DNAPrefixList.
>
> RA processing: O(p_r) insertion of prefixes into hash table.
>
> Timers: 1 Expiry timer (callback or operation based)
>
>
> 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).

Please correct me, if anything is wrong.

>
> RA processing: O(p_r) insertion of prefixes into hash table.
>
> Timers: 1 Expiry timer (callback or operation based)
>
>
> CompleteRA+PrefixLandmarks **** (Proposed Scheme)
> -------------------------------------------------
> Additional Storage: O(P) keep DNAprefixlist
>
> RA build time: O(1) comparison of landmark with DNAPrefixList.
>                OR
>                O(P) traverse DNAPrefixList.
>
>
> RA processing: O(p_r) insertion of prefixes into hash table.
>
> Timers: 1 Expiry timer (callback or operation based)
>
>
>
> 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 LinkID
will not change, O(1) is 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 compared
with the LinkID at the host.

> Timers: 1 expiry timer (callback or operation based)
>
>
> Unmodified RFC 2461 Routers:
> ----------------------------
> Additional Storage: zero
>
> RA Build time: O(1) (add pio processing time for own prefixes)
>
> RA processing: O(1) (RA consistency checks)
>                OR
>                zero
>
> Timers: 0 or 1 expiry timer (prefix retraction)
>
>
>
>
>
>
>
>
> Host Side storage and processing requirements.
> ==============================================
>
> CompleteRA:
> -----------
> Storage: O(P) Prefix List of distinct prefixes on link
>
> RA Processing: O(P) = O(p_r+l_r) storage of prefixes in prefix list.
>
> RS build time: O(1), normal RS.
>                OR
>                zero, no RS.
>
> Learning time: 1 message
>
>
> Prefix Landmark:
> ----------------
> Storage: O(1) landmark prefix (minimum)
>          O(P) prefix list (maximum/robust).
>
> RA Processing: O(1) landmark inpsection
>
> RS build time: O(1), normal RS + selected landmark.
>
> Learning time: 1 message
>
>
> CompleteRA+Prefix Landmark **** (Proposed Scheme  -- see below for CPL):
> --------------------------------------------------
> Storage: O(P) Prefix List of distinct prefixes on link
>
> RA Processing: O(1)landmark inspection
>                or
>                O(P) storage of prefixes in prefix list.
>
> RS build time: O(1), normal RS.
>                OR
>                O(1), normal RS + selected landmark
>                OR
>                zero, no RS.
>
> Learning time: 1 message ( more if Landmark:"NO" is incomplete)
>
>
>
>
> 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.

>
> RA Processing: O(1) LinkID inspection, comparison to recent LinkIDs.
>
> RS build time: O(1), normal RS.
>                OR
>                zero, no RS.
>
> Learning time: 1 message.
>

<cut>

Thanks & Regards,
Subba Reddy