[Xorp-hackers] BGP Minimum Route Advertisement Interval

[Atanu Ghosh]

Hi,

The MRAI code seems to have been correctly introduced but I have a
number of concerns.

The XORP BGP is event driven, an incoming route is typically processed
to completion. Other implementations have adopted a route scanner
approach which fits better with the concept of MRAI, where an artifact
of the implementation introduces a delay. Figure 13 in
<http://www.xorp.org/papers/xorp-nsdi.pdf> demonstrates the issue
nicely, XORP and MRTD don't introduce a delay, whereas Quagga and Cisco
do. We have never implemented MRAI in XORP because as RFC 4271 states to
implement it correctly would require a timer per destination, although
the RFC goes on to state that other techniques are acceptable.

The RFC states that the timer for internal peer should be shorter than
for external peers, it recommends five and thirty seconds
respectively. With the current placement of the MraiTable both peerings
will be treated the same. We have for a while been considering having
two fanout tables one for I-BGP and another for E-BGP. If we make this
change then two instances of the MraiTable table should solve this
problem.

As far as I can tell when the timer fires all the queued routes are sent
in a single loop. The default timer value, as recommended, is thirty
seconds a lot of routes could get queued in that time. We don't use
threads in XORP, so a single event such as a timer firing should not
take too much time. The clock() method should send a few routes and then
schedule a background task (eventloop().new_task()).

I wonder if it would be better to call this setting out-delay (Juniper's
name) rather than MRAI as what it seems to be doing is delaying all
routes until the timer fires, turning an event driven implementation
into a scanning implementation:-).

If the default setting for out-delay/mrai was zero and no resources are
consumed then we could consider adopting this code.

The transition from a non zero to a zero value out-delay should also
work correctly.

At the moment if the out-delay value is set to thirty seconds then an
update is delayed by zero to thirty seconds depending on when the update
arrives. It would be good if the incoming routes were stored such that
they are all delayed by thirty seconds. Perhaps by having the timer fire
every second and sending the oldest routes.

	Atanu.

>>>>> "Euan" == Euan Harris <euan.harris at cl.cam.ac.uk> writes:

    Euan> Hi,
    Euan> I'm working on a project with Xorp and Quagga and have recently been
    Euan> looking at the effect of the minimum route advertisement interval
    Euan> (MRAI).   Since Xorp doesn't seem to support MRAI I've had a go at
    Euan> implementing it.   I've attached a patch against the 1.3 release -
    Euan> apply with patch -p 1.   I'm looking forward to your comments or
    Euan> suggestions!

    Euan> SUMMARY

    Euan> I've added a new route table, called MraiTable, which goes in the
    Euan> central plumbing between the aggregation table and the fanout  table.
    Euan> MraiTable delays add, replace and delete messages coming  from the
    Euan> decision tables upstream, stores them up and sends them on  to the
    Euan> fanout table when a timer goes off.    It's a bit like using a  latch
    Euan> to synchronise the output of an asynchronous electronic  circuit.
    Euan> The overall effect is not quite to the letter of the RFC  but is
    Euan> similar to the behaviour of Quagga and Cisco - from the  outside it
    Euan> looks like the router recomputes the world and pushes new  routes
    Euan> every MRAI seconds.

    Euan> If MraiTable receives several route messages for a given prefix
    Euan> between timer ticks, it aggregates them according to the following
    Euan> rules, so that when the timer ticks at most one message per route
    Euan> will be sent downstream:

    Euan> 	add x, add ? -> error
    Euan> 	add x, replace x y -> add y
    Euan> 	add x, delete x -> do nothing

    Euan> 	replace x y, add ? -> error
    Euan> 	replace x y, replace y z -> replace x z
    Euan> 	replace x y, delete y -> delete x

    Euan> 	delete x, add x -> do nothing
    Euan> 	delete x, add y -> replace x y
    Euan> 	delete x, replace x ? -> error
    Euan> 	delete x, delete x -> error

    Euan> (all messages are for the same prefix;  x and y are routes; ? is any
    Euan> route)

    Euan> By adding the table after the decision processes but before the
    Euan> fanout table I should only have to deal with a well formed stream of
    Euan> updates - i.e. MraiTable should never actually see two adds for the
    Euan> same prefix.

    Euan> IMPLEMENTATION

    Euan> MraiTable is a subclass of BGPRouteTable.   I made some small changes
    Euan> to plumbing.cc to plumb it in between the aggregation table and the
    Euan> fanout table;  apart from that all the other changes are in
    Euan> MraiTable.cc and MraiTable.hh.    I've also added and XRL interface
    Euan> to set the MRAI from xorpsh - set protocols bgp mrai <int> from
    Euan> configure mode.

    Euan> Within MraiTable, delayed messages are stored as MraiCachedMessage
    Euan> objects in a RefTrie.   There are three subclasses of
    Euan> MraiCachedMessage, for Add, Replace and Delete messages.   Each
    Euan> subclass knows how to combine itself with an incoming message
    Euan> according to the rules above, so for instance calling
    Euan> merge_with_replace_message with message Y on an MraiCachedAddMessage
    Euan> containing message X will return a new MraiCachedAddMessage
    Euan> containing message Y.   If the result of the merge is to do nothing,
    Euan> the merge method returns NULL and the route's record is removed from
    Euan> the RefTrie.

    Euan> Each CachedMessage subclass knows how to apply itself to the next
    Euan> table.   When the timer goes off, we iterate through all the cached
    Euan> messages calling apply_self_to_table with the next table in the
    Euan> plumbing as an argument.   For cached adds and deletes this method
    Euan> just calls the relevant method on the downstream table.   For cached
    Euan> replace messages, it has to consider whether the peer advertising the
    Euan> route has changed;  if so it calls delete followed by add, otherwise
    Euan> it can call replace directly.

    Euan> The timer callback registers itself as a one-shot timer on the BGP
    Euan> master's event loop.  On every tick it reschedules itself, with some
    Euan> jitter.

    Euan> STATUS AND QUESTIONS

    Euan> I've tested this code in a simple EBGP clique topology, with no route
    Euan> filtering.   It seems to do the right thing in this context and
    Euan> doesn't crash, but it may be that it doesn't handle some other
    Euan> configuration that I haven't tried.  Please let me know if you think
    Euan> of one, or if you try it out and find a bug.

    Euan> It almost certainly leaks memory.  I'm a C++ newbie and usually code
    Euan> in languages with garbage collection.   Any, umm, pointers on my
    Euan> memory management would be appreciated! ;-P

    Euan> I've had some problems running the bootstrap script on my Ubuntu
    Euan> Dapper machine.   Automake bails with errors like "automake: pim/
    Euan> Makefile.am: not supported: source file `$(top_srcdir)/rib/
    Euan> redist_xrl.hh' is in subdirectory".   There are also warnings from
    Euan> autoheader.   Since I'm only adding a couple of files I updated the
    Euan> Makefile manually;  I hope it works better for you on FreeBSD!

    Euan> I'm looking forward to your comments! :-)

    Euan> Thanks,
    Euan> Euan


    Euan> _______________________________________________
    Euan> Xorp-hackers mailing list
    Euan> Xorp-hackers at icir.org
    Euan> http://mailman.ICSI.Berkeley.EDU/mailman/listinfo/xorp-hackers