[Olsr-users] XL routing protocol

[Juliusz Chroboczek]

>> I don't know how many of you have seen this paper from a group at UCSD 
>> (University of California at San Diego) which presents a new method of 
>> discerning which route updates to forward to a given node.
>> 
>> http://ccr.sigcomm.org/online/files/p15-levchenko.pdf

> what *is* the problem -

Nothing is the problem.

The authors are suggesting a number of optimisations to link-state
algorithms, and they show that they are correct.

This is unlike the fish-eye optimisation, which is not correct in
general.

Let me explain that.  Link-state algorithms are correct only under the
assumption that changes to the database are flooded in a timely manner
throughout the SPF domain.

There's been a lot of work to reduce the scope of flooding.
A successful example is that of OSPF, which takes the approach of
using multiple SPF domains, known as ``areas'', so that the
correctness only relies on speedy flooding within a single area.

Fish-eye and XL use a different approach, they delay some updates
under some conditions.  Fish-eye does that in a manner that does not
preserve correctness in general, but turns out to work pretty well in
most real networks.  XL do it in a manner that does preserve correctness.

You may want to look whether the optimisations they suggest are
applicable to OLSR (and I'm fairly certain that they are) and if so,
implement them in a future version of olsrd in place of or in addition
to fish-eye.

> -the authors assume that a link-state protocol has some form of reliable
>  transport to make sure that a necessary update reaches all corners of the
>  network.

Since almost all of the research in link-state protocols is aimed at
OSPF, and OSPF uses a reliable transport, you won't find many papers
that don't make this assumption.  The optimisation techniques remain
valid in the absence of such a transport, although the theoretical
results might not.

                                        Juliusz Chroboczek