Subject: Re: [homenet] source routing requirements for routing protocols

From: Teco Boot <[email-masked]>
Date: Sat, 3 Aug 2013 15:42:44 +0200

I tested SADR with Linux IPv6_SUBTREES, with disappointing outcome.
I posted my results on devnet, http://www.spinics.net/lists/netdev/msg245231.html
Can you verify?
I included the posting for convenience.

Teco

Op 2 aug. 2013, om 12:15 heeft Teco Boot <[email-masked]> het volgende geschreven:

> For destination & source address routing, I prefer the single routing table approach with IPV6_SUBTREES over the multiple tables with ip rules approach.
> Can some take a look at my findings? It looks broken. It seems the source address check in route cache is missing.
> 
> Teco
> 
> 
> Output:
> ==========
> this is my system:
> Linux ubuntu 3.8.0-25-generic #37-Ubuntu SMP Thu Jun 6 20:47:30 UTC 2013 i686 i686 i686 GNU/Linux
> CONFIG_IPV6_SUBTREES=y
> ... clean up for our experiment
> ... add a link-local
> ... add default
> ... add some source address specific defaults
> ====> now I have this routing table
> default from 2001:db8:10::/48 via fe80::10 dev eth0  metric 1024 
> default from 2001:db8:11::/48 via fe80::11 dev eth0  metric 1024 
> default from 2001:db8:12::/48 via fe80::12 dev eth0  metric 1024 
> fe80::1 dev eth0  proto kernel  metric 256 
> default via fe80::ff dev eth0  metric 1024 
> ====> show route to same destination
> 2001:db8:babe::1 from 2001:db8:10::1 via fe80::10 dev eth0  metric 0 \    cache 
> 2001:db8:babe::1 from 2001:db8:11::1 via fe80::ff dev eth0  metric 0 \    cache 
> 2001:db8:babe::1 from 2001:db8:12::1 via fe80::ff dev eth0  metric 0 \    cache 
> 2001:db8:babe::1 from 2001:db8:1::1 via fe80::ff dev eth0  metric 0 \    cache 
> 2001:db8:babe::1 from :: via fe80::ff dev eth0  metric 0 \    cache 
> ====> show route to different destinations
> 2001:db8:cafe::10 from 2001:db8:10::1 via fe80::10 dev eth0  metric 0 \    cache 
> 2001:db8:cafe::11 from 2001:db8:11::1 via fe80::11 dev eth0  metric 0 \    cache 
> 2001:db8:cafe::12 from 2001:db8:12::1 via fe80::12 dev eth0  metric 0 \    cache 
> 2001:db8:cafe::21 from 2001:db8:1::1 via fe80::ff dev eth0  metric 0 \    cache 
> 2001:db8:cafe::22 from :: via fe80::ff dev eth0  metric 0 \    cache 
> ====> now the route cache is
> 2001:db8:babe::1 from 2001:db8:10::/48 via fe80::10 dev eth0  metric 0 \    cache 
> 2001:db8:babe::1 via fe80::ff dev eth0  metric 0 \    cache 
> 2001:db8:cafe::10 from 2001:db8:10::/48 via fe80::10 dev eth0  metric 0 \    cache 
> 2001:db8:cafe::11 from 2001:db8:11::/48 via fe80::11 dev eth0  metric 0 \    cache 
> 2001:db8:cafe::12 from 2001:db8:12::/48 via fe80::12 dev eth0  metric 0 \    cache 
> 2001:db8:cafe::21 via fe80::ff dev eth0  metric 0 \    cache 
> 2001:db8:cafe::22 via fe80::ff dev eth0  metric 0 \    cache 
> 
> 
> 
> My script:
> =======
> #!/bin/sh
> 
> echo "this is my system:" 
> uname -a
> grep IPV6_SUBTREES /boot/config-3.8.0-25-generic
> 
> echo ... clean up for our experiment
> ip -6 address flush dev eth0
> ip -6 route flush table all
> 
> echo ... add a link-local
> ip address add fe80::1 dev eth0
> 
> echo ... add default
> ip -6 route add default via fe80::ff dev eth0
> 
> echo ... add some source address specific defaults
> ip -6 route add default from 2001:db8:10::/48 via fe80::10 dev eth0
> ip -6 route add default from 2001:db8:11::/48 via fe80::11 dev eth0
> ip -6 route add default from 2001:db8:12::/48 via fe80::12 dev eth0
> 
> echo -n "====> "
> echo now I have this routing table
> ip -6 -o route show table main
> 
> echo -n "====> "
> echo show route to same destination
> ip -6 -o route get 2001:db8:babe::1 from 2001:db8:10::1
> ip -6 -o route get 2001:db8:babe::1 from 2001:db8:11::1
> ip -6 -o route get 2001:db8:babe::1 from 2001:db8:12::1
> ip -6 -o route get 2001:db8:babe::1 from 2001:db8:1::1
> ip -6 -o route get 2001:db8:babe::1
> 
> echo -n "====> "
> echo show route to different destinations
> ip -6 -o route get 2001:db8:cafe::10 from 2001:db8:10::1
> ip -6 -o route get 2001:db8:cafe::11 from 2001:db8:11::1
> ip -6 -o route get 2001:db8:cafe::12 from 2001:db8:12::1
> ip -6 -o route get 2001:db8:cafe::21 from 2001:db8:1::1
> ip -6 -o route get 2001:db8:cafe::22
> echo -n "====> "
> echo now the route cache is
> ip -6 -o route show cache
> 
> 
> 

