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

From: David Lamparter <[email-masked]>
Date: Mon, 7 Aug 2017 10:40:21 +0200

On Thu, Jul 27, 2017 at 07:23:46PM -0700, Fred Baker wrote:
> > On Jul 27, 2017, at 2:06 AM, Matthieu Boutier <[email-masked]> 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

---

From: David Lamparter <[email-masked]>
Date: Mon, 7 Aug 2017 10:56:36 +0200

On Wed, Jul 26, 2017 at 12:16:17AM +0000, Acee Lindem (acee) wrote:
> I must admit that I had always thought that the source-routing paradigm in
> draft-troan-homenet-sadr-01.txt was backward with the destination address
> Longest Prefix Match (LPM) being done prior to the source address lookup.
> Rather I think if were going to standardize in the RTG WG, it should be
> the FIB organization described in section 3 of
> draft-ietf-rtgwg-enterprise-pa-multihoming-01.txt. Note that doing the
> source address lookup first  maps directly to the PA multi-homing
> use-case.

I see both a misunderstanding and an internal contradiction here.

The misunderstanding is that enterprise-pa-multihoming is describing
source-first RIB or protocol behaviour.  It isn't - it's describing a
destination-first RIB and a source-first FIB translation.  Conversely,
rtgwg-dst-src-routing isn't specifying a dst-first FIB, see below.

This is also where this contradicts itself;  the PA multi-homing
use-case does *not* map to source-first.  If it did, you wouldn't need
the route duplication.  In fact, the PA multihoming case -- just like
homenet -- needs destination-first to get local connectivity up and
running.

Also, and very importantly, I really don't want to go around telling
people how to run their FIBs.  It doesn't matter, as long as they're
forwarding packets in a manner confirming to the spec.  This is also why
I've moved A.1 and A.2 into the appendix on the -05 rev of the draft;  I
felt these suggestions on how to efficiently operate this on a
source-first (A.2) or destination-first (A.1) FIB are most appropriate
in an appendix.

On Wed, Jul 26, 2017 at 08:52:53PM +0000, Acee Lindem (acee) wrote:
> I believe the tables could be similarly collapsed giving source address
> higher precedence than destination address. Do you disagree?

They can be, this is described in appendix A.2. of dst-src-routing-05.
This does result in more duplicated routes than the other way around,
but it's a perfectly viable implementation choice.

That said, it makes no sense to use this in routing protocol signaling,
or even the RIB.  This is a FIB implementation detail.  For protocol and
RIB operation, destination-first-with-fallthrough provides the semantics
that make the most sense to describe a network and get it up and
running -- even if all of the routers have source-first FIBs and perform
this translation step on installing a route.

Cheers,

-David

---

From: David Lamparter <[email-masked]>
Date: Mon, 7 Aug 2017 11:04:05 +0200

On Fri, Jul 28, 2017 at 02:42:59PM +0200, Matthieu Boutier wrote:
[snip]
> Perhaps having something like the following(?):
> 
>     3.  Forwarding tables representations
>     3.1.  Source Address Dependant Forwarding tables
>       -> this is just a dump of the announces
>     3.2.  Source-Prefix-Scoped Forwarding Tables
>       -> using "Generating Source-Prefix-Scoped Forwarding Tables v2"
>     3.3.  Examples

It's already there: if you look at -04 of the draft, your 3.1 is 3.1,
and your 3.2 is 3.4 ;)
In the -05 version I've moved this to the new appendix A.

Note as mentioned in my reply to Fred, we actually have 3 cases here:
- "d-s-ft" destination-first with fallthrough / backtracking
- "d-s" destination-first
- "s-d" source-first

The way the draft is outlined uses "d-s-ft" to specify expected
behaviour and has A.1 / A.2 describing translations to "d-s" & "s-d".

-David
-

---

From: Matthieu Boutier <[email-masked]>
Date: Mon, 7 Aug 2017 11:12:02 +0200

