[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[DNA] Info: Computation Time/Space requirements for Link Identificationschemes
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).