Op 29 jul. 2013, om 16:32 heeft David Lamparter <[email-masked]> het volgende geschreven:

> On Mon, Jul 29, 2013 at 03:35:41PM +0200, Lorenzo Colitti wrote:
>> On Mon, Jul 29, 2013 at 1:27 PM, Michael Richardson
>> <[email-masked]>wrote:
>> 
>>> 1) if we are going to introduce a new route to deal with the
>>>   conflict, then the routing protocol must be able to express
>>>   what might appear to be multiple routes to the same dest/prefix.
>>> 
>> 
>> I believe the routes only need to be local and do not need to appear on the
>> wire and in the routing protocol (in fact, they don't even need to be
>> stored locally; the draft claims that they can be recalculated when adding
>> / removing real routes from the FIB).
>> 
>> As regards the reason for existence of the routes themselves, David
>> Lamparter tells me that he has in fact gotten the Linux IPv6 source routing
>> code (the mythical CONFIG_IPV6_SUBTREES?) to work on 3.8. Attempting to CC
>> a randomly-found email address I have for him so he can comment directly.
>> David?
> 
> (warning: wall of text.  skip down to last paragraph for results.)
> 
> I've tested the following setup:
> 
> host A - router
> # system: Linux 3.8.3
> # CONFIG_IPV6_SUBTREES=y
> # ip utility, iproute2-ss130221
> 
> # (0) enable ipv6 forwarding (...)
> 
> # (1) set routes
> 
> ip link add name test0 type dummy
> ip link add name test1 type dummy
> ip link add name test2 type dummy
> ip link add name test3 type dummy
> ip link set test0 up
> ip link set test1 up
> ip link set test2 up
> ip link set test3 up
> ip -6 route add 2001:db8::/32 via fe80::1 dev test0
> ip -6 route add 2001:db8:dead::/48 from 2001:db8:cafe:1::/64 via fe80::1 dev test1
> ip -6 route add 2001:db8:dead::/48 from 2001:db8:cafe:2::/64 via fe80::1 dev test2
> ip -6 route add 2001:db8:dead::/48 from 2001:db8:cafe:2::f00d/128 via fe80::1 dev test3
> ip -6 route add 2001:db8:dead:beef::/64 dev test3
> 
> # (2) connection to packet source - fix as needed
> ip -6 link set veth0 up
> ip -6 addr add fe80::1/64 dev veth0
> ip -6 addr add 2001:db8:cafe:0::1/64 dev veth0
> ip -6 addr add 2001:db8:cafe:1::1/64 dev veth0
> ip -6 addr add 2001:db8:cafe:2::1/64 dev veth0
> 
> # (3) now start 4 tcpdumps/wiresharks/... on test0..3
> 
> 
> host B - packet source
> 
> # - interlude: shortcut to virtualise host B, skip if appropriate -
> #   unshare -n /bin/bash
> # you now have a shell in a separate network namespace. now do:
> #   ip link set lo up
> #   ip link add name veth0 type veth peer name veth0 netns 1
> # you now have a "veth0" interface on both your host and your network
> # namespace shell session.  don't forget to set them "up".
> # - end interlude -
> 
> # (0) default route over linklocal, persistent over tests
> ip -6 route add ::/0 via fe80::1 dev veth0
> 
> # (1) source 2001:db8:cafe:0::2, does not match sources
> ip -6 addr add 2001:db8:cafe:0::2/64 dev veth0
> ping6 -c 3 2001:db8::1		 # => test0 on router
> ping6 -c 3 2001:db8:dead::1	 # => unreachable, no route [*]
> ping6 -c 3 2001:db8:dead:beef::1 # => test3 on router
> ip -6 addr del 2001:db8:cafe:0::2/64 dev veth0
> 
> # (2) source 2001:db8:cafe:1::2, matches "test1" source spec
> ip -6 addr add 2001:db8:cafe:1::2/64 dev veth0
> ping6 -c 3 2001:db8::1		 # => test0 on router
> ping6 -c 3 2001:db8:dead::1	 # => test1 on router
> ping6 -c 3 2001:db8:dead:beef::1 # => test3 on router
> ip -6 addr del 2001:db8:cafe:1::2/64 dev veth0
> 
> # (3) source 2001:db8:cafe:2::2, matches "test1" source spec
> ip -6 addr add 2001:db8:cafe:2::2/64 dev veth0
> ping6 -c 3 2001:db8::1		 # => test0 on router
> ping6 -c 3 2001:db8:dead::1	 # => test2 on router
> ping6 -c 3 2001:db8:dead:beef::1 # => test3 on router
> ip -6 addr del 2001:db8:cafe:2::2/64 dev veth0
> 
> # (4) source 2001:db8:cafe:2::2, matches more-specific /128 source
> ip -6 addr add 2001:db8:cafe:2::f00d/64 dev veth0
> ping6 -c 3 2001:db8::1		 # => test0 on router
> ping6 -c 3 2001:db8:dead::1	 # => test3 on router
> ping6 -c 3 2001:db8:dead:beef::1 # => test3 on router
> ip -6 addr del 2001:db8:cafe:2::f00d/64 dev veth0
> 
> 
> so, for the 2001:db8:dead::1 destination, the following happens:
> - source 2001:db8:cafe:0::2 - no source match - icmp unreachable
> - source 2001:db8:cafe:1::2 - matches ...1::/64 dev test1
> - source 2001:db8:cafe:2::2 - matches ...2::/64 dev test2
> - source 2001:db8:cafe:2::f00d - matches ...2::f00d/128 dev test3
> 
> 
> RESULT  (stop skipping here)
> ======
> 
> The non source specific routes keep working as intended.  The source
> specific routes work as intended, doing a longest-match on the source.
> The lookup also is "final", i.e. after not finding a route with a source
> match (=> first test case), Linux returns an "unreachable".
> 
> As far as I've been following, this is the desired effect?
> 
> Cheers,
> 
> 
> -David
> _______________________________________________
> homenet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/homenet

