RE: Architectural approaches to multi6

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

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: owner-multi6@ops.ietf.org [mailto:owner-multi6@ops.ietf.org]On
> Behalf Of Christian Huitema
> Sent: Friday, March 28, 2003 11:14 AM
> To: Tony Li; Dmitri Krioukov; multi6@ops.ietf.org
> Subject: RE: Architectural approaches to multi6
> 
> 
> > 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
>