Subject: Re: [homenet] longest-match (was: source routing requirements for routing protocols)

From: Ray Hunter <[email-masked]>
Date: Sat, 03 Aug 2013 17:54:54 +0200

Pierre PFISTER wrote:
>
> Le 31 juil. 2013 à 18:15, Alexandru Petrescu a écrit :
>
>> Le 31/07/2013 17:38, Wes Beebee (wbeebee) a écrit :
>>>> If no prefix is found by the longetst-matching on the src address,
>>>> will a default be used instead?
>>>> Alex
>>>>> There is also potentially a whole destination lookup table that¹s
>>>>> entirely devoted to the ::/0 source prefix.
>>>>> - Wes
>>> My understanding is that there IS a default for source address (see
>>> the above comment).
>>
>> Ok.
>>
>> The default for dst addresses leads to a nexthop.
>>
>> The default for src addresses leads also to a nexthop?  Or to the dst of
>> another dst prefix?  Or to the nexthop of the default of dst?
>>
>> It may sound as a rathole discussion but it is fully part of what the
>> longest-match algorithm does.
>>
>> Alex
>>
>
>
>
> I'm not sure about how it should be done but I can say how Linux seems
> to do it.
>
> * Those affirmation came by looking at the code... That I didn't
> wrote. So I cannot be 100% sure *
>
> Linux uses a tree structure in order to perform the longest prefix
> lookup on the destination address first.
> The found node (which has the longest prefix for the source address),
> CAN have a subtree. 
> This subtree has the same structure as a regular routing table, but is
> used with the source address.
>
> This means that each node in a routing table has its own source
> routing table. There is no
> destination lookup first and then a source lookup in a global table.
>
> --> See fib6_lookup, and fib6_lookup_1 functions
>
> Now, when you add a route with destination and source prefix, 
> the node for destination is created (or updated) and, then, 
> if the source routing prefix length is not null, a subtree is created
> (or updated) and
> a node with the provided source prefix is inserted.
>
> --> See fib6_add
>
> Therefore, for a given node in the main tree, if there is no source
> routing (no subtree), the route
> is always used. Otherwise, a longest prefix match is performed on the
> source address, using the subtree. 
> If there is no corresponding node for the source (no matching prefix,
> where the prefix length can be null), 
> then, the parent node in the destination routing table is used as
> default. 
>
> So, yes, inserting a route for a destination and source prefix will
> create an entry for the destination alone 
> (without source routing). 
> So the default route, for a source lookup, is basically the last
> inserted next-hop for the destination prefix... 
> Which could create unexpected behaviors.
>
>
> Concerning the previous question, Linux actually has
> a RTF_GATEWAY flag. But it doesn't seem to
> be used in the routing decision process. I guess it is used by other
> protocols that like to have a 
> concept of "default router".
>
>
>
> Pierre

OK I don't want to put words in anyone's mouth, but I seem to have read
4 different opinions on how to implement the longest match algorithm for
(source,destination) next hop selection.

Namely:

1. Two step matching destination first and then using the result to key
a longest match lookup on source address (Pierre re Linux code Wed, 31
Jul 2013 19:16:41)
2. Two step matching source first and then using the result to key a
longest match lookup on destinationaddress(Wes Mon, 29 Jul 2013 18:52:01
& Wed, 31 Jul 2013 17:01:29 )
3. Single step longest match with Fuzzy aspects (Alexandru Mon, 29 Jul
2013 10:44:27  )
4. Source-based routing will never work for locally originated packets
because source address selection is done after routing.  (Lorenzo Mon,
29 Jul 2013 19:41:48)

Is there a serious risk here that we may get forwarding loops, or
packets dropped by filters due to incorrect egress gateway selection,
even though we don't have routing loops, or doesn't it matter that
different implementations do different things?

-- 
Regards,
RayH

---

From: Mark Andrews <[email-masked]>
Date: Mon, 05 Aug 2013 07:57:41 +1000

