Subject: Re: [homenet] Source-specific routes in Linux [was: atomic updates...]

From: Dave Taht <[email-masked]>
Date: Sun, 5 May 2013 14:38:43 -0700

On Sun, May 5, 2013 at 1:05 PM, Juliusz Chroboczek
<[email-masked]> wrote:
>> It's not ECMP for ipv6 I'm looking to see solved for multiple routing
>> protocols, but the multiple ipv6 prefixes/multiple exits source
>> routing problem.
>
> As you well know, Dave, we've been working on that for the last
> fortnight or so.
>
> We've run into a limitation of the kernel:
>
>   http://www.spinics.net/lists/netdev/msg235316.html

Hmm. Given that this code path has only barely been exercised before
and so many changes to the routing paths have happened in the last 2+
years, I'm not surprised its broken.

>
> Unfortunately, I've had no reply to my question:
>
>   http://www.spinics.net/lists/netdev/msg235346.html
>
> So it looks like we're going to have to dynamically generate rule
> table entries... sigh.

Well, given the work going into mptcp in particular, a better API for
src specific routing for ipv6 than the ip rule system seems like a
good idea.

 Widening the distribution a little bit...

>> The homenet folk demonstrated this form of ipv6 multihoming working
>> (using a version of OSPF and BIRD, I believe) at the last ietf.
>
> That is interesting.  Would you happen to know how they're interfacing
> with the kernel?  Or perhaps have a link to their code?

I don't know where the ietf 86 bird work on multihoming went. (?)
Patterson's original work on ospf is here:

https://github.com/paterben/bird-homenet

and the ietf drafts are here

http://tools.ietf.org/wg/homenet/

> -- Juliusz

-- 
Dave Täht

Fixing bufferbloat with cerowrt: http://www.teklibre.com/cerowrt/subscribe.html

---

From: Dave Taht <[email-masked]>
Date: Sun, 5 May 2013 15:23:37 -0700

On Sun, May 5, 2013 at 2:38 PM, Dave Taht <[email-masked]> wrote:
> Well, given the work going into mptcp in particular,

This was a very good overview of where that work stands.

http://lwn.net/Articles/544399/

> a better API for

-- 
Dave Täht

---

From: Markus Stenberg <[email-masked]>
Date: Tue, 7 May 2013 11:08:14 +0000 (UTC)

> http://tools.ietf.org/wg/homenet/

Patterson's work is mostly of historic interest. 

[1] https://github.com/fingon/hnet has 'super-repository' which
has custom NetKit version, OpenWRT AA github link and everything
else to get it running on a Linux desktop for playing with
(with OpenWRT UML images running in a NetKit lab).

[2] https://github.com/fingon/hnet-openwrt-feed contains just
OWRT package feed for the stuff.

[3] https://github.com/fingon/hnet-core contains most of the new code.

I know it for a fact that people have gotten it running using any
of those approaches ([1] contains [2] and [3], and [2] refers to
[3]). Still, just for playing, [1] is probably the easiest
choice (given correct Linux distro, just following the README
should be enough).

Yet another implementation of interest might be:

https://github.com/edderick/quagga_zOSPF/

[1]/[2] versions do not interoperate with it (but they interoperate with
Arkko one); latest [3] version interoperates with it, but not Arkko..)

Cheers,

-Markus

P.S. [1] and [2] contain 'most recent tested' version, which as
of now, is the post-IETF86-bugfixes one; bleeding edge
development happens in [3] and it's sub-branch(es), but [1] and
[2] refer just to stable points of [3].

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 07 May 2013 13:46:02 +0200

> [3] https://github.com/fingon/hnet-core contains most of the new code.

Just to clarify -- this does OSPF-based autoconf and prefix
assignment, but not source-specific routing, right?

If you're actually doing source-specific routing, please show me how
you speak to the kernel.

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Tue, 7 May 2013 14:51:22 +0300

