RE: (multi6) requirements draft comments

["J. Noel Chiappa" <jnc@ginger.lcs.mit.edu>]

    > From: "J. Noel Chiappa" <jnc@ginger.lcs.mit.edu>

Now that I've had some sleep, and my neurons are fresh, I have a few more
things to say about this topic...

    > Kleinrock/Kamoun says that you can get scalable routing in *any*
    > arbitrary graph .. so theoretically at least we might be able to get
    > multi-homing support with the support costs buried in the routing
    > overhead.
    > ...
    > if you read the K-K math, their results hold for their optimal
    > aggregate size which is, IIRC, "e". That's right, 3 level-N entities
    > per level-(N-1) object.

I checked, and it is indeed e. Of course, that's a real-number solution which
doesn't apply to actual graphs, but they further go on to prove that for that
case, there's a global optimum with at most two levels of 2, and the rest of
3.

    > Still, a address aggregation hierarchy which did work with large
    > numbers of multihomed sites would probably do things like group me and
    > my neighours who have CATV into one fairly low-level entity - and
    > assign *both* the CATV and DSL links a single fairly-low-level
    > routing-name
    ...
    > it's perhaps the case that there are very pathological graphs in which
    > the K-K results *don't* hold - and a graph in which there are basically
    > two kinds of nodes, a very large group with only two neighbours, and a
    > very small group with many thouands, might be one. This makes sense: it
    > will be impossible to form those 3-element groups (remember them?) in
    > such a graph.

I thought about this some more, and checked the K-K paper, and I think their
results do hold for all graphs, but I need to study it some more (which I
don't really feel up to at the moment, frankly) to see if it still holds in
cases such as the one I outlined, in which the degree of a few nodes nodes is
very large, and of most nodes is very small.

However, that's to some degree irrelevant, because by thinking about it from
this point of view, it's become clear to me what one has to do (in terms of
the node routing-name assignment) to get the most efficient (in overhead
terms) possible results from doing multihoming support in the routing.


It's easiest to explain all this if I give an example. I came to this as a
kind of picture in my head, but it's not a picture I can easily put onto a
plane surface, so I'll try to do it with precise "words" instead.

Let's suppose that I'm in a place served by M different CATV providers (I
know in most places in the real world it's a monopoly, but I want to make a
point), C1 ... CM, and N DSL providers, D1 ... DN.

Of all the houses H1...Hn in the area, some subset S0j are served by one DSL
provider only, provider Dj, and some subset by CATV provider Ci only, Si0.
Those guys are simple, we don't care about them.

We need to think about the sets Sij, which are served by one CATV provider,
Ci, and one DSL provider, Dj. (There are also other sets which have more than
one CATV and/or more than one DSL, but let's leave them for the moment - the
system will extend to them.)

What you have to do is group (on the graph, which is how I came to this, but
it's hard to draw) all those nodes in set Sij together, and put a topology
naming boundary around them. I.e. assign that set a "network number", and
give them all routing-names from that network number. So house Hk which is in
set Sij will have routing-name "Sij".k (where "Sij" is the routing-name of
that set).

(Obviously, if M and/or N get large, the set S* of sets Sij as well as the
sets of things with 3 or more connections can get pretty large [I forget
whether it's an exponential in M+N, or a factorial - probably the latter,
but it's not important], but let's gloss over that for now.)

This is what you *have* to do to get as close as you reasonably can to the
K-K ideal of efficient (in terms of minimizing table size) routing.


Some of you may hear echoes of metro addressing in this, but there is a
crucial difference. In metro-addressing, routing-names are assigned, and then
the topology is constrained to meet certain properties. In this system, it's
the other way around: if you sign up for a different set of providers, you
have to get a new routing-name.

Well, that's no surprise; your routing-name says where you are in the
network, and if you change your location (into a different grouping), you
need a new routing-name.


What's more interesting is to think about what happens when there's a
failure. This is *not* a situation that K-K talks about - they are simply
analyzing the most efficient naming hiearchy for optimal (in terms of minimum
table size) routing.

If anyone cares about this, I'll talk about that in a separate message, this
one is already too long.

	Noel