So, is it getting worse?

Over the past few posts (the good and the bad), I have considered the various causes for a non-optimal Internet Routing Table. And now on to the question of whether it is getting worse.

The graph above (source) shows the deaggregation by Enterprise ASes. Enterprises represent the vast majority of the edge of the Internet. As such, they are by far the largest source of deaggregation. According to this, the level of deaggregation has not increased significantly.

However, the following graph (source) shows a significant increase in the deaggregation factor.

The discrepancy appears to be as a result of definition. The 1st graph is based on allocations (maximum aggregation is bound by RIR allocation size) , while the second is based on best-case aggregation (idealised aggregation to maximum possible per AS). These are very different. It is therefore getting worse and has increased from 1.27 in 1999 to 2.18 today. This represents an increase of over 70% in deaggregation.

What solutions are there. Well – a whole whack have been developed. However, how many are viable? This humorous post actually captures a stack of the issues.

Further Reading

BGP Aggregation & The Deaggregation Report

Evolution of Internet Address Space Deaggregation: Myths and Reality

CIDR REPORT

This is part of a series of posts – The Lisp Papers.

In the previous post, I considered the legitimate uses of deaggregation. Here are some examples of deaggregation for either indefensible reasons or through simple stupidity.

The New Internet

A deaggregation factor, developed by Philip Smith and reported in the BGP Routing Table Analysis (current prefixes / prefixes after maximum aggregation), shows to what extent an allocation is deaggregated.

Regional Internet Registry	Total Prefixes	Total Prefixes after Maximum Aggregation	Deaggregation factor
Total	332,835	152,832	2.18
APNIC	81,254	27,865	2.92
ARIN	136,028	70,167	1.94
RIPE	76,560	44,341	1.73
LACNIC	30,156	7,154	4.22
AfriNIC	7,441	1,886	3.95

The “new” Internet (APNIC – 2.92, AfriNIC – 3.95 and LACNIC – 4.22) have reasons for deaggregating but the scale is significant. For every prefix they should advertise, LACNIC’s subscribers produce 4.22 prefixes.

Fragmented address allocation

As discussed earlier, with unlimited addressing, the 35575 active ASes could be allocated a single large address block. This would be the lower bound for addressing allocations. As the address pool has shrunk, so the rules governing the allocation of addressing have tightened. The unintended consequence of this is that poorly administered and documented networks have not been able to justify large address allocations. This has meant that they have been issued with smaller and smaller blocks, and have in turn requested address allocations more frequently, all of which has been fragmented. The top 100 unaggregatable ASes (no aggregates can be created with any of their advertised addresses) add over 3k prefixes:

Unaggregateable ASes Top 100

AS	AS Name	Prefixes	After Aggregation	# removed
	Top 100 Total	3088