> If you're actually doing source-specific routing, please show me how

Most of that code is in Lua, and while I could have included C extension module that did similar things as ip -6 does, I didn't bother. So I'm just using ip -6 {route,rule} to set up source-specific rules that map to destination tables. One (destination-based) routing table is maintained by routing protocol, and the rest by Lua code which figures external defaults based on routes within routing protocol implementation. Not pretty, but it _does_ work.

Cheers,

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 07 May 2013 14:03:30 +0200

> Most of that code is in Lua, and while I could have included
> C extension module that did similar things as ip -6 does, I didn't
> bother.

We're doing pretty the same in our prototype code (saying
system("ip...") rather than speaking the netlink dialect of the day).
Could you point us at the relevant code, please?

> So I'm just using ip -6 {route,rule} to set up source-specific rules
> that map to destination tables.

Ah, okay.  So you're using rules, just as we found out (the hard way)
that we need to do.

> One (destination-based) routing table is maintained by routing
> protocol, and the rest by Lua code which figures external defaults
> based on routes within routing protocol implementation.

Nice hack.

-- Juliusz

---

From: Ole Troan <[email-masked]>
Date: Wed, 8 May 2013 09:56:50 +0200

Juliusz,

there is also a draft: http://tools.ietf.org/html/draft-troan-homenet-sadr-00

an implementation using Linux table support will require duplication of route entries into multiple tables.

cheers,
Ole

On May 7, 2013, at 14:03 , Juliusz Chroboczek <[email-masked]> wrote:

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

---

From: Dave Taht <[email-masked]>
Date: Wed, 8 May 2013 01:51:00 -0700

>   http://www.spinics.net/lists/netdev/msg235346.html

One thing that bugs me about hacks and workarounds like this is that Linux
(as well as openwrt) are intensely mutable systems, and it's totally
possible to improve linux rather than limp around in userspace.

I have long disliked the ip rule system in its primary use prior to now
(vpns), as buggy, arbitrary, and subject to race conditions, so if a better
api and methods for injecting/managing source address dependent routing
information could be designed I'm pretty sure there would be much
enthusiasm across the vpn, mptcp/sctp, and routing worlds for getting it
into linux itself.

> > based on routes within routing protocol implementation.

Except that probably it interacts badly with existing vpn manipulation of
these tables.

-- 
Dave Täht

Fixing bufferbloat with cerowrt:
http://www.teklibre.com/cerowrt/subscribe.html

---

From: Tim Chown <[email-masked]>
Date: Wed, 8 May 2013 10:29:52 +0100

> Arkko one); latest [3] version interoperates with it, but not Arkko..)

Hi,

So the github zOSPF iplementation above was done this year by an undergraduate project student of mine, Ed Seabrook.  He has tested his code against both Ben's and Markus' implementations, using a netkit test environment, with pretty successful results overall.  Ed has given some feedback to the draft authors based on his experience.

Ed chose to build on Quagga because he knew the bird implementations existed, and wanted to show interoperability with a different platform.  Ed has briefly looked at the source routing issue, and may do further work on that, but there's nothing in the git repository for that as yet.

As an aside I'm working on the homenet arch update this week, so please do comment on any outstanding issues you have to the list asap if you want them included in the imminent new version.

Tim

---

From: Dave Taht <[email-masked]>
Date: Wed, 8 May 2013 02:45:29 -0700

On Wed, May 8, 2013 at 2:29 AM, Tim Chown <[email-masked]> wrote:

> So the github zOSPF iplementation above was done this year by an
> undergraduate project student of mine, Ed Seabrook.  He has tested his code
> against both Ben's and Markus' implementations, using a netkit test
> environment, with pretty successful results overall.  Ed has given some
> feedback to the draft authors based on his experience.
>

It would be helpful if those comments were more public.

>
> Ed chose to build on Quagga because he knew the bird implementations
> existed, and wanted to show interoperability with a different platform.

