[[email protected]: [Atoms] AS graphs and BGP table size]
k claffy <[email protected]> Wed, 13 Nov 2002 20:10:44 -0800
| Newsgroups | gmane.network.research.irtf |
|---|---|
| Message-ID | <[email protected]> |
think andre meant to cc irtf-rr on this answer to dima's question re outdegrees k ----- Forwarded message from andre broido <[email protected]> ----- Date: Mon, 11 Nov 2002 00:14:59 -0800 From: andre broido <[email protected]> Subject: [Atoms] AS graphs and BGP table size To: [email protected] Cc: [email protected], k claffy <[email protected]>, [email protected] 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 <[email protected]> ----- Date: Sat, 9 Nov 2002 12:38:31 -0500 From: "Dmitri Krioukov" <[email protected]> Subject: RE: [Irtf-rr] Just an idea for a self organiziong IPv6 address space network To: <[email protected]> Cc: <[email protected]> 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:[email protected]] > Sent: Thursday, November 07, 2002 2:45 PM > To: Dmitri Krioukov > Cc: [email protected]; [email protected] > 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 [email protected] http://login.caida.org/mailman/listinfo/atoms ----- End forwarded message ----- _______________________________________________ irtf-rr mailing list [email protected] http://puck.nether.net/mailman/listinfo/irtf-rr