Date: Sun,  2 Aug 87 23:50:08 EDT
From: jnc@brubeck.proteon.com
Reply-to: jnc@proteon.com
Subject: Eureka! F=ma for Access Control routing
To: dev-cgw
CC: DClark@multics.mit.edu,jnc

	I have been thinking a lot recently about the enormous numbers
of policy requirements that Proteon customers seem to be giving us
with regard to control of routing information. It's quite clear to me
that the day that we (Internet architects) have dreaded since 1977,
when access control would start to impact routing, is upon us at last.
	Be in no doubt, what these people really want, in a lot of cases,
is access control. They are willing to use links they pay for to handle
only certain classes of traffic. This clearly impacts routing; there may
be two paths from A to B, but you can't use the shorter one since that
traffic is not allowed across one of the constituent links. The switches
have to be able to find the longer route to handle that traffic.
	They have other requirements, to make sure that (effectively)
hostile attacks in the rest of the system do not cause them to lose
connectivity. (I have been thinking about that one for even longer, and
most of those problems can be handled with cryptograhic means. Some
cannot; but that is a different issue and I don't have room to explore it
here.)

	Now, here's the thing that just crawled out of my subconcious,
and made me feel really ill. At the IETF, Milo Medin from NASA said to me
that he thought that the right routing algorithm was SPF.
	The problem comes when you add all the policy requirements that
people seem to have in their hip pockets these days, like "I'll forward
traffic through my AS, but only for my friends A, B and C". What is the
impact on an SPF based algorithm of saying "I'm X and I'm connected to P
and Q, but only for purposes of routing traffic to me or for getting
traffic among A, B, P, Q and me"? Clearly, classic SPF cannot cope with
this. You either have a link or you don't, and it affects the computation
of routes to all possible destinations in the system.
	I was writing up this awful thing, and I realized that there's a
way out, and moreover that the way out implies the final nail in the
coffin of Ford algorithms. 

	I can imagine a way to specify these access control restrictions
in the routing updates (for each link you specify, using pattern
matching, what source-destination pairs you are prepared to see flow over
that link). The problem that leaves me rigid is the thought of trying to
compute the routing table based on a graph with all these damn
restrictions.
	The solution is obvious: the right thing is for gateways to just
store the connectivity map, and not try and generate all the possible
routes. Routes will be stored in a cache, and computed as needed from the
map. It's silly to have the complete routing database precomputed; you
should just compute needed routes on demand.
	I haven't worked out the details, so I don't know how cheap an
algorithm you can build to find shortest paths on demand, if you are
doing one route at a time. The classic BBN SPF algorithms assume that a)
you build a complete routing table, so they construct the complete tree,
and b) that the tree gets updated a fair amount, so they have cheap
algorithms to do that. However, even if generating a route is fairly
expensive, we can still afford it, as long as we don't do it too often.
I don't think the access controls make things much harder; nodes are
only useful for inclusion in the path if you can meet any access controls
on them.
	Dave Feldmeier has done some work at MIT on routing caches, based
on measured traffic. His work was done in the contect of having a small
cache to speed up routing, but his numbers are equally applicable here. A
fairly small cache sufficed to handle most packets. Clearly, a bigger
cache would reduce the cost of computing new routes to an acceptable
small fraction of the total switch CPU power.
	There's an intersting tie in with TOS routing here. TOS also
multiplies the number of possible destinations, and has similar details;
each link is tagged with TOS data. Exactly the same solution applies;
only keep the map, and compute routes on demand.

	The way in which this implies the death of Ford algorithms is as
follows. Ford algorithms inherently imply the precomputation of the
routing database. I have just argued that the cost of the precomputation
has just become prohibitive. This clearly implies that Ford algorithms
will not be plausible in the world of access controls.
	You can sort of hack things up with filters, and other kludges,
but you don't really get what you want: if you advertise the route,
people want to use it for other traffic, but if you don't advertise it,
they can't to use it to get to you. Even for the things where filters
do work, management of this kind will eventually become unworkable.
Automated management implies cost explosion.
	I once argued that SPF algorithms were superior because the fact
that they split the data distribution from the route generation meant
that they were more resistant to bugs in individual implementations of
the routing algorithm. Since the algorithm is no longer distributed,
a route calculation bug in one router did not affect the others in the
system. It is now clear that the divorce of data distribution from
route generation also allows us to compute only those routes actually
needed (from the very large set now possible).


	I'd like to see this idea put in the public domain, and get the
brownie points for it. However, I'd like to see if the company can't get
a head start on a product based on it. We could specify an SPF protocol
(in the sense of packet formats and algorithms for calculating the
whole database) and pass that out, without mentioning the (internal)
efficiency hack from above.
	On the other hand, it seems like the idea is obvious as soon as
you think about the problem. On the other hand, maybe it's not so obvious;
none of the discussion on the INENG mailing list about Ford vs SPF
brought up the point of 'lazy evaluation'. Also,, looking at the DEC
proposed spec for ISO routing, they don't mention it either. Of course,
they don't talk about access controls or TOS routing (which they explicity
do not handle) either. Maybe we should let them set that ISO spec in
concrete and them upstage them!
	I haven't really decided yet what to do with this concept. It's
so simple, I'm sure someone else will tumble to it sooner or late, so
long term heavy protection isn't appropriate. I am labelling it as a "J
Noel Chiappa trade secret", to get everyone to keep a hat on it till we
decide what to do with it. So, it's proprietary for the moment.


	Noel

-------