---

From: David Lamparter <[email-masked]>
Date: Tue, 6 Aug 2013 13:12:56 +0200

> I included the posting for convenience.

Indeed I failed to take Linux's routing cache into account.  (Basically,
since I was testing interactively in a shell, I was too slow to trigger
this issue.)

So the core logic is correct, but it breaks as soon as there is a cache
entry.  The way the route cache works, this is a bit annoying to fix
correctly.

If someone wants to work on SADR on Linux right now, I have a patch that
partially fixes the cache lookup, but it only works as long as the
source specifications don't overlap.  [which should be the case in
homenet most of the time, but note it breaks when there is a route with
::/0 source.]

(For the interested, fib6_lookup/_1() and ip6_pol_route() need to be
restructured.  Also, the "BACKTRACK" macro is completely f*ken useless.
Not sure if this ever worked.)

-David

---

From: David Lamparter <[email-masked]>
Date: Tue, 6 Aug 2013 13:20:25 +0200

> entry.  The way the route cache works, this is a bit annoying to fix

Oh wait... I just had the evilest idea to fix this.  We can simply go
not create a cache entry for subtree routes.  If someone wants to do
this, edit net/ipv6/route.c and find this fragment:

	if (!(rt->rt6i_flags & (RTF_NONEXTHOP | RTF_GATEWAY)))
		nrt = rt6_alloc_cow(rt, &fl6->daddr, &fl6->saddr);
	else if (!(rt->dst.flags & DST_HOST))
		nrt = rt6_alloc_clone(rt, &fl6->daddr);

