Re: [GROW] draft on FIB aggregation

[Zartash Uzmi <[e-mail]>]

Comments inline.

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

>
> On Jul 6, 2010, at 5:18 AM, Lixia Zhang wrote:
>
>
>> On Jul 5, 2010, at 1:52 PM, Paul Francis wrote:
>>
>>  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.
>>>
>>
>> Note that the "zhang" in draft-zhang-fibaggregation-02 is really Beichuan
>> Zhang.
>> It's mostly Beichuan and Lan Wang's work.
>>
>>  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.
>>>
>>
>> will read and comment.
>>
>>  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:
>
>
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)

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


> Lan
>
>
>