CeroWrt uses quagga-RE (for BGPpgp and babel support), and if it is
possible to merge these patches into that branch, and the results useful,
I'd be delighted to do so...

> Ed has briefly looked at the source routing issue, and may do further work
> on that, but there's nothing in the git repository for that as yet.
>
>
Given that there are more eyeballs on the problem this month than ever
before I would hope that some faster progress be made...

/sign me
delighted to have got rid of my entire prior patch burden and willing to
take on new stuff

As an aside I'm working on the homenet arch update this week, so please do
> comment on any outstanding issues you have to the list asap if you want
> them included in the imminent new version.
>
> Tim

-- 
Dave Täht

---

From: Steven Barth <[email-masked]>
Date: Wed, 08 May 2013 11:48:01 +0200

On 08.05.2013 10:51, Dave Taht wrote:
> One thing that bugs me about hacks and workarounds like this is that
> Linux (as well as openwrt) are intensely mutable systems, and it's
> totally possible to improve linux rather than limp around in userspace.
>
> (vpns), as buggy, arbitrary, and subject to race conditions, so if a
> better api and methods for injecting/managing source address dependent
> routing information could be designed I'm pretty sure there would be
> much enthusiasm across the vpn, mptcp/sctp, and routing worlds for
> getting it into linux itself.

Hmm I must admit I'm wondering about this for the OpenWrt stack as well.

We have switched to RA-Handling in userspace for similar reasons already 
so I guess it's only the next logical step to create separate routing 
tables for each upstream interface to do source-based routing and filter 
out ULA-traffic on this layer instead of through iptables.

Having one central userspace management daemon for routing and address / 
prefix delegation in general might not be the best or cleanest solution 
in the end but I guess there is no better way right now.

---

From: Ole Troan <[email-masked]>
Date: Wed, 8 May 2013 12:26:10 +0200

[...]

> We have switched to RA-Handling in userspace for similar reasons already so I guess it's only the next logical step to create separate routing tables for each upstream interface to do source-based routing and filter out ULA-traffic on this layer instead of through iptables.

don't do it per upstream interface, that wouldn't work. per next-hop might. the draft suggests a single table with source constrained routers and backtracking.

> Having one central userspace management daemon for routing and address / prefix delegation in general might not be the best or cleanest solution in the end but I guess there is no better way right now.

cheers,
Ole

---

From: Ole Troan <[email-masked]>
Date: Wed, 8 May 2013 12:28:14 +0200

[...]

cheers,
Ole

---

From: Steven Barth <[email-masked]>
Date: Wed, 08 May 2013 12:51:07 +0200

Ole Troan <[email-masked]> wrote:

>[...]
>
>> We have switched to RA-Handling in userspace for similar reasons
>already so I guess it's only the next logical step to create separate
>routing tables for each upstream interface to do source-based routing
>and filter out ULA-traffic on this layer instead of through iptables.
>
>don't do it per upstream interface, that wouldn't work. per next-hop
>might. the draft suggests a single table with source constrained
>routers and backtracking.
>

Ah yes thanks for the hint. Please correct me if I got this wrong: I guess per interface would be problematic if there are multiple routers on the upstream link offering different prefixes. However in case of prefix delegation via DHCPV6-pd like on usual home ISP connections would it not be problematic to attribute the prefix to any specific router? - if there would be multiple routers which I guess is unlikely in that situation. One could maybe attribute the prefix to the source address of the DHCPv6 server but that sounds problematic to me aswell. Hmm did I miss something or am I completely on the wrong track now?

Thanks,
Steven

---

From: Ole Troan <[email-masked]>
Date: Wed, 8 May 2013 12:58:52 +0200

Steven,

> Ah yes thanks for the hint. Please correct me if I got this wrong: I guess per interface would be problematic if there are multiple routers on the upstream link offering different prefixes. However…

at least we're on the same track (and I think the correct one). ;-)

