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

From: Greg Daley <[email-masked]>
Date: Fri, 29 Jul 2005 08:46:37 +1000

Hi, 

Here's my time/space requirement analysis of the Link Identification
methods.  Based on my analysis, none of them seems to be terribly
difficult to support.

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

None of the schemes: LinkID, CompleteRA, Landmarks require sorted storage,

LinkID requires Minimum selection comparison

Hash tables work fine for DNAPrefixList in completeRA and
Prefix Landmark, so long as hash table traversal for
CompleteRA generation is linear: O(P).

Additional Storage indicates storage for learned information on 
routers, and ignores storage requirements for the RFC2461 AdvPrefixList.

Additional comparison of host side requirements for schemes when also
using Complete Prefix Lists is provided for context.

Time calculations ignore signature generation and verification times
(which are affected by the overall length of the message).

In order to be robust against prefix departures, O(P) prefixes may need
to be stored for LinkID, but the minimum is O(1).

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.

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

RA Build time: O(1) selection of LinkID and Old LinkID

RA Processing: O(p_r) comparison of each prefix with LinkID

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.

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.

Complete Prefix Lists:
----------------------
Storage: O(P + P') Current link object + Candidate Link Object.

RA processing: O(p_r) insertion of prefixes into candidate link object,
               + comparison with current link object.

RS build time: O(1), normal RS.

Learning time: NUM_RS_RA_COMPLETE (1..3) * 4 seconds.

CompleteRA + Complete Prefix Lists:
-----------------------------------
Storage: O(P + P') Current link object + Candidate Link Object.

RA processing: O(P) insertion of prefixes into candidate link object,
               + comparison with current link object.

RS build time: O(1), normal RS.

Learning time: 1 message.

Landmark + Complete Prefix Lists:
-----------------------------------
Storage: O(P + P') Current link object + Candidate Link Object.

RA processing: O(1) Landmark inspection
               OR
               O(P) insertion of prefixes into candidate link object,
               + comparison with current link object.

RS build time: O(1), normal RS + selected landmark

Learning time: 1 message (Landmark)
               NUM_RS_RA_COMPLETE (1..3) * 4 seconds (Complete Prefix List).

CompleteRA + Landmark + Complete Prefix Lists **** (Proposed Scheme):
---------------------------------------------------------------------
Storage: O(P + P') Current link object + Candidate Link Object.

RA processing: O(1) Landmark inspection
               OR
               O(P) insertion of prefixes into candidate link object,
               + comparison with current link object.

RS build time: O(1), normal RS + selected landmark
               OR
               O(1), normal RS.
               OR
               zero.

Learning time: 1 message

LinkID + Complete Prefix Lists  **** (Proposed Scheme):
-------------------------------------------------------
Storage: O(P + P') Current link object + Candidate Link Object.
         Maybe + O(N) set of linkIDs received recently on different IP
links.

RA processing: O(1) LinkID inspection, comparison to recent LinkIDs.
               OR
               O(P) insertion of prefixes into candidate link object,
               + comparison with current link object.

RS build time: O(1), normal RS.
               OR
               zero, no RS.

Learning time: 1 message
               OR
               NUM_RS_RA_COMPLETE (1..3) * 4 seconds (Complete Prefix List).

---

From: Subba Reddy <[email-masked]>
Date: Sat, 30 Jul 2005 12:57:53 +0530

Hi Greg,

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

I have few questions and comments.

> Parameters:

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.

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.

> CompleteRA+PrefixLandmarks **** (Proposed Scheme)

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

> Unmodified RFC 2461 Routers:

I think, here N is the number of different LinkIDs (if at all) advertised in
the last 1.5hrs
on the link.

> Learning time: 1 message.

<cut>

Thanks & Regards,
Subba Reddy