[CC: b.a.t.m.a.n@lists.open-mesh.org, see note 3 in particular]
Antonio,
On Wed, Mar 07, 2012 at 06:17:52PM +0100, Antonio Quartulli wrote:
Technical details about what? Interface-alternating? It is there! Gabriel wrote the link.
No. Please re-read my email carefuly. The wiki contains a rough explanation of the general principle (ie. “same interface = bad, different interface = good”). Not the actual algorithm used by batman-adv (quoting from the wiki: “the algorithm tries to avoid forwarding packets on the interface which just received the packet”).
Note that the wiki has been updated since then, by Simon with a few more details [1], and by Marek with benchmark results from WBMv3.
Gabriel said he has not enough time to look into it. I'm sorry, but I don't think this is a good reason to blame batman-adv devs :P
I finally decided to settle this issue and spent my breakfast reading batman-adv/routing.c [2] instead of my favorite newspaper. Here is what I understood:
At all times, batman-adv maintains a list of "bonding candidates" for each node (bonding_candidate_add, called from bat_iv_ogm.c:699). Some node "neigh" is a bonding candidate for another node "orig" if and only if: - neigh and orig have the same primary address, ie. are in fact the same router, - the links to reach them have the same quality up to some additive constant (BONDING_TQ_THRESHOLD = 50) [3], - orig does not already have another bonding candidate for the same interface, because it could interfere – but what if the neigh has a better link quality, isn’t it a pity to ignore it?
Then, assuming that "interface alternating" is enabled, the list of bonding candidates is used on every route selection (find_ifalter_router, called from routing.c:769). More precisely, once batman has chosen a next-hop router for a packet based on its classical routing algorithm, it walks the list of the bonding candidates associated to the primary interface for this router [4]. It selects the actual next-hop on the following criteria: - it must not be on the same interface as the packet came in, - its quality must be as high as possible (given the previous constraint).
This is the kind of explanation I would have loved to find on the wiki. By the way, consider it public domain and feel free to copy/paste/correct it if you wish.
It is still not clear to me exactly why this works, but I believe this is what the code does, and is definitely easier to discuss than generic, unsubstantiated claims.
Best regards, Gabriel
[1] “Interface alternating is only performed if the two candidate links to the next hop have a similar quality.” http://www.open-mesh.org/wiki/batman-adv/Multi-link-optimize
[2] http://www.open-mesh.org/projects/batman-adv/repository/revisions/master/ent...
[3] By the way, there is something I don’t understand: neigh_node->tq_avg will be accepted event if it is far greater than router->tq_avg + BONDING_TQ_THRESHOLD. Shouldn’t it be: abs(neigh_node->tq_avg - router->tq_avg) > BONDING_TQ_THRESHOLD? http://www.open-mesh.org/projects/batman-adv/repository/revisions/master/ent...
[4] Why the primary and not the chosen router directly? Is the bonding candidates list always associated to the primary interface?
Hey Gabriel,
thanks for bringing the discussion to the batman ml and giving some constructive input. I've written this bonding/alternating feature some time ago, and we released it at WBMv3 together with this little documentation to be found in the wiki. Actually, I considered the feature rather simple and therefore I did not write too much about it - because there is not really much to write about, or so I thought. Obviously, there were some things unclear, so thanks for pointing me/us to that.
When implementing, it is easy to miss some things that are not that obvious for outsiders, so please feel free to ask or suggest things. We'll rework the bonding/interface alternating part in the next days, and would be happy to include your suggestions. :)
Usually, we create the protocol documentation for the purpose of review and documentation for other batman-adv devs - and we don't expect that they all fall on the head at the same time. They are meant to describe the concept and not the actual implementation with all their nasty details.
On Wed, Mar 07, 2012 at 11:18:48PM +0100, Gabriel Kerneis wrote:
[CC: b.a.t.m.a.n@lists.open-mesh.org, see note 3 in particular]
Antonio,
On Wed, Mar 07, 2012 at 06:17:52PM +0100, Antonio Quartulli wrote:
Technical details about what? Interface-alternating? It is there! Gabriel wrote the link.
No. Please re-read my email carefuly. The wiki contains a rough explanation of the general principle (ie. “same interface = bad, different interface = good”). Not the actual algorithm used by batman-adv (quoting from the wiki: “the algorithm tries to avoid forwarding packets on the interface which just received the packet”).
Note that the wiki has been updated since then, by Simon with a few more details [1], and by Marek with benchmark results from WBMv3.
Maybe "algorithm" is a big word for a little feature like that. The bonding and interface alternating basically work in two steps:
1) detect that a neighbor is reachable via two different links 2) use the two different links for various manipulations (bonding, interface alternation)
1) The detection part is batman-specific, we use the the PRIMARIES_FIRST_HOP flag to do that. As a reminder (that might be documented somewhere else):
* OGMs from the primary interface are broadcasted on ALL interfaces and are spread over the mesh (big TTL) --> these get the PRIMARIES_FIRST_HOP flag, which is cleared when forwarded by other nodes * OGMs from the secondary interfaces are only broadcasted on their respective interface and are only used for local link sensing (TTL = 1)
When we receive OGMs with PRIMARIES_FIRST_HOP flags on different interfaces, we know that it came from the same neighbor, just from different interfaces. We have two links to this neighbor.
2) the manipulation step is independent of the routing protocol, as long as the routing protocol routes packets based on their destination and does not care about on which interface it comes in.
Because we already made our routing decision (we have chosen a neighbor), it does not matter on which link we send the frame. We use this freedom to either use another interface where the frame came in (interface alternation) or round-robin over the available, detected links (bonding). Note that this would work on any routing protocol and is independent of the BATMAN routing.
However, we need the fact that we are on layer 2 and can decide on the packet link usage in batman-adv. This would not work so easily with static layer 3 routing tables, I suppose.
Gabriel said he has not enough time to look into it. I'm sorry, but I don't think this is a good reason to blame batman-adv devs :P
I finally decided to settle this issue and spent my breakfast reading batman-adv/routing.c [2] instead of my favorite newspaper. Here is what I understood:
At all times, batman-adv maintains a list of "bonding candidates" for each node (bonding_candidate_add, called from bat_iv_ogm.c:699). Some node "neigh" is a bonding candidate for another node "orig" if and only if: - neigh and orig have the same primary address, ie. are in fact the same router,
that's right - we are talking about one neighbor, and the bonding candidates are the available links to this neighbor.
- the links to reach them have the same quality up to some additive constant (BONDING_TQ_THRESHOLD = 50) [3],
Yep, it would be useless if we can reach one link perfectly and the other one is dropping all the packets. We want similar TQ quality.
- orig does not already have another bonding candidate for the same interface, because it could interfere – but what if the neigh has a better link quality, isn’t it a pity to ignore it?
If it had a better quality, it would have been chosen as router already - at least we expect that here. Maybe this is a little rough, but using the same interface/frequency is far worse, IMHO.
Then, assuming that "interface alternating" is enabled, the list of bonding candidates is used on every route selection (find_ifalter_router, called from routing.c:769).
Thats right. Interface alternating is always enabled, BTW.
More precisely, once batman has chosen a next-hop router for a packet based on its classical routing algorithm, it walks the list of the bonding candidates associated to the primary interface for this router [4]. It selects the actual next-hop on the following criteria: - it must not be on the same interface as the packet came in, - its quality must be as high as possible (given the previous constraint).This is the kind of explanation I would have loved to find on the wiki. By the way, consider it public domain and feel free to copy/paste/correct it if you wish.
Thanks for sharing your explanation. I will happily include it on the rework of this section.
It is still not clear to me exactly why this works, but I believe this is what the code does, and is definitely easier to discuss than generic, unsubstantiated claims.
Best regards, Gabriel
[1] “Interface alternating is only performed if the two candidate links to the next hop have a similar quality.” http://www.open-mesh.org/wiki/batman-adv/Multi-link-optimize
[2] http://www.open-mesh.org/projects/batman-adv/repository/revisions/master/ent...
[3] By the way, there is something I don’t understand: neigh_node->tq_avg will be accepted event if it is far greater than router->tq_avg + BONDING_TQ_THRESHOLD. Shouldn’t it be: abs(neigh_node->tq_avg - router->tq_avg) > BONDING_TQ_THRESHOLD? http://www.open-mesh.org/projects/batman-adv/repository/revisions/master/ent...
We expect that router->tq_avg is already the highest, so neigh_node->tq_avg shouldn't be (far) higher than router->tq_avg.
[4] Why the primary and not the chosen router directly? Is the bonding candidates list always associated to the primary interface?
We might have chosen the originator of a secondary interface, but should also have the originator of the primary interface (as explained above, we receive this over the secondary interfaces as well). The primary orig will have all neighbors from secondary interfaces as well, and yes, the bonding candidates are only associated to this primary originator (to avoid duplication of the same information), so this is the proper originator to choose for bonding/alternation. This is merely a implementation issue, and does not change the routing decision.
Thanks again for your comments - I'll notify you when we have updated the protocol documentation for your review, if thats okay?
Cheers, Simon
On Fri, Mar 9, 2012 at 9:56 AM, Simon Wunderlich simon.wunderlich@s2003.tu-chemnitz.de wrote:
Hey Gabriel,
thanks for bringing the discussion to the batman ml and giving some constructive input. I've written this bonding/alternating feature some time ago, and we released it at WBMv3 together with this little documentation to be found in the wiki. Actually, I considered the feature rather simple and therefore I did not write too much about it
- because there is not really much to write about, or so I thought. Obviously, there
were some things unclear, so thanks for pointing me/us to that.
When implementing, it is easy to miss some things that are not that obvious for outsiders, so please feel free to ask or suggest things. We'll rework the bonding/interface alternating part in the next days, and would be happy to include your suggestions. :)
Usually, we create the protocol documentation for the purpose of review and documentation for other batman-adv devs - and we don't expect that they all fall on the head at the same time. They are meant to describe the concept and not the actual implementation with all their nasty details.
On Wed, Mar 07, 2012 at 11:18:48PM +0100, Gabriel Kerneis wrote:
[CC: b.a.t.m.a.n@lists.open-mesh.org, see note 3 in particular]
Antonio,
On Wed, Mar 07, 2012 at 06:17:52PM +0100, Antonio Quartulli wrote:
Technical details about what? Interface-alternating? It is there! Gabriel wrote the link.
No. Please re-read my email carefuly. The wiki contains a rough explanation of the general principle (ie. “same interface = bad, different interface = good”). Not the actual algorithm used by batman-adv (quoting from the wiki: “the algorithm tries to avoid forwarding packets on the interface which just received the packet”).
Note that the wiki has been updated since then, by Simon with a few more details [1], and by Marek with benchmark results from WBMv3.
Maybe "algorithm" is a big word for a little feature like that. The bonding and interface alternating basically work in two steps:
1) detect that a neighbor is reachable via two different links 2) use the two different links for various manipulations (bonding, interface alternation)
Hoping over the same frequency should be made costly.
Do you add a cost if the packet comes from the same wireless interface?
-- Benjamin Henrion <bhenrion at ffii.org> FFII Brussels - +32-484-566109 - +32-2-3500762 "In July 2005, after several failed attempts to legalise software patents in Europe, the patent establishment changed its strategy. Instead of explicitly seeking to sanction the patentability of software, they are now seeking to create a central European patent court, which would establish and enforce patentability rules in their favor, without any possibility of correction by competing courts or democratically elected legislators."
On Friday, March 09, 2012 17:17:47 Benjamin Henrion wrote:
Maybe "algorithm" is a big word for a little feature like that. The bonding and interface alternating basically work in two steps:
- detect that a neighbor is reachable via two different links
- use the two different links for various manipulations (bonding,
interface alternation)
Hoping over the same frequency should be made costly.
Do you add a cost if the packet comes from the same wireless interface?
Since this question keeps coming up and also seems to be the reason for the confusion, let me make it clear once more: There is no special protocol treatment in any way. No added cost, no protocol change, no magic commandline switches, etc. It simply is not necessary!
This concept is so plain simple that everybody keeps wondering what we are hiding. You are looking for something that is not there.
Cheers, Marek
PS: Admittedly, it took us several attempts to make it that simple. :)
On Fri, Mar 9, 2012 at 10:42 AM, Marek Lindner lindner_marek@yahoo.de wrote:
On Friday, March 09, 2012 17:17:47 Benjamin Henrion wrote:
Maybe "algorithm" is a big word for a little feature like that. The bonding and interface alternating basically work in two steps:
1) detect that a neighbor is reachable via two different links 2) use the two different links for various manipulations (bonding, interface alternation)
Hoping over the same frequency should be made costly.
Do you add a cost if the packet comes from the same wireless interface?
Since this question keeps coming up and also seems to be the reason for the confusion, let me make it clear once more: There is no special protocol treatment in any way. No added cost, no protocol change, no magic commandline switches, etc. It simply is not necessary!
This concept is so plain simple that everybody keeps wondering what we are hiding. You are looking for something that is not there.
So on which interface the packet is gonna be transmitted?
-- Benjamin Henrion <bhenrion at ffii.org> FFII Brussels - +32-484-566109 - +32-2-3500762 "In July 2005, after several failed attempts to legalise software patents in Europe, the patent establishment changed its strategy. Instead of explicitly seeking to sanction the patentability of software, they are now seeking to create a central European patent court, which would establish and enforce patentability rules in their favor, without any possibility of correction by competing courts or democratically elected legislators."
On Friday, March 09, 2012 17:56:17 Benjamin Henrion wrote:
Since this question keeps coming up and also seems to be the reason for the confusion, let me make it clear once more: There is no special protocol treatment in any way. No added cost, no protocol change, no magic commandline switches, etc. It simply is not necessary!
This concept is so plain simple that everybody keeps wondering what we are hiding. You are looking for something that is not there.
So on which interface the packet is gonna be transmitted?
Hopefully the optimum interface. :-)
Sorry, but your question is too broad to give a meaningful answer.
Regards, Marek
So on which interface the packet is gonna be transmitted?
Hopefully the optimum interface.
There was a short productive phase when we managed to get Marek to shut up. Unfortunately, it looks like this phase is over.
-- Juliusz
Hi,
On 9 March 2012 11:26, Juliusz Chroboczek jch@pps.jussieu.fr wrote:
So on which interface the packet is gonna be transmitted?
Hopefully the optimum interface.
There was a short productive phase when we managed to get Marek to shut up. Unfortunately, it looks like this phase is over.
Just a note for those who do not know about the nice atmosphere of the WBM events: those who are fighting in this thread are in fact good friends and can have very very interesting discussions ;)
-- Juliusz
Hi!
Just a note for those who do not know about the nice atmosphere of the WBM events: those who are fighting in this thread are in fact good friends and can have very very interesting discussions ;)
Love-hate relationship. ;-)
Mitar
Hi Benjamin,
On Fri, Mar 09, 2012 at 10:17:47AM +0100, Benjamin Henrion wrote:
On Fri, Mar 9, 2012 at 9:56 AM, Simon Wunderlich
Maybe "algorithm" is a big word for a little feature like that. The bonding and interface alternating basically work in two steps:
1) detect that a neighbor is reachable via two different links 2) use the two different links for various manipulations (bonding, interface alternation)
Hoping over the same frequency should be made costly.
Do you add a cost if the packet comes from the same wireless interface?
AFAIU, Batman will never send a packet back on the same interface (be it wired or wireless, whatever the frequency, etc. – they don’t care at all). Except if this is the only available one, of course, or if the alternative interfaces have been dismissed for some reason (too low quality, etc.).
They just decide upfront a set of alternative interfaces, and then choose the best interface that it is not the incoming one among this set, for each packet. You have no way to declare that two different wifi interfaces interfere, for instance; it is roughly similar to babel -z1.
They just decide upfront a set of alternative interfaces, and then choose the best interface that it is not the incoming one among this set, for each packet.
Can you confirm that, Simon?
You have no way to declare that two different wifi interfaces interfere, for instance; it is roughly similar to babel -z1.
Unlike in Babel, however, where that happens at the metric level, in BATMAN it appears to be implemented at the route selection level. I'd like to better understand all of the tradeoffs involved.
On the one hand, doing things at the route selection level makes BATMAN's approach to diversity completely metric-agnostic, and avoids tricky issues of metric compositionality. On the other hand, encoding the diversity information in the metric has the advantage of propagating the information to other nodes.
Consider the following topology (all links assumed lossless), where we're trying to route from A to S:
B---C / \ / \ A S \ / \ / B'---*C' (C' has just a single interface)
In Babel, even with just Z1,the diversity information is encoded in the metric, and so B announces a smaller metric than B'; this causes A to prefer the ABCS route to the AB'C'S route. Unless I'm misunderstanding something, in BATMAN no information is propagated to A -- the information about the extra diversity in the upper route is purely local to C.
(Note that this is completely orthogonal to explicitly propagating diversity information in addition to the metric, which only happens in Babel-Z3.)
-- Juliusz
Consider the following topology (all links assumed lossless), where we're trying to route from A to S:
B---C / \\ / \\A S \ / \ / B'---*C' (C' has just a single interface)
In Babel, even with just Z1,the diversity information is encoded in the metric, and so B announces a smaller metric than B'; this causes A to prefer the ABCS route to the AB'C'S route. Unless I'm misunderstanding something, in BATMAN no information is propagated to A -- the information about the extra diversity in the upper route is purely local to C.
Hi Juliusz
I'm no expert here, but if Simon happens to fall on his head.....
The metric is simply based on TQ. C=S will probably have a better local TQ than C'-S because of the load balancing over the two links, meaning there are less packets in the air, and so probably less collisions, etc.. A gets to know the complete link path TQ going both ways around the loop, so does get some idea that C=S is better than C'-S, assuming it is actually better.
Andrew
The metric is simply based on TQ. C=S will probably have a better local TQ than C'-S because of the load balancing over the two links,
Sorry for the confusion, I used « = » to mark a different frequency than « - ». There's only the one link between C and S, it's just using a different (non-interfering) frequency.
-- Juliusz
On Fri, Mar 09, 2012 at 02:10:02PM +0100, Juliusz Chroboczek wrote:
The metric is simply based on TQ. C=S will probably have a better local TQ than C'-S because of the load balancing over the two links,
Sorry for the confusion, I used « = » to mark a different frequency than « - ». There's only the one link between C and S, it's just using a different (non-interfering) frequency.
Then the route over the = link will probably have a better TQ due to less packet loss (as it doesn't interfere with any neighbouring link). But there is no explicit coding of this "better freq" in the metric.
Cheers,
-- Juliusz
-----Original Message----- From: battlemesh-bounces@ml.ninux.org [mailto:battlemesh- bounces@ml.ninux.org] On Behalf Of Juliusz Chroboczek Sent: Friday, March 09, 2012 2:10 PM To: Battle of the Mesh Mailing List Cc: b.a.t.m.a.n@lists.open-mesh.org Subject: Re: [Battlemesh] Diversity in BATMAN
The metric is simply based on TQ. C=S will probably have a better local TQ than C'-S because of the load balancing over the two links,
Sorry for the confusion, I used < = > to mark a different frequency than < - >. There's only the one link between C and S, it's just using a different (non-interfering) frequency.
Ah, O.K.
Humm, the answer stays the same :-)
C=S will probably have a better TQ if it is not getting as much interference due to collisions. A will get to know about this in the path TQ. Better still, B-C will also probably have a better TQ, since the link C=S is not interfering with it. So the path TQ is even better. A gets all this.
Andrew
On Fri, Mar 9, 2012 at 2:36 PM, andrew.lunn@ascom.com wrote:
-----Original Message----- From: battlemesh-bounces@ml.ninux.org [mailto:battlemesh- bounces@ml.ninux.org] On Behalf Of Juliusz Chroboczek Sent: Friday, March 09, 2012 2:10 PM To: Battle of the Mesh Mailing List Cc: b.a.t.m.a.n@lists.open-mesh.org Subject: Re: [Battlemesh] Diversity in BATMAN
The metric is simply based on TQ. C=S will probably have a better local TQ than C'-S because of the load balancing over the two links,
Sorry for the confusion, I used < = > to mark a different frequency than < - >. There's only the one link between C and S, it's just using a different (non-interfering) frequency.
Ah, O.K.
Humm, the answer stays the same :-)
C=S will probably have a better TQ if it is not getting as much interference due to collisions. A will get to know about this in the path TQ. Better still, B-C will also probably have a better TQ, since the link C=S is not interfering with it. So the path TQ is even better. A gets all this.
How do you compute the TQ?
-- Benjamin Henrion <bhenrion at ffii.org> FFII Brussels - +32-484-566109 - +32-2-3500762 "In July 2005, after several failed attempts to legalise software patents in Europe, the patent establishment changed its strategy. Instead of explicitly seeking to sanction the patentability of software, they are now seeking to create a central European patent court, which would establish and enforce patentability rules in their favor, without any possibility of correction by competing courts or democratically elected legislators."
On Friday, March 09, 2012 22:07:37 Benjamin Henrion wrote:
C=S will probably have a better TQ if it is not getting as much interference due to collisions. A will get to know about this in the path TQ. Better still, B-C will also probably have a better TQ, since the link C=S is not interfering with it. So the path TQ is even better. A gets all this.
How do you compute the TQ?
I suggest reading chapter 3.1 (specifically 3.1.3) of the excellent network coding paper[1] written by our catwoman specialists. It is very well written and contains the most comprehensive general overview about batman-adv in existence.
Regards, Marek
[1] http://downloads.open-mesh.org/batman/papers/batman-adv_network_coding.pdf
On Fri, Mar 9, 2012 at 3:36 PM, Marek Lindner lindner_marek@yahoo.de wrote:
On Friday, March 09, 2012 22:07:37 Benjamin Henrion wrote:
C=S will probably have a better TQ if it is not getting as much interference due to collisions. A will get to know about this in the path TQ. Better still, B-C will also probably have a better TQ, since the link C=S is not interfering with it. So the path TQ is even better. A gets all this.
How do you compute the TQ?
I suggest reading chapter 3.1 (specifically 3.1.3) of the excellent network coding paper[1] written by our catwoman specialists. It is very well written and contains the most comprehensive general overview about batman-adv in existence.
TQ is based on packet-loss only, so it is doomed to fail to detect fast interfaces.
With such metric, you don't make any difference between a 56K telephone line and a 10Ge NIC.
If you 10Ge has 5pc packet loss and your 56K line has 0pc, your TQ will be prefer the 56k link.
-- Benjamin Henrion <bhenrion at ffii.org> FFII Brussels - +32-484-566109 - +32-2-3500762 "In July 2005, after several failed attempts to legalise software patents in Europe, the patent establishment changed its strategy. Instead of explicitly seeking to sanction the patentability of software, they are now seeking to create a central European patent court, which would establish and enforce patentability rules in their favor, without any possibility of correction by competing courts or democratically elected legislators."
On Friday, March 09, 2012 23:25:03 Benjamin Henrion wrote:
TQ is based on packet-loss only, so it is doomed to fail to detect fast interfaces.
With such metric, you don't make any difference between a 56K telephone line and a 10Ge NIC.
If you 10Ge has 5pc packet loss and your 56K line has 0pc, your TQ will be prefer the 56k link.
Absolute correct assessment.
I'd like to add that batman was designed to work most efficiently in environments with packet loss. The main target was/is wireless and not environments without packet loss. However, we do noticed the desire to use batman in other environments too and are working on improving batman to satisfy this demand. I'm not sure we will ever be as efficient as routing protocols that were designed for "stable" environments only.
Regards, Marek
With such metric, you don't make any difference between a 56K telephone line and a 10Ge NIC.
If you 10Ge has 5pc packet loss and your 56K line has 0pc, your TQ will be prefer the 56k link.
If my 10Ge has 5% packet loss, its broken. I don't want to use it. Falling back to the 56K link is the right thing to do.
There is a general rule of thumb. The higher the bandwidth, the less packet loss there is. This is because high bandwidth links are generally not wireless and so don't suffer high packet loss.
As a side effect, BATMAN will tend to favor wired links over wireless links, because wired links tend to be reliable, wireless links drop packets.
Andrew
On Fri, Mar 9, 2012 at 4:43 PM, Andrew Lunn andrew@lunn.ch wrote:
With such metric, you don't make any difference between a 56K telephone line and a 10Ge NIC.
If you 10Ge has 5pc packet loss and your 56K line has 0pc, your TQ will be prefer the 56k link.
If my 10Ge has 5% packet loss, its broken. I don't want to use it. Falling back to the 56K link is the right thing to do.
There is a general rule of thumb. The higher the bandwidth, the less packet loss there is. This is because high bandwidth links are generally not wireless and so don't suffer high packet loss.
As a side effect, BATMAN will tend to favor wired links over wireless links, because wired links tend to be reliable, wireless links drop packets.
So compare a 1Mbits wireless link with a 54Mbits one.
-- Benjamin Henrion <bhenrion at ffii.org> FFII Brussels - +32-484-566109 - +32-2-3500762 "In July 2005, after several failed attempts to legalise software patents in Europe, the patent establishment changed its strategy. Instead of explicitly seeking to sanction the patentability of software, they are now seeking to create a central European patent court, which would establish and enforce patentability rules in their favor, without any possibility of correction by competing courts or democratically elected legislators."
On Fri, Mar 09, 2012 at 05:07:37PM +0100, Benjamin Henrion wrote:
On Fri, Mar 9, 2012 at 4:43 PM, Andrew Lunn andrew@lunn.ch wrote:
With such metric, you don't make any difference between a 56K telephone line and a 10Ge NIC.
If you 10Ge has 5pc packet loss and your 56K line has 0pc, your TQ will be prefer the 56k link.
If my 10Ge has 5% packet loss, its broken. I don't want to use it. Falling back to the 56K link is the right thing to do.
There is a general rule of thumb. The higher the bandwidth, the less packet loss there is. This is because high bandwidth links are generally not wireless and so don't suffer high packet loss.
As a side effect, BATMAN will tend to favor wired links over wireless links, because wired links tend to be reliable, wireless links drop packets.
So compare a 1Mbits wireless link with a 54Mbits one.
The 54Mbps link probably has a very low packet error rate. Otherwise it would not be running at 54 Mbps. The automatic rate selection algorithm would take it down to a lower rate if it had high packet loss.
On the other hand, any link running at 1Mbit probably has quite a high packet error rate. It must be a bad link, otherwise it would not be using the lowest possible coding rate.
So when comparing a 1Mbps and a 54Mbps link, probably the TQ for the 54Mbps link will be better than the 1Mbps link.
Andrew
Andrew,
On Fri, Mar 09, 2012 at 05:21:37PM +0100, Andrew Lunn wrote:
The 54Mbps link probably has a very low packet error rate. Otherwise it would not be running at 54 Mbps. The automatic rate selection algorithm would take it down to a lower rate if it had high packet loss.
On the other hand, any link running at 1Mbit probably has quite a high packet error rate. It must be a bad link, otherwise it would not be using the lowest possible coding rate.
So when comparing a 1Mbps and a 54Mbps link, probably the TQ for the 54Mbps link will be better than the 1Mbps link.
That was our intuition too, but experiments we did in Brussels using 802.11n multiradio routers, with Benjamin and Juliusz, seemed to show that packet loss (as measured by babel at least) is not always correlated to throughput. I do not claim to understand how this is possible.
It was in a limited setup, however, and we would be glad to get more results proving or disproving this hypothesis. Do you have any actual experimental results to share on this topic?
Best regards,
So when comparing a 1Mbps and a 54Mbps link, probably the TQ for the 54Mbps link will be better than the 1Mbps link.
That was our intuition too, but experiments we did in Brussels using 802.11n multiradio routers, with Benjamin and Juliusz, seemed to show that packet loss (as measured by babel at least) is not always correlated to throughput. I do not claim to understand how this is possible.
How do you define throughput? Do you mean the coding rate the wifi driver has chosen to use, or iperf/netperf measurements of throughput? Also, does babel perform its measurements using unicast or broadcast/multicast packets/frames?
It was in a limited setup, however, and we would be glad to get more results proving or disproving this hypothesis. Do you have any actual experimental results to share on this topic?
I've got no results on 11n. I've done most of my work on 11g. I will see if i've got any results for 11g which might be appropriate.
Maybe
I've got no results on 11n. I've done most of my work on 11g. I will see if i've got any results for 11g which might be appropriate.
Maybe
Upps. Got side tracked, disrupted, and hit send....
Maybe you could perform some more tests in this direction at the next WBM in Athens?
Andrew
On Sat, Mar 10, 2012 at 05:37:00 -0800, Mitar wrote:
Hi!
Maybe you could perform some more tests in this direction at the next WBM in Athens?
I don't think any of us are going to Athens.
No? How come? Why?
I'm wondering the same :(:(:(
From the participant list it seems that all the French guys but one gave up on WBM :(:(:( this is sad
Only a coincidence or there is something wrong this year?
Cheers,
I don't think any of us are going to Athens.
No? How come? Why?
Gabriel and I are busy -- we're hard at work wrapping up some stuff we've been working on for the last four years, we hope to finish soon. I cannot speak for the others.
There Ain't No Cabal, if that's what you mean. However, in my personal case, there's also the fact that WBM has been evolving in a direction that I don't feel comfortable with (less technical content, more self- promotion, tolerance for bomb-makers, etc.)
-- Juliusz
Hi!
However, in my personal case, there's also the fact that WBM has been evolving in a direction that I don't feel comfortable with (less technical content, more self- promotion, tolerance for bomb-makers, etc.)
Self-promotion of good ideas is not necessary bad. And others are there to squash the bad ideas. ;-)
But for technical content: I think you could easily volunteer to lead few round tables on the topic of protocol design. For example, this discussion we are now having on the mailing list about different aspects of routing protocols: oh, how I would love to have them in live, with everybody from all protocols together, sitting and explaining their approaches, their arguments and experiences why they are doing something in the way they are doing: is this theoretical argument, or is it simply a practical observation, can we find a theoretical reasoning behind it, can we maybe invalidate some theoretical argument with a practical (repeatable) experiment?
Because I think I am not the only one who does not know much about how other protocols are doing things, what were the reasons they have chosen the given approach, ... And it would really help understanding each other, and maybe, maybe, we could in some years even agree on a common routing protocol. ;-)
This would also be interesting for non-technical and new people, because they would be able to listen and understand how things work.
But because Juliusz is afraid to come, I can volunteer to moderate (and mediate) such tables if others prepare me a list of topics to discuss.
Mitar
Hey there,
On Sun, Mar 11, 2012 at 09:02:54AM -0700, Mitar wrote:
Hi!
However, in my personal case, there's also the fact that WBM has been evolving in a direction that I don't feel comfortable with (less technical content, more self- promotion, tolerance for bomb-makers, etc.)
Self-promotion of good ideas is not necessary bad. And others are there to squash the bad ideas. ;-)
I definitly agree. If we promote bad ideas as the batman-adv-team, I'm sure we'll be shouted at very loud, and thats a great thing.
But for technical content: I think you could easily volunteer to lead few round tables on the topic of protocol design. For example, this discussion we are now having on the mailing list about different aspects of routing protocols: oh, how I would love to have them in live, with everybody from all protocols together, sitting and explaining their approaches, their arguments and experiences why they are doing something in the way they are doing: is this theoretical argument, or is it simply a practical observation, can we find a theoretical reasoning behind it, can we maybe invalidate some theoretical argument with a practical (repeatable) experiment?
Because I think I am not the only one who does not know much about how other protocols are doing things, what were the reasons they have chosen the given approach, ... And it would really help understanding each other, and maybe, maybe, we could in some years even agree on a common routing protocol. ;-)
This would also be interesting for non-technical and new people, because they would be able to listen and understand how things work.
But because Juliusz is afraid to come, I can volunteer to moderate (and mediate) such tables if others prepare me a list of topics to discuss.
Sounds like a great idea! After some discussion with some other batman-adv devs, we would really like to join this. Actually I think its a good thing that we have some different routing protocols. Diversity gives birth to different approaches, which may succeed or fail, and in both events we can learn from each other. Anyway, maybe we should have put a list in the wiki what we want to dicuss? Do you want to put it as a side-event or more like a podium discussion thing?
Cheers, Simon
Hi!
Sounds like a great idea!
I am glad you like it.
Anyway, maybe we should have put a list in the wiki what we want to dicuss?
Agreed.
Do you want to put it as a side-event or more like a podium discussion thing?
Maybe it would be better if it would be a podium discussion thing. So that others could join in. If it would be a side-event, it would be more like a work-group meeting.
Mitar
That was our intuition too, but experiments we did in Brussels using 802.11n multiradio routers, with Benjamin and Juliusz, seemed to show that packet loss (as measured by babel at least) is not always correlated to throughput. I do not claim to understand how this is possible.
It's not magic, and I don't think it's due to .11n.
We currently measure using multicast, which in 802.11 is sent at a low rate. Minstrel, the rate adaptation algorithm used by Linux, uses unicast probes at the higher data rates to find out the optimum rate. What we have shown is that under some conditions, the multicast packet loss is zero, while Minstrel detects data loss at the higher data rates.
As Benjamin rightly noted, this implies that, for that particular class of links, multicast packet loss rate is a poor predictor of link quality. (Duh. It's constant zero.)
We've got various ideas about how to solve this issue. Dave suggested hooking into the data structures that Minstrel is using. For Babel, that'd be a cross-layer indication, which is something that makes me nervous, but it should be no problem for a layer 2 protocol. While I like Dave's suggestion, I also like to keep Babel lower-layer agnostic, and I'm considering the use of a different predictor which has the advantage of also making sense on wired links. I'm not telling more right now, I want to implement and test first.
-- Juliusz
Hey Simon,
On Fri, Mar 09, 2012 at 09:56:36AM +0100, Simon Wunderlich wrote:
- The detection part is batman-specific, we use the the PRIMARIES_FIRST_HOP flag
to do that. As a reminder (that might be documented somewhere else):
- OGMs from the primary interface are broadcasted on ALL interfaces and are spread over the mesh (big TTL) --> these get the PRIMARIES_FIRST_HOP flag, which is cleared when forwarded by other nodes
- OGMs from the secondary interfaces are only broadcasted on their respective interface and are only used for local link sensing (TTL = 1)
When we receive OGMs with PRIMARIES_FIRST_HOP flags on different interfaces, we know that it came from the same neighbor, just from different interfaces. We have two links to this neighbor.
I think my primary misunderstanding comes from this concept of “primary interface”. It might be due to my lack of knowledge about Batman, but it definitely looks like a hack to me: why do you need this symmetry breaking in the first place?
I believe the rest is only implementation details layered on top of this assumption.
Maybe there is some explanation that I have overlooked in the wiki? I have not found, for instance, how the primary interface is chosen.
Best regards,
On Friday, March 09, 2012 19:12:03 Gabriel Kerneis wrote:
When we receive OGMs with PRIMARIES_FIRST_HOP flags on different interfaces, we know that it came from the same neighbor, just from different interfaces. We have two links to this neighbor.
I think my primary misunderstanding comes from this concept of “primary interface”. It might be due to my lack of knowledge about Batman, but it definitely looks like a hack to me: why do you need this symmetry breaking in the first place?
I believe the rest is only implementation details layered on top of this assumption.
Maybe there is some explanation that I have overlooked in the wiki? I have not found, for instance, how the primary interface is chosen.
The concept of a primary interface goes back into the early days of batman and primarily is an optimization to reduce overhead. At some point we realized that it is not necessary to flood the mesh with OGMs from each and every interface we have. Nearby nodes might want to know about all interfaces to select the best one. Nodes that are far away don't care which interface is connected to what other interface. They only care about a route to their destination. This concept is briefly explained here[1] (section 2.1.6 and 2.1.7).
What interface is going to be the primary interface does not matter at all. For the sake of simplicty batman chooses the first interface to be the primary interface but it could be any interface you prefer. The key point is that only the primary interface is known in the entire mesh whereas secondary interfaces are known by single hop neighbors only.
Regards, Marek
[1] http://downloads.open-mesh.org/batman/papers/batman-status.pdf
On Fri, Mar 09, 2012 at 07:26:54PM +0800, Marek Lindner wrote:
The concept of a primary interface goes back into the early days of batman and primarily is an optimization to reduce overhead. At some point we realized that it is not necessary to flood the mesh with OGMs from each and every interface we have. Nearby nodes might want to know about all interfaces to select the best one. Nodes that are far away don't care which interface is connected to what other interface. They only care about a route to their destination. This concept is briefly explained here[1] (section 2.1.6 and 2.1.7).
Thanks for the pointer.
Does that mean that it is impossible to announce a route on some interfaces only? It looks like a rather arbitrary limitation.
In case I misunderstood and it is actually possible, I fail to see ĥow the alternating algorithm takes this into account: it seems to assume that a node will accept to route any packet on any interface. Did I miss something?
Best regards,
On Fri, Mar 09, 2012 at 01:04:55PM +0100, Gabriel Kerneis wrote:
On Fri, Mar 09, 2012 at 07:26:54PM +0800, Marek Lindner wrote:
The concept of a primary interface goes back into the early days of batman and primarily is an optimization to reduce overhead. At some point we realized that it is not necessary to flood the mesh with OGMs from each and every interface we have. Nearby nodes might want to know about all interfaces to select the best one. Nodes that are far away don't care which interface is connected to what other interface. They only care about a route to their destination. This concept is briefly explained here[1] (section 2.1.6 and 2.1.7).
Thanks for the pointer.
Does that mean that it is impossible to announce a route on some interfaces only? It looks like a rather arbitrary limitation.
OGMs are broadcasted over all the interfaces (there may be some neighs reachable only by one interface) and you can't force an OGM to be broadcasted only over one of them. I hope I correctly got your question.
In case I misunderstood and it is actually possible, I fail to see ĥow the alternating algorithm takes this into account: it seems to assume that a node will accept to route any packet on any interface. Did I miss something?
Packets are alternatively routed on all the "possible" interfaces (a neighbor could be connected only to a subset of them) until the metric on that interface is acceptable. I hope I correctly got your question again.
Cheers,
Antonio,
On Fri, Mar 09, 2012 at 01:39:06PM +0100, Antonio Quartulli wrote:
Does that mean that it is impossible to announce a route on some interfaces only? It looks like a rather arbitrary limitation.
OGMs are broadcasted over all the interfaces (there may be some neighs reachable only by one interface) and you can't force an OGM to be broadcasted only over one of them. I hope I correctly got your question.
My question is about some kind of policy routing (setup by the administrator, not guessed by batman).
Consider the following topology:
l0 l1 A ---- B ==== C l2
where --- is a single link (l0) and === are two links (l1 and l2).
Now imagine that the administator wants to dedicate the link l2 to the communication between B and C, for whatever reason. It is fairly easy to set netfilter rules to that effect, for instance.
1) Is it possible for the administrator of B to configure batman so that it announces a route to A only over l1, and not l2? Such that C will only ever send packets for A over l1, and B never replies on l2 either.
2) If that is possible, what is the mechanism in the alternating algorithm which prevents batman from sending packets from A to C over l2 (assuming TQ1 < TQ2)? It looks like both l1 and l2 will end up as bonding alternates for C.
Best,
On Fri, Mar 09, 2012 at 01:57:41PM +0100, Gabriel Kerneis wrote:
Antonio,
On Fri, Mar 09, 2012 at 01:39:06PM +0100, Antonio Quartulli wrote:
Does that mean that it is impossible to announce a route on some interfaces only? It looks like a rather arbitrary limitation.
OGMs are broadcasted over all the interfaces (there may be some neighs reachable only by one interface) and you can't force an OGM to be broadcasted only over one of them. I hope I correctly got your question.
My question is about some kind of policy routing (setup by the administrator, not guessed by batman).
Consider the following topology:
l0 l1 A ---- B ==== C l2where --- is a single link (l0) and === are two links (l1 and l2).
Now imagine that the administator wants to dedicate the link l2 to the communication between B and C, for whatever reason. It is fairly easy to set netfilter rules to that effect, for instance.
Thanks for the exhaustive explanation.
- Is it possible for the administrator of B to configure batman so that it announces a route to A only over l1, and not l2? Such that C will only ever send packets for A over l1, and B never replies on l2 either.
No, it is not possible. No filtering/manual selection is possible in batman-adv, right now.
It looks like both l1 and l2 will end up as bonding alternates for C.
Yes.
Cheers,
My question is about some kind of policy routing (setup by the administrator, not guessed by batman).
Consider the following topology:
l0 l1 A ---- B ==== C l2where --- is a single link (l0) and === are two links (l1 and l2).
Now imagine that the administator wants to dedicate the link l2 to the communication between B and C, for whatever reason. It is fairly easy to set netfilter rules to that effect, for instance.
Hi Gabriel
Remember that BATMAN is a Layer 2 mesh, not layer 3.
It would be possible to do what you want. Simply don't add the l2 interfaces to BATMAN, put IP addresses from a different subnet on the interfaces, and B and C can use the link l2 for themselves, and use the bat0 interface for access to the mesh subnet.
Andrew
Andrew,
On Fri, Mar 09, 2012 at 01:09:26PM +0000, andrew.lunn@ascom.com wrote:
Consider the following topology:
l0 l1 A ---- B ==== C l2where --- is a single link (l0) and === are two links (l1 and l2).
Now imagine that the administator wants to dedicate the link l2 to the communication between B and C, for whatever reason. It is fairly easy to set netfilter rules to that effect, for instance.
It would be possible to do what you want. Simply don't add the l2 interfaces to BATMAN, put IP addresses from a different subnet on the interfaces, and B and C can use the link l2 for themselves, and use the bat0 interface for access to the mesh subnet.
This was of course a simplified example.
What if there are an arbitrary number of nodes between B and C instead of a direct link?
l0 l1 A ---- B ---------- C Example: \ / I want to restrict the link l1 to communication D -- E -- F between A and C. (Nice frying-pan, isn’t it? ;-)
I love ASCII-art, I can build arbitrarily complex situations (and we actually use this kind of stuff with babel on wifi.pps.jussieu.fr). Your solution doesn’t scale, it only pushes the problem outside of batman.
Best,
l0 l1 A ---- B ---------- C Example: \ / I want to restrict the link l1 to communication D -- E -- F between A and C. (Nice frying-pan, isn’t it? ;-)
I think that Andrew has answered your question. BATMAN is a pure mesh protocol; it doesn't support filtering, aggregation, or overlapping prefixes, and only limited support for multiple interfaces per node. Pure mesh is an excellent choice for layer 2 routing, where there are no overlapping prefixes, and little opportunity for aggregation or filtering.
(In a pure mesh protocol, routers with multiple interfaces should probably appear as multiple nodes; that is not done in BATMAN, seemingly for efficiency reasons, a choice I am not quite comfortable with.)
Your solution [...] only pushes the problem outside of batman.
Yes, and that's a feature. Layer 3 problems are outside the scope of a layer 2 protocol.
-- Juliusz
Hi!
(In a pure mesh protocol, routers with multiple interfaces should probably appear as multiple nodes;
Why? I think it is good that the routing protocol knows that something (some interfaces) belongs together (node).
Mitar
I agree, whats the purpose of NOT having this information?
Henning
On Sat, Mar 10, 2012 at 17:20, Mitar mitar@tnode.com wrote:
Hi!
(In a pure mesh protocol, routers with multiple interfaces should probably appear as multiple nodes;
Why? I think it is good that the routing protocol knows that something (some interfaces) belongs together (node).
Mitar
Hmm, are we getting off-topic for the Battlemesh list?
(In a pure mesh protocol, routers with multiple interfaces should probably appear as multiple nodes;
Why? I think it is good that the routing protocol knows that something (some interfaces) belongs together (node).
I agree with both of you, this is precious information that should not be dropped. The question is whether it should be embedded in the network model, or kept outside of it.
A pure mesh model has the attraction of being extremely clean and pure; most graph theory theorems apply to a pure mesh model straight away, which allows you to leverage a large body of existing litterature. So intuitively there should be some strong advantages to keeping your model small and clean, and encoding the information about linked interfaces in a separate data structure.
I'm not quite sure what model BATMAN uses, but it would appear that it's almost, but not quite, a pure mesh model. Perhaps the BATMAN developers have thought long and hard about giving up the purity of a mesh model, and decided that it's worth it. Perhaps they haven't. It's difficult to say, since they're not interested in communicating on technical issues.
OLSR uses a pure model and encodes extra information in additional data structures. That's why OLSR uses MIDs and HNAs -- they're the packets carrying the additional data. An alternative "clean" model would be to have a router id for each interface, and an extra flag within TC entries that shows which links are between multiple interfaces of a single node, which is what I suggest might be a good choice at layer 2.
Babel uses a different model, the classical Internet model (very well described by Clark in the early 80s, but I don't have the paper handy). In that model, we're not working with a graph, but with a structure with three kind of entities: nodes, interfaces, and links, where links connect interfaces rather than connecting nodes. There are some advantages to using a model that more faithfully represents reality, and that is a good fit with what classical routing protocols do, but of course the downside is that we're working with a somewhat messy data structure that hasn't been studied as exhaustively as graphs have.
-- Juliusz
Hi!
Perhaps the BATMAN developers have thought long and hard about giving up the purity of a mesh model, and decided that it's worth it. Perhaps they haven't. It's difficult to say, since they're not interested in communicating on technical issues.
So we have one topic for the round tables. Good. Just ... we will not know how does Babel does it. Because you will not be there.
I propose a new name of a discipline at Battlemesh: Battletable! Where we get together representatives of different routing protocols and get them to fight! Which concept is better, why, how, what are arguments, cases, how to create a test case, ... We could even make it a reality show, or at least a talk show of Jerry Springer style!
I volunteer to moderate and mediate the fights, keeping them constructive and without low punches (OK, allowing some for the entertainment of the public).
You know, Juliusz, not being available for the discussion yourself makes you look like the person not interested in communication. Or you communicate only over e-mails? Because I understand perfectly that it is hard to write documentation, write long explanatory e-mails, we much more like to do concrete stuff: code, deploy, test ... And such events as Battlemesh are perfect especially because all interested-in-the-subject people can get together and you have a better feeling that it is "worth" the energy to explain all internals of routing protocols to others, because you are doing it to the multiple people at the same time. And a nice side effect can then be a video posted on your website with this discussion where others can watch you later.
Mitar
Andrew,
On Fri, Mar 09, 2012 at 01:09:26PM +0000, andrew.lunn@ascom.com wrote:
Remember that BATMAN is a Layer 2 mesh, not layer 3.
Sorry, I just recalled what it implies. You can ignore my previous answer, I was focused on babel-like, layer 3 examples.
On Fri, Mar 09, 2012 at 02:49:28PM +0100, Gabriel Kerneis wrote:
Andrew,
On Fri, Mar 09, 2012 at 01:09:26PM +0000, andrew.lunn@ascom.com wrote:
Remember that BATMAN is a Layer 2 mesh, not layer 3.
Sorry, I just recalled what it implies.
:-)
You can ignore my previous answer, I was focused on babel-like, layer 3 examples.
l0 l1 A ---- B ---------- C Example: \ / I want to restrict the link l1 to communication D -- E -- F between A??and C. (Nice frying-pan, isn???t it? ;-)
It is still possible, but requires more configuration effort. But anybody who can setup iptable rules should be able to achieve it.
Create a mesh with B, D, E, F, C, but leave out the interfaces for B-l0, B-l1 and C-l1. Setup a bridge on B. Add to the bridge the interfaces bat0, b-l1, b-l0. Add ebtable rules to the bridge to bridge A<->C frames between b-l0 and b-bl1 interfaces, the rest of the traffic from A is bridged into the bat0 interface. You need a similar bridge on C, with ebtable rules to pass the frames over the correct interfaces.
You also need to take a little bit of care with multicast frames, or the spanning tree protocol might get upset and block some of the interfaces in order to break the loops it sees.
Andrew
b.a.t.m.a.n@lists.open-mesh.org
-
Andrew Lunn -
andrew.lunn＠ascom.com -
Antonio Quartulli -
Benjamin Henrion -
Gabriel Kerneis -
Henning Rogge -
Juliusz Chroboczek -
Marek Lindner -
Mitar -
Roger Baig Viñas -
Simon Wunderlich