Hi David,

> It's already there

I was speaking about rtgwg-enterprise-pa-multihoming. ;-)

Thanks by the way for your explanations in your two previous
mails.  I think this really helps us understand each other.

Cheers,
Matthieu

---

From: David Lamparter <[email-masked]>
Date: Mon, 7 Aug 2017 11:24:53 +0200

> I was speaking about rtgwg-enterprise-pa-multihoming. ;-)

Oh, sorry, I jumped over because the section numbers were so similar ;-D

-David

---

From: David Lamparter <[email-masked]>
Date: Mon, 7 Aug 2017 11:27:33 +0200

On Thu, Jul 27, 2017 at 05:55:01PM +0000, Chris Bowers wrote:
> With the proposed generalization of rule #3, together with a clarification that the source-prefix-scoped
> forwarding table should be chosen based on longest source prefix match with the source address of the packet,
> I think we are in agreement that the forwarding behavior described in rtgwg-enterprise-pa-multihoming 
> Is identical to that described in rtgwg-dst-src-routing.
> 
> If anyone thinks that the forwarding behaviors (after the proposed generalization and clarification in
> rtgwg-enterprise-pa-multihoming) are different, please speak up and provide an example.

Indeed this fixes pa-multihoming's section 3 to correspond to
dst-src-routing's section A.2.

> Assuming that the forwarding behaviors are identical, we can now ask the question:  Is it useful to have 
> two different representations of the same forwarding behavior?  I think it is.

Sure, it's a cool feature to be able to show different perspectives of
the same RIB.  The same, it's nice to be able to install this into a FIB
that is organised in a different way in silicon.

However, we need a non-ambiguous specification for the RIB (and in
extension the routing protocols).  I've had conversations at IETF99 that
consider using BGP to signal an application service provider's service
into an enterprise IS-IS domain.  To make this entire topic work without
huge kludges, we need an uniform understanding of what a (D,S) route in
the RIB means.

I think the pa-multihoming draft is actively counterproductive to this.
It doesn't even specify what a (D,S) route means to begin with, it heads
straight for installation instructions for a source-first RIB.  It makes
no mention that these generated tables aren't what the routing protocol
would advertise;  it lacks all of the larger interaction considerations
that are in dst-src-routing sections 4 and 5.

Basically, I can use pa-multihoming to put together a script for my DHCP
client that makes the appropriate calls to update some static routes and
policies in an enterprise network.  dst-src-routing tries to properly
describe the foundation of an useful dst-src routing system.  (And it
doesn't do so in an arbitrarily limited scope to set off in.)

That said, I will go through the dst-src-routing draft to edit to make
more clear that it is a behavioural specification with (at least) 3
implementation possibilities.  The mails I've been sending today have
made perfectly clear to me that this is not at all obvious from the
draft - it should be.  My bad.

> It is not the case that "All the section 3 is about what to do if we don't have native destination-first SADR
> tables but only policy routing."   If the two representations produce the same forwarding behavior, then one
> should be free to implement using either representation.

Yep, either of the 3 representations, one of which is described in
pa-multihoming, and all 3 of which are in dst-src-routing ;)

(*SCNR*)

> I think that enterprise network operators are going to have a very difficult time understanding 
> destination-first SADR forwarding tables.   Instead, operators are very familiar with simple
> destination-based forwarding tables.  I think that operators will find it much easier to understand and
> troubleshoot when this forwarding behavior is represented using a set of source-prefix-scoped 
> destination-based forwarding tables. 
> 
> When routing protocols are working properly, it shouldn't matter.  But when packets are not going where the 
> network operator wants them to, they are going to want to be able to troubleshoot this by looking at the 
> forwarding tables.

Absolutely, as long as we're in agreement on what specifically a (D,S)
route in the RIB means.  We seem to have consensus that this is
destination-first with fallthrough, as that's now what both drafts are
describing.

Cheers,

-David