Subject: RE: Architectural approaches to multi6

From: "Christian Huitema" <[email-masked]>
Date: Fri, 28 Mar 2003 08:13:54 -0800

> I would NOT agree that there are no solutions in routing.
> That said, I think that a solution MUST involve having
> the transport NOT use the locator as a portion of the
> pseudo-header.  So at the very least, there must be host
> changes.

I disagree with Tony. There is a known solution, which is to use
multiple addresses per endpoint. This effectively provides a solution to
the aggregation/routing load dilemma by representing the routing graph
as the superposition of several trees, all rooted in the DFZ. I would
contend that this is the only solution in case of host multi-homing
(e.g. GPRS+WIFI): in this case, the independent trees are joined at
their leaves. 

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. In
practice, this is not an issue for very small sites, e.g. single subnet
sites, as the branch is tiny. It is not a real issue either for very
large branches, e.g. sites such as IBM or Microsoft, as the branch is so
large that it can be considered "close to the root" and given its own
number. 

We have an issue for the medium size branches, which can be solved
either by a routing solution (find a way to route more prefixes) or by a
site engineering solution (better management to make medium sites look
like large sites).

-- Christian Huitema

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Fri, 28 Mar 2003 19:53:40 +0100

On vrijdag, maa 28, 2003, at 17:13 Europe/Amsterdam, Christian Huitema 
wrote:

> 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: "Dmitri Krioukov" <[email-masked]>
Date: Fri, 28 Mar 2003 17:35:01 -0500

Christian,

A near optimal bounds of the number of trees
required for tree-cover routing were found in
http://www.cs.tau.ac.il/~zwick/papers/route-SPAA.ps.gz
It follows that if no path inflation is
allowed (stretch k=1), then this number
scales as O(N) on generic graphs, so you
do not gain anything (which is, of course,
just a consequence of the more general fact
that the shortest path routing is incompressible).

But the Internet topology is not generic,
it's scale-free. So, has there any analysis
been done on tree-covers of Internet-like
topologies (with the hope for better scaling)?

Also, given the dynamic version of the problem,
how do I know what tree to use to reach
a specific destination at a specific moment
of time?

thanks,
--
dima.

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On
> Behalf Of Christian Huitema
> Sent: Friday, March 28, 2003 11:14 AM
> To: Tony Li; Dmitri Krioukov; [email-masked]
> Subject: RE: Architectural approaches to multi6
> 
>