[OLSR-users] willingness vs. LQ routing

[Stefan Sayer]

Hello Thomas and Andreas,

let me first say I am in no way experience neither with routing 
protocols nor with wireless networking...I am rather only using it... I 
assume things I am considering here have been discussed various times, 
and I am sure someone came up with very sophisticated thoughts about it, 
but nevertheless some of my thoughts about LQ, willingness and link speed:

it seems reasonable to introduce additional parameters to characterize a 
link:
* link quality: packet loss
* link quality: link speed
* willingness (e.g. from battery status)
* link cost (? -> especially setups with multiple internet-HNA)
* maybe more?

It makes sense to weight these parameters in the calculation of the 
metric which will be used for routing, e.g. linearly
metric = a*LQ(packet loss) + b*LQ(link speed) + c*will + d*link cost + ...

with a,b,c,d being some constants which can be used to fine tune routing 
behaviour or adapt to the intended use of the routing.

Now I can generally think of two methods for determining the metric to 
be used for routing:
1) broadcast all _link_characterisation_parameters_ and statically 
configure the constants (or broadcast them by some central manager) and 
let every node calculate the metric of every link (remote links, too)
2) have every node calculate the metric of the link and broadcast 
_the_metric_; the constants a,b,c,d being locally configured or managed 
by some central manager

I like the second option much better as it is more following the 
distributed and self-organizing paradigma, e.g. you cannot have routing 
loops caused by some case where two nodes calculate different routes 
because they have not the same formula for calculating the metric.

On the other hand I'd recommend to not do things like skipping sequence 
numbers (this seems to me like a dirty hack) out of the following reasons:
- diagnostics of the network become more complex: have to know the skip 
sequence number of every node to calculate real packet loss
- tuning of the network or adapting to other configuration becomes 
problematic

So I'd propose the following:
* every link calculates the metric for the (incoming) link and 
broadcasts it; this metric is used for the route calculation.
* link characterisation parameters (e.g. willingness, cost, ...) can be 
broadcasted by a node for the other nodes to help them calculate their 
link metric and for diagnostics
* link metric calculation constants (a,b,c,d in the above example) might 
be broadcasted to allow for centralized configuration/tuning of the network.

This is not very much different what is there today - I'm just thinking 
about this and maybe we can come up with a flexible solution which can 
be extended to adapt to specific needs.
Some things I am not clear about is
  * traffic overhead of broadcasting link characterisation parameters
  * are there cases where the metric of a link has to be determined by 
both the node and its neighbour?
  * can with the current plug-in interface the calculation of the metric 
be done in a plug-in?

btw for debugging of LQ I made a patch here
http://user.cs.tu-berlin.de/~sayer/olsr/lqhack4_patch.tgz
where you can define in the config
LQHack4 {
  IP_src1 IP_dst1 lq1
  IP_src2 IP_dst2 lq2
etc.
}
which will override the LQ calculated from packet loss of the links 
IP_src1 to IP_dst1 with lq1 (and 2 respectively) and use that for route 
calculation (tested on win32/cygwin only).

Stefan

Andreas Petersson wrote:
> Thomas Lopatic wrote:
> 
>> Hi Stefan,
>>
>> Currently the willingness is not considered when creating the routing 
>> table or when selecting MPRs when LQ extensions are enabled. But, as 
>> you say, it probably makes sense to include the willingness in the 
>> link quality determined by a node. The lower the willingness, the 
>> worse the announced link quality for each link in the direction from 
>> the neighbour to the node should be.
>>
>> This would then affect the ETX and hence the routing table as well as 
>> MPR selection. Strictly speaking, we would not need the willingness 
>> anymore, as a node's willingness is reflected by the announced link 
>> qualities.
>>
> 
> hi!
> i am glad that this suggestion is brought up now, because i have some 
> concerns towards the bandwidth scalability of dense asymetric olsr mesh 
> networks.
> 
> the LQ metric is a great improvement towards a strict hop-count metric, 
> but it is not the final solution.
> 
> at funkfeuer our topology consits basically of four types of links:
> 
> http://subway.funkfeuer.at/topo/
> 
> 1)wired ethernet links - 100mbit
> 2)wireless coulds of omnidirectional antennas - varying from 1 mbit to 
> 18 mbit
> 3)wireless point-to-point links - typicall from 18mbit to 48mbit, but at 
> quite constant speed.
> 4)vpn tunnels through the internet - typically 2mbit but with quite high 
> delays of 20-100 ms, and by definition, without packet loss (since 
> openvpn handles this)
> 
> the nodes "ag5" and "kh" have vpn links to the central router.
> 
> XXXomni means it is an onmidirectional antenna
> 
> XXXtoYYY means it is a point-to point link (directional to directional 
> antenna)
> 
> nodes with the same prefix are connected via ethernet links
> 
> every node has typically 2 interfaces (one wired and one wireless), 
> although some of them are not in use.
> 
> if we just look at the topology  and the packet losses then we have the 
> following situation: a lot of traffic is routed though the vpn tunnels, 
> since they have by definition a packet loss of 0. we could have much 
> better speeds if we could somehow define the vpn tunnels as a backup line.
> 
> I would suggest the following: instead of a "expected transmission 
> COUNT" metric one could use a "expected transmission TIME" metric.
> 
> keep the etx calculation as it works now.
> configure one link_speed parameter per interface.
> when calculating the edge values of the graph, divide the etx value with 
> the link_speed. this is the new edge cost.
> 
> how difficult would it be to implement such a metric?
> 
> i have two ideas how this could be accomplished:
> 
> idea A)
> when olsr sends out messages for which he assignes sequence numbers, he 
> could voluntarily *skip* message numbers. that would trick the other 
> nodes into thinking he has a lossy link. the amount of numbers skipped 
> is indirectly proportinal to the assiged link speed.
> so we would need to define a "maximum Speed" -> mS parameter and a link 
> Speed -> lS. each sequence number will be increased by mS/lS (as a float 
> value),but sent out rounded. that would automatically lead to a 
> calculation of edge values how i proposed it, since the normal physical 
> packet loss applies as normal.
> 
> idea B)
> the link_speed information could be published via MID messages. the 
> definition of MID messages needs to be changed in order to allow this.
> 
> greetings
> andreas
> _______________________________________________
> olsr-users mailing list
> (spam-protected)
> https://www.olsr.org/mailman/listinfo/olsr-users
> 
>