Comments inline. On Tue, Jul 6, 2010 at 12:18 PM, Lan Wang <[email protected]> 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 > > >
_______________________________________________ GROW mailing list [email protected] https://www.ietf.org/mailman/listinfo/grow