786	JANET The JANET IP Service	190	190	0
33668	CMCS - Comcast Cable Communications, Inc.	95	95	0
158	ERI-AS - Ericsson Network Systems, Inc.	88	88	0
7016	CCCH-3 - Comcast Cable Communications Holding	74	74	0
3307	BANETELE-NORWAY BaneTele AS (formerly Enitel)	59	59	0
17561	SERVICENET-AP Internet service provision to W	51	51	0
3248	SIL-AT SILVER SERVER GmbH	49	49	0
2554	IDC2554 Yahoo Japan Corporation	46	46	0
13649	ASN-VINS - ViaWest	46	46	0
12312	ECOTEL ecotel communication ag	42	42	0
28571	Universidade de Sao Paulo - USP	42	42	0
33660	CMCS - Comcast Cable Communications, Inc.	42	42	0
16265	LEASEWEB LEASEWEB AS	40	40	0
5413	AS5413 Vialtus Solutions Ltd.	39	39	0
12654	RIPE-NCC-RIS-AS RIPE NCC RIS project	39	39	0
2519	VECTANT VECTANT Ltd.	38	38	0
766	REDIRIS RedIRIS Autonomous System	38	38	0
29550	SIMPLYTRANSIT Simply Transit Ltd	37	37	0
553	BELWUE Landeshochschulnetz Baden-Wuerttemberg	36	36	0
8473	BAHNHOF Bahnhof AB	35	35	0
9644	SKTELECOM-NET-AS SK Telecom., Ltd.	35	35	0
29308	GSD-AS Gesellschaft fuer Systemforschung	35	35	0
4181	TDS-AS - TDS TELECOM	34	34	0
6079	RCN-AS - RCN Corporation	34	34	0
1241	FORTHNET-GR FORTHnet	33	33	0
21844	THEPLANET-AS - ThePlanet.com Internet Service	32	32	0
25668	CIPHERKEY - Cipherkey Exchange Corp.	32	32	0
2381	WISCNET1-AS - WiscNet	31	31	0
12843	TELEMAXX TelemaxX Telekommunikation GmbH Auto	31	31	0
13432	ASN-CXA-LV-13432-CBS - Cox Communications Inc	31	31	0
30217	DESYNC - Desync Networks	31	31	0
16445	ISPACE - Wave2Wave Communications, Inc	30	30	0
25577	C4L-AS C4L main AS	30	30	0
33654	CMCS - Comcast Cable Communications, Inc.	30	30	0
2129	HP-EUROPE-AS-TRADE Hewlett-Packard	29	29	0
2527	SO-NET So-net Entertainment Corporation	29	29	0
7497	CSTNET-AS-AP Computer Network Information Cen	28	28	0
9650	CITEC-AU-AP QLD Government Business (IT)	28	28	0
15576	NTS NTS workspace AG, Bern, Switzerland	28	28	0
16718	EMBARQ-HMBL - Embarq Corporation	28	28	0
19169	Telconet S.A	28	28	0
6428	CDM - CDM	27	27	0
9891	CSLOX-IDC-AS-AP CS LOXINFO Public Company Lim	27	27	0
12350	VTX-NETWORK VTX Services SA	27	27	0
16097	HLKOMM HL komm Telekommunikations GmbH	27	27	0
33665	CMCS - Comcast Cable Communications, Inc.	27	27	0
46837	VRCT-BOS - SunGard VeriCenter Inc	27	27	0
2518	BIGLOBE NEC BIGLOBE, Ltd.	26	26	0
4691	DTI Dream Train Internet Inc.	26	26	0
6171	WORLDGATE - WorldGate	26	26	0
6315	XMISSION - XMission, L.C.	26	26	0
17402	EMBARQ-CHSK - Embarq Corporation	26	26	0
33655	CMCS - Comcast Cable Communications, Inc.	26	26	0
2611	BELNET AS for BELNET, The Belgian National Re	25	25	0
3265	XS4ALL-NL XS4ALL	25	25	0
13000	LEON-AS Leon sp. z o.o.	25	25	0
32613	IWEB-AS - iWeb Technologies Inc.	25	25	0
40020	FARMERS-TELECOMMUNICATIONS-COOPERATIVE-INC -	25	25	0
9947	SIMNET-AS-KR Simulation Multimedia Network	24	24	0
25180	EXPONENTIAL-E-AS Exponential-e Ltd	24	24	0
31406	ESIDE Bucharest, Romania	24	24	0
790	EUNETFI EUnet Finland	23	23	0
4264	CERNET-ASN-BLOCK - California Education and R	23	23	0
31313	STS Serviciul de Telecomunicatii Speciale	23	23	0
31400	ACCELERATED-IT Accelerated IT Services GmbH	23	23	0
33656	CMCS - Comcast Cable Communications, Inc.	23	23	0
3475	LANT-AFLOAT - Navy Network Information Center	22	22	0
7341	VELOCITY - The Velocity Network	22	22	0
15623	CYBERLINK Cyberlink AG	22	22	0
29551	HGCOMP-ASN Aixit GmbH	22	22	0
3249	ESTPAK Elion Enterprises Ltd.	21	21	0
8400	TELEKOM-AS TELEKOM SRBIJA a.d.	21	21	0
12968	CDP Crowley Data Poland, sp. z o.o.	21	21	0
14910	EMBARQ-FTMY - Embarq Corporation	21	21	0
16245	NGDC NetGroup A/S	21	21	0
20500	GRIFFIN Griffin Internet European Network	21	21	0
25176	AC-NET LaNet Vasterbotten Data och Tele AB	21	21	0
37914	UNIVNET Advanced Software Technology & Mechat	21	21	0
47965	SATLYNX_AG Satlynx AG	21	21	0
1761	TGSCNET - General Services Commission	20	20	0
1811	CSC-300-AS1810-AS1815 - Computer Sciences Cor	20	20	0
11252	ISU-NET-AS - Idaho State University	20	20	0
14155	RURAL-TELEPHONE-SVCCO - Rural Telephone Servi	20	20	0
22958	FIDELITY-001 - Fidelity Access Networks, LLC	20	20	0
23481	HCTC-LINK1 - Hill Country Telephone Cooperati	20	20	0
30081	CACHENETWORKS - CacheNetworks, Inc.	20	20	0
31822	CITY-UNIVERSITY-OF-NEW-YORK - City University	20	20	0
42652	DELUNET inexio Informationstechnologie und Te	20	20	0
378	MACHBA-AS ILAN	19	19	0
1741	FUNETAS FUNET autonomous system	19	19	0
1901	EUNETAT-AS eTel Austria Gesmbh u. CO KG	19	19	0
5669	VIA-NET-WORKS-AS PSINet Europe / VIA NET.WORK	19	19	0
8680	Cable & Wireless Channel Island Network	19	19	0
9167	WEBPARTNER WEBPARTNER A/S is a Danish Interne	19	19	0
9708	PKNU-AS Pukyong National University	19	19	0
12578	APOLLO-AS LATTELEKOM-APOLLO	19	19	0
13193	ASN-NERIM Nerim SAS	19	19	0
14793	API-DIGITAL - API Digital Communications Grou	19	19	0
16095	JAYNET jay.net a/s	19	19	0
18117	HARBOURMSP-AU-AP Harbour MSP Pty. Ltd	19	19	0

