[Olsr-users] XL routing protocol

[Hannes Gredler]

On Mon, Sep 08, 2008 at 02:44:28AM +0200, Juliusz Chroboczek wrote:
| 
| >> 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.

well if nothing *is* the problem there is no reason to waste time
on a solution :-P
 
| The authors are suggesting a number of optimisations to link-state
| algorithms, and they show that they are correct.

the authors look from a wrong angle (read: assumptions) at the problem

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

i agree - fisheye sucks - and everybody working on link-state protos
for a while knows that.

| 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.

done that and from an optimization point of view its an uninteresting
excercise.

| > -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.

i am more concerned about *practical* considerations. as of today
frequent updates *are* the reliability mechanism of olsr. reducing
it breaks the protocol from a robustness point of view.

/hannes