In message <[email-masked]>, Ray Hunter writes:
> 
> 
> Pierre PFISTER wrote:
> >
> > Le 31 juil. 2013 =E0 18:15, Alexandru Petrescu a =E9crit :
> >
> >> Le 31/07/2013 17:38, Wes Beebee (wbeebee) a =E9crit :
> >>>>> There is also potentially a whole destination lookup table that=B9s
> > CAN have a subtree. =
> > Now, when you add a route with destination and source prefix, =
> 
> > the node for destination is created (or updated) and, then, =
> 
> > source address, using the subtree. =
> 
> > where the prefix length can be null), =
> 
> > default. =
> > create an entry for the destination alone =
> 
> > (without source routing). =
> 
> > inserted next-hop for the destination prefix... =
> 
> > protocols that like to have a =
> 

When you do not have a source address you use destination first to
get a source address.  When you have a source address you use source
address first.

One can implement this a number of ways.  Depending upon how one
implements you use source address first or destination address
first.  As long as it gets the same destination we shouldn't care
how it is implemented.

Effectively you have a route table for each prefix and when you
have a source address you use longest match in the table that
corresponds to that source address.  When you don't have a
source address you look in all the tables and find the longest
match of the longest match.  Note there are other constraints
that may reduce the set of source addresses you look for longest
match in when choosing source a source address.

> -- =
> _______________________________________________
> homenet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/homenet
-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: "Wes Beebee (wbeebee)" <[email-masked]>
Date: Mon, 5 Aug 2013 13:34:37 +0000

