Subject: Re: [GROW] ORTC

From: Beichuan Zhang <[email-masked]>
Date: Wed, 11 Nov 2009 11:50:19 -0700

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

---

From: Zartash Uzmi <[email-masked]>
Date: Fri, 13 Nov 2009 05:54:51 +0500

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-masked]> wrote:

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