.

In all, over 10,000 ASes advertise 2 or more ASes of which none are aggregatable. This group of ASes add over 40k routes. The entire list of Unaggregateable ASes is available here (an up to date source is available at CIDR report)

For detailed information regarding the prefixes advertised, enter an AS here to generate an aggregation report for the AS – e.g. “786″

Poor configuration

There are two other reasons that contribute to the problem. The first is a lack of knowledge of CIDR. The application of /16 and /24 to allocated aggregates (“to match the class”) by well-meaning but misguided staff is a source of deaggregation.

Another “reason” put forward is fear of Denial of Service attacks by neighbouring ISPs falsely announcing longer prefixes. This is a beggar thy neighbour policy, as all routers have to carry these additional routes. Taken to an extreme, all networks should advertise /32s, as these could never be hijacked by longer prefixes. Of course, this would result in over a billion routes, so clearly not a serious recommendation! Even deaggregating everything to /24 will result in over 5 million prefixes.

How many prefixes do top deaggregators contribute? The top 1% of deaggregators inject 10% of the prefixes in the Internet. Deaggregating ASes contribute nearly 50% of the routing table size. At NANOG 50, the following example of routes direct from your favourite coffeemaker, Starbucks:

route-server>sh ip bgp 98.96.0.0/14 longer-prefixes | i 98.96|98.97

