[PATCH] Add the Babel routing protocol to Bird

[Toke Høiland-Jørgensen]

Ondrej Zajicek <santiago at crfreenet.org> writes:

> Also one thing i forgot to notice. For generated external routes, you
> initialize metric to 0 (r->metric = 0 in babel_rt_notify()). You
> should use ea_get_int(attrs, EA_BABEL_METRIC, 0) to allow user set it
> in export filters.

Ah, so that's what that is for. Noted.

> Default metric probably should be more than zero (zero makes sense
> for /128 local address, while more than zero for locally reachable
> network prefix).

Hmm, but if it's a prefix locally reachable prefix, no more routing is
needed, so the *routing* metric is surely 0? There will still be path
cost added at the neighbours... What else would you suggest it should
be?

> 3) Documentation of functions. It is true that for protocols this is
> less important than for public lib or nest functions, but in the case
> of non-trivial / non-obvious functions it is a good idea. I would
> suggest to document esp. functions manipulating with internal
> structures, implementing some protocol processes and timer/event
> hooks. It is usually useless to document the usual protocol glue (e.g.
> babel_start, babel_make_tmp_attrs, babel_get_route_info), unless it
> does some nontrivial things (like babel_rt_notify()).

Right, will make sure there are appropriate comments in the code, of
course. But should these be formatted so as to be picked up by the
documentation extractor?

> 3) Use get_uXX()/put_uXX() in handle/send functions. That would also
> eliminate a need for separate ntoh/hton functions. You could use
> something like:
>
> #define GET_U32(p,f) get_u32(((char *) p) + OFFSETOF(typeof(*p),f))
> #define GET_U16(p,f) get_u16(((char *) p) + OFFSETOF(typeof(*p),f))
>
> to access fields by GET_U16(tlv, seqno) instead of tlv->seqno.

Right, this makes sense, will try that.

> BTW, using babel_tlv_header is also a bit problematic, as some
> architectures enforce minimal structure alignment ant therefore
> size (to e.g. 4). Probably declaring it packed should be enough.

Ah, bugger. Well, guess I'll have to change to copying the TLVs around
in any case, then. Might be cleaner to change the architecture to do
away with most of the pointer arithmetic entirely, then...

>> Not entirely sure what compilers you are targeting; that macro seems to be
>> GCC-specific, but is also supported in LLVM since 1.5:
>> http://llvm.org/releases/1.5/docs/ReleaseNotes.html
>
> We are mainly targetting GCC, but i guess we could support LLVM with
> some minor tweaks. Sane GCC extensions could be used, things like
> __buildin_* should be used through some define.

Okidoki, noted.

>> Yeah, well, was planning to actually make it do something useful instead
>> (i.e. support proper reconfiguring).
>
> This function is not related to reconfiguration, it is related to protocol
> templates, these do not make much sense for non-BGP protocols.

Ah, I see. Cool, will nuke it.

>> Not sure what you mean here? Are you referring to htobe64() being
>> glibc-specific? An how do you suggest to handle it? :)
>
> Well, according to man page, these functions are not standardized
> (although widely available), be64toh is named betoh64 on OpenBSD, and
> different header file should be included on Linux and BSDs.
>
> We could have lib/endian.h, which can include appropriate headers and
> define aliases.

Okay, I'll give it a shot. You may have to tweak it for other systems,
though... :)

>> Ah, was trying to be careful with this; obviously didn't work. Will give
>> it another go.
>
> BTW, why is babel_send_queue() / babel_copy_tlv() so complicated?

Partly because the code evolved that way (added in the TLV buffering at
a later stage).

> If i understand it correctly, you have one TLV buffer (used for
> accumulation of TLVs) which has the same size as socket TX buffer,
> therefore you can (if TX buffer is empty) just copy whole TLV buffer
> to TX buffer and send the packet.

Hmm, that might be. I think the issue was that I wanted to support the
case where the tx buffer wasn't empty, and so TLVs should be added to
the end of an already existing packet. Not sure this really makes sense,
though, will look over it again.

> BTW, i missed one answer - in:
>
>> +static void
>> +babel_select_route(struct babel_entry *e)
>> +{
>> +  struct babel_proto *p = e->proto;
>> +  net *n = net_get(p->p.table, e->n.prefix, e->n.pxlen);
>> +  struct babel_route *r, *cur = e->selected;
>> +  
>> +  /* try to find the best feasible route */
>> +  WALK_LIST(r, e->routes)
>> +    if((!cur || r->metric < cur->metric)
>> +       && is_feasible(babel_find_source(e, r->router_id),
>> +                   r->seqno, r->advert_metric))
>> +      cur = r;
>
>   Why feasibility is checked here? I would expect that feasibility is checked when
>   the route is received, but all accepted to e->routes stays feasible.
>
> Is that true or the routes in e->routes may later turn infeasible?

Yes, because the feasibility distance can change. For example in this
scenario:

We receive route X from routers A and B with metrics 50 and 100,
respectively. We then add the path cost of 20 to each of those, so we'll
be announcing it with metric 70, making the route towards B infeasible
(feasibility distance is 70 < 100). Now, if router B gets a better route
and re-announces with metric 20 (this could also be a from a new router
C), that route will turn feasible. We will then pick that, and
re-announce with metric 40, turning that into our new feasibility
distance. This makes the route towards A infeasible even though nothing
changed in A's announcement.

-Toke
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 472 bytes
Desc: not available
URL: <http://trubka.network.cz/pipermail/bird-users/attachments/20151009/5d7b5531/attachment.asc>