Re: Persistent loops when mixing rtgwg-enterprise-pa-multihoming and rtgwg-dst-src-routing

[David Lamparter <[e-mail]>]

On Thu, Jul 27, 2017 at 07:23:46PM -0700, Fred Baker wrote:
> > On Jul 27, 2017, at 2:06 AM, Matthieu Boutier <[e-mail]> wrote:
> > 
> > Did you agree that:
> > 
> >  1. destination first give the correct behaviour as-is.
> > 
> >  2. source first needs extra mechanism and route duplication.
> 
> Actually, I don't. I can produce cases in which source first gives the
> wrong route, and in which destination first gives the wrong route. The
> only way I see to make doing either one first *always* gives the right
> result is if a small set of routes is duplicated.

You're right, and we have a SNAFU in terminology here.
rtgwg-dst-src-routing isn't suggesting "destination-first".  It's
"destination-first with fallthrough".

The set of routes that need to be duplicated for destination-first is
exactly this small set that is covered by fallthrough.  Duplicating
these routes is what appendix A.1. of dst-src-routing-05 is describing;
particularly because this duplication significantly reduces
worst-case forwarding/lookup cost - going from "129x129" to "129+129".

[Conversely, appendix A.2. describes translation to "source-first".]

I'll check the draft for whether this terminology SNAFU is in there too.
It explicitly describes the fallthrough as backtracking, so it's
definitely not a content/specification issue, but it may well be jumbled
wording.

FWIW, the Linux kernel implements "destination-first with fallthrough"
plus the separate source-first policy routing feature.  Also, somewhat
relatedly, there were quite a few caching issues back when this was
fresh.

> The issue is when prefixes overlap. If you have sources S1 and S2,
> destinations D1 and D2, D1 is a more specific of D2, and D1 is
> advertised by S1 but not S2, and D2 is advertised by S2. If you are
> looking from S1, you should find S1->D1, and if you are looking from
> S2, you should find S2->D2. If you look destination first, and happen
> to be looking from S2, I think you wind up trying to find S2->D1,
> which doesn't exist.

Right, hence the fallthrough from D1 to D2.

> Every time I get my head into this space, I have to rethink it, and
> the emails I wrote a few years back are unavailable to me now as I am
> no longer at Cisco. I need to think the source version through again.
> But you get the idea. I have pretty much convinced myself that you
> need to duplicate S2->D2 as S2->D1 but with the next hop associated
> with S2->D2 in order to make destination first work. There is a
> similar case regarding source-first lookup.

Source-first lookup simply requires a lot more duplicated routes to get
the same local connectivity coverage. (And fallthrough doesn't help,
because the source-first entry would usually have a default route.)

> This is the reason I have suggested a PATRICIA algorithm or something
> like it that looks up both addresses at the same time.

I've tried to describe the behaviour in terms of functional
requirements;  hence A.1 and A.2 as appendixes describing efficient
implementation choices.

Cheers,


-David