*  98.96.0.0/17     12.123.29.249                          0 7018 ?
*  98.96.0.0/16     12.123.29.249                          0 7018 ?
*  98.96.0.0/15     12.123.29.249                          0 7018 ?
*  98.96.0.0/14     12.123.29.249                          0 7018 ?
*  98.96.41.0/24    12.123.29.249                          0 7018 ?
*  98.96.74.0/24    12.123.29.249                          0 7018 ?
*  98.96.86.0/24    12.123.29.249                          0 7018 ?
*  98.96.100.0/24   12.123.37.250                          0 7018 ?
*  98.96.108.0/24   12.123.29.249                          0 7018 ?
*  98.96.149.0/24   12.123.29.249                          0 7018 ?
*  98.96.247.0/24   12.123.29.249                          0 7018 ?
*  98.97.114.0/24   12.123.29.249                          0 7018 ?
*  98.97.116.0/24   12.123.29.249                          0 7018 ?
*  98.97.117.0/24   12.123.29.249                          0 7018 ?
*  98.97.118.0/24   12.123.29.249                          0 7018 ?
*  98.97.131.0/24   12.123.17.244                          0 7018 ?
*  98.97.140.0/24   12.123.29.249                          0 7018 ?
*  98.97.141.0/24   12.123.29.249                          0 7018 ?
*  98.97.142.0/24   12.123.29.249                          0 7018 ?
*  98.97.144.0/24   12.123.29.249                          0 7018 ?
*  98.97.149.0/24   12.123.29.249                          0 7018 ?
*  98.97.150.0/24   12.123.29.249                          0 7018 ?
*  98.97.152.0/24   12.123.29.249                          0 7018 ?
*  98.97.154.0/24   12.123.29.249                          0 7018 ?
*  98.97.155.0/24   12.123.29.249                          0 7018 ?
*  98.97.156.0/24   12.123.29.249                          0 7018 ?
*  98.97.160.0/24   12.123.29.249                          0 7018 ?
*  98.97.161.0/24   12.123.29.249                          0 7018 ?
*  98.97.162.0/24   12.123.29.249                          0 7018 ?
*  98.97.164.0/24   12.123.29.249                          0 7018 ?
*  98.97.168.0/24   12.123.29.249                          0 7018 ?
*  98.97.169.0/24   12.123.29.249                          0 7018 ?
*  98.97.174.0/24   12.123.13.241                          0 7018 ?
*  98.97.176.0/24   12.123.29.249                          0 7018 ?
*  98.97.209.0/24   12.123.29.249                          0 7018 ?
*  98.97.210.0/24   12.123.29.249                          0 7018 ?
*  98.97.214.0/24   12.123.29.249                          0 7018 ?
*  98.97.217.0/24   12.123.29.249                          0 7018 ?
*  98.97.222.0/24   12.123.29.249                          0 7018 ?
*  98.97.226.0/24   12.123.29.249                          0 7018 ?
*  98.97.236.0/24   12.123.29.249                          0 7018 ?
*  98.97.249.0/24   12.123.29.249                          0 7018 ?
*  98.97.250.0/24   12.123.29.249                          0 7018 ?

I’ll leave it up to you to decide whether there could be any legitimate reason for advertising their routing in this fashion.

So, we’ve looked at two categories of deaggregation, the “good” and “bad”. With a classic sense of the cliché, the next blog will consider how extensive the problem really is, a.k.a. the “ugly”.

This is part of a series of posts – The Lisp Papers.

In the previous post, I looked at a number of causes for routing table growth. In this post, I will consider Multi-homing and Traffic engineering. These are legitimate causes of de-aggregation and add the largest number of deaggregated prefixes to the table.

Multi-homing

According to a number of authorities (Cisco, Internet Research Task Force, IEEE) a major factor in the growth of routing tables is quite simple. End-points are multi-homing. This means that enterprises are connecting to multiple Service Providers. In the example below, resilient connectivity is compared with multihoming. Although the complexity is higher and an additional load is placed on the internet BGP tables, multihoming is popular because of the advantages. Clearly, the flexibility and additional fault-tolerance is appreciated by network teams.

In the diagram above (click images for full size) the left topology depicts a normal resilient connection. Two problems present themselves. Firstly, the connection to the Internet is entirely dependant on the upstream partner. If you are going to all of the bother of divergent circuits and Telco suppliers (and you would, right?) then surely you would want a separate upstream partner.

