Re: [GROW] ORTC

[Zartash Uzmi <zartash at gmail.com>]

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 <bzhang at arizona.edu> 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> 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