RE: Architectural approaches to multi6

["Dmitri Krioukov" <dima@krioukov.net>]

Iljitsch,

This is not math but CS :)

You probably refer to some place in the overview
where generic graphs are discussed. Sure, routing
on special types of graphs can be much more compact.
For example, it's O(1) for rings. For trees, the best
known result requires only ~O(log(N)) bits of memory
to store node IDs, and nothing else, -- based only
on its node ID plus source and destination node IDs,
the node can make its routing decisions in constant
time.

All known constructions with multiple levels of
abstraction are inferior to more recent findings.
In addition, you cannot seriously speak about
"locality" on the Internet inter-domain graph
since there are very few "remote" vertices --
the average AS path length is between 3 and 4
with a very narrow width of the distance
distribution.

The main problem with applicability of those
generic results to the Internet is that they are
too generic. The Internet is not a ring or a tree,
of course, but it has its specific topology, which
is scale-free (power-law) and for which exact
bounds are not known yet (at least to me).
--
dima.


> -----Original Message-----
> From: owner-multi6@ops.ietf.org
> [mailto:owner-multi6@ops.ietf.org]On Behalf Of Iljitsch van Beijnum
> Sent: Friday, March 28, 2003 8:02 PM
> To: Dmitri Krioukov
> Cc: multi6@ops.ietf.org
> Subject: Re: Architectural approaches to multi6
>
>
> On vrijdag, maa 28, 2003, at 23:35 Europe/Amsterdam, Dmitri Krioukov
> wrote:
>
> > http://citeseer.nj.nec.com/gavoille01routing.html
>
> > With these definitions, I guess more
> > people would agree with my initial
> > assertion since the multihomer is
> > necessarily a node on the graph and
> > the shortest path routing was found
> > to be incompressible on generic graphs
> > (see the above link but note that it
> > deals with the ideal world (static
> > and centralized), yet it provides
> > valuable information on the fundamental
> > limitations of any routing (even
> > not yet invented)).
>
> I'm not so sure. I'm sure the math guys are really good at what they
> do, however it often doesn't have much to do with the real world. I
> have to admit that I can't decode a good deal of the math, but
> regardless of what omega is here, the following doesn't make sense:
>
> "The current lower bound is only ¥Ø(¡în) bits for strategies optimizing
> shortest paths" (talking about local memory)
>
> I believe that in a strictly hierarchical routing system it's possible
> to suffice with d+log(d)+3*log(3) bits of memory. Sure, you need
> something like n*log(n) routers that way, but that's another story...
>
> In a hierarchical system, you can aggregate away more and more
> information as you get higher in the hierarchy. However, when a node
> moves to another part of the hierarchy, you break aggregation for part
> of the tree. The farther the node moves, the more aggregation suffers.
> But we can move nodes short distances in the hierarchy without causing
> many problems. So if we align our addressing hierarchy with the
> possible movements of nodes and/or the other way around, routing-based
> and scalable multihoming becomes possible. Hence my proposal for
> geographic aggregation. Then, when a site moves from one ISP to another
> as the result of a rehoming event, aggregation is still intact from the
> closest place where the ISPs interconnect and up.