IPv4 BGP Table Reduction Analysis

Brief Report: IP Prefixes Filter by Regional Internet Registries (RIRs) Minimum Allocations Boundaries Methodology

Author: Eduardo Ascenço Reis - <eduardo@intron.com.br>

Version: 2007112901

Time Reference: 2007-10-23-2000

Observations
This document is a general summary of the presentation done (in Portuguese) at the 24ª Meeting of the Brazilian Network Engineering and Operation Work Group (GTER) on 26th Oct 2007, which is focused on Brazilian AS and IP prefixes. [ PDF | Meeting Program ]

1. Introduction

IPv4 BGP table growth is a well known discussed subject that matters to all Autonomous Systems (AS) in the Internet with no size distinction.

IPv4 Prefixes Growth Curve on BGP Table - Route-Views (AS6447 ) Report [ http://bgp.potaroo.net/as6447/ | http://www.cidr-report.org/ ]

The proportional demand for hardware resources in some cases is reaching platforms limits in order to support IPv4 BGP full table operation.

Memory and processing capacity are the two known great villains of this issue. As finite resources, technical solutions to reduce their requirements are under development.

Different methodologies can be applied to reduce the BGP table size. One theoretical example is the algorithm used by CIDR-Report (http://www.cidr-report.org/), in which IP prefixes are aggregated only when precise AS-PATH match occurs. Doing that traffic transit policies are preserved minimizing negative impacts.

This work analyzes IPv4 prefixes filter by Regional Internet Registries (RIRs) minimum allocations boundaries input policy methodology, as discussed at NANOG list.

09/07/07 Route table growth and hardware limits.. Jon Lewis
http://www.merit.edu/mail.archives/nanog/msg02822.html

Barry Greene - bgreene@cisco.com
ftp://ftp-eng.cisco.com/cons/isp/security/Ingress-Prefix-Filter-Templates/T-ip-prefix-filter-ingress-strict-check-v18.txt

2. Methodology

2.1. IPv4 prefixes filter

It was used an IPv4 prefixes filter (Cisco prefix-list format) modified from the one posted by Jon Lewis at NANOG list.

Small modifications were done on Jon Lewis prefix-list to update RIR allocations and to change some bitcount masks.

RIR minimum allocations URLs:
  • AfriNIC - http://www.afrinic.net/documents.htm#templates
  • APNIC - http://www.apnic.net/db/min-alloc.html
  • ARIN - http://www.arin.net/reference/ip_blocks.html#ipv4
  • LACNIC - http://lacnic.net/pt/registro/index.html
  • RIPE - https://www.ripe.net/ripe/docs/ripe-ncc-managed-address-space.html

    • Prefix-list ISP-Ingress-In-Strict: bgp.prefix-list.ISP-Ingress-In-Strict.2007-10-24.txt

    2.2. Laboratory – Logical Diagram

    2.3. Laboratory – Test Flowchart

    2.4. BGP Database

    University of Oregon Route Views Archive Project by David Meyer http://archive.routeviews.org/

    RIB

    Original file: http://archive.routeviews.org/oix-route-views/2007.10/oix-full-snapshot-2007-10-23-2000.dat.bz2 

    $ wc -l oix-full-snapshot-2007-10-23-2000.dat
9010444 oix-full-snapshot-2007-10-23-2000.dat
$

    2.5. /8 Blocks Identification – RIR Distribution

    IANA original data: http://www.iana.org/assignments/ipv4-address-space

    IANA used file (last updated 2007-09-28): ipv4-address-space

    Except for RIR allocations, all other /8 blocks were identified as IANA (legacy, reserved, etc) 

    $ head ipv4-address-space.alloc-RIR.2007-10-24.ok 
000/8 IANA
001/8 IANA
002/8 IANA
003/8 IANA
004/8 IANA
005/8 IANA
006/8 IANA
007/8 IANA
008/8 IANA
009/8 IANA
$

    Generated file with RIR ID: ipv4-address-space.alloc-RIR.2007-10-24.ok

    2.6. Produced FIB from Oregon RIB

    The FIB file was produced from Oregon BGP snapshot (RIB) original data against RIR ID file.

    The algorithm used considered only valid prefixes and choose the best match entry for each destination.

    File Format (fields): PREFIX|ASPATH|BR|RIR

    BR: Identifies if the Prefix is allocated to Brazil (BR) or not (NOBR).

    FIB FILE: oix-full-snapshot-2007-10-23-2000.dat.prefixes-aspath.txt.v9 

    $ head oix-full-snapshot-2007-10-23-2000.dat.prefixes-aspath.txt.v9
3.0.0.0/8|3356 701 703 80|NOBR|IANA
4.0.0.0/8|3356|NOBR|IANA
4.0.0.0/9|3356|NOBR|IANA
4.23.112.0/22|6079 174 21889|NOBR|IANA
4.23.112.0/24|3561 174 21889|NOBR|IANA
4.23.113.0/24|3561 174 21889|NOBR|IANA
4.23.114.0/24|3561 174 21889|NOBR|IANA
4.36.116.0/23|3561 174 21889|NOBR|IANA
4.36.116.0/24|3561 174 21889|NOBR|IANA
4.36.117.0/24|3561 174 21889|NOBR|IANA
$

    BGP Table Size (Number of IPv4 Valid Prefixes): 242,151 

    $ wc -l oix-full-snapshot-2007-10-23-2000.dat.prefixes-aspath.txt.v9
242151 oix-full-snapshot-2007-10-23-2000.dat.prefixes-aspath.txt.v9
$

    2.7. Produced IP Test List

    IP address list to be tested

    The algorithm used to produce the IP list considered only one IPv4 prefix on overlapping cases based on longest match lookup.

    File Format: IP|PREFIX|AS-PATH

    Test File: oix-full-snapshot-2007-10-23-2000.dat.prefixes-aspath.txt.v9.ip-list 

    $ head oix-full-snapshot-2007-10-23-2000.dat.prefixes-aspath.txt.v9.ip-list 
3.0.0.0|3.0.0.0/8|3356 701 703 80
4.0.0.0|4.0.0.0/9|3356
4.23.112.0|4.23.112.0/24|3561 174 21889
4.23.113.0|4.23.113.0/24|3561 174 21889
4.23.114.0|4.23.114.0/24|3561 174 21889
4.36.116.0|4.36.116.0/24|3561 174 21889
4.36.117.0|4.36.117.0/24|3561 174 21889
4.36.118.0|4.36.118.0/24|3561 174 21889
4.67.64.0|4.67.64.0/22|11608 19281
4.78.192.96|4.78.192.96/27|3333 22822 26769
$ 


    $ wc -l oix-full-snapshot-2007-10-23-2000.dat.prefixes-aspath.txt.v9.ip-list 
230962 oix-full-snapshot-2007-10-23-2000.dat.prefixes-aspath.txt.v9.ip-list
$

    A validation test was performed to check each IP address from IP Test List against original FIB (from Route-Views RIB) and against client FIB with no input filter. On both cases 100% IP address tested were Ok (reachable and same AS-PATH).

    2.8. BGP Table Reduction Test

    The ISP-Ingress-In-Strict prefix-list was applied in the input policy of the client router to test BGP table reduction efficiency and to estimate possible impacts.

    This experiment considers that the client router has default route (0/0) pointing to Null 0. In other words, any IP address destination should be resolved by routing lookup.

    3. Results

    3.1. Filtered Prefixes Verification

    Extract output from show ip bgp neighbor command on client router. Laboratory - Filtered Prefixes Verification

    In this case the soft-reconfiguration inbound command was used to highlight the filtered prefixes number and associated memory.

    3.2. Efficiency Analysis

    3.3. Impact Analysis

    3.4. Impact Analysis per RIR

    3.5. Affected IPv4 Prefixes Distribution

    3.6. Unreachable IPv4 Prefixes Distribution per RIR


    		Total AfriNIC APNIC ARIN IANA LACNIC RIPE

    		Prefixes % Prefixes % Total Prefixes % Total Prefixes % Total Prefixes % Total Prefixes % Total Prefixes % Total
    /20 195 0.7
    		0
    		0
    		0
    		0
    		0 195 100
    /21 2066 7.41
    		0
    		0 1300 62.92
    		0 400 19.36 366 17.72
    /22 3761 13.49
    		0 633 16.83 1530 40.68
    		0 537 14.28 1061 28.21
    /23 3502 12.56 168 4.8 323 9.22 1601 45.72
    		0 205 5.85 1205 34.41
    /24 18267 65.51 757 4.14 2299 12.59 8396 45.96
    		0 1392 7.62 5423 29.69
    /25 52 0.19
    		0 8 15.38 25 48.08 1 1.92 3 5.77 15 28.85
    /26 12 0.04
    		0 5 41.67 2 16.67
    		0
    		0 5 41.67
    /27 10 0.04
    		0 4 40 3 30 2 20
    		0 1 10
    /28 3 0.01
    		0 1 33.33
    		0 2 66.67
    		0
    		0
    /29 4 0.01
    		0 1 25
    		0 3 75
    		0
    		0
    /30 13 0.05
    		0 1 7.69
    		0 12 92.31
    		0
    		0















    TOTAL 27885
    		925
    		3275
    		12857
    		20
    		2537
    		8271

    3.7. IPv4 Prefixes Distribution per RIR

    3.8. IPv4 Prefixes Accounting

    Expanded Table


    		 OIX BR AfriNIC APNIC ARIN IANA LACNIC RIPE
    Mask Prefixes % Total BR % OIX AfriNIC % OIX APNIC % OIX ARIN % OIX IANA % OIX LACNIC % OIX RIPE % OIX
    /8 19 0.01
    		0
    		0 1 5.26
    		0 18 94.74
    		0
    		0
    /9 9 0
    		0
    		0
    		0
    		0 9 100
    		0
    		0
    /10 16 0.01
    		0
    		0 4 25 2 12.5 4 25
    		0 6 37.5
    /11 38 0.02
    		0
    		0 8 21.05 15 39.47 2 5.26
    		0 13 34.21
    /12 135 0.06
    		0 1 0.74 38 28.15 42 31.11 24 17.78
    		0 30 22.22
    /13 273 0.11
    		0 4 1.47 95 34.8 72 26.37 43 15.75 1 0.37 58 21.25
    /14 484 0.2
    		0 1 0.21 139 28.72 128 26.45 87 17.98 5 1.03 124 25.62
    /15 952 0.39 14 1.47 4 0.42 223 23.42 283 29.73 169 17.75 22 2.31 251 26.37
    /16 9799 4.05 175 1.79 31 0.32 1833 18.71 1091 11.13 5339 54.49 266 2.71 1239 12.64
    /17 4242 1.75 128 3.02 18 0.42 1134 26.73 1171 27.6 622 14.66 212 5 1085 25.58
    /18 6811 2.81 291 4.27 39 0.57 2078 30.51 2261 33.2 581 8.53 478 7.02 1374 20.17
    /19 14727 6.08 223 1.51 77 0.52 3522 23.92 4679 31.77 1009 6.85 1368 9.29 4072 27.65
    /20 17650 7.29 426 2.41 211 1.2 4877 27.63 6434 36.45 1380 7.82 1062 6.02 3686 20.88
    /21 15766 6.51 382 2.42 139 0.88 3443 21.84 5446 34.54 1625 10.31 1861 11.8 3252 20.63
    /22 20221 8.35 194 0.96 297 1.47 4210 20.82 7967 39.4 2299 11.37 1340 6.63 4108 20.32
    /23 21115 8.72 198 0.94 230 1.09 3688 17.47 8426 39.91 2840 13.45 971 4.6 4960 23.49
    /24 126446 52.22 902 0.71 1343 1.06 28017 22.16 44539 35.22 22042 17.43 7739 6.12 22766 18
    /25 899 0.37 10 1.11
    		0 504 56.06 166 18.46 133 14.79 32 3.56 64 7.12
    /26 1126 0.46 4 0.36 1 0.09 658 58.44 255 22.65 133 11.81 25 2.22 54 4.8
    /27 624 0.26
    		0
    		0 315 50.48 156 25 115 18.43 11 1.76 27 4.33
    /28 270 0.11 1 0.37
    		0 120 44.44 19 7.04 54 20 40 14.81 37 13.7
    /29 194 0.08
    		0
    		0 88 45.36 18 9.28 76 39.18 3 1.55 9 4.64
    /30 264 0.11
    		0
    		0 68 25.76 21 7.95 164 62.12 1 0.38 10 3.79
    /32 71 0.03
    		0
    		0 2 2.82 23 32.39 36 50.7 1 1.41 9 12.68

















    TOTAL 242151 100 2948 1.22 2396 0.99 55065 22.74 83214 34.36 38804 16.02 15438 6.38 47234 19.51

    3.9. Analysis Files

    3.9.1. Client Partial IPv4 BGP Table (RIR minimum allocation filter) Generated File - (FIB)

  • route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered 

    • $ 
$ head route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered
3.0.0.0/8|3356 701 703 80|NOBR|IANA
4.0.0.0/8|3356|NOBR|IANA
4.0.0.0/9|3356|NOBR|IANA
4.23.112.0/22|6079 174 21889|NOBR|IANA
4.23.112.0/24|3561 174 21889|NOBR|IANA
4.23.113.0/24|3561 174 21889|NOBR|IANA
4.23.114.0/24|3561 174 21889|NOBR|IANA
4.36.116.0/23|3561 174 21889|NOBR|IANA
4.36.116.0/24|3561 174 21889|NOBR|IANA
4.36.117.0/24|3561 174 21889|NOBR|IANA
$ 
$ wc -l route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered
150832 route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered
$

    3.9.2. IP Test - Ok List File

  • route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.Ok 

    • $ 
$ head route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.Ok
3.0.0.0|3.0.0.0/8|3356 701 703 80|IANA|NOBR|3.0.0.0/8|3356 701 703 80
4.0.0.0|4.0.0.0/9|3356|IANA|NOBR|4.0.0.0/9|3356
4.23.112.0|4.23.112.0/24|3561 174 21889|IANA|NOBR|4.23.112.0/24|3561 174 21889
4.23.113.0|4.23.113.0/24|3561 174 21889|IANA|NOBR|4.23.113.0/24|3561 174 21889
4.23.114.0|4.23.114.0/24|3561 174 21889|IANA|NOBR|4.23.114.0/24|3561 174 21889
4.36.116.0|4.36.116.0/24|3561 174 21889|IANA|NOBR|4.36.116.0/24|3561 174 21889
4.36.117.0|4.36.117.0/24|3561 174 21889|IANA|NOBR|4.36.117.0/24|3561 174 21889
4.36.118.0|4.36.118.0/24|3561 174 21889|IANA|NOBR|4.36.118.0/24|3561 174 21889
4.67.64.0|4.67.64.0/22|11608 19281|IANA|NOBR|4.67.64.0/22|11608 19281
4.79.181.0|4.79.181.0/24|812 10310 14780|IANA|NOBR|4.79.181.0/24|812 10310 14780
$ 
$ wc -l route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.Ok
159520 route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.Ok
$

    3.9.3. IP Test - SubOptimal List File

  • route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.SubOptimal 

    • $ head route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.SubOptimal
4.78.192.96|4.78.192.96/27|3333 22822 26769|IANA|NOBR|4.0.0.0/9|3356
4.78.192.112|4.78.192.112/28|3333 22822 26769|IANA|NOBR|4.0.0.0/9|3356
8.3.16.0|8.3.16.0/25|3549 22822 26769|IANA|NOBR|8.0.0.0/9|3356
24.25.3.0|24.25.3.0/24|12956 7843 11426|ARIN|NOBR|24.25.0.0/19|3356 11426
24.25.4.0|24.25.4.0/23|12956 7843 11426|ARIN|NOBR|24.25.0.0/19|3356 11426
24.25.6.0|24.25.6.0/23|12956 7843 11426|ARIN|NOBR|24.25.0.0/19|3356 11426
24.25.8.0|24.25.8.0/21|12956 7843 11426|ARIN|NOBR|24.25.0.0/19|3356 11426
24.25.12.0|24.25.12.0/23|12956 7843 11426|ARIN|NOBR|24.25.0.0/19|3356 11426
24.25.16.0|24.25.16.0/22|12956 7843 11426|ARIN|NOBR|24.25.0.0/19|3356 11426
24.25.18.0|24.25.18.0/24|12956 7843 11426|ARIN|NOBR|24.25.0.0/19|3356 11426
$ 
$ wc -l route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.SubOptimal
43557 route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.SubOptimal
$

    3.9.4. IP Test - Unreachable List File

  • route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.Unreachable.info 

    • $ head route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.Unreachable.info
24.28.32.0|24.28.32.0/21|3356 11427|ARIN|NOBR
24.28.40.0|24.28.40.0/21|3356 11427|ARIN|NOBR
24.32.16.0|24.32.16.0/21|3356 6395 21615|ARIN|NOBR
24.32.24.0|24.32.24.0/21|3356 19108|ARIN|NOBR
24.32.32.0|24.32.32.0/21|3356 19108|ARIN|NOBR
24.32.40.0|24.32.40.0/21|3356 19108|ARIN|NOBR
24.32.48.0|24.32.48.0/21|3356 6395 21615|ARIN|NOBR
24.32.56.0|24.32.56.0/23|3356 19108|ARIN|NOBR
24.32.58.0|24.32.58.0/23|7018|ARIN|NOBR
24.32.60.0|24.32.60.0/23|7018 22773 19108 21615|ARIN|NOBR
$ 
$ 
$ wc -l route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.Unreachable.info
27885 route-server.bgp-dump.partial-table-filter-rir.2007-10-23-2000.dat.prefixes-aspath.txt.v9.recovered.Unreachable.info
$

    4. Conclusions

    Although IPv4 prefixes filter by RIRs minimum allocations boundaries methodology has a good efficiency (around 40%) reducing BGP table size, care should be taken in its general adoption. The estimated number of affect prefixes considering suboptimal routing and unreachable destinations are also high (around 30%).

    When considering that any AS in the Internet can use this methodology even an AS with all powerful routers that can support full BGP table can have connectivity problems with the AS that use these filters.

    RIR have an important role in this situation to educate local AS to avoid unnecessary specific advertisements and whenever possible to make the advertisement of the prefix corresponding to the allocated CIDR block (or the respective minimum allocation size for AS with less specific CIDR).

    It is important to consider that any methodology to reduce BGP IPv4 table size is likely to be associated with loss of information which can result in connection problems in the Internet. The need for BGP table reduction solutions is a current fact, but general adoption calls for methodologies well defined and accepted by Internet administrators (AS) as a whole (e.g. with RFC) in order to avoid routing inconsistency.

    Although representing less than 1% of all suboptimal and unreachable prefixes, /20 prefixes call attention because of their mask size to be expected as normal. In this experiment all /20 affected prefixes are from 2 RIPE CIDR (62/8 and 212/7) with /19 longest prefix, which data could eventually be used by RIPE to reviews these CIDR policy allocations. This is only one use example of applications that can be derived from analysis like this one.

    Regarding the affected prefixes distribution analysis, /24 prefixes highlights with more than 65% of all suboptimal and unreachable prefixes. Also Oregon full BGP table shows that /24 prefixes represents more than 50% of all IPv4 BGP table. These data is significant and would suggests that a dedicated analysis about /24 prefixes could help to understand IPv4 BGP table growth and maybe it shows a way about how to interfere in this process in order to even reduce the current table size.

    5. Thanks

    Special thanks to CTBC Multimidia (AS27664) for sharing laboratory resources.

    Any comments ? Eduardo Ascenço Reis - <eduardo@intron.com.br>