on the border router this is quite simple. if a border router uses PD and it discovers a default router on the same interface,
that will result in a SADR route (S, D) -> interface, next-hop. where S is PD prefix, D is ::/0, interface is the interface the PD was received
on and next-hop is whatever router discovery came back with.

the issue is with internal routers, where you may have an internal router connected to two exits on the same link, or behind another
IR that is connected to both..., i.e. arbitrary topology. 

cheers,
Ole

---

From: Lorenzo Colitti <[email-masked]>
Date: Wed, 8 May 2013 20:06:19 +0900

On Wed, May 8, 2013 at 7:51 PM, Steven Barth <[email-masked]> wrote:

> if there would be multiple routers which I guess is unlikely in that
> situation. One could maybe attribute the prefix to the source address of
> the DHCPv6 server but that sounds problematic to me aswell.
>

So you're talking about the case where you have ISP1 and ISP2 "plugged into
a switch together with your router"?

In that case I can't see any better way than attempting to match the
link-local IPv6 address that you got the RA from to the link-local address
of the DHCPv6 server you got the PD from.

I can't think of a situation why these would be different, but perhaps
there is. Can the DHCPv6 server be a global address?

---

From: Steven Barth <[email-masked]>
Date: Wed, 08 May 2013 14:54:28 +0200

> IR that is connected to both..., i.e. arbitrary topology.
OK, thanks again for the explanation. I think I will add an additional 
routing-table-ID parameter to the network daemon. This way any routing 
daemon that is going to be properly integrated into OpenWrt can select a 
target table for each route, prefix, etc.

Cheers,

Steven

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 09 May 2013 00:46:47 +0200

> One thing that bugs me about hacks and workarounds like this is that Linux (as
> well as openwrt) are intensely mutable systems, and it's totally possible to
> improve linux rather than limp around in userspace.

I can only agree with you.

Now, as mentioned in my second message linked above, source-specific
routing for IPv6 in a single table appears to be supposed to work with
CONFIG_IPV6_SUBTREES.  My tests indicate it doesn't, at least in
recent kernels.

I've tried to look at the relevant code (in ipv6/ipv6_fib.c and
ipv6/route.c), and this code is way beyond my grokking abilities.
Should a friendly kernel hacker choose to fix this, we can switch our
implementation to using that simpler API with little effort.
(Acutally deleting a bunch of code -- Matthieu is going to hate me.)

> api and methods for injecting/managing source address dependent routing

My preference goes towards dumping all routes into a single routing
table.  This applies both to source-specific routes, to
input-interface specific routes (which is what Steven Barth was
referring to), as well as to any future extensions to the model
(TOS-specific routes, flow-id-specific routes, evil-bit-specific
routes, etc.)

The semantics of such an API is ambiguous, but userspace can work
around that by injecting extra routes into the FIB.  The number of
such routes is at worst proportional to r^s, where r is the number of
"real" routes and s is the number of selection mechanisms, but (1)
this worst case is unlikely to happen in practice, and (2) this number
can be greatly reduced by having reasonable default disambiguation
rules in the kernel (use the destination as the primary key, the
source as the secondary key, and any other selectors as the tertiary key).

-- Juliusz

---

From: Tim Chown <[email-masked]>
Date: Mon, 20 May 2013 14:32:03 +0100

> It would be helpful if those comments were more public.  

Markus and Edward have discussed the issues arising from Edward's project work.  There is a small number of open questions/ambiguities resulting. I agree these should be summarised and posted here for comment to help improve the relevant draft(s).

> 
> Ed chose to build on Quagga because he knew the bird implementations existed, and wanted to show interoperability with a different platform.  
> 
> CeroWrt uses quagga-RE (for BGPpgp and babel support), and if it is possible to merge these patches into that branch, and the results useful, I'd be delighted to do so...

It would be useful to get some code review... I'll email you off-list.

Tim