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

[Xiaowei Yang]

Thanks for the explanations and for the pointers. I agree that
dynamically allocating IP addresses is not desirable in practice, but
I do think it is possible to "statically" allocate provider-rooted
hierarchical addresses. (I was not the one originating the thread, but
my thesis work is related to the topic.)

What I mean by "statically" is that once a provider-customer
relationship is established, the customer is allocated a fixed address
block from the provider.  A multi-homed customer will be allocated one
or more address blocks from each of its providers.

I agree that there might be reluctance to adopt this approach.  This
is a general problem discussed in Shenker et al's paper on algorithmic
mechanism design. In a distributed system like Internet, we can not
simply expect that each AS cares about the stability and scalability
of BGP and will follow the protocols we design. Each AS will act
selfishly, but we can design protocols with incentives for an AS to
follow.

As an example, if an global address prefix costs a significant amount
of fortune, perhaps many small networks / local ISPs are willing to
take address blocks from their providers. If becoming a visible entry
in the global BGP table costs money, perhaps many networks would want
to be aggregated into their providers' entries.

By this allocation, ISPs can still operate if the rest of the Internet
collapses, because dynamic failures do not terminate the business
relationships and do not change the address blocks a domain owns.

We do not need algorithms to determine which ASes are the top level
ones. Whichever affords the money can buy a global unique address
prefix.

Due to the hierarchical aggregation, some dynamic failure will be
hidden from outside the address blocks. Thus, the end system itself
will need to have some error recovery mechanisms. Once an address
fails, it tries another one.

Kleinrock's hierarchical routing scheme cannot be directly applied to
the Internet. In Kleinrock's work, there is no "policy routing"
involved. Each node is willing to provide transit service for each
other. Thus, the cluster boundaries can be formed easily. In Internet,
due to policy routing, there is no natural way of forming clusters.

However, landmark routing can be applied to the Internet.  This
hierarchical allocation scheme can be viewed as a variant of landmark
routing. A provider is the landmark for a customer. Packets are routed
towards the landmarks unless a better route is heard.


At Wed, 30 Oct 2002 12:23:31 -0500,
Curtis Villamizar wrote:
> 
> 
> 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
> >