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

From: David Lamparter <[email-masked]>
Date: Wed, 19 Jul 2017 19:29:13 +0200

Hello again, rtgwg,

Unfortunately (and possibly contradicting earlier statements I may have
made to the opposite), the routing system behaviour described in
https://tools.ietf.org/html/draft-ietf-rtgwg-enterprise-pa-multihoming-01#section-3
is not compatible with the behaviour described in
https://tools.ietf.org/html/draft-ietf-rtgwg-dst-src-routing
and will result in loops in specific cases when mixing implementations.

The failure scenario is illustrated by the following setup:

Considering 2 connected routers A and B, A implementing dst-src-routing
and B implementing enterprise-pa-multihoming.

Have:
- A advertise D=::/0, S=::/0
- B advertise D=2001:db8::/32, S=2001:db8::/32
- B advertise D=2001:db8:aaaa::/48, S=2001:db8:ffff::/48

B will build the following "scoped tables":
- unscoped:
  ::/0 via A
- scope 2001:db8::/32
  2001:db8::/32 local
  ::/0 via A
- scope 2001:db8:ffff::/48
  2001:db8:aaaa::/48 local
  ::/0 via A

Note that the last scope has no entry for 2001:db8::/32, since item 3.
in the first list in section 3 of the draft only prescribes propagating
unscoped entries to the scoped table.

This leads to a packet with S=2001:db8:ffff::1, D=2001:db8::1 looping
between the routers:
- router B performs the lookup as:
  - longest matching scoped table is S=2001:db8:ffff::/48
    - scoped table contains route to ::/0 pointing at A
- router A performs the lookup as:
  - most specific destination match is 2001:db8::/32
    - under this destination, route with S=2001:db8::/32 points to B
=> persistent loop.

It is my understanding that this discrepancy in behaviour is accidental
and the enterprise-pa-multihoming draft is attempting to describe the
same behaviour in local wording.

Assuming this is the case, I'm unsure how we've ended up in this
situation.  I've heard the rtgwg-dst-src-routing draft may be hard to
understand.  If there are specific concerns, I'd ask for them to be
voiced so that I can address them.  I've checked for such feedback and
found none, if I lost any I'm terribly sorry and hope it can be resent.
If there are shared unspecific concerns, I suppose I can look at
different ways to argue section 3 / 3.1.

Still assuming that this was intended to be identical in behaviour, I
would hope the mismatch can be addressed in enterprise-pa-multihoming.
Looking at, well, the title of that draft, it seems that it's trying to
be complete in describing the specific application in multihomed
enterprises.  This may also explain the specific mismatch in behaviour;
it's in fact identical as long as one only considers exit routing with
non-overlapping source prefix restrictions.

rtgwg-dst-src-routing argues a broader applicability of the idea and
tries to be thorough in describing a routing system feature to build on.
As such, I'd be very happy to see enterprise-pa-multihoming describing
in detail how to apply this feature for its title.

Assuming it is _not_ the case that the intention is for these to be
identical, we're IMHO heading for a rather bad place.  I'd rather not
argue this without confirming we're indeed there.

Cheers,

-David

P.S.: rtgwg-dst-src-routing already had a description on how to
translate its routes into a form suitable for "policy routing"
implementations.  The version just posted adds a reference to
https://hal.inria.fr/file/index/docid/947234/filename/source-sensitive-routing.pdf
which argues the implementation specifics and correctness of this
translation in its full mathematical gore ;)

---

From: David Lamparter <[email-masked]>
Date: Thu, 20 Jul 2017 09:41:32 +0200

Gah, forgot Cc:s, resending to list so replies will inherit Cc:s
(please reply on this one to get the Cc:s)

On Wed, Jul 19, 2017 at 07:29:13PM +0200, David Lamparter wrote:
Hello again, rtgwg,

Have:

Cheers,

-David

---

From: David Lamparter <[email-masked]>
Date: Thu, 20 Jul 2017 09:45:43 +0200

... I should step away from electronical devices, for some reason I'm
missing Chris Bowers <[email-masked]> and Fred Baker
<[email-masked]> again...

---

From: "Acee Lindem (acee)" <[email-masked]>
Date: Wed, 26 Jul 2017 00:16:17 +0000

Hi David, 

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. 

Thanks,
Acee 

On 7/19/17, 1:29 PM, "rtgwg on behalf of David Lamparter"
<[email-masked] on behalf of [email-masked]> wrote:

>_______________________________________________
>rtgwg mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/rtgwg

---

From: Matthieu Boutier <[email-masked]>
Date: Wed, 26 Jul 2017 15:05:07 +0200

Hi,

David, you're right, and as you remark, the draft says:

