BGP Routing Table Analysis

Introduction

In the early days of the Internet very little examination of the contents of the Routing Table had been carried out. While there were many discussions about the size of the table, only a one or two efforts at recording the size and contents of the table had been made.

With the introduction of CIDR and the transition from classful to classless addressing, the CIDR Report was instigated by Tony Bates as an effort to encourage ISPs to drop classful prefixes in favour of classless aggregates. The CIDR Report looked at the Internet Routing Table on a global scale and listed the top 30 ISPs who were contributing to the size of the table.

The CIDR Report was all there really was available to the general public, and examination of the table on a global scale ignored regional variations. The Routing Report was born out of this need.

Background

The Routing Report takes a BGP feed from an Internet router hosted by APNIC at the DIX-IE (formerly NSP-IXP2) facility in Japan. This router has a view of the full Internet Routing Table as received from APNIC's transit providers at DIX-IE.

Initially the analysis was targeted at the Asia Pacific Region, APNIC's service region, giving statistics on the Routing Table size and the APNIC region ISP's contribution to the Routing Table.

However, other regions showed interest in the details delivered by the report, and very soon it was extended to include other RIR regions, most recently with AfriNIC joining the RIR system. The report is now sent to the major operations lists around the world, on a request basis.

The report is produced on a weekly basis, with the mail shot based on data captured at 4am Australian Eastern Standard Time (+10GMT) every Saturday. The report is actually run on a daily basis, with a specialist mailing list (bgp-stats at lists.apnic.net) as the destination for interested subscribers.

The weekly mailshot is currently sent to the NANOG, APOPS, RIPE Routing Working Group, AfNOG and AusNOG mailing lists.

Explaining the Report

This section explains the contents of the report based on the headings contained in it.

Analysis Summary

• BGP Routing Table Entries Examined

  Lists the number of unique routing entries in the Internet Routing Table

• Prefixes after Maximum Aggregation

  Lists how large the Internet Routing Table would be after aggregating as much as possible. No attention is paid to origin AS or AS paths, so no allowance is made for deaggregation requirements to aid traffic engineering for multihoming

  For example, if 172.16.0.0/24, 172.16.8.0/21 and 172.16.0.0/16 are all present in the BGP table, "maximum aggregation" will remove the 172.16.0.0/24 and the 172.16.8.0/21 announcements, leaving just 172.16.0.0/16. The origin AS and AS PATH of each of these announcements is ignored in making this calculation.

• Deaggregation Factor

  Lists the ratio of "Total BGP Table" and "Maximum Aggregation". A perfectly aggregated BGP table would give a Deaggregation Factor value of 1.0.

• Unique Aggregates Announced to Internet

  Lists how large the Internet Routing Table would be after aggregating the prefixes present in the Internet Routing Table by origin AS.

  For example, if 172.16.8.0/21 and 172.16.0.0/16 is originated by AS100, we'd have just one unique aggregate, 172.16.0.0/16. However, if 172.16.8.0/21 is originated by AS200 instead, then there would be two unique aggregates. Also, if AS100 originates 172.16.0.0/16 and 172.17.0.0/16, then we'd have just one unique aggregate, 172.16.0.0/15.

• Total ASes present in the Internet Routing Table

  Lists the total number of 16-bit ASNs visible in the Internet Routing Table.

• Prefixes per ASN

  Lists the average number of prefixes announced per 16-bit ASN.

• Origin-only ASes present in the Internet Routing Table

  Lists the ASNs that only originate prefixes - they do not provide transit to any other ASN in this view.

• Origin ASes announcing only one prefix

  Lists the origin ASNs which announce just one prefix to the Internet

• Transit ASes present in the Internet Routing Table

  Lists those ASes which provide transit to other ASNs in the Internet.

• Transit-only ASes present in the Internet Routing Table

  Lists those ASes which are only providing transit to other ASNs - they do not originate any prefixes at all.

• Average AS path length visible in the Internet Routing Table

  Lists the average AS depth of the Internet (including prepends)

• Max AS path length visible

  Lists the longest AS path (including prepends) visible in the Internet Routing Table.

• Max AS path prepend

  Lists the largest AS path prepend seen in the Internet Routing Table and which ASN is prepended that often. Intended to highlight silly prepends.

• Prefixes from unregistered ASNs in the Routing Table

  Lists prefixes being originated by either private, reserved, or unallocated ASNs.

• Unregistered ASNs in the Routing Table

  Counts all the private, reserved or unallocated ASNs, including prepends.

• Number of 32-bit ASNs allocated by the RIRs

  Counts the number of 32-bit ASNs which have been distributed by the RIRs.

• Prefixes from 32-bit ASNs in the Routing Table

  Counts the number of prefixes being originated from 32-bit ASNs. Router does not yet support 32-bit ASNs, so this simply counts the prefixes being originated by AS23456.

• Special use prefixes present in the Routing Table

  Lists any private or special use address space (as defined in RFC 3330) being announced to the Internet Routing Table. At this stage, the analysis lists 0/8, 10/8, 127/8, 169.254/16, 172.16/12, 192.0.2/24, 192.168/16, 198.18/15 and 224/3.

• Prefixes being announced from unallocated address space

  Lists prefixes being announced from address space which is still in the IANA reserved pool. This is basically all the /8s listed as "IANA Reserved" as well as address blocks from the former B-space (128/2) and the first block of C-space (192/8) for which no registration information can be found.

• Number of addresses announced to Internet

  Lists the amount of address space being announced to the Internet. As well as a 32-bit integer, it is also displayed in more human readable terms using natural address mask sizes. Should the default route be announced, this is ignored in the calculation of addresses announced, as that announcement is an error, and it isn't desirable for the tally to be skewed by this error.