>3. Single step longest match with Fuzzy aspects (Alexandru Mon, 29 Jul

1+2 amount to the same thingŠ
3+4 seem to be different from 1+2, and 3 is different from 4.

- Wes

---

From: Henning Rogge <[email-masked]>
Date: Mon, 5 Aug 2013 15:40:35 +0200

> 3+4 seem to be different from 1+2, and 3 is different from 4.

I wonder if source-based routing could/should work for sockets which
are bounded to a fixed local IP address, not IP_ANY. This would mean
the source address for locally originated packets should be well known
before the routing.

Henning Rogge

-- 
We began as wanderers, and we are wanderers still. We have lingered
long enough on the shores of the cosmic ocean. We are ready at last to
set sail for the stars - Carl Sagan

---

From: Teco Boot <[email-masked]>
Date: Mon, 5 Aug 2013 16:23:11 +0200

> the source address for locally originated packets should be well known

I think it MUST work. Otherwise, apps will not run after enabling SADR. Better not.
In practice this means there is always a (set of) non-source_address_dependent default route(s). 

Teco

---

From: Teco Boot <[email-masked]>
Date: Mon, 5 Aug 2013 16:40:54 +0200

> 1+2 amount to the same thingŠ
Are you sure?
Routing table:
  to 2001:db8:10::1 from 2001:db8:1::/48 via fe80::1
  to 2001:db8:10::/48 from 2001:db8:1::1 via fe80::2
Packet has source 2001:db8:1::1, destination 2001:db8:10::1
With rule 1, nexthop is fe80::1
With rule 2, nexthop is fe80::2

Rule 1 is (to_be_fixed) running code in Linux and proposed in draft-troan-homenet-sadr-00.
I can agree on this.

I suggest the sadr draft is updated so it reflects this choice with notation of (D, S) -> Nexthop. First D, then S.
I also suggest ::/0 notation for match all, for source and destination (so not using * for source ::/0).

Teco

---

From: Ray Hunter <[email-masked]>
Date: Mon, 05 Aug 2013 19:12:56 +0200

> Teco Boot <mailto:[email-masked]>
> 5 August 2013 16:40
Exactly.

and then throw 

2001:db8:10::1/48 from 2001:db8:1::/48 via fe80::3

into the mix, and it looks to me like it would be possible to have a
forwarding loop without a routing loop (unless someone provides further
clarification).
> Wes Beebee (wbeebee) <mailto:[email-masked]>
> 5 August 2013 15:34
>
> ------------------------------------------------------------------------

-- 
Regards,
RayH

---

From: Teco Boot <[email-masked]>
Date: Mon, 5 Aug 2013 23:13:18 +0200

> forwarding loop without a routing loop (unless someone provides further

If all routers follow same rule, why would there be a loop?

For completeness, there is another rule in Fred's work. It suggests additional fib entries composed with intersections of source and destination prefixes, with intersections of the next hops. In my example, there will be a to 2001:db8:10::1 from 2001:db8:1::1 blackhole route.
Not my preference. There is nothing wrong with selecting one or the other, as long as we pick one of them and disallow the other.

Teco

---

From: Lorenzo Colitti <[email-masked]>
Date: Tue, 6 Aug 2013 12:20:07 +0900

> the source address for locally originated packets should be well known

I just tested this and it does work (on a not-so-new 3.5.x kernel).

Specifically, with these addresses:

$ ip -6 addr list scope global temporary | grep -v lft
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qlen 1000
    inet6 2401:fa00:4:1000:e1f8:a201:fd06:4beb/64 scope global temporary
dynamic
3: wlan0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qlen 1000
    inet6 2401:fa00:4:1012:19b6:e86a:e1a3:168b/64 scope global temporary
dynamic

and with a default route out eth0, I configured source routing so anything
coming from 2401:fa00:4:1012::/64 goes out on wlan0:

$ sudo ip -6 rule add from 2401:fa00:4:1012::/64 lookup 100
$ sudo ip -6 route add table 100 default dev wlan0 via fe80::5:73ff:fea0:fb

Then when I send packets:

$ python
[...]
>>> from socket import *
>>> s = socket(AF_INET6, SOCK_DGRAM, IPPROTO_UDP)
>>> s.sendto("foo", ("2000::", 53))
3
>>> s = socket(AF_INET6, SOCK_DGRAM, IPPROTO_UDP)
>>> s.bind(("2401:fa00:4:1012:19b6:e86a:e1a3:168b", 0))
>>> s.sendto("foo", ("2000::", 53))
3

The first packet goes out on eth0, the second on wlan0.

---

From: Ray Hunter <[email-masked]>
Date: Tue, 06 Aug 2013 18:07:54 +0200

<snip>
 
> If all routers follow same rule, why would there be a loop?
There wouldn't. We just need to make sure that they do all follow the
same rules (apparently not the case currently).

<snip>

-- 
Regards,
RayH

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 07 Aug 2013 12:26:14 +0200

> 1. Two step matching destination first [...]
> 2. Two step matching source first [...]
> 3. Single step longest match with Fuzzy aspects [...]

I was under the impression that there is consensus that (1) is the
right semantics, at least for Homenet.

As far as I understand, (4) is just a description of a limitation/bug
in the Linux kernel; Lorenzo will correct me if I've misunderstood,
but I'm pretty sure he's not actually advocating this semantics.

I do not understand proposal (3).

Proposal (2) is technically correct, but will require inserting
additional routes into the routing domain in most realistic
topologies.  (I suspect it can be done automatically in a distributed
fashion, but I haven't thought about it seriously.)

> Is there a serious risk here that we may get forwarding loops,

It is clear that (1) and (2) cannot coexist in the same network, since
they will cause persistent routing loops in most realistic topologies.
See the last paragraph of Section 2.2.2 in draft-boutier for an
example.  The general case is described in Section 4.2.

> packets dropped by filters due to incorrect egress gateway selection,

As mentioned before, this will happen in a hybrid network (ordinary
next-hop routers mixed with dest-source routers) if the dest-source
subgraph is not connected.  I consider this as a mild form of failure,
much preferable to persistent routing loops.

-- Juliusz