Hi all, Loading a large set of prefixes into the static protocol is pretty quick, but reconfiguring is really slow. The current implementation uses linked lists which are traversed lots of times during the reconfiguration. I was wondering if these could be indexed and sorted in some way with one of the existing bird data structures - perhaps with a FIB - which would allow the use of a faster merge algorithm. Any other suggestions as to how the static reconfigure could be made faster? Rgs Neil
On Tue, Jul 12, 2011 at 04:15:31PM +0100, Neil Wilson wrote:
Hi all,
Loading a large set of prefixes into the static protocol is pretty quick, but reconfiguring is really slow.
The current implementation uses linked lists which are traversed lots of times during the reconfiguration.
I was wondering if these could be indexed and sorted in some way with one of the existing bird data structures - perhaps with a FIB - which would allow the use of a faster merge algorithm.
Yes, static protocol has time complexity O(n^2) for reconfiguration, so reconfiguration is slow for thousands of routes. FIB could be used and i will probably fix that in that way.
Any other suggestions as to how the static reconfigure could be made faster?
Quick workaround would be split these routes to several static protocols (for examle one per hundred routes). -- Elen sila lumenn' omentielvo Ondrej 'SanTiago' Zajicek (email: santiago@crfreenet.org) OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net) "To err is human -- to blame it on a computer is even more so."
Hi!
Yes, static protocol has time complexity O(n^2) for reconfiguration, so reconfiguration is slow for thousands of routes. FIB could be used and i will probably fix that in that way.
Either that, or just sort the lists. Have a nice fortnight -- Martin `MJ' Mares <mj@ucw.cz> http://mj.ucw.cz/ Faculty of Math and Physics, Charles University, Prague, Czech Rep., Earth
On Wed, Jul 13, 2011 at 04:19:15PM +0100, Neil Wilson wrote:
On Wed, 2011-07-13 at 13:24 +0200, Ondrej Zajicek wrote:
Quick workaround would be split these routes to several static protocols (for examle one per hundred routes).
Yep, that works like magic. Down to 2 seconds from six minutes!
How many static routes do you have? -- Elen sila lumenn' omentielvo Ondrej 'SanTiago' Zajicek (email: santiago@crfreenet.org) OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net) "To err is human -- to blame it on a computer is even more so."
On Wed, 2011-07-13 at 23:10 +0200, Ondrej Zajicek wrote:
How many static routes do you have?
I have potentially a few hundred thousand routes - that can't be summarised for various reasons and tend to change a lot. A situation that the standard routing protocols were not designed to handle. So I'm trying an unconventional approach :) Rgs Neil
participants (3)
-
Martin Mares -
Neil Wilson -
Ondrej Zajicek