We analyze the evolution of the global Internet interdomain routing system on AS, prefix and IP address l evel granularities, using snapshots of RouteViews BGP tables from 1997 to 2001. We introduce the notion of semiglobally route d prefixes, those present in the majority of backbone tables, and classify them into standalone -- those wh ich have no subsets, no supersets; root -- have subsets, but no supersets; and subset, or more specific, which are subsets of other blocks.

Using these distinctions we find that from 1999 to 2001 many measures of routing system complexity demons trated stability in the form of slow growth, dynamic equilibrium, and occasional contraction.

We find that many net change measures reflect contributions of opposite sign, and that true measure of va riation, or churn, is the sum of their absolute magnitudes rather than the difference. Appearance and disappearance o f prefixes, ASes and RouteViews peers, as well as status changes (an AS changing from transit to non-transit, or a prefix shifting from a standalone prefix to a root prefix) are instances of routing system churn. One advantage of using our not ion of semiglobal prefixes is that they exhibit less churn than global prefixes (those prefixes common to all backbone tabl es) and as such allow for derivation of more robust macroscopic statistics about the routing system.

We study route prefix instability at a medium time granularity for late 2001 using 2-hour snapshots of BGP tables, and find that half of all prefix reannouncements (flips) are contributed by 1% of all ASes, with governme nt networks, telecoms in developing countries and major backbone ISPs at the top of the list of instability contributo rs. Small ASes (those who originate only a few prefixes into the global routing system) do not contribute more than thei r fair share of either route entries or churn to the global routing system. We conclude that during 1999-2001 many Intern et metrics were stable, and that the routing system's growth and instability are mostly caused by large and medium-sized ISPs.

We use BGP tables from RouteViews archive, selected once per half year in 1997-2002, once per month in 2001, and bi-hourly over one month in November 2001.

We introduce the concept of semiglobal prefixes that makes comparison between datasets collected at different times and by different monitor sets possible.

We study the peering richness, defined as the entropy of the outbound links of a node. The links are weigted by the number of prefix announcements or AS paths traversing each link.

A preliminary version of the presented analysis appears in the report: A.Broido, kc claffy. "Complexity of global routing policies." CAIDA, 2001.

C.Labowitz, R.Malan, F.Jahanian. "Internet Routing Stability". SIGCOMM 1997.