Subject: [GROW] draft on FIB aggregation

From: Paul Francis <[email-masked]>
Date: Mon, 5 Jul 2010 22:52:23 +0200

Hi Gang,

Zartash Uzmi and myself have posted an internet draft of FIB aggregation 
that is basically a follow on to Lixia et.al. draft 
http://tools.ietf.org/html/draft-zhang-fibaggregation-02.

You can find it at http://www.ietf.org/id/draft-uzmi-smalta-00.txt.  We 
expect to give a short presentation of it at the next GROW meeting.

Any comments appreciated.

Thanks,

PF

---

From: Lixia Zhang <[email-masked]>
Date: Mon, 5 Jul 2010 14:18:10 -0700

> http://tools.ietf.org/html/draft-zhang-fibaggregation-02.

Note that the "zhang" in draft-zhang-fibaggregation-02 is really Beichuan Zhang.
It's mostly Beichuan and Lan Wang's work.

> Any comments appreciated.

will read and comment.

Lixia

---

From: Lan Wang <[email-masked]>
Date: Tue, 6 Jul 2010 18:18:50 +0800

>> Any comments appreciated.
Since ORTC is the optimal algorithm that does not introduce extra  
routable space, I'm interested in the difference between this work  
and ORTC.  Just did a quick search in the draft and found the following:

-----------
SMALTA's one-shot aggregation is derived from ORTC
    [Paper.Draves-ORTC].  Like its precursor, one-shot runs three passes
    over a tree data structure: ... [LW: omitted some text here]
    Unlike ORTC, SMALTA one-shot is not provably optimal, though it is
    very close to optimal.  This is because SMALTA places some minor
    constraints on the ORTC algorithm in order to allow the aggregated
    table and the original non-aggregated table to be implemented as a
    single data structure.
---------

Beichuan can correct me, but I think ORTC algorithm allows the  
aggregated table and the original table to be implemented as a single  
data structure.  In fact, we have implemented ORTC using a patricia  
trie.  We have a paper to appear in Globecom that talks about this.

Lan

---

From: Zartash Uzmi <[email-masked]>
Date: Tue, 6 Jul 2010 13:20:24 +0200

Comments inline.

On Tue, Jul 6, 2010 at 12:18 PM, Lan Wang <[email-masked]> wrote:

> routable space, I'm interested in the difference between this work and ORTC.
>  Just did a quick search in the draft and found the following:
>
>
Yes, ORTC is the optimal algorithm that does not produce extra routable
space. There are two caveats:

(1) ORTC provides one-time compression -- there is no provision for
incorporating BGP updates unless you decide to run the ORTC again (which
requires 3 passes of the entire data structure).

(2) ORTC does not allow the aggregated table and the original table to share
the same data structure (unless you allow multiple next hops for the same
prefix). There is an example in the technical report (link below) that
depicts this.

SMALTA addresses both these caveats: the first through the update algorithm
and the second through the one-shot algorithm. More details and examples are
in the technical report which is available at
http://www.mpi-sws.org/~zartash/TR-MPI-SMALTA.pdf  (also referenced in the
I-D)

-----------
> Beichuan can correct me, but I think ORTC algorithm allows the aggregated
> table and the original table to be implemented as a single data structure.
>  In fact, we have implemented ORTC using a patricia trie.  We have a paper
> to appear in Globecom that talks about this.
>
>
With ORTC, you sometimes run into a situation when a prefix exists in the
original table as well as in the aggregated table, but with different next
hops. Given this, if you want to store the original table and the aggregated
table in current RIB data structures (in Loc-RIB, for example), you have
multiple options. We chose to use one specific option (the NR constraint in
the tech report).

best,
Zartash