Subject: Re: [lisp] WG Review: Recharter of Locator/ID Separation Protocol (lisp)

From: [email-masked] (Noel Chiappa)
Date: Tue, 13 Mar 2012 15:53:25 -0400 (EDT)

> From: John Scudder <[email-masked]>

    > Re cache management schemes, I think that depends on whether you
    > mean "system level behavior" of a small-scale system, or one
    > operating at large scale or under some kind of stress. The earlier
    > discussion notwithstanding, for practical purposes caching is
    > central to LISP; as such, it's a little weird to say it's
    > architecturally unimportant.

I didn't hear him say that. I think he said 'the details of particular
cache management algorithm(s) aren't important to an _architectural_
understanding of LISP'.

Now, what you mean by 'architectural understanding' and what I (and
probably Joel) mean by 'architectural understanding' may be two different
things, which may be the source of the problem.

What I mean by that term is 'how is the entire system broken up into
subsystems' (i.e. what are the functional units), and 'how do they
interact'. I.e. a very high-level view of how the system as a whole
operates - an overview in which more detailed views of individual
subsystems can be slotted.

That is something totally different from 'a complete model/understanding of
how the system operates in various operational environments', which is
somewhere in the direction of what you seem to want?

Now, clearly the latter is something useful to have, but I'd like to point
out that in its maximum generality it may be a 'boil the ocean' kind of
goal.

E.g. to have a complete and total understanding of how, say, the Internet
path selection system as whole operates, you'd have to model every last
piece of it (every router, etc, etc), because there's no analytical proof
that it operates in any particular way. However, of necessity, any such a
model is probably infeasible - we can build smaller models, and see how
they operate, but they can only offer limited insight (how limited, we
cannot say for sure) into just how the full-scale system is going to work.

To do that, we just built it (why do multi-dimensional mice come to mind
here?), and we can instrument it and watch it (as numerous studies have
done, e.g. the very fine work by Craig Leibowitz and Abha Ahuja some years
ago). But any sub-full-scale model is necessarily going to be 'an
incomplete description of reality', to use the fine phrase from EPR.

Which is not to say that better understanding of how the caching in LISP works
in various operating environments (e.g. under various kinds of attack/stress),
and how different potential cache management algorithms would work across a
range of operational scenarios, is not useful and/or desirable. Of course it
would be.

(Do we have any volunteers? A considerable amount of work on caching
simulation has already been done, but of course there's an infinite space of
possible things to explore, both on the algorithm side and the operational
scenario side.)

However, i) such work is not a 'description of the architecture' as I
understand it, nor ii) is it _absolutely_ necessary before trying a system in
large scale, because to do it 'perfectly' is an impossible 'chicken and egg'
situation: there is no perfect model _other than the system itself_. The only
way to _really_ see how it works is to build it.

Or am I too misunderstanding something?

	Noel

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 14 Mar 2012 17:30:32 -0400 (EDT)

> On Mar 13, 2012, at 3:04 PM, Joel M. Halpern wrote:

    >> It may take engineering and evaluating some cache management
    >> schemes

    > Isn't it relevant to the architecture document, that it be possible
    > for a reader to judge whether the architecture is a good one or not?

Yes and no.

At the _architectural_ level, the details of the algorithms are not
generally visible - and, more importantly, as explained below, in a 'good'
architecture, it's _designed_ so that algorithms can be changed. (As
Corbato so neatly put it in his Multics design paper, without the ability
to change course, one has a boat without a rudder.) So in one sense, no,
it's not an 'architectural' issue.

However, an architecture might be a failure if there is _no possible_
algorithm which can perform a certain required function. But that
condition is awfully hard to ascertain (it's hard to prove a negative).

For some insight into this, look at TCP: _could_ you say, looking at the
TCP specs circa 1977, that it was "[architecturally] a good [design] or
not"?

Even more importantly, was it right to go off and build the Internet, with
the retransmission/etc algorithms we had in TCP in the late 1970s?
(Especially given that the retransmission algorithms later turned out to
be colossally wrong, leading to congestive collapse of the network about 5
years later.)

Sometimes you just gotta go build it and see what happens, and see if
smart people can figure out ways around whatever issues crop up. Not being
able to absolutely, cast-iron prove, a priori up front, that it's
feasible, is not a reasonable requirement: had we had that in place in the
late 1970s, we'd never have built the Internet.

_At an architectural level_, TCP did have one thing going for it with
regard to its algorithms: the retransmission, window management, etc,
algorithms could be replaced piece-meal (i.e. we did not have to have a
co-ordinated flag day). That really saved our bacon when it turned out
they had issues (and not just with retranmission - I actually remember
Silly Window Syndrome).

The same thing is true of the cache management algorithm(s) in the xTRs.
There's no requirement that everyone run the same one, and if the current
cache management algorithms turns out to have issues, it will be no more
hassle to change them than it was to change TCP's retransmission algorithm.

So, at the _architectural level_, LISP's cache management does have that
desirable property: we can experiment with new ones, and deploy better
ones, whenever we want. Also, some sites might have load patterns that are
different from othersm, so that we might want to run different cache
management algorithms in different places. Again, _at an architectural
level_, this turns out to be trivial to do.

	Noel