Hi all, as promised, I have completed the analysis of the protocol overhead providing also simulation results with and whitout the OGM aggregation mechanism activated. As anticipated the results shows that aggregation works well in reducing the overhead. In attachment the report (OGMoverhead.pdf).
In attachment you will also find a draft/proposals of a new routing approach. It is based on the collection of more link parameters (the current TQ, bit-rate and node-load) to write in OGM at each hop. This permit to develop a more thorough metric and can open new room of improvement such multi-path routing.
Any comment/suggestion is welcome!
Regards.
In attachment you will also find a draft/proposals of a new routing approach. It is based on the collection of more link parameters (the current TQ, bit-rate and node-load) to write in OGM at each hop. This permit to develop a more thorough metric and can open new room of improvement such multi-path routing.
Hi Daniele
Do you have any suggestions how to collect this bit-rate information? Do you suggest measuring it, or asking the wireless LAN driver? Is there an API in the kernel to allow access to this information?
Also, how do you see this interacting with the hidden node problem? In order to reduce the hidden node problem, you ideally want to use the lowest coding rate and transmit power possible to get your packets through. Currently this is not being done. Current wireless systems optimize for maximum bandwidth between two nodes, which may not be the optimum for the complete mesh bandwidth, due to inter node interference.
Will you be at the WBMv4 next Month?
Andrew
2011/2/28 Andrew Lunn andrew@lunn.ch:
In attachment you will also find a draft/proposals of a new routing approach. It is based on the collection of more link parameters (the current TQ, bit-rate and node-load) to write in OGM at each hop. This permit to develop a more thorough metric and can open new room of improvement such multi-path routing.
Hi Daniele
Do you have any suggestions how to collect this bit-rate information? Do you suggest measuring it, or asking the wireless LAN driver? Is there an API in the kernel to allow access to this information?
I'm not a kernel guru but i find out that the new core mac80211 and cfg80211 (http://linuxwireless.org/) offers the possibility to obtain a per-station bit-rate information that should be driver independent. The measurement is an alternative but I think it is more complex to implement. The load measurement instead is more difficult and at this moment have not idea of how to do it!!
Also, how do you see this interacting with the hidden node problem? In order to reduce the hidden node problem, you ideally want to use the lowest coding rate and transmit power possible to get your packets through. Currently this is not being done. Current wireless systems optimize for maximum bandwidth between two nodes, which may not be the optimum for the complete mesh bandwidth, due to inter node interference.
I have not mentioned the hidden node problem. But I think this problem is very difficult to remove, the only best practice to reduce the problem is to force the RTS/CTS mechanism to be active. Other phenomena such as capture effect instead are intrinsic in the wireless networking and are very difficult to eliminate. The optimization of bandwidth in my opinion does not influence the protocol because if the link is bad, rate adaption mechanism will reduce the bit-rate and I can read this information from the driver.
Anyhow collecting more information about link can help much in evaluating the best route I think, and offer a big opportunity to experiment new metrics.
Will you be at the WBMv4 next Month?
I'm afraid but I cannot be at WMBv4, I hope I can come to the next WBM, maybe with a working implementation :)
Andrew
I'm not a kernel guru but i find out that the new core mac80211 and cfg80211 (http://linuxwireless.org/) offers the possibility to obtain a per-station bit-rate information that should be driver independent.
O.K. I will take a look at this.
I have not mentioned the hidden node problem. But I think this problem is very difficult to remove, the only best practice to reduce the problem is to force the RTS/CTS mechanism to be active.
RTS/CTS helps, true. But it has a few problems. e.g. most meshing protocols use broadcast packets for there management. e.g. BATMANs OGMs are broadcast. These cannot be protected with RTS/CTS. So the OGMs can collide with RTS packets from a hidden node, or OGMs from a hidden node.
Another way to help reduce the hidden node problem, or interference with other nodes, is to use a low coding rate and transmit power when possible. So for example when we don't have much traffic to send to node X, it could send the packets with the lowest coding rate and low power. This keeps the interference with other nodes to a minimum. As the amount of data for X increases, the coding rate and transmit power can be increased, so increasing the available bandwidth to X, but at the same time increasing the amount of interference the traffic produces.
Such a scheme to minimize interference does not play too well with your idea of putting the coding rate into the OGMs. We would have to ensure that the coding rate is the highest possible coding rate usable between two peers, not the currently used coding rate, which could be low in order to avoid interference.
Will you be at the WBMv4 next Month?
I'm afraid but I cannot be at WMBv4, I hope I can come to the next WBM, maybe with a working implementation :)
Shame, i plan to talk more about the hidden node problem during WBMv4. It is also a good place to discuss new ideas like adding information into the OGMs.
Andrew
2011/2/28 Andrew Lunn andrew@lunn.ch:
I'm not a kernel guru but i find out that the new core mac80211 and cfg80211 (http://linuxwireless.org/) offers the possibility to obtain a per-station bit-rate information that should be driver independent.
O.K. I will take a look at this.
I have not mentioned the hidden node problem. But I think this problem is very difficult to remove, the only best practice to reduce the problem is to force the RTS/CTS mechanism to be active.
RTS/CTS helps, true. But it has a few problems. e.g. most meshing protocols use broadcast packets for there management. e.g. BATMANs OGMs are broadcast. These cannot be protected with RTS/CTS. So the OGMs can collide with RTS packets from a hidden node, or OGMs from a hidden node.
In my opinion the use of broadcast is somehow useful. If many OGM packet collide it means that the link is congested and batman will use another. It would be wrong to protect OGM from collision or hidden node.
Another way to help reduce the hidden node problem, or interference with other nodes, is to use a low coding rate and transmit power when possible. So for example when we don't have much traffic to send to node X, it could send the packets with the lowest coding rate and low power. This keeps the interference with other nodes to a minimum. As the amount of data for X increases, the coding rate and transmit power can be increased, so increasing the available bandwidth to X, but at the same time increasing the amount of interference the traffic produces.
Yes, I think that it is always better to use low transmission power and favor multi-hop so short link, especially in dense network. The schema I propose effectively favor short link offering the possibility of reducing transmission power. Anyhow a transmission power management system is out of the scope of my work, but it is a very interesting area. It is certainly possible to add transmission power level to OGM in order to use also this information in routing decision. More information we now of link and more accurate will be the routing decisions.
Such a scheme to minimize interference does not play too well with your idea of putting the coding rate into the OGMs. We would have to ensure that the coding rate is the highest possible coding rate usable between two peers, not the currently used coding rate, which could be low in order to avoid interference.
The current rate is decided by the driver basing on link quality and collision so indirectly tells us how much interference there are in the link. Why it is a bad idea to use this information?
Will you be at the WBMv4 next Month?
I'm afraid but I cannot be at WMBv4, I hope I can come to the next WBM, maybe with a working implementation :)
Shame, i plan to talk more about the hidden node problem during WBMv4. It is also a good place to discuss new ideas like adding information into the OGMs.
Andrew
On Mon, Feb 28, 2011 at 05:00:23PM +0100, Daniele Furlan wrote:
2011/2/28 Andrew Lunn andrew@lunn.ch:
I'm not a kernel guru but i find out that the new core mac80211 and cfg80211 (http://linuxwireless.org/) offers the possibility to obtain a per-station bit-rate information that should be driver independent.
O.K. I will take a look at this.
I have not mentioned the hidden node problem. But I think this problem is very difficult to remove, the only best practice to reduce the problem is to force the RTS/CTS mechanism to be active.
RTS/CTS helps, true. But it has a few problems. e.g. most meshing protocols use broadcast packets for there management. e.g. BATMANs OGMs are broadcast. These cannot be protected with RTS/CTS. So the OGMs can collide with RTS packets from a hidden node, or OGMs from a hidden node.
In my opinion the use of broadcast is somehow useful. If many OGM packet collide it means that the link is congested and batman will use another.
And what if the other link is not really useful for e.g. TCP? batman would switch to that link then anyway. At least that's what I had been experiencing in some indoor scenarios here. The hidden node can lead to degrading the measured LQ values from ~90% down to < 10% packet delivery ratio.
It would be wrong to protect OGM from collision or hidden node.
So I'd not quite agree with that.
But I'm actually also a little confused why you, Andrew, came up with the hidden node problem :) (which these papers did not try to solve, if I'm not missing something). Or do you mean, that this idea could be extended maybe be able to solve that hidden node problem for OGMs, using the bitrate measuremens to detect / avoid switching to bad links?
Another way to help reduce the hidden node problem, or interference with other nodes, is to use a low coding rate and transmit power when possible. So for example when we don't have much traffic to send to node X, it could send the packets with the lowest coding rate and low power. This keeps the interference with other nodes to a minimum. As the amount of data for X increases, the coding rate and transmit power can be increased, so increasing the available bandwidth to X, but at the same time increasing the amount of interference the traffic produces.
Yes, I think that it is always better to use low transmission power and favor multi-hop so short link, especially in dense network. The schema I propose effectively favor short link offering the possibility of reducing transmission power. Anyhow a transmission power management system is out of the scope of my work, but it is a very interesting area. It is certainly possible to add transmission power level to OGM in order to use also this information in routing decision. More information we now of link and more accurate will be the routing decisions.
Such a scheme to minimize interference does not play too well with your idea of putting the coding rate into the OGMs. We would have to ensure that the coding rate is the highest possible coding rate usable between two peers, not the currently used coding rate, which could be low in order to avoid interference.
The current rate is decided by the driver basing on link quality and collision so indirectly tells us how much interference there are in the link. Why it is a bad idea to use this information?
Hmm, I guess that depends on the interference pattern a lot. Afaik minstrel for instance is one of the rate selection algorithms which can chose higher enconding rates to reduce interference in case of bursty loss. So when your rate selection algorithm selects 54MBit/s, that does not necessarily mean that you have a higher net throughput / that the link is "better" compared to another link where the rate selection algorithm has chosen for instance 36MBit/s. So to make the selected rate information somehow useful, you'd have to take the loss rates at that enconding rate into account too.
Will you be at the WBMv4 next Month?
I'm afraid but I cannot be at WMBv4, I hope I can come to the next WBM, maybe with a working implementation :)
Hmm, what a pitty. But, ok, see you next time then :).
Shame, i plan to talk more about the hidden node problem during WBMv4. It is also a good place to discuss new ideas like adding information into the OGMs.
Andrew
Nice papers there, thanks for sharing! Just looked at them briefly so far but seems very interesting.
Cheers, Linus
-- Daniele Furlan
PS: Just one thing I noticed so far, isn't it possible to simplify the formula B = 1 + \sum^{N\{0}}_{k \in N} p^{l_{o,k}} to just: B = \sum_{k \in N} p^{l_{o,k}}? p^{l_{o,k}} is already 1 for k = o isn't it?
But I'm actually also a little confused why you, Andrew, came up with the hidden node problem :) (which these papers did not try to solve, if I'm not missing something). Or do you mean, that this idea could be extended maybe be able to solve that hidden node problem for OGMs, using the bitrate measuremens to detect / avoid switching to bad links?
Hi Linus
If we can extend minstrel so that it also takes transmit power and load into consideration, we might be able to optimize the coding rate & TX power for complete mesh bandwidth, not a single link bandwidth.
I would expect there are a number of research papers looking at this, and many ideas which can be taken from cellular networks. I also think the commercial mesh products do this.
However, for Daniele idea of putting the coding rate into the OGM, we probably need the achievable coding rate, not the current coding rate. It could be the link is idle, so is using the lowest coding rate and minimum TX power, just to carrier a few ARP reply packets etc. If however the link becomes loaded, it would increase the coding rate and TX power so allowing more packets through.
Daniele's idea is good, but i'm just being careful it does not block ideas like dynamic coding rate/TX power control.
Andrew
2011/3/1 Andrew Lunn andrew@lunn.ch:
But I'm actually also a little confused why you, Andrew, came up with the hidden node problem :) (which these papers did not try to solve, if I'm not missing something). Or do you mean, that this idea could be extended maybe be able to solve that hidden node problem for OGMs, using the bitrate measuremens to detect / avoid switching to bad links?
Actually I did not mentioned the hidden node problem in the report. But the idea of extending the information contained in OGM can help also in implementing some technique to solve this problem. Maybe the bit-rate is not enough, but from the driver I think can be also obtained, for example, tx-retries and tx-failed.
Hi Linus
If we can extend minstrel so that it also takes transmit power and load into consideration, we might be able to optimize the coding rate & TX power for complete mesh bandwidth, not a single link bandwidth.
I would expect there are a number of research papers looking at this, and many ideas which can be taken from cellular networks. I also think the commercial mesh products do this.
However, for Daniele idea of putting the coding rate into the OGM, we probably need the achievable coding rate, not the current coding rate. It could be the link is idle, so is using the lowest coding rate and minimum TX power, just to carrier a few ARP reply packets etc. If however the link becomes loaded, it would increase the coding rate and TX power so allowing more packets through.
Daniele's idea is good, but i'm just being careful it does not block ideas like dynamic coding rate/TX power control.
Andrew
The idea I have for the moment is only to increase the information that OGM can carry. Than in a second phase it is possible to use these information to implement whatever solution.
Another important improvement that a solution with the entire path registered in OGM is the possibility of preventing routing loops in a simple way, and also to provide a formal proof that batman is loop-free.
b.a.t.m.a.n@lists.open-mesh.org
-
Andrew Lunn -
Daniele Furlan -
Linus Lüssing