Re: [Babel-users] Route-dete :wq
Juliusz Chroboczekwrites: >> Well, that is quite useful in any case. > > It's very useful, but it creates extra state, extra timers, and might > timeout over wireless (EIGRP style). So I'm not really sure how I feel > about it. Sure, it adds a bit of temporary state; but if it times out it just means you'll just end up back at the hold time mechanism. I.e., it doesn't make anything worse... -Toke ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
Re: [Babel-users] Route-dete :wq
>>> My thinking on this is that you only need the host routes when a client >>> actually roams. >> This is only going to work if you either use no hold time, or implement >> the optional algorithm in Section 3.1 of rfc6126bis. > I'm assuming you mean the ACKed retraction algorithm in Section 3.5.5? Yes, sorry. Colloquially known as Chouasne's algorithm. > Well, that is quite useful in any case. It's very useful, but it creates extra state, extra timers, and might timeout over wireless (EIGRP style). So I'm not really sure how I feel about it. (Take this litterally -- I don't know how I feel about it.) -- Juliusz ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
Re: [Babel-users] Route-dete :wq
Juliusz Chroboczekwrites: >> My thinking on this is that you only need the host routes when a client >> actually roams. > > This is only going to work if you either use no hold time, or implement > the optional algorithm in Section 3.1 of rfc6126bis. I'm assuming you mean the ACKed retraction algorithm in Section 3.5.5? Well, that is quite useful in any case. My implementation for Bird (pending review): http://trubka.network.cz/pipermail/bird-users/2018-February/011936.html -Toke ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
Re: [Babel-users] Route-dete :wq
On Fri, Mar 9, 2018 at 3:29 PM, Christof Schulzewrote: >> I start running into trouble with 1000+ routes using 1Mbit mcast. >> Sooner if I seriously >> slam the network with flent or something else that abuses mcast like mdns. >> YMMV. > > So what is the culprit here? What would it take to add an order of > magnitude? Most of the meshy networks run wifi mcast at 11Mbit or higher. Ath9k devices support this, many others don't. Experiment with the new unicast code, as that will transfer routes at the underlying rate of the medium (up to 300Mbit on wireless-n). Don't run odhcpd or network manager either. They tend to get in a tussle with babeld in the kernel. Simulate first, deploy second. Don't prematurely optimize. :) I have a backlog of other optimizations for babel lying about, ranging from trivial stuff like at least logging when you are low on compute or overbuffered: https://github.com/dtaht/rabeld/commit/b74b4a6f9b532717ee93346963efd894e94615b3 to something that tries to be more aware of compute bounds, to another thing that pushes some work down into the kernel via bpf > >> As for aggregation and filtering: Most of my Aps have at minimum, >> ethernet, and two channels - usually four, including the meshy links. >> The meshy links are ptp, so I've generally "wasted" an entire /22 ipv4 >> network to talk to the Aps. ipv6 /62s. >> >> The lab component of my network, for example, has two main links to >> the production net, and the gateways only announce the >> subnet it is on (172.22.0.0/16). This cuts the churn seen outside the >> network when I do crazy things like reboot the whole thing. >> >> The biggest problem I've run into, is that meshy links, are, meshy - >> and I've lost track of the number of times where >> I had a well defined /16 network in the lab suddenly leak all the >> meshy /32 bits over the worst possible link - because I plugged >> something in that was adhoc (and poorly) connected to the outside >> network that I shouldn't have. >> >> Lede creates one /48 ULA by default per AP, and then more /60s. I've >> had a tendency to try to share one /48, but more recently I was trying >> to go native ipv6 and disabled the ULA generation entirely. >> >> I don't bridge anything except sometimes on the last Aps on a link >> (which don't announce babel on that bridge). Bridging can do weird >> things to daemons that want also to be measuring the individual links. >> >> So in your network design I'd try to identify your backbone links and >> try upfront to rationally partition the network numbering scheme, >> and still, periodically try to optimize it. It makes no sense to >> export all the churn the last hop of a meshy, yet leaf network can >> have to the whole network. I'd simulate what you plan, and then slam >> it with traffic from every point with a tool like flent, and deploy >> cake or htb+fq_codel on the ISP up/downlinks. > > This being a Freifunk-Network, there is not going to be much planning of the > structure beyond mere basics. > Until now I just hoped we could get away with having 10K+ routes in one > network which would translate into 3k+ clients when considering many nodes > and 3 IPv6 addresses for each client which seems to be a reasonable amount > when taking into account a clat-address per client and IPv6 privacy > extensions. As toke noted, just distribute the /64. Source specific routing is cool, too, you should try distributing real ipv6 ranges from two or more gateways. > There are approaches to reduce the amount of routes per client including > using nat66 on each node. You certainly are making it sound like there > should be put some thought into reducing the amount of routes. This will be > the next step after we have more than just a few nodes / clients inside the > same network. > > BTW: the Freifunk networks use an autoupdater. This might just solve your > tree-climbing-problem in the long run... Across 6 versions of the OS in 6 years of deployment, and 5 different generations of hardware, my automation problem is hopeless. Of all the gear I've had to date the nanostation 5s, wndr3800s, and picostations have been the best. I'm having good results thus far with the ubnt UAP-AC-M-USes with the candeletech firmware - aside from not having enough flash for a web interface. > > Cheers > Christof > >> >> I'm working these days, on making netem better emulate wifi's >> behaviors. I'm not satisified with it yet. >> > >>> Note that babeld currently sends updates as a single burst when the upate >>> interval expires (the same is true of Toke's implementation of Babel, as >>> far as I'm aware). For very large networks, it would be good to split >>> updates into one-packet pieces that are sent throughout the update >>> interval. I'd be glad to accept a patch that does that. I'd rather like to keep the burst but measure how long it takes to transmit. > * making babel trigger updates on newly appeared routes > > >>> I've gone
Re: [Babel-users] Route-dete :wq
Christof Schulzewrites: > There are approaches to reduce the amount of routes per client > including using nat66 on each node. You certainly are making it sound > like there should be put some thought into reducing the amount of > routes. This will be the next step after we have more than just a few > nodes / clients inside the same network. My thinking on this is that you only need the host routes when a client actually roams. I.e., you assign a /64 to each node that clients can connect to, and announce that /64 to the whole network. As long as clients stay connected to the same node, no additional routing is required. Once a client roams to a different node, you install host routes (/128s) on the new node to redirect the traffic. This way you only need host nodes for clients that roam, which should be fewer than the total number of clients. Now, this of course requires clients to be well-behaved, which is where I think this could break down. I.e., the assumption is that the client will get an address from the RA on the first node, then keep that active while it is using it, and drop it and switch to the different prefix on another node. I *think* this is more or less what Linux does, but I'm not sure if it'll keep an address around even after there are no more RAs received for it if it is being used (active connections); if it doesn't, existing connections will obviously break... -Toke ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
Re: [Babel-users] Route-dete :wq
I start running into trouble with 1000+ routes using 1Mbit mcast. Sooner if I seriously slam the network with flent or something else that abuses mcast like mdns. YMMV. So what is the culprit here? What would it take to add an order of magnitude? As for aggregation and filtering: Most of my Aps have at minimum, ethernet, and two channels - usually four, including the meshy links. The meshy links are ptp, so I've generally "wasted" an entire /22 ipv4 network to talk to the Aps. ipv6 /62s. The lab component of my network, for example, has two main links to the production net, and the gateways only announce the subnet it is on (172.22.0.0/16). This cuts the churn seen outside the network when I do crazy things like reboot the whole thing. The biggest problem I've run into, is that meshy links, are, meshy - and I've lost track of the number of times where I had a well defined /16 network in the lab suddenly leak all the meshy /32 bits over the worst possible link - because I plugged something in that was adhoc (and poorly) connected to the outside network that I shouldn't have. Lede creates one /48 ULA by default per AP, and then more /60s. I've had a tendency to try to share one /48, but more recently I was trying to go native ipv6 and disabled the ULA generation entirely. I don't bridge anything except sometimes on the last Aps on a link (which don't announce babel on that bridge). Bridging can do weird things to daemons that want also to be measuring the individual links. So in your network design I'd try to identify your backbone links and try upfront to rationally partition the network numbering scheme, and still, periodically try to optimize it. It makes no sense to export all the churn the last hop of a meshy, yet leaf network can have to the whole network. I'd simulate what you plan, and then slam it with traffic from every point with a tool like flent, and deploy cake or htb+fq_codel on the ISP up/downlinks. This being a Freifunk-Network, there is not going to be much planning of the structure beyond mere basics. Until now I just hoped we could get away with having 10K+ routes in one network which would translate into 3k+ clients when considering many nodes and 3 IPv6 addresses for each client which seems to be a reasonable amount when taking into account a clat-address per client and IPv6 privacy extensions. There are approaches to reduce the amount of routes per client including using nat66 on each node. You certainly are making it sound like there should be put some thought into reducing the amount of routes. This will be the next step after we have more than just a few nodes / clients inside the same network. BTW: the Freifunk networks use an autoupdater. This might just solve your tree-climbing-problem in the long run... Cheers Christof I'm working these days, on making netem better emulate wifi's behaviors. I'm not satisified with it yet. Note that babeld currently sends updates as a single burst when the upate interval expires (the same is true of Toke's implementation of Babel, as far as I'm aware). For very large networks, it would be good to split updates into one-packet pieces that are sent throughout the update interval. I'd be glad to accept a patch that does that. * making babel trigger updates on newly appeared routes I've gone through different approaches for scheduling updtes, and the current master is more aggressive with scheduling updates. I'd need to check to make sure, but I believe it already does what you suggest. If you have time, could you please check if current master improves things; if it doesn't, we need to work together to improve the implementation (no protocol changes will be needed). You could also try Toke's implementation, which is very well written. * communicating the appearance of a route across the network outside babel and inserting that at the gateway I'm not sure what you mean. What do you think about those approaches? Please try current master. If not, we'll need to think together about redesigning our approach to sending triggered updates. -- Juliusz ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users -- () ascii ribbon campaign - against html e-mail /\ against proprietary attachments signature.asc Description: PGP signature ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
Re: [Babel-users] Route-dete :wq
> One thing that fell out of that was mainline babeld had a very > suboptimal routine for merging routes (also it's use of memcmp was > inefficient) - and juliusz put out a call for a qsorted implementation > a while back. Just to be clear -- the quadratic behaviour is for routes redistributed from another routing protocol. Routes learned from other protocols use a O(log n) data structure. But you're right to remind me of the issue, I really ought to take care of it after I get 1.8.1 out the door. > I have high hopes for the unicast stuff to lighten the routing load by > potentially orders of magnitude. We'll see. > The biggest problem I've run into, is that meshy links, are, meshy - > and I've lost track of the number of times where > I had a well defined /16 network in the lab suddenly leak all the > meshy /32 bits over the worst possible link - because I plugged > something in that was adhoc (and poorly) connected to the outside > network that I shouldn't have. Yes, filtering is error-prone. I have some ideas about making it less so. -- Juliusz ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
Re: [Babel-users] Route-dete :wq
On Wed, Mar 7, 2018 at 2:41 PM, Juliusz Chroboczekwrote: > Christof, I'm very much interested in your experiments, which are likely > to improve the quality of the Babel implementations. > >> We have update-interval set to 5 minutes to reduce the load on the network >> because we are hoping to run this topology on 500+ APs with 1000+ Clients. I wrote the rtod tool to experiment with creating large topologies. I've not got around to publishing the veth topos, but the tool is here: https://github.com/dtaht/rtod One thing that fell out of that was mainline babeld had a very suboptimal routine for merging routes (also it's use of memcmp was inefficient) - and juliusz put out a call for a qsorted implementation a while back. Elsewhere in babeld, atomic updates remain elusive. I made a bit of progress on that last year (unreachable routes have to keep the same metric to be an atomic change) but got beat by another bug that juliusz/martin(?) fixed later. These are both problems that I've long meant to get to, but the prospect of redeploying with the pending unicast feature and source specific routing, as well as reflashing a few dozen devices in treetops with modern code, has thus far stopped me. I kind of hope to use bird on a goodly portion of the next deployment, and hopefully this summer I can find someone that likes climbing trees in california more than I do. I have high hopes for the unicast stuff to lighten the routing load by potentially orders of magnitude. Somewhere in there (after breaking every routing daemon and protocol in multiple ways with rtod, and making several improvements to "rabeld", and scheming to replace all! all of it, with my own massively sorted, threaded, NEON coprocessor using version of everything rewritten from scratch and running out of time long before it reached plausible promise)... I read "No Free Lunch Theorems for Search", and despaired. Every daemon and protocol will break on some number of routes. Period. See: https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization Short of a revolution in graph theory I see no way to get anywhere on that, and yet tend to think dynamically making the update interval larger to account for various bounds (cpu,bandwidth) is part of a way out, along with having a harder r/t scheduler for the bellman-ford calc (needn't be threaded) would help to make sure it fits within bounds, repeating important packets more often, etc. (please note that most of what I'm saying as per NFL, etc is common to all routing protocols and daemons) > The protocol is very flexible, but the reference implementation is not > designed to work with such large update intervals. The amount of data in > an update is pretty small, so I would recommend reducing the update > interval -- it should be fine with thousands of routes in your network. Try to remember that other traffic eats capacity, and even in a fq_codel'd environment you only can get a percentage of bandwidth (with low delays). I've seen devices with essentially infinite queues for mcast, also - over 16 seconds long! I start running into trouble with 1000+ routes using 1Mbit mcast. Sooner if I seriously slam the network with flent or something else that abuses mcast like mdns. YMMV. > The right way to reduce the amount of routing traffic in Babel is not to > increase the update interval (which can at best yield a linear reduction), > but to use aggregation and filtering (which can yield an exponential > decrease in a well designed network). Dave Taht has been successful with > this approach, perhaps he'll want to chime in. I've also experimented with dynamically changing the broadcast update interval, as long term stable routes are, well, long term stable. Even a linear reduction seemed worthwhile at the time I was fiddling with this. Another way to preserve some percentage of sanity would be to always update default routes often but with a long declared broadcast interval and less used routes on a longer one. As for aggregation and filtering: Most of my APs have at minimum, ethernet, and two channels - usually four, including the meshy links. The meshy links are ptp, so I've generally "wasted" an entire /22 ipv4 network to talk to the APs. ipv6 /62s. The lab component of my network, for example, has two main links to the production net, and the gateways only announce the subnet it is on (172.22.0.0/16). This cuts the churn seen outside the network when I do crazy things like reboot the whole thing. The biggest problem I've run into, is that meshy links, are, meshy - and I've lost track of the number of times where I had a well defined /16 network in the lab suddenly leak all the meshy /32 bits over the worst possible link - because I plugged something in that was adhoc (and poorly) connected to the outside network that I shouldn't have. Lede creates one /48 ULA by default per AP, and then more /60s. I've had a tendency to try to share one /48, but more
Re: [Babel-users] Route-dete :wq
> I think babel is meant to do triggered updates however using tcpdump I was > not able to see them when the route was inserted. That's a fair assessment. Triggered updates are broken in 1.8.0, they should work in current master. (My fault for introducing the bug, and full credit to Gwendoline Chouasne for showing me the issue.) Folks -- I'm badly overworked right now, if you can help with testing current master, I'll be grateful. -- Juliusz ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
Re: [Babel-users] Route-dete :wq
Hi Toke, possible solutions that come to my mind are: * making babel trigger updates on newly appeared routes Wait, it isn't doing that already? Yeah, this would be an obvious improvement :) I think babel is meant to do triggered updates however using tcpdump I was not able to see them when the route was inserted. From a user perspective this means no perceived connectivity until the next update. Also, why isn't l3roamd detecting when the client connects to the AP and inserting the route immediately (that is complementary, but could further decrease the delay). l3roamd does exactly that. However in a multi-hop scenario it is not enough to just add routes to the local AP. The routes must be adjusted in all other places along the route towards the edges of the network at the very least. Christof -- () ascii ribbon campaign - against html e-mail /\ against proprietary attachments signature.asc Description: PGP signature ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
Re: [Babel-users] Route-dete:wq
Christof, I'm very much interested in your experiments, which are likely to improve the quality of the Babel implementations. > We have update-interval set to 5 minutes to reduce the load on the network > because we are hoping to run this topology on 500+ APs with 1000+ Clients. The protocol is very flexible, but the reference implementation is not designed to work with such large update intervals. The amount of data in an update is pretty small, so I would recommend reducing the update interval -- it should be fine with thousands of routes in your network. The right way to reduce the amount of routing traffic in Babel is not to increase the update interval (which can at best yield a linear reduction), but to use aggregation and filtering (which can yield an exponential decrease in a well designed network). Dave Taht has been successful with this approach, perhaps he'll want to chime in. Note that babeld currently sends updates as a single burst when the upate interval expires (the same is true of Toke's implementation of Babel, as far as I'm aware). For very large networks, it would be good to split updates into one-packet pieces that are sent throughout the update interval. I'd be glad to accept a patch that does that. > * making babel trigger updates on newly appeared routes I've gone through different approaches for scheduling updtes, and the current master is more aggressive with scheduling updates. I'd need to check to make sure, but I believe it already does what you suggest. If you have time, could you please check if current master improves things; if it doesn't, we need to work together to improve the implementation (no protocol changes will be needed). You could also try Toke's implementation, which is very well written. > * communicating the appearance of a route across the network outside > babel and inserting that at the gateway I'm not sure what you mean. > What do you think about those approaches? Please try current master. If not, we'll need to think together about redesigning our approach to sending triggered updates. -- Juliusz ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
Re: [Babel-users] Route-dete :wq
Christof Schulzewrites: > possible solutions that come to my mind are: > * making babel trigger updates on newly appeared routes Wait, it isn't doing that already? Yeah, this would be an obvious improvement :) Also, why isn't l3roamd detecting when the client connects to the AP and inserting the route immediately (that is complementary, but could further decrease the delay). -Toke ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
Re: [Babel-users] Route-dete:wq
Hello, When using babeld in a Freifunk network, I am seeing an issue with network convergence on newly appearing routes in this topology: Client AP1 AP2 === Gateway === (INTERNET) ===remote host Each client has a /128 address and /128 route inside the same /64 net-wide prefix. Client roaming is handled by detecting where clients are connected and having babel work out which routes need to be set. We have update-interval set to 5 minutes to reduce the load on the network because we are hoping to run this topology on 500+ APs with 1000+ Clients. Currently the following happens when a Client connects to AP1: 1 A client connects to a local access point. It will grab one or more ipv6 IP-addresses based on RA sent by uradvd running locally on this AP and start using this IPv6 address. 2 the client will initiate a connection to somewhere else, let's say to the internet and send a packet towards some remote host. 3 Using routing, the request will be delivered to the remote host. 4 The remote host will reply, the reply is delivered to the first gateway inside the Freifunk network which is acting as border router for the network. At this point no route towards the client's IP, the destination of the response, is known to this gateway. Therefore a seek-operation (implemented by l3roamd) is triggered. 5 l3roamd will check locally on all client interfaces using NDP whether a client having this IP is connected and it will query the l3roamd processes on neighbouring nodes to do the same. 6 AP2 checks locally and asks AP1 to do the same 7 AP1 checks locally, detects that a client using this new IP-address is connected locally and inserts a host-route into its local routing table 8 The user of the client is experiencing a no-connection-situation be cause no route from the gateway to the client is known until... 9 After the update-interval is expired (possibly minutes) babeld triggers an update, the routes are then known to AP2, and successively to the Gateway where babeld will insert routes towards the next-hops for this new IP to AP1/AP2 respectively upon which point the gateway can route it's packets towards the correct destination. 10 the l3roamd running on the gateway flushes its internal packet buffer and now the client has connectivity What can I sensibly do to shorten the time where the client does not appear to have internet connectivity in step 8/9? possible solutions that come to my mind are: * making babel trigger updates on newly appeared routes * communicating the appearance of a route across the network outside babel and inserting that at the gateway What do you think about those approaches? Regards Christof On Fri, Feb 09, 2018 at 09:12:11PM +0100, Christof Schulze wrote: You're probably just seeing fallback routes. (We'd need to see your dump to be sure.) Babel keeps a redundant routing table -- it keeps routes to every destination through every single neighbour. This way, it can switch to a different route immediately when it detects that its current next-hop is down. If you have 10 neighbours and there are 60 routes in the network, you'll see 600 routes in your routing table. Don't worry, though -- a fallback route is just a 60-byte data structure, so 600 routes take less than 40kB of memory. (Fallback routes are not visible to the kernel, and are not announced over the network.) You can distinguish between redundant routes and the routes actually used by the "installed" flag -- a route that is marked as "installed" is currently used for traffic, a route that is marked as "feasible" is a fallback route that can be used straight away if necessary, a route that is not marked is an "unfeasible" route, one that cannot be used without doing a quick packet exchange to make sure that it is loop-free. My advice would be: - don't panic, in large, friendly letters; - only start worrying if babeld starts having a large RSS or uses more than a fraction of CPU; - use BabelWeb in order to better understand better what's going on in your network: https://github.com/Vivena/babelweb2 Please don't hesitate to send me a route dump (through the list or, if you're concerned about your users' privacy, by private mail), I'd be curious to see what's going on. Thanks for the input, I have sent a reply off-list containing routes and dump from babel. Unfortunately in my tiny network a 3 digit number of routes is actually installed. viele Grüße Christof -- () ascii ribbon campaign - against html e-mail /\ against proprietary attachments signature.asc Description: PGP signature ___ Babel-users mailing list Babel-users@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users