• Percentage of available address space announced

  Lists how much of the total usable IPv4 address space is announced to the Internet. Usable address space is everything apart from most of the special use address space described in RFC 3330 and specifically documented above.

• Percentage of allocated address space announced

  Lists how much of the address space which has been assigned to endsites and allocated to the RIRs is announced to the Internet.

• Percentage of available address space allocated

  Lists how much of the available address space has been assigned to endsites and allocated to RIRs - this shows how close to we are to the exhaustion of the IPv4 address pool.

Registry Region Analysis Summary

• Prefixes being announced by RIR Region ASes

  Lists the number of unique routing entries being announced by ASNs which are listed as being located in the service region covered by the specified RIR.

• Total RIR Prefixes after Maximum Aggregation

  Lists the contribution to the Internet Routing Table after aggregating by RIR region origin ASN - no attention is paid to different paths, so no allowance is made for deaggregation for traffic engineeing to aid multihoming.

• Prefixes being announced by RIR address blocks

  Lists the number of unique routing entries being announced from address blocks which have been allocated to the RIR.

• Unique Aggregates Announced from the RIR address blocks

  Lists the contribution to the Internet Routing Table after aggregating just the prefixes from the address blocks allocated to the RIR - it ignores the originating ASN.

• RIR Region origin ASes present in the Internet Routing Table

  Lists the number of ASNs from the RIR region visible in the Internet Routing Table.

• RIR Origin ASes announcing only one prefix

  Lists the origin ASNs from the RIR region which announce just one prefix to the Internet.

• RIR Transit ASes present in the Internet Routing Table

  Lists those ASes from the RIR region which provide transit to other ASNs in the Internet.

• Average RIR Region AS path length visible in the Internet Routing Table

  Lists the average AS depth of the Internet in the RIR region only.

• Max RIR AS path length visible

  Lists the longest AS path (including pre-pends) visible in the Internet Routing Table in the RIR region only

• Unregistered ASNs in the Routing Table

  Counts all the private, reserved or unallocated ASNs, including prepends.

• Number of RIR region addresses announced to Internet

  Lists the amount of address space being announced to the Internet from the RIR region. As well as a 32-bit integer, it is also displayed in more human readable terms using natural address mask sizes.

• Percentage of available RIR address space announced

  Lists how much of the total usable IPv4 address space allocated to the RIR is announced to the Internet. Usable address space is everything apart from most of the special use address space described in RFC 3330.

• RIR AS Blocks

  Lists all the AS blocks which were originally allocated to the RIR. Since the completion of the recent ERX transfer project, there are now substantial holes in these blocks - documentation of these holes can be found on the RIR websites.

• RIR Address Blocks

  Lists all the address blocks which have been allocated to the RIR.

RIR Region Per AS Prefix Count Summary

This section lists the top 20 ASNs per RIR service region and their contribution to the Internet Routing Table. This is not the same as listing the largest ISPs, but those who are contributing most prefixes to the Internet. The columns list the ASN and the registered name of the ASN holder, the number of prefixes being announced, and the equivalent size in units of /20 blocks, and the number of prefixes they would announce if the ASN operator attempted to aggregate their announcements better.

Global Per AS Maximum Aggregation Summary

This section lists the top 20 ASNs who would contribute most to reducing the size the Internet Routing Table if they would perform better aggregation of their BGP announcements.

List of Unregistered Origin ASNs (Global)

This section lists any unallocated ASNs in use on the Internet. Mostly this captures private ASNs, but can also capture unallocated or ASNs still in the IANA reserved pool.

Advertised Unallocated Addresses

This section lists any prefixes being announced from unallocated address space.

Number of prefixes announced per prefix length (Global)

This section lists how many prefixes are being announced per prefix length in the Internet Routing Table

Advertised prefixes smaller than registry allocations

This section lists the top 20 ASNs which are announcing prefixes smaller than the minimum allocations made by the RIRs. It indicates the top deaggregators in the Internet.

Number of /24s announced per /8 block (Global)

This section lists how many /24s are being announced out of each of the /8 address blocks. It is designed to show where all the /24s in the Internet Routing Table are coming from.

Other Details

The analysis software generally assumes it is going to receive a file which is the snapshot of BGP feed from a Cisco IOS router. Generally a captured "show ip bgp summary" is sufficient.

The analysis software will take the BGP table from the router, and process the best paths only, ignoring alternative paths. The idea is that it makes most sense to use the paths that the router considers best, rather than anything else.

If the feed provided to the router has no best path in it at all (for example, it might be the BGP feed received from a peer only), the software will process that in its stead. Where multiple paths to the destination are available, with no best path chosen by the router, the software will take the first path in the list (basically the oldest path as the router sees it).

Summary

It is hoped that the data that the Routing Report supplies is useful to service providers and Internet operations observers. While the original aim was to encourage aggregation on a regional basis, it now has a much larger role of providing info on various Internet metrics.

Caveats

I really do hope that the analysis is bug free. It wouldn't surprise me if there are errors though. If you find any, please let me know.

Some of the older reports had some small errors in them - while I've fixed errors in the software, I haven't gone back and re-run the analysis.

IPv6

I have no plans as yet to look at the IPv6 Routing Table. If you really need to see what it is doing, please look at the IPv6 version of the CIDR Report.

Acknowledgements

Acknowledgements go to the many people who have reported bugs in the analysis software, to Tony Bates for original inspiration, and to Geoff Huston for many constructive suggestions and ideas.

Also, appreciative thanks to APNIC for permitting access to their Japanese node router, and for providing the server to run the analysis software and store the copious quantity of data it produces.

Philip Smith

October 2009