2.5: « It is also useful to note that the prefixes assigned to the site by
       different ISPs will not overlap. »

This hypothesis breaks your example.  But, as you, I think that we should
not rely on such hypothesis: it seems error-prone.  And I think that some
drafts (including yours) report use cases with overlapping prefixes.

> Note that doing the source address lookup first maps directly to the
> PA multi-homing use-case.

Acee, I strongly disagree with that, and that's all the point of section
3 of draft-ietf-rtgwg-enterprise-pa-multihoming.  We have routers A and B
advertising respectively (D=::/0, S=2001:db8:a::/48) and
(D=2001:db8:a::/48, S= ::/0).  This is exactly two routes.  No more.  A
dest-src table, like the one in the Linux kernel (IPv6 subtrees) will
handle these routes correctly:

        Destination                Source      Nexthop
    --------------------------------------------------
               ::/0      2001:db8:a::/48             X
    2001:db8:a::/48                 ::/0             Y

Two routes are advertised, the routing table has two routes: everything is
clear.  By the way, this is the simplest realistic scenario possible:

    2001:db8:a::/48
    +------+----…---- R --- ISP
    |      |
    H1     H2

So now, how to read this table?  If you do source lookup first, *all* your
packets are going towards the Internet, even the one coming from the
Internet… too bad.  If you do destination lookup first, everything is ok.

Now, the purpose of section 3 of enterprise-pa-multihoming-01 is just (in
my understanding) to tell people how to configure their routers if they
don't have native source-specific tables with destination-first ordering.
In that case, you have to deal with policy routing using multiple routing
tables with trafic engineering rules over it.  The result is:

             Source          Destination      Nexthop
    ---------------      -----------------------------
    (unscoped) ::/0      2001:db8:a::/48             X

             Source          Destination      Nexthop
    ---------------      -----------------------------
    2001:db8:a::/48                 ::/0             Y
                         2001:db8:a::/48             X  # section 3's copy

However, section 3's method only works with disjoint source prefixes.  We
provided a general solution...  From a draft cited in this draft:

   [SS-ROUTING]
              Boutier, M. and J. Chroboczek, "Source-Specific Routing",
              August 2014.
              In Proc.  IFIP Networking 2015.  A slightly earlier
              version is available online from http://arxiv.org/
              pdf/1403.0445.

... and an implementation....

    https://github.com/boutier/babeld/blob/dev/disambiguation.c

Section 3 should be more clear about its motivations, and might just be a
reference to David's draft.  It's also unclear if it's the role of the
administrator to configure routing or if it's the role of the routing
protocol.  Section 3 says « The method described in this document is
intended to be easy to understand for network enterprise operators while
at the same time being functionally correct ».  I believe that presenting
plain dst-src tables is much easier to understand.

Anyway.  Also, the first examples of the draft use SADR domains and
"normal-routed" domain, sometimes with tunnels and so on... while saying
that having such topology may not lead to have the best route.  I think
that the draft would be improved if it first present the clean solution
which is: *all the network support dst-src routing*.  This is what we
really want for the long term.  I think that all the discussion of 2.1
and 2.2 about what if all my routers don't implement SADR should be
moved in an annex named "progressive deployment" (or something like that).

Matthieu

---

From: "Acee Lindem (acee)" <[email-masked]>
Date: Wed, 26 Jul 2017 20:52:53 +0000

Matthieu, 

I believe the tables could be similarly collapsed giving source address
higher precedence than destination address. Do you disagree?

Thanks,
Acee

---

From: Chris Bowers <[email-masked]>
Date: Wed, 26 Jul 2017 22:11:47 +0000

David,

It seems to me that the example that creates a routing loop depends on having two routes where 
one non-default source prefix of one route contains the source prefix of the other route

Specifically,  S=2001:db8::/32 contains S=2001:db8:ffff::/48.

I think that we can resolve the discrepancy between the two forwarding behavior descriptions if we 
generalize rule #3 from section 3 of draft-ietf-rtgwg-enterprise-pa-multihoming-01 to propagate
routes from each less specific source-prefix-scoped forwarding table to the more specific
source-prefix-scoped forwarding tables contained in the less specific one.  This can be
seen as generalizing the rule to propagate routes from the unscoped (S=::/0) forwarding table
to the scoped forwarding tables, since they are all contained in the S=::/0 prefix.

With this generalization, the forwarding table on B scoped for S=2001:db8:ffff::/48 would inherit an extra route from 
the forwarding table scoped for S=2001:db8::/32 which contains it.  The resulting forwarding table 
on B scoped for S=2001:db8:ffff::/48 would look as below.  So there is no routing loop.

