Subject: [Roll] TBRPF Analysis in http://www.ietf.org/internet-drafts/draft-levis-roll-overview-protocols-00.txt

From: "Ian Chakeres" <[email-masked]>
Date: Wed, 2 Apr 2008 04:18:47 +0530

I asked Richard Ogier ([email-masked]) author of TBRPF to
look over the overview-protocols document and its statements about
TBRPF.

Here is his response.

=====

 The brief summary in Section 3.3 is fine, but I don't agree
 with the analysis (spelled "analsysis") in Section 11.
 They say the total control overhead is O(n^2), which would be
 the overhead if every node advertises its entire source tree,
 since each source tree has n-1 links.
 So O(n^2) can be considered the worst case, with high churn
 and overlapping trees, which they claim would be even larger.
 So at the very minimum, the text should be changed to say
 that O(n^2) is the worst case, not the optimal case.

 The optimal case would probably be O(n^2 / d), but
 I don't have a proof for this.

 Similarly, the last paragraph says that in the worst case,
 each node reports the entire topology.  This is not true.
 In the worst case, each node reports its entire source tree.
 So in the worst case, each node would have to maintain
 O(n) state for each neighbor, or O(n*d) for all neighbors.

 In the best case, each node reports only part of its
 source tree, so each node would have to maintain
 O(n) for all neighbors (again I don't have a proof),
 plus O(d^2) for all neighbors' neighbors.

 Richard

 Here is the analysis from the document:

   "TBRPF"

   The information transmitted within a neighborhood is the union of all
   the reported trees of the nodes, where the reported tree is defined
   in the protocol.  In the optimal case, this union comprises a single
   copy of the entire Topology Graph, which has size O(n * d).  Thus
   given O(n / d) neighborhoods in the entire network, the total control
   overhead will be O(n ^2).  In the worst case, for example with high
   churn, nodes within a neighborhood will transmit larger, overlapping
   reported trees leading to more control traffic.  Additionally, since
   TBRPF makes extensive use of differental updates, the observed
   control overhead may be much smaller if the topology is relatively
   static.

   Each node maintains the global network link-state, as reported by
   each neighbor.  Each of these copies has size O(n * d).  Thus in the
   worst case, where each neighbor reports the entire topology, this
   information has size O(n * (d ^ 2)).  However, in the optimal case
   where each neighbor reports non-overlapping subsets of the topology,
   the total state will be only O(n * d).
_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: Philip Levis <[email-masked]>
Date: Wed, 2 Apr 2008 09:20:27 -0700

> look over the overview-protocols document and its statements about

This is great, Ian. It's exactly the kind of inspection and iteration  
we need. Thanks for doing this.

> I don't have a proof for this.

Well, big-O is a worst-case analysis, except for randomized  
algorithms, where it's an expected analysis based on worst-case input.

> O(n) state for each neighbor, or O(n*d) for all neighbors.

Nice catch.

> plus O(d^2) for all neighbors' neighbors.

As big-O is worst case, the above makes more sense.

Phil

---

From: Richard Ogier <[email-masked]>
Date: Wed, 02 Apr 2008 10:41:07 -0800

> algorithms, where it's an expected analysis based on worst-case input.
Do you agree to change the analysis to say that O(n^2) is the worst 
case, instead
of the optimal case?   Also, since your analysis also mentions the 
optimal case,
do you agree to say that the optimal case can be better
than this since each node reports only a part of its source tree?
After all, that is the whole point of advertising only part of the 
source tree!

>> O(n) state for each neighbor, or O(n*d) for all neighbors.

Thanks.  I am mainly concerned that you missed my first catch above.

Richard

  "TBRPF"