[Irtf-rr] Just an idea for a self organiziong IPv6 address space network

Sat, 9 Nov 2002 12:38:31 -0500

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.
> >
> >
> > > -----Original Message-----
> > > From: Curtis Villamizar [mailto:curtis@workhorse.fictitious.org]
> > > Sent: Thursday, October 31, 2002 7:05 PM
> > > To: Dmitri Krioukov
> > > Cc: Xiaowei Yang; irtf-rr@puck.nether.net;
> > > curtis@workhorse.fictitious.org
> > > Subject: Re: [Irtf-rr] Just an idea for a self organiziong
> IPv6 address
> > > space network
> > >
> > >
> > >
> > > In message <NCBBIKACLKNMKDHKKKNFMEGEHGAA.dima@krioukov.net>,
> > > "Dmitri Krioukov"
> > > writes:
> > > > For one of the best attempts to uncover the
> > > > current Internet hierarchy incorporating customer-
> > > > provider relationship please see this:
> > > > http://www.cs.berkeley.edu/~sagarwal/research/BGP-hierarchy/
> > > >
> > > > However, it doesn't change a bit in calculations
> > > > derived from the fundamental Kleinrock's results.
> > > > And this is essentially reinforced by Curtis's
> > > > considerations below.
> > > > --
> > > > dima.
> > >
> > >
> > > Dima,
> > >
> > > Thanks for the URL.
> > >
> > > They did a nice job "quantifying the mess".  A summary can be found on
> > > the slides at
> > > <http://www.cs.berkeley.edu/~sagarwal/research/BGP-hierarchy/infoc
> > > om02-present.pdf>
> > > Slide 30 has a nice picture of the top level.  CAIDA has done similar
> > > visualizations.  Skitter plots make nice T-shirts but don't show any
> > > clear hierarchy on which allocation of addresses could be based.
> > >
> > > Curtis
> > >
> > >
> > > > > -----Original Message-----
> > > > > From: Curtis Villamizar [mailto:curtis@workhorse.fictitious.org]
> > > > > Sent: Wednesday, October 30, 2002 8:24 PM
> > > > > To: Xiaowei Yang
> > > > > Cc: Dmitri Krioukov; Pepmiller, Craig E.; irtf-rr@puck.nether.net
> > > > > Subject: Re: [Irtf-rr] Just an idea for a self organiziong
> > > IPv6 address
> > > > > space network
> > > > >
> > > > >
> > > > >
> > > > > In message <pzvbs5c3oeh.wl@cordelia.lcs.mit.edu>, Xiaowei
> Yang writes:
> > > > > >
> > > > > > just out of curiosity, can someone explain what "meshy
> > > networks" are?
> > > > > > I understand Internet is no telephone network, and does
> not have a
> > > > > > strict hierarchy. but the customer-provider
> relationship defines a
> > > > > > hierarchical relationship, and two provider trees may be
> > > connected by
> > > > > > horizontal peering links. so, why is the idea of self organizing
> > > > > > address space so surprising?
> > > > >
> > > > >
> > > > > There are at least a dozen providers who would consider
> themselves to
> > > > > be "tier 1" and at the top of the IPv4 hierarchy.  There are other
> > > > > providers connected to more than one "tier 1" provider.
> Many second
> > > > > tier providers and some large enterprises have so far
> flatly refused
> > > > > to take address space from a higher level provider block,
> citing the
> > > > > impossible task of renumbering all of the organizations that have
> > > > > recieved numbers from them using current technology.
> > > > >
> > > > > Historically the top level providers in particular have
> been known for
> > > > > their reluctance to cooperate in the area of route registry.  They
> > > > > want blocks of addresses and they want any other party to
> simply trust
> > > > > that whatever routes they announce are valid.  I would
> expect far more
> > > > > vigorous refusal to accept addresses dynamically and than the
> > > > > reluctance to register routing information.
> > > > >
> > > > > Providers have always cited a chicken and egg problem in dynamicly
> > > > > learning such things as the IP addresses of routers.  (Routers are
> > > > > needed to reach things and to reach things they need addresses).
> > > > > Routers therefore have always had a configured set of addresses to
> > > > > speed recovery in the event of a massive outage.  Routers
> don't rely
> > > > > on other services such as DNS for this reason (a resolver
> is available
> > > > > but cannot be needed to bring up services).
> > > > >
> > > > > Any algorithm would have a tough time determining which of the few
> > > > > thousand AS where top level vs some lower level.  One
> could argue that
> > > > > this is a technically solvable problem.  It just may not be
> > > > > politically solvable.
> > > > >
> > > > > There are issues of security of this whole hierarchy.
> ISPs like the
> > > > > fact that if the rest of the Internet completely
> collapsed their IGP
> > > > > would remain up and running and their direct customers
> would still be
> > > > > served.  Not even DNS is a vulnerablity for an enterprise
> using such
> > > > > an ISP and resolving their own domain locally or through the ISP.
> > > > >
> > > > > By design, the Internet is a collection of more or less autonomous
> > > > > networks glued together.  You are proposing adding a very
> fundamental
> > > > > dependency on entities higher up in a hierarchy.  There
> is probably no
> > > > > enterprise of over 100 emplyees willing to dynamically
> take addresses
> > > > > from their provider such that if they went down (for
> example, due to
> > > > > power outage) and found themselves up but isolated from
> their provider
> > > > > they would not have an authoritative source of addresses.  This is
> > > > > even more true for providers not wanting dependencies on others.
> > > > >
> > > > > Even in a complete mesh, all nodes being equal with no
> hierarchy at
> > > > > all, you could assert that in theory some sort of
> spanning tree could
> > > > > assign numbers and in that way "organize the network".
> In practice,
> > > > > you don't have any chance of getting the Internet
> providers to adopt
> > > > > it.  My advice is to direct your efforts elsewhere.
> > > > >
> > > > > Curtis
> > > > >
> > > > >
> > > > > > At Wed, 30 Oct 2002 00:24:22 +0300,
> > > > > > Dmitri Krioukov wrote:
> > > > > > >
> > > > > > > I perfectly understand Curtis's reply.
> > > > > > > It would be quite surprising to know
> > > > > > > how anything like this could work on
> > > > > > > meshy networks. Some preliminary
> > > > > > > calculations based on fundamental
> > > > > > > Kleinrock's results on hierarchical
> > > > > > > routing are included in:
> > > > > > > http://www.krioukov.net/~dima/pro/lulea/lulea-msrw.ppt
> > > > > > > --
> > > > > > > dima.
> > > > > > >
> > > > > > > _______________________________________________
> > > > > > > irtf-rr mailing list
> > > > > > > irtf-rr@puck.nether.net
> > > > > > > http://puck.nether.net/mailman/listinfo/irtf-rr
> > > > > >
> > > > > > _______________________________________________
> > > > > > irtf-rr mailing list
> > > > > > irtf-rr@puck.nether.net
> > > > > > http://puck.nether.net/mailman/listinfo/irtf-rr
> > > > > >
> > > > _______________________________________________
> > > > irtf-rr mailing list
> > > > irtf-rr@puck.nether.net
> > > > http://puck.nether.net/mailman/listinfo/irtf-rr
> > > >
> >
> > _______________________________________________
> > irtf-rr mailing list
> > irtf-rr@puck.nether.net
> > http://puck.nether.net/mailman/listinfo/irtf-rr