Re: [rrg] Rerouting by readdressing

[P S <[e-mail]>]

> The research we've done wants to lead us in a direction where the host address isn't stable.


you may want to check here http://rina.tssg.org
 
Thank you,


Peter


________________________________
 From: William Herrin <[e-mail]>
To: Noel Chiappa <[e-mail]> 
Cc: [e-mail] 
Sent: Monday, November 12, 2012 6:30 PM
Subject: [rrg] Rerouting by readdressing
 
On Sun, Nov 11, 2012 at 8:55 PM, Noel Chiappa <[e-mail]> wrote:
>     > From: William Herrin <[e-mail]>
>
>     > 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 ................ [e-mail]  [e-mail]
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004
_______________________________________________
rrg mailing list
[e-mail]
http://www.irtf.org/mailman/listinfo/rrg