-  scope S=2001:db8:ffff::/48
   2001:db8:aaaa::/48 local
   2001:db8::/32 local
   ::/0 via A

Does this generalization of rule #3 resolve the discrepancy ?

Thanks,
Chris

-----Original Message-----
From: David Lamparter [mailto:[email-masked]] 
Sent: Thursday, July 20, 2017 2:42 AM
To: [email-masked]
Cc: Anton Smirnov <[email-masked]>; Jen Linkova <[email-masked]>; Chris Bowers <[email-masked]>; Fred Baker <[email-masked]>
Subject: Persistent loops when mixing rtgwg-enterprise-pa-multihoming and rtgwg-dst-src-routing

Gah, forgot Cc:s, resending to list so replies will inherit Cc:s (please reply on this one to get the Cc:s)

Unfortunately (and possibly contradicting earlier statements I may have made to the opposite), the routing system behaviour described in
https://tools.ietf.org/html/draft-ietf-rtgwg-enterprise-pa-multihoming-01#section-3
is not compatible with the behaviour described in https://tools.ietf.org/html/draft-ietf-rtgwg-dst-src-routing
and will result in loops in specific cases when mixing implementations.

Considering 2 connected routers A and B, A implementing dst-src-routing and B implementing enterprise-pa-multihoming.

Have:

Note that the last scope has no entry for 2001:db8::/32, since item 3.
in the first list in section 3 of the draft only prescribes propagating unscoped entries to the scoped table.

This leads to a packet with S=2001:db8:ffff::1, D=2001:db8::1 looping between the routers:
- router B performs the lookup as:
  - longest matching scoped table is S=2001:db8:ffff::/48
    - scoped table contains route to ::/0 pointing at A
- router A performs the lookup as:
  - most specific destination match is 2001:db8::/32
    - under this destination, route with S=2001:db8::/32 points to B => persistent loop.

It is my understanding that this discrepancy in behaviour is accidental and the enterprise-pa-multihoming draft is attempting to describe the same behaviour in local wording.

Assuming this is the case, I'm unsure how we've ended up in this situation.  I've heard the rtgwg-dst-src-routing draft may be hard to understand.  If there are specific concerns, I'd ask for them to be voiced so that I can address them.  I've checked for such feedback and found none, if I lost any I'm terribly sorry and hope it can be resent.
If there are shared unspecific concerns, I suppose I can look at different ways to argue section 3 / 3.1.

Still assuming that this was intended to be identical in behaviour, I would hope the mismatch can be addressed in enterprise-pa-multihoming.
Looking at, well, the title of that draft, it seems that it's trying to be complete in describing the specific application in multihomed enterprises.  This may also explain the specific mismatch in behaviour; it's in fact identical as long as one only considers exit routing with non-overlapping source prefix restrictions.

rtgwg-dst-src-routing argues a broader applicability of the idea and tries to be thorough in describing a routing system feature to build on.
As such, I'd be very happy to see enterprise-pa-multihoming describing in detail how to apply this feature for its title.

Assuming it is _not_ the case that the intention is for these to be identical, we're IMHO heading for a rather bad place.  I'd rather not argue this without confirming we're indeed there.

Cheers,

-David

P.S.: rtgwg-dst-src-routing already had a description on how to translate its routes into a form suitable for "policy routing"
implementations.  The version just posted adds a reference to https://hal.inria.fr/file/index/docid/947234/filename/source-sensitive-routing.pdf
which argues the implementation specifics and correctness of this translation in its full mathematical gore ;)

---

From: Matthieu Boutier <[email-masked]>
Date: Thu, 27 Jul 2017 11:06:54 +0200

> higher precedence than destination address. Do you disagree?

mmm, it seems I failed to explain something since that's not the point…
Did you agree that:

  1. destination first give the correct behaviour as-is.

  2. source first needs extra mechanism and route duplication.

So we can do it, but we don't *want* so!  I was pointing out that it's
also what is behind this draft, even if not explicitly said.

I'm probably missing something: why would you like "the FIB organization
described in section 3"?

Matthieu

---

From: Matthieu Boutier <[email-masked]>
Date: Thu, 27 Jul 2017 18:41:22 +0200

Hi,

> Does this generalization of rule #3 resolve the discrepancy ?

It's not enough, because if you have overlapping source prefix, you'll
need to change the following.

   1.  If the source address of the packet matches one of the source
       prefixes, then look up the destination address of the packet in
       the corresponding source-prefix-scoped forwarding table to
       determine the next-hop for the packet.

   2.  If the source address of the packet does NOT match one of the
       source prefixes, then look up the destination address of the
       packet in unscoped forwarding table to determine the next-hop for
       the packet.

