Subject: RE: Architectural approaches to multi6

From: "Bound, Jim" <[email-masked]>
Date: Fri, 28 Mar 2003 14:15:56 -0500

This was also my architectural point about the Internet being chaos :--)
/jim

> -----Original Message-----
> From: Iljitsch van Beijnum [mailto:[email-masked]] 
> Sent: Friday, March 28, 2003 1:54 PM
> To: Christian Huitema
> Cc: [email-masked]
> Subject: Re: Architectural approaches to multi6
> 
> 
> On vrijdag, maa 28, 2003, at 17:13 Europe/Amsterdam, 
> Christian Huitema 
> wrote:
> 
> > This is a suboptimal but workable solution in case of site
> > multi-homing,
> > as the independent trees are joined at the "site" branch. How 
> > suboptimal
> > depends on the size of that branch vs. the size of the tree.
> 
> I'd like to take this opportunity to remark that internet addressing 
> doesn't look like a tree. It's more like a field full of weed. There 
> are just two levels in the hierarchy: ISPs and customers. There is no 
> level above the ISPs. With a /8 worth of /32s that makes for a 
> potential of 512M bonsais rather than a single tree.
> 
> That's a shame really, because a tree would allow interesting new 
> routing mechanisms.
> 
> 
>

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Fri, 28 Mar 2003 20:47:44 +0100

> This was also my architectural point about the Internet being chaos 

In the end entropy will get the better of us, but that doesn't mean we 
can create some order in the chaos for the time being.

Any opinions as to whether it's worth the trouble to try to create a 
hierarchy? With the right renumbering tools it could be done.

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Fri, 28 Mar 2003 17:35:01 -0500

Thanks for replies so far.

I'd just like to note that I used the term
"routing" in a very narrow sense. To be
precise, I meant the "routing function."
The definition can be found, for example,
in: http://citeseer.nj.nec.com/gavoille01routing.html

For example, separation of "locators" and
"identificators", and then using various
dynamic binding mechanisms, is not routing
in this sense.

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)).
--
dima.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sat, 29 Mar 2003 02:02:07 +0100

On vrijdag, maa 28, 2003, at 23:35 Europe/Amsterdam, Dmitri Krioukov 
wrote:

> http://citeseer.nj.nec.com/gavoille01routing.html

> limitations of any routing (even

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.

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Fri, 28 Mar 2003 21:26:55 -0500

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.

> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Iljitsch van Beijnum
> Sent: Friday, March 28, 2003 8:02 PM
> To: Dmitri Krioukov
> Cc: [email-masked]