---------- Forwarded message ---------- From: hlabishi kobo hlabishik@gmail.com Date: Sun, 28 Nov 2010 22:06:01 +0200 Subject: Fwd: BATMAN routing To: lindner_marek@yahoo.de
Hi
Thank you very much for your reply. The reason why i sent this to you and your colleague is that i have tried the mail list before and all my post kept on being returned, i used this address b.a.t.m.a.n-owner@lists.open-mesh.org. I would really appreciate it if this can reach the mailing list public (i will keep on trying). i will send you a follow up on the full explanation of the concept like you requested.
Regards Hlabishi ---------- Forwarded message ---------- From: b.a.t.m.a.n-owner@lists.open-mesh.org Date: Sat, Nov 27, 2010 at 12:58 AM Subject: Fwd: BATMAN routing To: hlabishik@gmail.com
Message rejected by filter rule match
---------- Forwarded message ---------- From: hlabishi kobo hlabishik@gmail.com To: b.a.t.m.a.n@lists.open-mesh.org Date: Sat, 27 Nov 2010 00:58:09 +0200 Subject: Fwd: BATMAN routing
---------- Forwarded message ---------- From: Marek Lindner lindner_marek@yahoo.de Date: Fri, Nov 26, 2010 at 5:23 PM Subject: Re: BATMAN routing To: hlabishi kobo hlabishik@gmail.com, Linus Lüssing < linus.luessing@web.de> Cc: siwu@hrz.tu-chemnitz.de
Hi,
welcome to the project! :-)
Firstly my apologies for sending this email to your personal email. My
name
is Hlabishi Isaac Kobo at the, an Msc computer science student at the University of the Western Cape in South Africa, I am doing a research on routing in a hybrid (combination of static and mobile dynamic routers) mesh.
I don't see a good reason to apologize, just wondering why you are not sending this mail to the public list ?
I want to use the mesh potatoes as well as the batphone (android version of batman) to create a mesh model.
What is the "batphone" ? A project name or a nick name you invented ? :-)
Note: Various tests have shown that running a mobile device (smartphone/tablet/etc) in adhoc mode plus running a mesh protocol on top is a battery killer, hence not practical in real world scenarios (in addition of the hassle to install and configure the mesh software on each and every device). This was one of the main reasons to start developing batman-adv as it allows mobile devices to take advantage of the mesh (e.g. roaming) without having to run the mesh on the device itself.
You might be aware of this - I am just mentioning it because many people are not.
First we say the recently received OGMs will give a clear indication on
the
reliability on the link, so we give the recently received OGMs from the sliding window a priority in deciding the best next hop link towards a destination. We want to count and add the indexes were an OGM was recorded in an interval (seconds), (hence the recently received OGM will have more weight). At the end the link with more recent OGMs will have more weight and hence become the current best link.
This is a good idea. We are in the process of redesigning the current protocol and welcome any input. Giving older OGMs less "weight" was also one of the ideas we had. Would you mind explaining your concept in greater detail ?
I went through the source code so many times and I got few questions about this:
Are we talking about the batman daemon source code or the batman-adv kernel module ? All my answers will refer to the kernel module as this is the place where most of the development is going on at the moment.
- What structure is used to keep track of the sliding window? If its the
has how does it get updated based on the sliding packet range?
Each "struct orig_node" has a bitarray to keep track of its own seqnos repeated by its neighbors (bcast_own) and each "struct neigh_node" having a bitarray for its own OGMs (real_bits).
- How are the OGM's recorded, is in a form of binary where 1 will
represent the received OGM and 0 otherwise?
Correct.
- I looked in the source and still not sure of where the ranking
decisions
are made, can you enlighten me on that?
You mean which function changes the route when a better neighbor was found ? That would be update_orig() in routing.c.
On the second approach we want to use mac layer stats to estimate the signal strength and probably the congestion rate of the top N ranked
links.
We acknowledge the fact that usually links with lower signal strength will loose more OGM's which results in an automatic low rank, however in a frequently changing topology, current signal strength is crucial. We plan to use SNR or RSSI in this case.
The concept is known since a while but nobody has implemented it so far because its implementation is fairly complex. Do you have an idea how it should work in the end ?
- How can i get the RSSI/LQI of th neighbor links?
I don't get this question. You intend to use RSSI but you don't know how ?
I would really appreciate your opinions and advices in this regard more specially how to go about implementing changes in BATMAN protocol.
This is a little abstract. Usually, we discuss specific concepts / ideas in our IRC channel or on the mailing list long before starting to implement them. The past has shown it is often better to let other people dive into your ideas and comment because routing is a rather complex subject.
As I mentioned above: We are in a redesign phase right now and welcome anyone interested to join. As the next step we envisioned a collection of routing scenarios in which the current implementation behaves poorly. All routing protocol changes have to go through this collection of scenarios to estimate its impact. What do you think about this idea ?
Regards, Marek
Hi Hlabishi and welcome!
As I mentioned above: We are in a redesign phase right now and welcome anyone interested to join.
Hmm, what would you think about a voip conference for anyone interested to join :)? I think there are still quite some open questions about how a BATMAN V algorithm could look like. And I wanted to discuss some of the recent experiences in mobile scenarios anyway.
We could try something like mumble for the chatting, I've setup an experimental server on open-mesh.org on its default port. I'd suggest something like 6pm UTC. If anyone who's interested to join can't make it at that time, feel free to suggest another date then. Anyone who thinks this is fine and would like to attend, please drop a note :).
Cheers, Linus
PS: Some interesting ideas and questions have been raised so far, I'm looking forward to interesting answers via email already, too :).
module ? All my answers will refer to the kernel module as this is the place where most of the development is going on at the moment.
On the second approach we want to use mac layer stats to estimate the signal strength and probably the congestion rate of the top N ranked
links.
We acknowledge the fact that usually links with lower signal strength will loose more OGM's which results in an automatic low rank, however in a frequently changing topology, current signal strength is crucial. We plan to use SNR or RSSI in this case.
The concept is known since a while but nobody has implemented it so far because its implementation is fairly complex. Do you have an idea how it should work in the end ?
- How can i get the RSSI/LQI of th neighbor links?
I don't get this question. You intend to use RSSI but you don't know how ?
I would really appreciate your opinions and advices in this regard more specially how to go about implementing changes in BATMAN protocol.
This is a little abstract. Usually, we discuss specific concepts / ideas in our IRC channel or on the mailing list long before starting to implement them. The past has shown it is often better to let other people dive into your ideas and comment because routing is a rather complex subject.
scenarios in which the current implementation behaves poorly. All routing protocol changes have to go through this collection of scenarios to estimate its impact. What do you think about this idea ?
Regards, Marek
We could try something like mumble for the chatting, I've setup an experimental server on open-mesh.org on its default port. I'd suggest something like 6pm UTC. If anyone who's interested to join can't make it at that time, feel free to suggest another date then. Anyone who thinks this is fine and would like to attend, please drop a note :).
Woops, forgot to suggest the day, what about next Sunday?
Dear Marek and the BATMAN community. The idea is to prioritize recently received OGM's thus giving them more weight for the routing decisions. This is because they give a precise indication of the status of current situation of the link. BATMAN algorithm currently counts the number of received OGM's in a current sliding window and the link with the most OGM's becomes the best next-hop towards a that destination. A lot can happen within a second in an ad hoc wireless network. if a lot of OGM's where recorded at the beginning of the window range and less towards the end which be that the link was better at the beginning not at the end of the sliding window (current). This could be selected as the best as opposed to the one that recorded a lot of OGM's towards the end but less in total. e.g. suppose you have sliding window of 10, link 1 records [1111100000]= 5 and link 2 [0000001111] = 4. link 1 will be chosen and as it stands the current best would have been link 2. The proposed concept prioritizes the recently received OGM's by giving them more weight. Thus we want to add the indexes of which an OGM was received in that interval. from the example above we would have link 1+2+3+4+5+6= 21 and link 2 7+8+9+10 = 34.
Kind Regards Hlabishi
On 11/29/10, hlabishi kobo hlabishik@gmail.com wrote:
---------- Forwarded message ---------- From: hlabishi kobo hlabishik@gmail.com Date: Sun, 28 Nov 2010 22:06:01 +0200 Subject: Fwd: BATMAN routing To: lindner_marek@yahoo.de
Hi
Thank you very much for your reply. The reason why i sent this to you and your colleague is that i have tried the mail list before and all my post kept on being returned, i used this address b.a.t.m.a.n-owner@lists.open-mesh.org. I would really appreciate it if this can reach the mailing list public (i will keep on trying). i will send you a follow up on the full explanation of the concept like you requested.
Regards Hlabishi ---------- Forwarded message ---------- From: b.a.t.m.a.n-owner@lists.open-mesh.org Date: Sat, Nov 27, 2010 at 12:58 AM Subject: Fwd: BATMAN routing To: hlabishik@gmail.com
Message rejected by filter rule match
---------- Forwarded message ---------- From: hlabishi kobo hlabishik@gmail.com To: b.a.t.m.a.n@lists.open-mesh.org Date: Sat, 27 Nov 2010 00:58:09 +0200 Subject: Fwd: BATMAN routing
---------- Forwarded message ---------- From: Marek Lindner lindner_marek@yahoo.de Date: Fri, Nov 26, 2010 at 5:23 PM Subject: Re: BATMAN routing To: hlabishi kobo hlabishik@gmail.com, Linus Lüssing < linus.luessing@web.de> Cc: siwu@hrz.tu-chemnitz.de
Hi,
welcome to the project! :-)
Firstly my apologies for sending this email to your personal email. My
name
is Hlabishi Isaac Kobo at the, an Msc computer science student at the University of the Western Cape in South Africa, I am doing a research on routing in a hybrid (combination of static and mobile dynamic routers) mesh.
I don't see a good reason to apologize, just wondering why you are not sending this mail to the public list ?
I want to use the mesh potatoes as well as the batphone (android version of batman) to create a mesh model.
What is the "batphone" ? A project name or a nick name you invented ? :-)
Note: Various tests have shown that running a mobile device (smartphone/tablet/etc) in adhoc mode plus running a mesh protocol on top is a battery killer, hence not practical in real world scenarios (in addition of the hassle to install and configure the mesh software on each and every device). This was one of the main reasons to start developing batman-adv as it allows mobile devices to take advantage of the mesh (e.g. roaming) without having to run the mesh on the device itself.
You might be aware of this - I am just mentioning it because many people are not.
First we say the recently received OGMs will give a clear indication on
the
reliability on the link, so we give the recently received OGMs from the sliding window a priority in deciding the best next hop link towards a destination. We want to count and add the indexes were an OGM was recorded in an interval (seconds), (hence the recently received OGM will have more weight). At the end the link with more recent OGMs will have more weight and hence become the current best link.
This is a good idea. We are in the process of redesigning the current protocol and welcome any input. Giving older OGMs less "weight" was also one of the ideas we had. Would you mind explaining your concept in greater detail ?
I went through the source code so many times and I got few questions about this:
Are we talking about the batman daemon source code or the batman-adv kernel module ? All my answers will refer to the kernel module as this is the place where most of the development is going on at the moment.
- What structure is used to keep track of the sliding window? If its
the has how does it get updated based on the sliding packet range?
Each "struct orig_node" has a bitarray to keep track of its own seqnos repeated by its neighbors (bcast_own) and each "struct neigh_node" having a bitarray for its own OGMs (real_bits).
- How are the OGM's recorded, is in a form of binary where 1 will
represent the received OGM and 0 otherwise?
Correct.
- I looked in the source and still not sure of where the ranking
decisions
are made, can you enlighten me on that?
You mean which function changes the route when a better neighbor was found ? That would be update_orig() in routing.c.
On the second approach we want to use mac layer stats to estimate the signal strength and probably the congestion rate of the top N ranked
links.
We acknowledge the fact that usually links with lower signal strength will loose more OGM's which results in an automatic low rank, however in a frequently changing topology, current signal strength is crucial. We plan to use SNR or RSSI in this case.
The concept is known since a while but nobody has implemented it so far because its implementation is fairly complex. Do you have an idea how it should work in the end ?
- How can i get the RSSI/LQI of th neighbor links?
I don't get this question. You intend to use RSSI but you don't know how ?
I would really appreciate your opinions and advices in this regard more specially how to go about implementing changes in BATMAN protocol.
This is a little abstract. Usually, we discuss specific concepts / ideas in our IRC channel or on the mailing list long before starting to implement them. The past has shown it is often better to let other people dive into your ideas and comment because routing is a rather complex subject.
As I mentioned above: We are in a redesign phase right now and welcome anyone interested to join. As the next step we envisioned a collection of routing scenarios in which the current implementation behaves poorly. All routing protocol changes have to go through this collection of scenarios to estimate its impact. What do you think about this idea ?
Regards, Marek
Hi,
The idea is to prioritize recently received OGM's thus giving them more weight for the routing decisions. This is because they give a precise indication of the status of current situation of the link. BATMAN algorithm currently counts the number of received OGM's in a current sliding window and the link with the most OGM's becomes the best next-hop towards a that destination. A lot can happen within a second in an ad hoc wireless network. if a lot of OGM's where recorded at the beginning of the window range and less towards the end which be that the link was better at the beginning not at the end of the sliding window (current). This could be selected as the best as opposed to the one that recorded a lot of OGM's towards the end but less in total. e.g. suppose you have sliding window of 10, link 1 records [1111100000]= 5 and link 2 [0000001111] = 4. link 1 will be chosen and as it stands the current best would have been link 2. The proposed concept prioritizes the recently received OGM's by giving them more weight. Thus we want to add the indexes of which an OGM was received in that interval. from the example above we would have link 1+2+3+4+5+6= 21 and link 2 7+8+9+10 = 34.
your idea makes perfect sense. As a next step we want to split the OGM packet into 2 distinct types to increase efficiency. We are heavily discussing your concept in our IRC channel. You should drop in if you have the time or attend the discussion next weekend.
Cheers, Marek
HI marek
Thank you for considering this concept, i am working on the implementation now. I would love to attend your IRC channel discussions, just tell date and time.
Kind Regards Hlabishi
On 11/30/10, hlabishi kobo hlabishik@gmail.com wrote:
Dear Marek and the BATMAN community. The idea is to prioritize recently received OGM's thus giving them more weight for the routing decisions. This is because they give a precise indication of the status of current situation of the link. BATMAN algorithm currently counts the number of received OGM's in a current sliding window and the link with the most OGM's becomes the best next-hop towards a that destination. A lot can happen within a second in an ad hoc wireless network. if a lot of OGM's where recorded at the beginning of the window range and less towards the end which be that the link was better at the beginning not at the end of the sliding window (current). This could be selected as the best as opposed to the one that recorded a lot of OGM's towards the end but less in total. e.g. suppose you have sliding window of 10, link 1 records [1111100000]= 5 and link 2 [0000001111] = 4. link 1 will be chosen and as it stands the current best would have been link 2. The proposed concept prioritizes the recently received OGM's by giving them more weight. Thus we want to add the indexes of which an OGM was received in that interval. from the example above we would have link 1+2+3+4+5+6= 21 and link 2 7+8+9+10 = 34.
Kind Regards Hlabishi
On 11/29/10, hlabishi kobo hlabishik@gmail.com wrote:
---------- Forwarded message ---------- From: hlabishi kobo hlabishik@gmail.com Date: Sun, 28 Nov 2010 22:06:01 +0200 Subject: Fwd: BATMAN routing To: lindner_marek@yahoo.de
Hi
Thank you very much for your reply. The reason why i sent this to you and your colleague is that i have tried the mail list before and all my post kept on being returned, i used this address b.a.t.m.a.n-owner@lists.open-mesh.org. I would really appreciate it if this can reach the mailing list public (i will keep on trying). i will send you a follow up on the full explanation of the concept like you requested.
Regards Hlabishi ---------- Forwarded message ---------- From: b.a.t.m.a.n-owner@lists.open-mesh.org Date: Sat, Nov 27, 2010 at 12:58 AM Subject: Fwd: BATMAN routing To: hlabishik@gmail.com
Message rejected by filter rule match
---------- Forwarded message ---------- From: hlabishi kobo hlabishik@gmail.com To: b.a.t.m.a.n@lists.open-mesh.org Date: Sat, 27 Nov 2010 00:58:09 +0200 Subject: Fwd: BATMAN routing
---------- Forwarded message ---------- From: Marek Lindner lindner_marek@yahoo.de Date: Fri, Nov 26, 2010 at 5:23 PM Subject: Re: BATMAN routing To: hlabishi kobo hlabishik@gmail.com, Linus Lüssing < linus.luessing@web.de> Cc: siwu@hrz.tu-chemnitz.de
Hi,
welcome to the project! :-)
Firstly my apologies for sending this email to your personal email. My
name
is Hlabishi Isaac Kobo at the, an Msc computer science student at the University of the Western Cape in South Africa, I am doing a research on routing in a hybrid (combination of static and mobile dynamic routers) mesh.
I don't see a good reason to apologize, just wondering why you are not sending this mail to the public list ?
I want to use the mesh potatoes as well as the batphone (android version of batman) to create a mesh model.
What is the "batphone" ? A project name or a nick name you invented ? :-)
Note: Various tests have shown that running a mobile device (smartphone/tablet/etc) in adhoc mode plus running a mesh protocol on top is a battery killer, hence not practical in real world scenarios (in addition of the hassle to install and configure the mesh software on each and every device). This was one of the main reasons to start developing batman-adv as it allows mobile devices to take advantage of the mesh (e.g. roaming) without having to run the mesh on the device itself.
You might be aware of this - I am just mentioning it because many people are not.
First we say the recently received OGMs will give a clear indication on
the
reliability on the link, so we give the recently received OGMs from the sliding window a priority in deciding the best next hop link towards a destination. We want to count and add the indexes were an OGM was recorded in an interval (seconds), (hence the recently received OGM will have more weight). At the end the link with more recent OGMs will have more weight and hence become the current best link.
This is a good idea. We are in the process of redesigning the current protocol and welcome any input. Giving older OGMs less "weight" was also one of the ideas we had. Would you mind explaining your concept in greater detail ?
I went through the source code so many times and I got few questions about this:
Are we talking about the batman daemon source code or the batman-adv kernel module ? All my answers will refer to the kernel module as this is the place where most of the development is going on at the moment.
- What structure is used to keep track of the sliding window? If its
the has how does it get updated based on the sliding packet range?
Each "struct orig_node" has a bitarray to keep track of its own seqnos repeated by its neighbors (bcast_own) and each "struct neigh_node" having a bitarray for its own OGMs (real_bits).
- How are the OGM's recorded, is in a form of binary where 1 will
represent the received OGM and 0 otherwise?
Correct.
- I looked in the source and still not sure of where the ranking
decisions
are made, can you enlighten me on that?
You mean which function changes the route when a better neighbor was found ? That would be update_orig() in routing.c.
On the second approach we want to use mac layer stats to estimate the signal strength and probably the congestion rate of the top N ranked
links.
We acknowledge the fact that usually links with lower signal strength will loose more OGM's which results in an automatic low rank, however in a frequently changing topology, current signal strength is crucial. We plan to use SNR or RSSI in this case.
The concept is known since a while but nobody has implemented it so far because its implementation is fairly complex. Do you have an idea how it should work in the end ?
- How can i get the RSSI/LQI of th neighbor links?
I don't get this question. You intend to use RSSI but you don't know how ?
I would really appreciate your opinions and advices in this regard more specially how to go about implementing changes in BATMAN protocol.
This is a little abstract. Usually, we discuss specific concepts / ideas in our IRC channel or on the mailing list long before starting to implement them. The past has shown it is often better to let other people dive into your ideas and comment because routing is a rather complex subject.
As I mentioned above: We are in a redesign phase right now and welcome anyone interested to join. As the next step we envisioned a collection of routing scenarios in which the current implementation behaves poorly. All routing protocol changes have to go through this collection of scenarios to estimate its impact. What do you think about this idea ?
Regards, Marek
On Wednesday 01 December 2010 10:46:10 hlabishi kobo wrote:
Thank you for considering this concept, i am working on the implementation now. I would love to attend your IRC channel discussions, just tell date and time.
The IRC meetings are less formal. Just join us when you have the time. People hang out there all the time.
Cheers, Marek
Hi everyone,
thanks for having joined the IRC channel, Hlabishi and Chris, that's really speeding the discussions up a lot, I guess :). Just wanted to throw in another idea open for discussions which is refering to Hlabisihi's packet count weighting.
What do you guys think about pushing this concept even one step further and removing the local packet count window? And instead using a "smoother" exponential weighted average which got very popular in TCP for it's RTT estimations:
RQ_new = f(newseqno, lastseqno, RQ_old, α) = (1-α) * RQ_old + α * 1 / Δ(newseqno, lastseqno)
As in TCP, α is then the parameter for tweaking on how much more priority a newer packet shall have and is chosen between 0 (conservative) and 1 (opportunistic).
What do you think?
Cheers, Linus
On Wed, Dec 01, 2010 at 01:30:18PM +0100, Marek Lindner wrote:
On Wednesday 01 December 2010 10:46:10 hlabishi kobo wrote:
Thank you for considering this concept, i am working on the implementation now. I would love to attend your IRC channel discussions, just tell date and time.
The IRC meetings are less formal. Just join us when you have the time. People hang out there all the time.
Cheers, Marek
Hi all*,
On gio, dic 02, 2010 at 11:27:52 +0100, Linus Lüssing wrote:
Hi everyone,
thanks for having joined the IRC channel, Hlabishi and Chris, that's really speeding the discussions up a lot, I guess :). Just wanted to throw in another idea open for discussions which is refering to Hlabisihi's packet count weighting.
What do you guys think about pushing this concept even one step further and removing the local packet count window? And instead using a "smoother" exponential weighted average which got very popular in TCP for it's RTT estimations:
RQ_new = f(newseqno, lastseqno, RQ_old, α) = (1-α) * RQ_old + α * 1 / Δ(newseqno, lastseqno)
As in TCP, α is then the parameter for tweaking on how much more priority a newer packet shall have and is chosen between 0 (conservative) and 1 (opportunistic).
What do you think?
IMHO this is not the best solution. Probably it could better than the actual strategy, but, as TCP demonstrates, this is not a really nice way of evaluating the RQ.
Imho, since we have more and more information than TCP for evaluating the new RQ, we could try to make a better choice considering "more values": instead of using only the deltaSEQ and the oldRQ, we could try to apply a function that can weight also the previous history of the link (of course with a limit). Something like
newRQ = f(window[0], ...., window[N-1]) in which, each OGM (received or not) can be weighted in a different way depending on its position.
I hope I've been clear.
furland is probably working on this aspect.
Bye!
Cheers, Linus
On Wed, Dec 01, 2010 at 01:30:18PM +0100, Marek Lindner wrote:
On Wednesday 01 December 2010 10:46:10 hlabishi kobo wrote:
Thank you for considering this concept, i am working on the implementation now. I would love to attend your IRC channel discussions, just tell date and time.
The IRC meetings are less formal. Just join us when you have the time. People hang out there all the time.
Cheers, Marek
Hi all,
I'm doing a research project on the topic discussed. I think the solutions proposed can improve the performance of the protocol, especially its reactivity in case of link failures. But in my opinion the main cause of performance deficiency is the route flap problem documented in some research paper. This is a common problem, especially in dense network. My work focus on finding out some strategy to reduce this problem maintaining at the same time a good reactivity in route decision. The first strategy I will try, is to introduce an hysteresis in route change and then I will study more sophisticated technique.
As soon as I have some written material I will send it to the mailing list hoping to receive some suggestion or critiques.
PS. I'm also working on a theoretical analysis on routing overhead in term of network utilization. Soon I will post some results.
Bye.
2010/12/2 Antonio Quartulli ordex@ritirata.org
Hi all*,
On gio, dic 02, 2010 at 11:27:52 +0100, Linus Lüssing wrote:
Hi everyone,
thanks for having joined the IRC channel, Hlabishi and Chris, that's really speeding the discussions up a lot, I guess :). Just wanted to throw in another idea open for discussions which is refering to Hlabisihi's packet count weighting.
What do you guys think about pushing this concept even one step further and removing the local packet count window? And instead using a "smoother" exponential weighted average which got very popular in TCP for it's RTT estimations:
RQ_new = f(newseqno, lastseqno, RQ_old, α) = (1-α) * RQ_old + α * 1 / Δ(newseqno, lastseqno)
As in TCP, α is then the parameter for tweaking on how much more priority a newer packet shall have and is chosen between 0 (conservative) and 1 (opportunistic).
What do you think?
IMHO this is not the best solution. Probably it could better than the actual strategy, but, as TCP demonstrates, this is not a really nice way of evaluating the RQ.
Imho, since we have more and more information than TCP for evaluating the new RQ, we could try to make a better choice considering "more values": instead of using only the deltaSEQ and the oldRQ, we could try to apply a function that can weight also the previous history of the link (of course with a limit). Something like
newRQ = f(window[0], ...., window[N-1]) in which, each OGM (received or not) can be weighted in a different way depending on its position.
I hope I've been clear.
furland is probably working on this aspect.
Bye!
Cheers, Linus
On Wed, Dec 01, 2010 at 01:30:18PM +0100, Marek Lindner wrote:
On Wednesday 01 December 2010 10:46:10 hlabishi kobo wrote:
Thank you for considering this concept, i am working on the implementation now. I would love to attend your IRC channel discussions, just tell date and time.
The IRC meetings are less formal. Just join us when you have the time. People hang out there all the time.
Cheers, Marek
-- Antonio Quartulli
Ognuno di noi, da solo, non vale nulla Ernesto "Che" Guevara
-- Daniele Furlan (furland)
Hi,
But in my opinion the main cause of performance deficiency is the route flap problem documented in some research paper. This is a common problem, especially in dense network.
would you mind explaining in a few words why you think rapid route changes are a performance problem or name the paper you are referring to ?
As soon as I have some written material I will send it to the mailing list hoping to receive some suggestion or critiques.
PS. I'm also working on a theoretical analysis on routing overhead in term of network utilization. Soon I will post some results.
Great! Looking forward to your results.
Cheers, Marek
Hi all,
2010/12/6 Marek Lindner lindner_marek@yahoo.de:
Hi,
But in my opinion the main cause of performance deficiency is the route flap problem documented in some research paper. This is a common problem, especially in dense network.
would you mind explaining in a few words why you think rapid route changes are a performance problem or name the paper you are referring to ?
The paper I refer is "Routing Stability in Static Wireless Mesh Networks" Krishna Ramachandran, Irfan Sheriff, Elizabeth Belding, Kevin Almeroth University of California, Santa Barbara
The rapid route change is an advantage in case of variable and unstable wireless link, but can become a problem in case of multiple available "good" links. In my opinion, in this case useless route change happens, maybe for a temporary throughput improvement, so it is important to protect current good route from route flapping.
As soon as I have some written material I will send it to the mailing list hoping to receive some suggestion or critiques.
PS. I'm also working on a theoretical analysis on routing overhead in term of network utilization. Soon I will post some results.
Great! Looking forward to your results.
Cheers, Marek
I hope I've been clear.
Bye!
-- Daniele Furlan
Hi Antonio,
thanks for the feedback on the exponential weighted average.
IMHO this is not the best solution. Probably it could better than the actual strategy, but, as TCP demonstrates, this is not a really nice way of evaluating the RQ.
Well, I guess TCP could have used a weighted window for doing its RTT estimations, too, couldn't it? Do you know if there has been a particular design decision to using an exponential weighted average instead of a weighted window here?
Imho, since we have more and more information than TCP for evaluating the new RQ, we could try to make a better choice considering "more values": instead of using only the deltaSEQ and the oldRQ, we could try to apply a function that can weight also the previous history of the link (of course with a limit). Something like
Hmm, I think with an exponential weighted average we are weighting the previous history as well, aren't we? And due to the exponential behaviour, history further in the past will be considered less - which sounds similar to the scheme proposed by Hlabishi with a wighted window, doesn't it? And by the way, an exponential weighted average should consid "more value" compared to the weighted window, shouldn't it? The window is limited in size and packets get kicked out again, while in an exponential weighted average, even a veeeery old packet still has an influence (though a veeeery little one then, too ;) ).
One thing that might be something not easily doable with an exponential weighted average is changing the weight of a single, previously received packet on demand (we cannot suddenly say that we now want to make the packet we received 3 seconds ago now 5 times more important). But I guess that's not needed with the current ideas so far, is it?
For changing the weight of a just received packet, doing special weighting could even be easier, as a different α could be applied for this single packet. For instance there were some discussions if we should send larger packets for packet loss probing from time to time and giving these a higher priority.
newRQ = f(window[0], ...., window[N-1]) in which, each OGM (received or not) can be weighted in a different way depending on its position.
Yes, I think that's what Hlabishi had in mind, too.
I actually started doing some googling and there seem there seem to be even more ways of how to weight a set of samples. Anyone with some more knowledge in the field of signal processing? Or economics / stock markets :D?
Hlabishi, I'd be curious if there was a certain design decision for using a weighted window in favour for other weigthing techniques and if you considered using other techniques, too. Or was the idea of using a weighted window due to the fact, that we are already having a window and that you did not want to temper too much with that?
Cheers, Linus
Hi Linus, First we considered using statistical methods but we found a lot of deficiencies and we opted for the weighting window as it simple and made a lot of sense and yes because there was a window already to work on. Hlabishi
On 12/1/10, hlabishi kobo hlabishik@gmail.com wrote:
HI marek
Thank you for considering this concept, i am working on the implementation now. I would love to attend your IRC channel discussions, just tell date and time.
Kind Regards Hlabishi
On 11/30/10, hlabishi kobo hlabishik@gmail.com wrote:
Dear Marek and the BATMAN community. The idea is to prioritize recently received OGM's thus giving them more weight for the routing decisions. This is because they give a precise indication of the status of current situation of the link. BATMAN algorithm currently counts the number of received OGM's in a current sliding window and the link with the most OGM's becomes the best next-hop towards a that destination. A lot can happen within a second in an ad hoc wireless network. if a lot of OGM's where recorded at the beginning of the window range and less towards the end which be that the link was better at the beginning not at the end of the sliding window (current). This could be selected as the best as opposed to the one that recorded a lot of OGM's towards the end but less in total. e.g. suppose you have sliding window of 10, link 1 records [1111100000]= 5 and link 2 [0000001111] = 4. link 1 will be chosen and as it stands the current best would have been link 2. The proposed concept prioritizes the recently received OGM's by giving them more weight. Thus we want to add the indexes of which an OGM was received in that interval. from the example above we would have link 1+2+3+4+5+6= 21 and link 2 7+8+9+10 = 34.
Kind Regards Hlabishi
On 11/29/10, hlabishi kobo hlabishik@gmail.com wrote:
---------- Forwarded message ---------- From: hlabishi kobo hlabishik@gmail.com Date: Sun, 28 Nov 2010 22:06:01 +0200 Subject: Fwd: BATMAN routing To: lindner_marek@yahoo.de
Hi
Thank you very much for your reply. The reason why i sent this to you and your colleague is that i have tried the mail list before and all my post kept on being returned, i used this address b.a.t.m.a.n-owner@lists.open-mesh.org. I would really appreciate it if this can reach the mailing list public (i will keep on trying). i will send you a follow up on the full explanation of the concept like you requested.
Regards Hlabishi ---------- Forwarded message ---------- From: b.a.t.m.a.n-owner@lists.open-mesh.org Date: Sat, Nov 27, 2010 at 12:58 AM Subject: Fwd: BATMAN routing To: hlabishik@gmail.com
Message rejected by filter rule match
---------- Forwarded message ---------- From: hlabishi kobo hlabishik@gmail.com To: b.a.t.m.a.n@lists.open-mesh.org Date: Sat, 27 Nov 2010 00:58:09 +0200 Subject: Fwd: BATMAN routing
---------- Forwarded message ---------- From: Marek Lindner lindner_marek@yahoo.de Date: Fri, Nov 26, 2010 at 5:23 PM Subject: Re: BATMAN routing To: hlabishi kobo hlabishik@gmail.com, Linus Lüssing < linus.luessing@web.de> Cc: siwu@hrz.tu-chemnitz.de
Hi,
welcome to the project! :-)
Firstly my apologies for sending this email to your personal email. My
name
is Hlabishi Isaac Kobo at the, an Msc computer science student at the University of the Western Cape in South Africa, I am doing a research on routing in a hybrid (combination of static and mobile dynamic routers) mesh.
I don't see a good reason to apologize, just wondering why you are not sending this mail to the public list ?
I want to use the mesh potatoes as well as the batphone (android version of batman) to create a mesh model.
What is the "batphone" ? A project name or a nick name you invented ? :-)
Note: Various tests have shown that running a mobile device (smartphone/tablet/etc) in adhoc mode plus running a mesh protocol on top is a battery killer, hence not practical in real world scenarios (in addition of the hassle to install and configure the mesh software on each and every device). This was one of the main reasons to start developing batman-adv as it allows mobile devices to take advantage of the mesh (e.g. roaming) without having to run the mesh on the device itself.
You might be aware of this - I am just mentioning it because many people are not.
First we say the recently received OGMs will give a clear indication on
the
reliability on the link, so we give the recently received OGMs from the sliding window a priority in deciding the best next hop link towards a destination. We want to count and add the indexes were an OGM was recorded in an interval (seconds), (hence the recently received OGM will have more weight). At the end the link with more recent OGMs will have more weight and hence become the current best link.
This is a good idea. We are in the process of redesigning the current protocol and welcome any input. Giving older OGMs less "weight" was also one of the ideas we had. Would you mind explaining your concept in greater detail ?
I went through the source code so many times and I got few questions about this:
Are we talking about the batman daemon source code or the batman-adv kernel module ? All my answers will refer to the kernel module as this is the place where most of the development is going on at the moment.
- What structure is used to keep track of the sliding window? If its
the has how does it get updated based on the sliding packet range?
Each "struct orig_node" has a bitarray to keep track of its own seqnos repeated by its neighbors (bcast_own) and each "struct neigh_node" having a bitarray for its own OGMs (real_bits).
- How are the OGM's recorded, is in a form of binary where 1 will
represent the received OGM and 0 otherwise?
Correct.
- I looked in the source and still not sure of where the ranking
decisions
are made, can you enlighten me on that?
You mean which function changes the route when a better neighbor was found ? That would be update_orig() in routing.c.
On the second approach we want to use mac layer stats to estimate the signal strength and probably the congestion rate of the top N ranked
links.
We acknowledge the fact that usually links with lower signal strength will loose more OGM's which results in an automatic low rank, however in a frequently changing topology, current signal strength is crucial. We plan to use SNR or RSSI in this case.
The concept is known since a while but nobody has implemented it so far because its implementation is fairly complex. Do you have an idea how it should work in the end ?
- How can i get the RSSI/LQI of th neighbor links?
I don't get this question. You intend to use RSSI but you don't know how ?
I would really appreciate your opinions and advices in this regard more specially how to go about implementing changes in BATMAN protocol.
This is a little abstract. Usually, we discuss specific concepts / ideas in our IRC channel or on the mailing list long before starting to implement them. The past has shown it is often better to let other people dive into your ideas and comment because routing is a rather complex subject.
As I mentioned above: We are in a redesign phase right now and welcome anyone interested to join. As the next step we envisioned a collection of routing scenarios in which the current implementation behaves poorly. All routing protocol changes have to go through this collection of scenarios to estimate its impact. What do you think about this idea ?
Regards, Marek
Hi everyone,
just wanted to share a website I found, which is actually for stock markets and their charts, but I think the Moving Average of a data set, that's what we'd have in common. And I guess what the economists have discovered and thought being useful could be useful for us, too. There are some nice and easy to understand articles here that explain the pros and cons:
http://www.investopedia.com/university/
Dictionary: - Simple Moving Average: http://www.investopedia.com/terms/s/sma.asp (what we have now) - Weighted Moving Average: http://www.investopedia.com/terms/l/linearlyweightedmovingaverage.asp (Hlabishi's proposal) - Exponential Moving Average: http://www.investopedia.com/terms/e/ema.asp - Double Exponential Moving Average: http://www.investopedia.com/terms/d/double-exponential-moving-average.asp
Articles: - Weighted Moving Average: http://www.investopedia.com/articles/technical/060401.asp - Simple vs. Exponential Moving Average: http://www.investopedia.com/articles/trading/10/simple-exponential-moving-av... - Double Exponential Moving Averages Explained: http://www.investopedia.com/articles/trading/10/double-exponential-moving-av... - Moving Averages: http://www.investopedia.com/university/movingaverage/default.asp
Cheers, Linus
HI everyone
Its been a while, I have been trying to test the weighted algorithm (debugging and changing). I made changes on the method bit_packet_count or rather replaced it with a method weighted_bit_packet_count on which i try to count the number of received OGMs received in a sliding window and giving them weights. However when i test, i cant seem to ping other nodes to verify connectivity (i first try on only two nodes). I have trying this and i do not know i might have went wrong. see the code below.
int weighted_bit_packet_count(TYPE_OF_WORD *seq_bits) { int i, count = 0; TYPE_OF_WORD word;
for (i = 0; i < NUM_WORDS; i++) { //word = seq_bits[i]; if (seq_bits[i] == 1) count += i; } return count;
}
Kind Regards Hlabishi
On 12/20/10, Linus Lüssing linus.luessing@web.de wrote:
Hi everyone,
just wanted to share a website I found, which is actually for stock markets and their charts, but I think the Moving Average of a data set, that's what we'd have in common. And I guess what the economists have discovered and thought being useful could be useful for us, too. There are some nice and easy to understand articles here that explain the pros and cons:
http://www.investopedia.com/university/
Dictionary:
- Simple Moving Average: http://www.investopedia.com/terms/s/sma.asp (what we have now)
- Weighted Moving Average: http://www.investopedia.com/terms/l/linearlyweightedmovingaverage.asp (Hlabishi's proposal)
- Exponential Moving Average: http://www.investopedia.com/terms/e/ema.asp
- Double Exponential Moving Average: http://www.investopedia.com/terms/d/double-exponential-moving-average.asp
Articles:
- Weighted Moving Average: http://www.investopedia.com/articles/technical/060401.asp
- Simple vs. Exponential Moving Average:
http://www.investopedia.com/articles/trading/10/simple-exponential-moving-av...
- Double Exponential Moving Averages Explained:
http://www.investopedia.com/articles/trading/10/double-exponential-moving-av...
- Moving Averages: http://www.investopedia.com/university/movingaverage/default.asp
Cheers, Linus
Disclaimer: I will not comment on the whole subject. All my comments are only based on following code.
On Thursday 24 February 2011 10:58:02 hlabishi kobo wrote:
int weighted_bit_packet_count(TYPE_OF_WORD *seq_bits) { int i, count = 0; TYPE_OF_WORD word;
for (i = 0; i < NUM_WORDS; i++) { //word = seq_bits[i]; if (seq_bits[i] == 1) count += i; } return count;}
You only gave us the following code and no other information. I must assume that other parts of the code weren't modified. The part of the code seems to be derived from following function:
int bit_packet_count(unsigned long *seq_bits) { int i, hamming = 0;
for (i = 0; i < NUM_WORDS; i++) hamming += hweight_long(seq_bits[i]);
return hamming; }
It is easy to notice that the original function is aware that many bits inside a word (unsigned long) are set either to zero or to one. The sum of all bits inside all words (sum of the hamming weights) is complete set of information the routing algorithm needs to make any decision.
Your function is also operating on the same data, but only tests if the last bit in every word is 1. Lets assume that a unsigned long is 64 bit long and we have 8 of them. That means that we are only allowed to have received every 8th ogm and that we are currently shifted these bits to the lsb position of each word. Something tells me that I should not start to calculate the probability of such an event.
I would suggest that you check your originator and global/local translation tables.
Best regards, Sven
Thanks for the reply, what does hweight_long does? i tried to search it but i cant find a clear description of it. My intention is to count and add the indexes where an OGM was recorded (where there is a '1' ).
Small clarification at the beginning. In my example I said "received every 8th ogm". Of course this should have been every 64th ogm. I wanted to write a more detailed example using the 8 bytes but thrown that idea away quite early. In the current setup you will have 64 bits in either a single unsigned long or 64 bits in 2 32-bit unsigned longs. This depends on the target architecture.
Please keep in mind that this can easily increased to 256 or more bits for the TQ_LOCAL_WINDOW_SIZE
hlabishi kobo wrote:
Thanks for the reply, what does hweight_long does? i tried to search it but i cant find a clear description of it. My intention is to count and add the indexes where an OGM was recorded (where there is a '1' ).
hweight_long == Hamming weight for an unsigned long (sum of bits != 0) [1]
So what you want is to program it using bit shifts, ands and test operations. This means that you will calculate for the maximum (all ogms received) using your current strategy 2016 ([n+(n-1)]/2; n == number of bits). This of course is generated by looking at the bits and not at the bytes like your current implementation. The sum is even because you omit the last received ogm (in your version it has an index of 0). And it is even a bigger problem that you would give the ogms which are more recent a smaller weight than the ogms which are received in the past.
I hope that these are enough hints for you.
So lets assume that you implemented a correct weighted version of bit_packet_count. The weights are distributed over 64 slots (the bits) were 1 is the weight for the oldest slot and 64 is the weight for the slot of newest ogm. The weights are distributed in a linear fashion (second newest has weight 63, ...).
What would be the weighted sum (64 bit implementation) for {0xCEED2866E2DEE707} and what would be the weighted sum (32 bit implementation) of {3806258951, 3471648870}? Write a program which calculates those sums. Proof that this can or cannot be implemented in less operations per long using clever bit operations which evaluate more than one bit per round.
Best regards, Sven
All,
I figured I would throw out some stuff that I/we have been working on as possibly some ideas that may help improve the routing algorithm, some of these ideas are off subject of the current thread, and I apologize for that, but all of the ideas are about the routing algorithm.
All of these implementations apply to batman advanced (layer 2, kernel module).
First a little history, here at "Gateworks" I/we have been tasked with implementing a MANET that is very mobile and has a host of different types of configurations all under an "Open Source" license. We have picked BATMAN as our base for implementation. One of the configurations has 16 so called "tower" nodes that have a board with 4 radio's in it, using 2 radio's as backhaul's and 2 radios connected to sectors to distribute to so called "mobile" nodes. These mobile(32) nodes will have either 1 or 2 radio's in them and will be either mounted on vehicles or men. The other side of things is that we had to have this mesh network work with any kind of network traffic including multicast (typically video/audio traffic).
We have done a tremendous amount of testing in this type of configuration with both unicast and multicast traffic and have made some modifications that improve the scenario we are working with and the work we have implemented is as follows, any comments, ideas, criticism, etc are welcome:
- Implement RSSI into the routing decisions This is accomplished by adding an rssi_penalty into each of the orig_nodes that an OGM is received from, along with adding an rssi field into the OGM. We grab the rssi value from the wireless interface (currently through an ugly module dependency between madwifi and batman, but could be done through wireless extensions) on a regular interval for each mac address that the wireless device sees and and store this rssi value in the orig table. We store this as a value between 0 and 40 with 0 being the highest quality and not adding any penalty to the OGM. Thus the value stored in the orig table is really 40 - rssi. Then when a OGM is sent out, it contains on rssi value of 0, when it is received by a node, the rssi_penalty is read from the orig table for the node that sent the OGM if it is greater then the rssi value stored in the batman packet, it overwrites the value with the new rssi_penalty. Thus, on a multiple hop link, the batman packet contains the rssi_penalty of the weakest link. This value is then applied to the tq similar to how the hop_penalty is applied when processing the OGM.
- Don't send multicast packets as broadcast packets In the current implementation of BATMAN, multicast packets are sent as broadcast packets and broadcast packets are sent 3 times. There are inherent issues with this when sending a large amount of multicast traffic. The other issue that came into play is that wireless devices send broadcast/multicast traffic at 1MB by default, which can be overcome by setting the multicast rate to a higher value, but is not an acceptable solution in a mobile environment because the best rate is not known and cannot be fixed. Now, just as an example, if we consider a 4 node mesh network where each node can route to each other and the nodes occupy the same general RF space, then if a single multicast packet is transmitted, it will really be sent 12 times (3 times by each node) which will quickly create to much interference when using a large amount of multicast. The idea was then to transmit the multicast as unicast packets but to only transmit them done any given route one time. In the example case I gave, this would reduce the total number of transmissions of the packet to 3. This will also allow the packet to be transmitted at a higher wireless rate due to it being unicast, and also helps to ensure that the delivery of the packet is successful (not 100% obviously as only link layer acks are being used and no network layer acks). In order to determine where the packets should be sent, a new table is created both for the batman interface (for new packets) and in each entry in the orig table (for forwarded packets). A mcast_discovery packet is then sent to each node on the given route to describe to whom they should then forward the multicast traffic. Then a multicast packet is sent along this same route. The route is updated periodically through the mcast_discovery packets. Also, the mcast_discovery packets are not sent out unless there is actual multicast traffic. The multicast still uses seqno's and TTL in order to reduce duplicates. I won't go into further detail unless requested to do so as it will just make this too long. Further work is in process to also add IGMP snooping to only forward packets to nodes that have joined the multicast group.
- Don't send out HNA's in OGM's, instead use multicast trasmission above In order to reduce the size of OGM's, we have utilized the multicast transmission described above to send out HNA's. This allow the broadcasted OGM packets to be very small and use less RF space.
- Prod the routing algorithm to change routes when RSSI is dropping We have added a starvation flag to the OGM's and we send out an OGM when the RSSI of a link begins to be reduced with this starvation flag set. When the OGM is received it is weighed heavier in order to encourage the routing algorithm to make a different decision on how to route packets.
I apologize for the length of this email, but am trying to give a clear picture of the implementations without going into too much detail.
We have all of the above working in a real world environment with a lot of testing being completed, and with a lot more testing going to be done in the coming weeks ( a lot more!!! ). I have patches (against r1828) for all of the above but none in the quality that they need to be for inclusion, and also I rely on some very ugly module dependencies that are un-acceptable along with some modifications to the madwifi driver (that are not neccessary for the above, but in the current code are being used). But if there is interest in the work that we have done above, I will begin to cleanup the code into a usable state.
Thanks for your time,
b.a.t.m.a.n@lists.open-mesh.org
-
Antonio Quartulli -
Chris Lang -
Daniele Furlan -
hlabishi kobo -
Linus Lüssing -
Linus Lüssing -
Marek Lindner -
Sven Eckelmann