Basically, you'll have to replace these two points by only one saying:
"order your entries by prefix specificity (longest match first)".

And… I have the feeling that the routing part is overcomplicated.  It
should be as simple as: "put a SADR routing protocol on your network".
And you're done.

The draft discusses a lot about how to progressively deploy SADR in the
network.  This should be put in a "progressive deployment" section, which
would essentially say:

  - have a connected SADR backbone including the edge routers,

  - announce a default route from the backbone to attract packets.

It's the role of the routing protocol to be backward compatible with
the legacy (non-SADR) version.

Also, about routing tables, section 3 clearly shows that if a packet
matches two routes, it should follow the one with the most specific
destination.  All the section 3 is about what to do if we don't have
native destination-first SADR tables but only policy routing.  I
believe it's the role of the routing protocol's implementation to
deal with that (that's what we do since 2013).  Then section 3 could
probably just be a reference to David's draft, since it only concerns
SADR/dst-src/source-specific/etc. routing protocol implementations.

Matthieu

---

From: Chris Bowers <[email-masked]>
Date: Thu, 27 Jul 2017 17:55:01 +0000

Matthieu, 

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.

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.

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.  

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.

Thanks,
Chris

-----Original Message-----
From: Matthieu Boutier [mailto:[email-masked]] 
Sent: Thursday, July 27, 2017 11:41 AM
To: Chris Bowers <[email-masked]>
Cc: David Lamparter <[email-masked]>; [email-masked]; Anton Smirnov <[email-masked]>; Jen Linkova <[email-masked]>
Subject: Re: Persistent loops when mixing rtgwg-enterprise-pa-multihoming and rtgwg-dst-src-routing

Hi,

> Does this generalization of rule #3 resolve the discrepancy ?

It's not enough, because if you have overlapping source prefix, you'll need to change the following.

And… I have the feeling that the routing part is overcomplicated.  It should be as simple as: "put a SADR routing protocol on your network".
And you're done.

The draft discusses a lot about how to progressively deploy SADR in the network.  This should be put in a "progressive deployment" section, which would essentially say:

It's the role of the routing protocol to be backward compatible with the legacy (non-SADR) version.

Also, about routing tables, section 3 clearly shows that if a packet matches two routes, it should follow the one with the most specific destination.  All the section 3 is about what to do if we don't have native destination-first SADR tables but only policy routing.  I believe it's the role of the routing protocol's implementation to deal with that (that's what we do since 2013).  Then section 3 could probably just be a reference to David's draft, since it only concerns SADR/dst-src/source-specific/etc. routing protocol implementations.

Matthieu

---

From: Fred Baker <[email-masked]>
Date: Thu, 27 Jul 2017 19:23:46 -0700

> On Jul 27, 2017, at 2:06 AM, Matthieu Boutier <[email-masked]> wrote:
> 
> Did you agree that:
> 

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.

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.

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.

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

---

From: Matthieu Boutier <[email-masked]>
Date: Fri, 28 Jul 2017 14:42:59 +0200

Thank's Chris, it makes things much more clear.

> With […], 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.

I think so. :-)

> 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.
> 
> 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.
> 
> 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.

I completely missed this discussion while reading the draft.  I understand that
people may want to have different representations.  Perhaps the draft should
speak about both representations, since routes are advertised as pairs (D,S),
and it's likely that routing protocols will keep this simple representation.

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

> 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.

Now I see the point.

Thanks,
Matthieu

---

From: Matthieu Boutier <[email-masked]>
Date: Sat, 29 Jul 2017 10:46:49 +0200

> 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.

Interesting! (but I'm lost with the example below)

> 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.

Did you mean: it any cases, the administrator himself will have to
duplicate routes to achieve its goals?

> 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…

I'm lost somewhere.  I'm unable to draw this example, being confused with
"who announces what?".  For example, when you say "D1 is advertised by S1
but not S2", does that mean that S1 wants to announce a route for the
destination D1 and for all sources except S2?  or S1 announces (D1, S1)
but not (D1, S2) ?  The first solution would give:

     (D1, ¬S2)
---.  <--     
S1 |----------
---'

:/

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

I should have missed the reference.  Could you please resend?  I guess you
first complete tables and then do the lookup, right?

Thanks,
Matthieu

---

From: Fred Baker <[email-masked]>
Date: Sat, 29 Jul 2017 16:30:59 -0700

> On Jul 29, 2017, at 1:46 AM, Matthieu Boutier <[email-masked]> wrote:
> 

If I had meant that I would have said it. I think the set of such FIB routes would be detected and programmed by the software that writes the FIB.

Let me work through the example for the rest of your email.