Subject: RE: (multi6) requirements draft comments

From: "J. Noel Chiappa" <[email-masked]>
Date: Thu, 20 Dec 2001 20:43:13 -0500

> From: "Tony Hain" <[email-masked]>

    > There is an implicit geographic context which modifies the scope of the
    > topology graph.

Only insofar as things which are topologically related often *happen* to have
a geographical relationship. All the *network* cares about is that these
things are next to each other in the connectivity graph. Their geographic
co-location is an accident of which *no* use is made.

    > Your picture is too simple to be useful in addressing the scope of this
    > problem.

It was simply intended as an example of the process of abstraction; I didn't
mean that this particular example had anything to do with this case.

    >> Now, do the same thing for all the other local ISP's hardware

    > This focus on *local* is the basic problem.

In that particular case, I was again speaking of local to mean "things which
are topologically close, and by accident happen to be physically close".

    > The actual topology frequently connects both at some local level and
    > pulls in a few very remote ISPs. Consider MegaRandomCorp which has
    > connections to 6 ISPs in the SF area, but on the same set of border
    > routers has direct circuits to an ISP in London, Tokyo, and Sydney. At
    > the same time RandomMegaCorp has connections to 3 of the same SF,
    > Tokyo, and Sydney ISPs, but a different one in London.

*It doesn't matter*. The resulting connectivity graph is still a graph, and
K-K still applies.

The naming abstraction boundaries you may have to create may not be ones that
people are happy with for policy reasons, but K-K guarantees that even a
network chock-a-block with the kind of connections you posit here can have
efficient (in the sense of small routing tables) routing - *provided* that
appropriate naming abstraction boundaries are picked.

    > If you fold the above complexity into your graph along with the other
    > ~12000 ASs that are prefix origins today, and managing the
    > topology-names becomes an administrative burden

Which is why, if you want to do multi-homing purely with routing (i.e.
multi-homed machines have a single routing-name, and the routing makes the
"right thing" happen), routing-name assignment shouldn't be done manually,
and why bureacracies to assign routing-names are problematic.

    > as topology is constantly shifting.
    >> the users have to renumber when they change providers
 
    > Actually they have to renumber everytime their neighbors change
    > providers as well, because the entire graph changes around them.

I've already explained this point to Christian, but apparently I wasn't clear
enough. Let me try again:

    >>> You'd only have to renumber if you wanted to to maintain absolute
    >>> optimality. Since absolute optimality produces a routing table of
    >>> size e*ln(N), i.e. as I mentioned before a 60 entry routing table for
    >>> a 10^8 node network, somehow I don't think we have to maintain
    >>> absolute optimality!

So we can almost certainly maintain our required degree of routing table size
limitation without constant renumbering. Yes, large changes (e.g. a local ISP
connects up to a new national ISP) might cause some renumbering, but that's
true even for uni-homed hosts.

    >>> Second (and this is really irrelevant, given the point above, but in
    >>> true routing-graph-theory-geek style I mention it for completeness) I
    >>> expect that the vast majority of connectivity changes in a graph can
    >>> be handled with a renumbering over a scope that's less than global.

In other words, if you are trying (for some reason) to provide the optimal
abstraction hierarchy, I would imagine that for most changes in the graph,
creation of a new optimal abstraction hierarchy would require changes to only
a reduced scope of the graph.

	Noel

---

From: Tony Li <[email-masked]>
Date: Thu, 20 Dec 2001 18:24:48 -0800

We do ourselves a disservice when we use the word 'optimal' because it is,
in fact, not what we're after.  We know that we can only have optimality if
we have infinite information.  There's a small scalability problem with
that.

What we need is an abstraction hierarchy that is 'good enough': the number of
items at any level of the hierarchy never grows faster than Moore's law.
Note that this is and will continue to be sufficiently challenging as it
is.

Tony

---

From: Daniel Hagerty <[email-masked]>
Date: Thu, 20 Dec 2001 22:08:26 -0500

> The naming abstraction boundaries you may have to create may not be
 > ones that people are happy with for policy reasons, but K-K
 > guarantees that even a network chock-a-block with the kind of
 > connections you posit here can have efficient (in the sense of
 > small routing tables) routing - *provided* that appropriate naming
 > abstraction boundaries are picked.

    In other words, a techinically proper routing layer implementation
has some serious layer 9 issues to be resolved.