Secondly, your addressing will in all likelihood be part of your ISP’s allocation (known as Provider Aggregatable Address Space). If you want to move, you would need to change addressing, with DNS Record updates and possible downtime.

If you want to multihome (right topology), you must have Provider Independent Address Space and a separate AS. This is advantageous, as an enterprise could simply run in new connectivity and change suppliers. If your connectivity goes into an Internet Exchange, then changing connectivity might be as simple as a few commands on a router.

What is advantageous for the Enterprise carries a heavy burden for the Internet as a whole, as the Enterprise’s addressing cannot be aggregated into a larger Provider Aggregation.

Traffic-engineering

A further reason for the expansion of the routing table is traffic engineering policy. Traffic engineering is delivered either by advertising longer prefixes, with or without the shorter prefix, down specific links or by AS Prepending. Essentially deaggregation is being used to influence traffic flows.

In the diagram above, the left-hand configuration depicts longer prefix advertisements. The longest match rule will pass traffic towards the longest prefix. As a result, traffic destined to 8.8.8.0/24 will transit AS 3356 and 8.8.9.0/24 will transit AS 3549.

In the right-hand configuration, AS prepending is used. 8.8.8.0/24 is advertised with an extra copy of the 15169 AS towards 3356, and 8.8.9.0/24 with an extra AS towards 3549. In AS702, traffic towards 8.8.8.0/24 will transit 3549 and 8.8.9.0/24 will transit 3356.

Traffic engineering can be optimised using the no-advertise community in specific cases where traffic is being TE’d towards a single provider over resilient links.  By sending the aggregate and the longer prefixes, with the no-advertise community set for the longer prefixes, traffic will follow the aggregate to the upstream provider. At the upstream provider traffic will then follow the longer match towards the correct link.

80% of deaggregation can be attributed to the  factors discussed above – 50% to multihoming and 30% to traffic engineering. These factors are, to a large extent, unavoidable.

In the next post, I will look at the less defensible causes of deaggregation.

This is part of a series of posts – The Lisp Papers.

In the previous post I considered the expansion of the Internet Routing Table. What is driving this trend and will it get better or worse? Obviously, the Internet is getting bigger. Is this enough to explain the size? Is the Routing table as efficiently optimised as possible?

The extremes of the routing table are as follows:

• 1 address range per AS. Every independent Autonomous System would only advertise a single block. This is largely impossible to achieve with the Internet today. In order to achieve this, BGP would need a native Traffic Engineering mechanism and each AS would require a sufficiently large block of addresses to cater for current and future needs. IPv6 is the hope for the latter. There are some thoughts around the former (SCTP, LISP and others). This would reduce the Internet Routing Table to approximately 10% of its current size (35,600 ASes active).
• Optimally aggregated – if we  took all prefixes that matched in AS Path (to preserve traffic transit policies – discussed below) and aggregated them, we could reduce the routing table by 38.2%. This would mean aggregating over address holes (without violating allocations) and crossing consecutive allocations per AS – essentially nothing would change in the way that the Internet routes today but there would be a sizeable reduction.
• BGP routing table that matches allocations by RIRs. This would neither aggregate over consecutive allocations nor deaggregate to longer prefixes. This is approximately 20% smaller than the current Internet Routing Table and 20% larger than the optimally aggregated. If an ISP were allocated 10/8 and 11/8, it would neither aggregate to 10/7 or deaggregate to longer prefixes.
• The Internet Routing table – the current jumble of (mostly) deaggregrations, aggregrations and omissions.

So, if the Internet is approximately 40% larger than optimal and 20% larger than allocated, why?

The following causes of an expanded routing table are considered significant:

• Multi-homing
• Traffic Engineering
• Fragmented allocation
• Poor configuration

In the next post, I will consider Multi-homing and Traffic engineering. These are legitimate causes of de-aggregation and add the largest number of deaggregated prefixes to the table.

This is part of a series of posts – The Lisp Papers.