On Sun, Nov 11, 2012 at 8:55 PM, Noel Chiappa <j...@mercury.lcs.mit.edu> wrote: > > From: William Herrin <b...@herrin.us> > > > I have a notion for a "routing" protocol > > I'm glad you put the 'routing' in quotations, because to me, 'routing' is i) > the _selection of paths_, and ii) the distribution of the information needed > to select paths.
Hi Noel, Well, I figure: we've been trying for 20 years to come up with a BGP replacement that scales. In that time we've discovered that: 1. Algorithmically determining the netmask instead of passing it as a separate datum is a bad idea. 2. Building layer 4 protocols with a static dependence on the layer 3 address requires any network that isn't part of a perfect heirarchy to blast destination knowledge to every other network that isn't a strict hierarchy. 3. Because the FIB has distinctly different outputs than the RIB, its possible to aggregate it where it wasn't possible to aggregate the RIB. 4. Disaggregation = bad. If all of that is correct, and it does seem to be, then maybe there just aren't any good answers to be found within the "box" bounded by TCP's need to have a stable IP address. So, lets set that box aside for a while and think about what routing might look like without it. What can we do if we don't care whether the endpoint has a stable layer-3 address so long as it has some layer-3 address at any given time? > I'm not sure what definition other people are using, but it might be useful > to come up with a standard one to prevent confusion. At its most abstract, the routing process figures out how to get packets from A to B via C. Everything at a finer level of detail is subject to detail-level rules. Some of them can be bent. Others can be broken. > > which manages link changes through dynamic re-addressing and multiply > > addressing hosts. By and large the addresses change so that the > > trivially aggregable routes don't have to. Not just at the host level > > but all the way downstream from the link change. > > If I understand you properly, this is a way of dealing with topology changes > by re-numbering things? (To use the definition of 'routing' above, you > wouldn't need to propogate new information, because the old data would still > be valid - it's just that the things the old information would apply to have > changed?) That's the gist of it, yeah. Any given node has three types of links: coreward, hostward and sideward. A coreward link is one from which this node accepts a block of addresses tied to a "default route." Not necessarily 0/0. 2000::/3 is a default route. A hostward link is one on which this node offers blocks of addresses tied to a default route and the neighboring node has accepted assignment of those addresses. A sideward link is one on which an offer of addresses has been made but rejected by the neighbor as it already has a satisfactory coreward path, yet this node has also rejected the neighbors offer of addresses. Each address block you hold (and you don't hold many) is tied to a single coreward path which immediately aggregates into a larger block of addresses held by your coreward neighbor. If any element of the coreward path fails, you send a message hostward instructing every router and host in that direction that the address block is no longer valid. >From your hostward neighbor, you'll receive a notification that the assigned address block has reached its utilization high water mark. If you have enough addresses, you'll assign it a new bigger block and tell it to schedule release of the existing block in 300 seconds. And in 300 seconds you send another message hostward declaring the old block invalid. If you need more addresses to fulfill the request, you send a message coreward indicating that you've reached your high water mark and need a bigger address block. Same process when your hostward neighbor advises that his address utilization has reached his low water mark. Sideward you send disaggregated routes which create shortcuts through the network so it need not operate as a strict heirarchy. But these routes are needed only for efficiency, not connectedness. They can be discarded at any distance without harm. It's probably even practical to implement a short-term tunneled reroute via a formerly sideward now coreward link so that you can release the old addresses gracefully after a link failure. > I need to go away and think about this for a while before I can have some > really solid reaction, but off the top of my head I wonder if the work > involved in keeping up with the changing addresses isn't as much (or possibly > more) work than the usual approach. TANSTAAFL, after all... Overall, it's more work for a certainty. In terms of the maximum work required for any particular node, my SWAG puts it far smaller than it is now. And it seems to exhibit negligible growth with the number of links and nodes in the network -- more than a couple hops away you're dealing with a single aggregate regardless. > > Even bumps automatic resizing requirements upstream so that over time > > any given router offers exactly one route outward which automatically > > aggregates with the route its upstream already holds. > > Err, routing (in the sense given at the top) is trivial when there's only one > path ("its upstream"). It's finding/selecting paths in arbitrary graphs with > lots of alternate paths (i.e. ones with lots of 'cycles', to use the > graph-theory term) which is the hard case. We have excellent solutions for the hard case provided the graph-like component to the network contains a sufficiently small number of prefixes. If we can find a solution for a sufficiently large portion of the network which looks as much like a heirarchy as a graph, and that solution plays nicely with the purely graphy parts, then pragmatically speaking the scalability problem is solved. > > It does require a new suite of transport protocols > > ... > > the odds of ever reaching deployment on an approach which requires us > > to abandon TCP and UDP are not good? > > That's infeasible; you can't require changing all hosts. You need to see if > you can come up with some approach that avoids that. > > (E.g. if we have location-identity separatation deployed, you could hide the > new locators from the hosts.) Perhaps. But maybe it's worth setting aside that question long enough to determine whether an internally consistent technical solution can be built at all. A transport protocol which doesn't require a stable address should work equally well on a network which does provide one and on a network which does not. Maybe that's the way in. >> Are you game to flesh it out and see how far we can run with it > > Right at the moment, I personally don't have any spare time/energy. Well, lack of spare time/energy is a problem. But if there's only time to consider ideas within the box bounded by a TCP-required stable host address then it hardly seems fair to criticize the research process for not finding anything new or insightful. > But you > should think about it (and try and write something); even if it's not usable > directly, there might be some aspects that could be useful to other designs. As it happens, I've spent a few dozens of hours pondering it. But it's only so much fun to play with one's self and my participation here is not paid (hire me please!) The research we've done wants to lead us in a direction where the host address isn't stable. I respectfully suggest we follow and see what there is to be seen. Regards, Bill Herrin -- William D. Herrin ................ her...@dirtside.com b...@herrin.us 3005 Crane Dr. ...................... Web: <http://bill.herrin.us/> Falls Church, VA 22042-3004 _______________________________________________ rrg mailing list rrg@irtf.org http://www.irtf.org/mailman/listinfo/rrg