North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: CIDR Aggregation Tool

  • From: Curtis Villamizar
  • Date: Mon Nov 27 14:53:39 1995

Avi,

While this is useful as a metric of the degree of aggregation, it is
not sufficient to configure aggregation.  This is still useful as a
means to look at where improvement may be needed.  Please don't get me
wrong in pointing out that there are limits to the applicability, this
*is* useful.

In message <[email protected]>, Avi Freedman writes:
> Well, after observing the debates about What To Do About The Routing Table
> Size, I decided to work on some informal tools to examine the current
> routing table space for possible aggregations.
> 
> Right now, the raw data is the routing table from the Net Access MAE-East
> router.
> 
> It only searches for aggregates /15 < x < /25 right now - ignoring some
> fairly obvious aggregation-suggestions in the /8 < x < /16 range.
> 
> The results are up at http://routes.netaxs.com and the some of the caveats 
> are listed on the web page, but are:
> 
> 1) When the Net Access MAE-East router has multiple identical routes that 
>    point to the same next-hop (192.41.177.x), the system only uses the one 
>    first listed in the cisco 'sho ip bgp summ' output - even though that's
>    not always the 'best' route.

The routing table seen at one place in the Internet is insufficient to
determine whether aggregation is possible.  Part of the problem is
that equally specific alternate paths are supressed until primary
connectivity is lost.  You may not see alternate paths for multihomed
sites that would prevent aggregation.

> 2) When an AS advertises both an aggregate and a specific, the specific 
>    is 'dropped' by the aggregator. If the input is:
>    {205.89.10.128/17, 205.89.10.130}, the output will be:
>    {205.89.10.128/17} (205.89.10.130 will be dropped).

This is often done to allow a multihomed component of an aggregate to
be routed correctly while still providing the backup path, or allowing
load splitting across providers (usually load split by AS path
filtering or more simply by AS path length).  There is no way to tell
a mistake from this being done intentionally.

> 3) The source of data is the Net Access MAE-East router routing table, 
>    and we don't peer with all parties at MAE-East directly - thus, it's 
>    possible that the system catches aggregations that are impossible
>    because they're announced to a 3rd party via different paths - but
>    an informal look around doesn't appear to indicate that.
> 
> 4) The system goes by next-hop rather than by AS-Path.  There seems to
>    be a good correlation, but ...

You really need to take into account AS path.  As far back as 1992
we've seen grossly optimistic estimates based solely on next hop at
single points (including estimates from me in June/July 1992).

In effect what you have is the degree of aggregation possible if the
aggregartion boundry was extended around the entire rest of the world
(or at least everyone that peered directly with you at the point of
measurement).  What can be aggregated according to such an estimate
will vary according to who is making the measurement and where.

> Also, the final disclaimer: I've examined the results and they *look* 
> reasonable.  But I haven't written tester-tools to attempt to verify
> by another algorithm that the results are correct.
> 
> Here's the table at the end of the web page:
> 
>                            Before   After 
>                            Run      Agg. Run
> 192.41.177.110 ibm             81     68
> 192.41.177.115 digex           98     98
> 192.41.177.120 eu.net         949    775
> 192.41.177.125 nsn.nasa       126    112
> 192.41.177.140 ans           2146   1425
> 192.41.177.145 agis           539    304
> 192.41.177.150 uscyber          2      2
> 192.41.177.160 interpath        2      2
> 192.41.177.170 net99          309    246
> 192.41.177.180 mci              2      2
> 192.41.177.181 mci           8963   6828
> 192.41.177.190 pipex          367    308
> 192.41.177.210 netcom         370    348
> 192.41.177.235 psi              1      1
> 192.41.177.240 icp           4499   3712
> 192.41.177.241 sprintlink    6429   4694
> 192.41.177.245 psi           1491   1098
> 192.41.177.249 alternet      3971   3148
> 192.41.177.251 es.net          96     88
> 192.41.177.252 es.net         122    101
> 192.41.177.6   suranet        470    445
> 192.41.177.70  internex         1      1
> 192.41.177.80  ios             10      8
> 192.41.177.85  cais           184    158
> 192.41.177.86  hlc            354    243
> 192.41.177.89  energis          2      2
> 192.41.177.95  delphi           3      3
> 
> A final note:  We're open to {Additional static sources of route tables at
> MAE-East; Additional static sources of route tables at {MAE-West, Pennsauken,
> or the PacBell NAP}; and dynamic (i.e. the vty password so we can run
> a sho ip bgp summ every so often) sources at any of the MAEs or NAPs.

You will find that while improvement is possible, and may still even
be fairly substantial, your figures represent an optimistic estimate.

Another way of estimating what can be aggregated is by determining
from how many places all of the components of an aggregate could be
heard in all backup situations.  In some cases it might be reasonable
to drop some degree of alternate connectivity (fourth or fifth
preferred paths) and allow a number of holes (specifically aggregated
components).  In principle this could be done algorithmically using
the IRR.  In practice, you need to check with some of the parties
involved to make sure registered information (particialrly aut-num AS
peerings) are accurate beforehand.

Using the IRR you (or we) can select candidates for aggregation and
then make sure the aggregation can really be asfely done.  This is a
little different in than you estimate in that it the viewpoint is what
can we aggregate, rather than what might we see better aggregated in
the future.  The bgp paths at major interconnects could form a useful
sanity check, making sure that AS paths do not conflict with IRR AS
peering information for any candidate for aggregation.

> If we get good feedback, we may automate this to run overnight and keep
> a history.
> 
> Avi Freedman
> [email protected]

Thanks for the information.

Curtis

ps- This thread was not about ANS, but for those following NANOG
activity might who may want it, here is a brief update.  We have not
yet deployed the code needed to generate configurations that take
advantage of aggregates marked in the IRR.  For a rough hint at where
we are headed, see:
  ftp://ftp.ans.net/pub/papers/slides/nanog-sep-1995-proxy-agg.ps