The ORTC paper provides table size results from tables that were as old as ORTC itself. On recent tables, the saving is around 60-70%, which means the table size after aggregation will be about 30-40% -- which isn't too different from the level-4 results.
Here is a first-cut comparison of ORTC with level-x aggregation (x from 1 to 4) for various benchmarks: 1) Size of table after aggregation: ORTC is optimal (proved in the paper!) but level-4 also comes close 2) Processing requirements: For initial aggregation, ORTC requires 3 passes of the tree but level-4 does not(?) 3) Corner cases where routing correctness may break down when an update is incorporated: fewer in level-x for small x and too many in ORTC. 4) Updates: easy to incorporate in level-x (especially for small x) but not in ORTC (due to large number of corner cases in ORTC but once you get it right, it's a matter of correctly incorporating the updates into the algorithm). 5) Increase in table size after incorporating updates: no data for level-x. For ORTC, for a June 2004 routeviews table, the initial reduction was 66.5% (from 160818 prefixes) and the reduction remained more than 60% after incorporating 86904 updates. How long does it take? Depends upon the frequency of the updates which is dependent upon the vantage point. 6) extra routable space: introduced in level-x (for large x) but not in ORTC. I will be able to send the ORTC code as soon as I get back from IETF. Zartash On Wed, Nov 11, 2009 at 11:50 PM, Beichuan Zhang <[email protected]> wrote: > Thanks for the pointer to the paper! I just had a quick read. The ORTC > algorithm passes the tree 3 times and gives the optimal aggregation when no > extra routable space is allowed. The table size after aggregation is around > 60-70%. > > Our level-4 result, however, shows that if extra space is allowed, the > table size after aggregation is 30-40%. > > It'll be great if you could send us the ORTC code. We're very interested in > comparing it with other schemes under the same environment. > > Thanks, > > --- > beichuan > > On Nov 11, 2009, at 11:23 AM, Beichuan Zhang wrote: > > Quick synopsis: > > ORTC performs FIB compression such that the number of entries in the > compressed FIB is the smallest. However, ORTC requires 3 passes if a tree > data structure is used to store the prefixes. > > The compression achieved is roughly of the order of what is achieved by > level-4b (about 70% on recent tables from routeviews) but no "new" routable > space created that was previously unroutable. > > On Wed, Nov 11, 2009 at 7:02 AM, Zartash Uzmi <zartash at > gmail.com<zartash%20at%20gmail.com> > > wrote: > >> I have a working implementation of ORTC and can make it available if >> needed. The implementation has been tested for routing correctness, on a >> large number of routeviews tables. >> >> Zartash >> >> >> On Wed, Nov 11, 2009 at 6:52 AM, John G. Scudder <jgs at >> juniper.net<jgs%20at%20juniper.net> >> > wrote: >> >> Constructing Optimal IP Routing Tables >>> Draves, R.P. King, C. Venkatachary, S. Zill, B.D. >>> INFOCOM '99 >>> >>> http://research.microsoft.com/apps/pubs/default.aspx?id=69698 >>> >>> (I got the acronym expansion wrong, it's "Optimal Routing Table >>> Constructor".) >>> >>> --John >> >> >
_______________________________________________ GROW mailing list [email protected] https://www.ietf.org/mailman/listinfo/grow
