[Irtf-rr] [broido@caida.org: [Atoms] AS graphs and BGP table size]
k claffy
kc@caida.org
Wed, 13 Nov 2002 20:10:44 -0800
think andre meant to cc irtf-rr on this
answer to dima's question re outdegrees
k
----- Forwarded message from andre broido <broido@caida.org> -----
Date: Mon, 11 Nov 2002 00:14:59 -0800
From: andre broido <broido@caida.org>
Subject: [Atoms] AS graphs and BGP table size
To: dima@krioukov.net
Cc: andre@caida.org, k claffy <kc@caida.org>, atoms@caida.org
Dima,
BGP degrees of ASes are reasonably close to a power
function [1]. This applies more to outdegree than to
indegree which is resticted by limited # of views.
(Think of each view as of a tree, although it is not
exactly a tree; indegree is <= #views.)
The outdegrees of the skitter IP graph and other
measures are close to Weibull distribution [2].
But skitter AS degree distributions are still
close to a power function, even though indegrees
stretch much further than those of BGP AS graph.
The power for indegrees is still higher than for
outdegrees because of limited #views and because
a perfectly successful tier 2 ISP can only have 2
upstream providers, but needs many more customers;
indegree is not a good measure of richness :)
"Aggregation" beyond the AS level can be done using
crown atoms [1]. There are 29K atoms right now and 22.5K
crown atoms. If we could convince many ISPs to renumber,
a 2-3 fold reduction of routing table can be achieved
while keeping all routing policies in place.
Most of the prefixes in current use are announced
by transit ASes. As of Nov.10, 2002, transit AS
announce 54% routes and non-transit ASes announce 45%
(another 1% are multi-origin).
These numbers were stable for the last 2 years.
([3] and IETF and NANOG presentations [4].)
Multihomed stub networks make up 50% of all ASes and
their fraction grows (albeit slowly), yet their share
of routes remains stable. Even if every route that they
announce is withdrawn, the table will reduce by only 30%.
BGP is not a very reliable source for AS
connectivity. We found (to be posted soon)
that the discrepancy between BGP and traceroute
AS paths is 18-100% depending on collector location.
Large portions of connectivity information provided by
BGP are incomplete, because it is strictly downstream.
However, the customer-provider part is likely to be correct,
and the hierarchy produced by stripping [2] is more reliable.
We parse it from Route Views on monthly basis. (Original
"Skitter AS core poster" of April 2000 was also stripped to
the core. Skitter core makes up 30% of skitter AS graph;
note the tenfold difference with BGP data below. Since
then, we always put all ASes on the graph.)
For Nov.01, 2002 (36 tables with >111K routes)
Route Views BGP hierarchy has the following breakdown:
Transit nodes nodes links nodes nodes nodes gone/ links 2-loops links/ outdeg
level remain rem,% remain checked gone affectd affectd gone gone nodes geo.mean
0 14232 100.00 29628 - - - - - - 2.08 2.9042
1 2320 16.30 8304 2320 11912 2146 5.55 21324 20 3.58 2.3820
2 926 6.51 4839 1030 1394 721 1.93 3465 25 5.23 2.3501
3 548 3.85 3644 489 378 314 1.20 1195 15 6.65 2.4617
4 408 2.87 3113 241 140 155 0.90 531 4 7.63 2.4304
5 361 2.54 2891 133 47 95 0.49 222 6 8.01 2.5105
6 333 2.34 2764 80 28 56 0.50 127 0 8.30 2.4811
7 327 2.30 2721 31 6 30 0.20 43 3 8.32 2.5196
8 319 2.24 2706 23 8 15 0.53 15 0 8.48 2.5304
9 316 2.22 2674 32 3 32 0.09 32 1 8.46 2.5599
10 311 2.19 2641 30 5 28 0.18 33 0 8.49 2.5425
11 311 2.19 2641 4 0 0 0 0 8.49 2.5425
Indegree counts for removed nodes at each transit level
Level Indegree:#nodes
1 1:4829 2:5725 3:994 4:227 5:82 6:40 7:17 8:15 9:9 10:3 11:2 12:2 13:1 14:3 17:1 18:1 19:1
2 1:531 2:470 3:221 4:96 5:47 6:22 7:13 8:13 9:6 10:9 11:1 12:2 13:2 14:2 15:1 17:2 19:1 20:2 21:1 23:1
3 1:138 2:114 3:58 4:37 5:12 6:16 7:6 8:9 9:5 10:3 11:1 12:1 14:2 15:1 16:1 17:1 19:1 21:1 23:1
4 1:43 2:36 3:15 4:14 5:16 6:7 7:5 8:1 9:2 10:1 11:2 12:2 16:1 18:2 24:1
5 1:23 2:13 3:8 4:3 6:1 7:2 8:1 9:2 11:1 13:2 14:1 20:2
6 1:11 2:3 3:3 4:1 6:5 8:2 9:1 18:1 24:1
7 1:8 2:1 10:2 13:1
8 1:5 2:2 6:1
9 1:2 2:1 3:1 25:1
10 1:1 2:2 5:1 23:1
Any other algorithm of inferring Internet core will
of course produce very similar result. (See papers by
Lixin Gao, by her students and the ones you mentioned.)
[1] www.caida.org/outreach/papers/2001/CGR/
[2] www.caida.org/outreach/papers/2001/OSD/
[3] www.caida.org/outreach/papers/2002/EGR/
[4] www.caida.org/outreach/presentations/nanog0202/
AB
On Sat, Nov 09, 2002 at 10:08:52PM -0800, k claffy wrote:
----- Forwarded message from Dmitri Krioukov <dima@krioukov.net> -----
Date: Sat, 9 Nov 2002 12:38:31 -0500
From: "Dmitri Krioukov" <dima@krioukov.net>
Subject: RE: [Irtf-rr] Just an idea for a self organiziong IPv6 address space network
To: <sagarwal@CS.Berkeley.EDU>
Cc: <irtf-rr@puck.nether.net>
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0)
Sharad,
What I meant to say is that your AS class definitions
might no longer be telling us anything in, say, a couple
of years. In fact, I'm not so sure what they're trying
to tell us today (beyond this "quantifying the mess"
thing). Where does this lead us to? What would be your
next steps? In particular, how this would help us with
(impossibility of) aggregation beyond the AS level?
Or this way: could you please check how closely your in-
and out-degrees follow power law distributions? If the match
is close then this would be what matters, and any splitting
into classes would seem quite artificial, I believe.
--
dima.
> -----Original Message-----
> From: Sharad Agarwal [mailto:sagarwal@CS.Berkeley.EDU]
> Sent: Thursday, November 07, 2002 2:45 PM
> To: Dmitri Krioukov
> Cc: curtis@fictitious.org; irtf-rr@puck.nether.net
> Subject: Re: [Irtf-rr] Just an idea for a self organiziong IPv6 address
> space network
>
>
> I've made an attempt at understanding the evolutionary dynamics at the
> AS level :
> http://www.cs.berkeley.edu/~sagarwal/research/BGP-hierarchy/graph.hier.png
>
> I've taken our AS hierarchy data from Jan/Feb 2002 and backtracked
> through the Routeviews data (route-views.oregon-ix.net) to see when
> each AS first showed up in BGP. The graph shows that most of the ASes
> today that we call "customers" came into existence recently, while
> most of the larger ISPs today have been around for a while. I know
> this is somewhat inaccurate (due to changing number of routeviews
> peers, merging / selling of ASes, ASes migrating from one tier to
> another, etc.)
>
> Sharad.
>
>
> On Sun, Nov 03, 2002 at 01:52:55PM +0300, Dmitri Krioukov wrote:
> > Curtis,
> >
> > Yes, but my comment would be that it's evolving.
> > Of course, it's very interesting to know what it
> > looks like today but what is more interesting is
> > to know the evolutionary dynamics of the Internet
> > topology and hierarchy. Search for reasonable explanations
> > of emerging of power laws (see this one, for example:
> > http://citeseer.nj.nec.com/461232.html), which turned
> > out to be a surprise for many, is probably the first
> > well-defined step on this path.
> > --
> > dima.
_______________________________________________
Atoms mailing list
Atoms@caida.org
http://login.caida.org/mailman/listinfo/atoms
----- End forwarded message -----