Terminology:

• Transit and Stub : A transit AS is one that carries traffic on behalf of another AS; a stub (non-transit) AS is just a source or sink for traffic. On the BGP graph, a transit AS node will have positive outdegree; a stub AS will have outdegree 0. A stub AS is always the last AS in any AS path in which it appears.
• Multihomed and single-homed : A multihomed network accepts traffic from more than one upstream provider. In the BGP AS graph, multihomed nodes have indegree >= 2. BGP data indicates only a lower bound on multihoming, although a relatively consistent one across peer selection.
• BGP AS graph : The ASes and AS paths present in a set of backbone BGP tables form a graph that we call the BGP AS graph. ASes are nodes of the graph, connected to each other if they are adjacent in some AS path in one of the BGP tables, i.e., if a BGP peering session was observed between the two ASes.

Main observation:

	Nov.1999	Nov.2000	Nov.2001	Oct.2002	Jun.2003	Jun.2004
Transit AS	18%	17%	16%	16%	16%	16%
Multihomed AS	57%	58%	61%	62-63%	66-67%	63-64%
Stub Multihomed AS	44%	46%	49%	50%	53-54%	51%

Table 1: Cross-section of BGP ASes by category over time (as seen from RouteViews data)

Our data can be viewed as confirming that the fraction of stub ASes was stable in 2001-2004. In November 2001 this fraction was 84%, which is the same as in June 2004 within the error margin. In other words, the fractions of transit/stub ASes have been stable for the last 2.5 years.

We estimate our error margin as 0.5%, primarily due to variations in the set of peers contributing to RouteViews and treatment of private ASes.

The changes of the fraction of stub multihomed ASes (from 49% to 53-54% over 2001-2003, and then back down to 51% by 2004) slightly exceed our error margin. We observe the same pattern (increase followed by decrease) in the fraction of all multihomed ASes, transit and stub.

The trend appears to have reverted some time between November 2001 and June 2004, and now points toward a decrease in the fraction of multihomed stub ASes. In other words, the number of those ASes currently grows more slowly than the number of all ASes (9% vs. 14% growth over the last year).

More detailed data for April-July 2003:

We also analyzed 13 BGP AS graphs over April-July 2003. Figure 1 and Figure 2 are time series bar plots of AS types.

The data suggest that during the 3.5 month observation period, the number of transit ASes grew steadily (from 2454 in April to 2567 in July), while the percentage of transit ASes remained quite stable at around 16%, since the total number of ASes grows as well. The percentage of multihomed ASes varies between 63% and 67% over that period.

Figure 1: Number of ASes in each category: transit single-homed, transit multihomed, stub single-homed, and stub multihomed. (2003.04.01 to 2003.07.16) Cumulative numbers of ASes in each category are shown in stacked bars. The exact values are shown in solid lines with corresponding color.



Figure 2: Percentage of ASes in each category (2003.04.01 to 2003.07.16)

Reference:

1. "Internet Expansion, Refinement, and Churn" authored by Andre Broido, Evi Nemeth, and kc claffy. Published in European Transactions on Telecommunications, v.13, pp.33-52, January 2002.