[Xorp-hackers] BGP Minimum Route Advertisement Interval

[Euan Harris]

Hi,

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

SUMMARY

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

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

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

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

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

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

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

IMPLEMENTATION

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

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

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

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

STATUS AND QUESTIONS

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

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

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

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

Thanks,
Euan

-------------- next part --------------
A non-text attachment was scrubbed...
Name: mrai.patch.gz
Type: application/x-gzip
Size: 9127 bytes
Desc: not available
Url : http://mailman.ICSI.Berkeley.EDU/pipermail/xorp-hackers/attachments/20070104/48599807/attachment.gz 
-------------- next part --------------