replace with:

	if (FIB6_SUBTREE(fn) || rt->rt6i_src.plen)
		nrt = NULL; /* lalala */
	else if (!(rt->rt6i_flags & (RTF_NONEXTHOP | RTF_GATEWAY)))
		nrt = rt6_alloc_cow(rt, &fl6->daddr, &fl6->saddr);
	else if (!(rt->dst.flags & DST_HOST))
		nrt = rt6_alloc_clone(rt, &fl6->daddr);

(I didn't test this, I'll try out later if no one else beats me to it)

-David

---

From: Dave Taht <[email-masked]>
Date: Tue, 6 Aug 2013 04:21:32 -0700

> Not sure if this ever worked.)

git clone git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next.git

There have been a half dozen commits in linux's net-next kernel tree
around the route cache in the last few weeks, notably one simplified
ip rule for dealing with default routes, another broke out the genid
stuff to make route flushing ipv4 not affect ipv6 and vice versa. Can
I encourage those looking at this to look at that and see what can be
leveraged/improved/fixed/de-borked?

commit 7764a45a8f1fe74d4f7d301eaca2e558e7e2831a
Author: Stefan Tomanek <[email-masked]>
Date:   Thu Aug 1 02:17:15 2013 +0200

    fib_rules: add .suppress operation

    This change adds a new operation to the fib_rules_ops struct; it allows the
    suppression of routing decisions if certain criteria are not met by its
    results.

    The first implemented constraint is a minimum prefix length added to the
    structures of routing rules. If a rule is added with a minimum prefix length
    >0, only routes meeting this threshold will be considered. Any other (more
    general) routing table entries will be ignored.

    When configuring a system with multiple network uplinks and default routes,
    is often convinient to reference the main routing table multiple times - but
    omitting the default route. Using this patch and a modified "ip" utility, th
    can be achieved by using the following command sequence:

      $ ip route add table secuplink default via 10.42.23.1

      $ ip rule add pref 100            table main prefixlength 1
      $ ip rule add pref 150 fwmark 0xA table secuplink

    With this setup, packets marked 0xA will be processed by the additional rout
    table "secuplink", but only if no suitable route in the main routing table c
    be found. By using a minimal prefixlength of 1, the default route (/0) of th
    table "main" is hidden to packets processed by rule 100; packets traveling t
    destinations with more specific routing entries are processed as usual.

-- 
Dave Täht

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

---

From: David Lamparter <[email-masked]>
Date: Tue, 6 Aug 2013 13:28:11 +0200

> leveraged/improved/fixed/de-borked?

I've already been working on top of net-next, I have skimmed over those
changes and don't believe they come in helpful.  Part of the problem is
that the route cache entries simply aren't created correctly.  I'm not
sure if that's the entire problem - can't test the lookup logic without
correct entries - but I believe so at a confidence of 75%.

What I'd really like to do is just copy the subtree pointer from the
original route to the cache entry.  But that gives me 2 problems - (a) I
need to check the deletion semantics against ending up with a dead
pointer and (b) the code isn't designed to create a cache entry for a
"dead" route (which the parent of multiple source routes without a
default source route would be).  Cloning the subtree instead of copying
the pointer is an option in case (a) blows up, but if avoidable I'd like
to avoid it.

I'm still fiddling with this, but it might take a bit since I need to
keep doing some, er, paycheck work...

-David

---

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

>  since I was testing interactively in a shell, I was too slow to trigger

I thought the routing cache was gone on recent-enough linux kernels?

---

From: Robert Bradley <[email-masked]>
Date: Tue, 6 Aug 2013 13:18:38 +0100

> I thought the routing cache was gone on recent-enough linux kernels?

Only the IPv4 cache was removed; the IPv6 routing cache still exists for now.
-- 
Robert Bradley

---

From: David Lamparter <[email-masked]>
Date: Tue, 6 Aug 2013 14:49:52 +0200

> I thought the routing cache was gone on recent-enough linux kernels?

So thought I, but apparently that only happened for IPv4.  No idea what
the kernel guys' plan for IPv6 is in this regard...

---

From: Lorenzo Colitti <[email-masked]>
Date: Tue, 6 Aug 2013 23:58:36 +0900

> the kernel guys' plan for IPv6 is in this regard...

Unfortunately, it seems that their plan for IPv6 can generally be best
described as "send patches". :-(