[B.A.T.M.A.N.] Fwd: BATMAN routing

[B.A.T.M.A.N.] Fwd: BATMAN routing

[hlabishi kobo]

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


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


> 2. How are the OGM's recorded, is in a form of binary where 1 will
> represent the received OGM and 0 otherwise?

Correct.


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


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

Re: [B.A.T.M.A.N.] Fwd: BATMAN routing

[Linus Lüssing]

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

Re: [B.A.T.M.A.N.] Fwd: BATMAN routing

[Linus Lüssing]

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

Re: [B.A.T.M.A.N.] BATMAN routing

[hlabishi kobo]

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.
>
>
>> 1. 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).
>
>
>> 2. How are the OGM's recorded, is in a form of binary where 1 will
>> represent the received OGM and 0 otherwise?
>
> Correct.
>
>
>> 3. 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 ?
>
>
>> 1. 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
>

Re: [B.A.T.M.A.N.] BATMAN routing

[Marek Lindner]

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

Re: [B.A.T.M.A.N.] BATMAN routing

[hlabishi kobo]

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.
>>
>>
>>> 1. 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).
>>
>>
>>> 2. How are the OGM's recorded, is in a form of binary where 1 will
>>> represent the received OGM and 0 otherwise?
>>
>> Correct.
>>
>>
>>> 3. 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 ?
>>
>>
>>> 1. 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
>>
>

Re: [B.A.T.M.A.N.] BATMAN routing

[Marek Lindner]

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

Re: [B.A.T.M.A.N.] BATMAN routing

[Linus Lüssing]

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
> 

Re: [B.A.T.M.A.N.] BATMAN routing

[Antonio Quartulli]

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

Re: [B.A.T.M.A.N.] BATMAN routing

[Daniele Furlan]

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)

Re: [B.A.T.M.A.N.] BATMAN routing

[Marek Lindner]

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

Re: [B.A.T.M.A.N.] BATMAN routing

[Daniele Furlan]

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

Re: [B.A.T.M.A.N.] BATMAN routing

[Linus Lüssing]

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

Re: [B.A.T.M.A.N.] BATMAN routing

[hlabishi kobo]

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.
>>>
>>>
>>>> 1. 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).
>>>
>>>
>>>> 2. How are the OGM's recorded, is in a form of binary where 1 will
>>>> represent the received OGM and 0 otherwise?
>>>
>>> Correct.
>>>
>>>
>>>> 3. 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 ?
>>>
>>>
>>>> 1. 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
>>>
>>
>

Re: [B.A.T.M.A.N.] BATMAN routing

[Linus Lüssing]

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-averages-compare.asp
- Double Exponential Moving Averages Explained:
  http://www.investopedia.com/articles/trading/10/double-exponential-moving-average.asp
- Moving Averages:
  http://www.investopedia.com/university/movingaverage/default.asp

Cheers, Linus

Re: [B.A.T.M.A.N.] BATMAN routing

[hlabishi kobo]

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-averages-compare.asp
> - Double Exponential Moving Averages Explained:
>
> http://www.investopedia.com/articles/trading/10/double-exponential-moving-average.asp
> - Moving Averages:
>   http://www.investopedia.com/university/movingaverage/default.asp
>
> Cheers, Linus
>

Re: [B.A.T.M.A.N.] BATMAN routing

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 2726 bytes --]

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

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] BATMAN routing

[hlabishi kobo]

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


-- 
Kind Regards
Hlabishi I. Kobo, Mr
B S.c Computer Science (Msc)
University of the Western Cape
Bellville, Cape Town, South Africa
http://www.cs.uwc.ac.za/~hkobo <http://www.cs.uwc.ac.za/%7Emmotlhabi/>
+27 72 840 7719
+27 21 959 2461

Re: [B.A.T.M.A.N.] BATMAN routing

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 2170 bytes --]

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

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] BATMAN routing

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 1126 bytes --]

On Monday 28 February 2011 20:15:05 hlabishi kobo wrote:
> Thanks again for your reply sven, but i think my code might have maybe
> you a different view of wht i want to do, see below.
> The idea is to prioritize recently received OGM's thus giving them
> more weight for the routing decisions. suppose you have sliding window
> of 10, a link A records  [1111100000]= 5 and link B records
> [0000001111] = 4, currently this will be used towards the calculation
> of local TQ. in the proposed method we want to add the indexes on
> which an OGM was received in that interval. from the example above we
> would have link A 1+2+3+4+5+6= 21 and link B 7+8+9+10 = 34. this
> actually what i meant by counting and adding indexes.

I know what you want, but it seems (judging from your "implementation") that 
you don't know how to write that down. I hope that I gave you enough 
information to show you why your implementation isn't what you want.

The last part should help you to implement it the right way and to understand 
what the values represent and how you should operate on them.

Best regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] BATMAN routing

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 2231 bytes --]

On Monday 07 March 2011 22:00:25 hlabishi kobo wrote:
> Linus suggested to me that i should print the window and see how it
> looks, I did that and it returns this ef0fffffe, ffbffff, f70fffff,
> eb1b53c0, eb3950b8, eb1749c0. I am not sure if this are hexadecimal
> number or what.

I would think that you wrote the part which prints out this values. This means 
that you know which parameters you gave printk and that you should know the 
conversation specifiers and length modifiers that you used in the format 
string.

But I would guess without having any of these information that you used %x to 
print these values. Whatever you used as argument - 32 bit (size of single 
int) of it were printed in unsigned in hexidecimal notation. Maybe you should 
think about using %lx to print unsigned long ints in hexidecimal notation in 
case you really used %x.

Which brings me to another question: Why to I see 6 numbers in your post and 
why has the first one 9 nibbles?

As said before (and also recommended by Linus): try to write a small c program 
which uses these values, print the single bits, try to write some test 
algorithm using these decoded bits and play a little bit around with other 
test inputs before trying random things inside the kernel.

> Again this is the results of printing seq_bits, so far
> i have not been able to print real_bits as this cannot even make a
> network ping. Could you enlighten me in this case.

I cannot understand how pings and printks are related...


May I ask how these things are related to your work/studies? It is ok to play 
around a little bit as small side project/hobby without having the time and 
knowledge to understand what you are really doing. That is usually a good way 
to find new interesting topics and maybe to learn something (or blow up a 
building...). But I would highly recommend to switch the topic in case this is 
part of your thesis or work.

It is not meant as harsh criticism of what you try to do, but it seems that 
right now you aren't able to efficiently work with it and to gain enough 
knowledge by yourself to be able to understand simple parts the thing you are 
working with.

Best regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] BATMAN routing

[hlabishi kobo]

Hi thank you very much for your suggestions Sven, they were really
helpful. i actually now put the below code down which i am still busy
trying to test it.

int weighted_bit_packet_count(TYPE_OF_WORD *seq_bits)
{
	int i,check, count = 0;
	int j;
	//TYPE_OF_WORD *word;
	int word;

	for (i = 0; i < NUM_WORDS; i++) {
		word = seq_bits[i];
		
		for (j = 0; j < 32; j++){			
        		check = (word & (1 << j)) >> j;
       		 	if (check == 1)
         		   count += j;
		}
	printk("our count is %d\n", count);
	return count;				
	}
	//printk("our count is %d\n", count);
	//return count;
}
When i am using it on two PC's my ping seems to be recording much
delay. I will appreciate your feedback in this regard.
Thank you and kind Regards
Hlabishi

On 3/8/11, Sven Eckelmann <sven@narfation.org> wrote:
> On Monday 07 March 2011 22:00:25 hlabishi kobo wrote:
>> Linus suggested to me that i should print the window and see how it
>> looks, I did that and it returns this ef0fffffe, ffbffff, f70fffff,
>> eb1b53c0, eb3950b8, eb1749c0. I am not sure if this are hexadecimal
>> number or what.
>
> I would think that you wrote the part which prints out this values. This
> means
> that you know which parameters you gave printk and that you should know the
> conversation specifiers and length modifiers that you used in the format
> string.
>
> But I would guess without having any of these information that you used %x
> to
> print these values. Whatever you used as argument - 32 bit (size of single
> int) of it were printed in unsigned in hexidecimal notation. Maybe you
> should
> think about using %lx to print unsigned long ints in hexidecimal notation in
> case you really used %x.
>
> Which brings me to another question: Why to I see 6 numbers in your post and
> why has the first one 9 nibbles?
>
> As said before (and also recommended by Linus): try to write a small c
> program
> which uses these values, print the single bits, try to write some test
> algorithm using these decoded bits and play a little bit around with other
> test inputs before trying random things inside the kernel.
>
>> Again this is the results of printing seq_bits, so far
>> i have not been able to print real_bits as this cannot even make a
>> network ping. Could you enlighten me in this case.
>
> I cannot understand how pings and printks are related...
>
>
> May I ask how these things are related to your work/studies? It is ok to
> play
> around a little bit as small side project/hobby without having the time and
> knowledge to understand what you are really doing. That is usually a good
> way
> to find new interesting topics and maybe to learn something (or blow up a
> building...). But I would highly recommend to switch the topic in case this
> is
> part of your thesis or work.
>
> It is not meant as harsh criticism of what you try to do, but it seems that
> right now you aren't able to efficiently work with it and to gain enough
> knowledge by yourself to be able to understand simple parts the thing you
> are
> working with.
>
> Best regards,
> 	Sven
>


-- 
Kind Regards
Hlabishi I. Kobo, Mr
B S.c Computer Science (Msc)
University of the Western Cape
Bellville, Cape Town, South Africa
+27 72 840 7719
+27 21 959 2461

Re: [B.A.T.M.A.N.] BATMAN routing

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 1455 bytes --]

On Thursday 17 March 2011 23:40:06 hlabishi kobo wrote:
> Hi thank you very much for your suggestions Sven, they were really
> helpful. i actually now put the below code down which i am still busy
> trying to test it.
> 
> int weighted_bit_packet_count(TYPE_OF_WORD *seq_bits)
> {
> 	int i,check, count = 0;
> 	int j;
> 	//TYPE_OF_WORD *word;
> 	int word;
> 
> 	for (i = 0; i < NUM_WORDS; i++) {
> 		word = seq_bits[i];
> 
> 		for (j = 0; j < 32; j++){
>         		check = (word & (1 << j)) >> j;
>        		 	if (check == 1)
>          		   count += j;
> 		}
> 	printk("our count is %d\n", count);
> 	return count;
> 	}
> 	//printk("our count is %d\n", count);
> 	//return count;
> }
> When i am using it on two PC's my ping seems to be recording much
> delay. I will appreciate your feedback in this regard.
> Thank you and kind Regards

Ehrm, you know that you ignore the fact that seq_bits[i] may be 64 bits? And 
you only calculate the weighted sum of a single "word" (which you static 
casted to int....?) and not all words. And the sum is still wrong weighted 
(you still give zero weight for the newest one and increase the weight for the 
older). And the way you check the bits is even for a sequential implementation 
overly complex. And it is normal that printk heavily increase the amount of 
time... maybe you meant that by delay.

Sry, I have really no idea what I should say to it.

Regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] BATMAN routing

[hlabishi kobo]

On 3/18/11, Sven Eckelmann <sven@narfation.org> wrote:
> On Thursday 17 March 2011 23:40:06 hlabishi kobo wrote:
>> Hi thank you very much for your suggestions Sven, they were really
>> helpful. i actually now put the below code down which i am still busy
>> trying to test it.
>>
>> int weighted_bit_packet_count(TYPE_OF_WORD *seq_bits)
>> {
>> 	int i,check, count = 0;
>> 	int j;
>> 	//TYPE_OF_WORD *word;
>> 	int word;
>>
>> 	for (i = 0; i < NUM_WORDS; i++) {
>> 		word = seq_bits[i];
>>
>> 		for (j = 0; j < 32; j++){
>>         		check = (word & (1 << j)) >> j;
>>        		 	if (check == 1)
>>          		   count += j;
>> 		}
>> 	printk("our count is %d\n", count);
>> 	return count;
>> 	}
>> 	//printk("our count is %d\n", count);
>> 	//return count;
>> }
>> When i am using it on two PC's my ping seems to be recording much
>> delay. I will appreciate your feedback in this regard.
>> Thank you and kind Regards
>

Thank you very much Sven. Your feedback have been really helpful.

> Ehrm, you know that you ignore the fact that seq_bits[i] may be 64 bits?
I actually printed the seq_bits[i] and that is basically why i used 32
but that was just for debugging purpose. But actually if i use
NUM_WORDS, my weighted sum become very small whereas if i use 32 it
becomes very big, trying to understand what might be causing it to be
that way.
And
> you only calculate the weighted sum of a single "word" (which you static
> casted to int....?) and not all words.
i actually dont understand this very well, how many words does seq_bits[i] have?
 And the sum is still wrong weighted
> (you still give zero weight for the newest one and increase the weight for the older).
Thanks for letting alerting me about this, i hv now changed from
ascending to descending order.
 And the way you check the bits is even for a sequential
> implementation
> overly complex. And it is normal that printk heavily increase the amount of
> time... maybe you meant that by delay.
even if i comment out the printk() statement its still carries with the delay.
> Sry, I have really no idea what I should say to it.
>
> Regards,
> 	Sven
>

Kind Regards
Hlabishi

Re: [B.A.T.M.A.N.] BATMAN routing

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 980 bytes --]

On Monday 21 March 2011 23:40:57 hlabishi kobo wrote:
[...]
> I actually printed the seq_bits[i] and that is basically why i used 32
> but that was just for debugging purpose. But actually if i use
> NUM_WORDS, my weighted sum become very small whereas if i use 32 it
> becomes very big, trying to understand what might be causing it to be
> that way.

NUM_WORDS == amount of unsigned long/words
WORD_BIT_SIZE == amount of bits in a unsigned long
TQ_LOCAL_WINDOW_SIZE == sum of bits in seq_bits

Nothing really fancy here.

> > you only calculate the weighted sum of a single "word" (which you static
> > casted to int....?) and not all words.
> 
> i actually dont understand this very well, how many words does seq_bits[i]
> have?

a single "word"/unsigned long. seq_bits consist of NUM_WORDS words (words are 
defined in context of seq_bits as unsigned long - that's why we removed 
TYPE_OF_WORD completely and just use unsigned long).

Regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] BATMAN routing

[hlabishi kobo]

Thank you very much Sven, your feedback was very helpful. i ended up
with the code below which i am still testing.

int weighted_bit_packet_count(TYPE_OF_WORD *seq_bits)
{
	int i,check, count = 0;
	TYPE_OF_WORD word;

	for (i = 0; i < NUM_WORDS; i++) {
		word = seq_bits[i];
		int j = WORD_BIT_SIZE, k = 1;			

		while (j > 0 && k <= 32){			
        		check = (word & (1 << j)) >> j;		
       		 	if (check == 1)
         		   count += k;
		j--;
		k++;
		}					
	}
	return count;
}

Kind Regards
Hlabishi

On 3/22/11, Sven Eckelmann <sven@narfation.org> wrote:
> On Monday 21 March 2011 23:40:57 hlabishi kobo wrote:
> [...]
>> I actually printed the seq_bits[i] and that is basically why i used 32
>> but that was just for debugging purpose. But actually if i use
>> NUM_WORDS, my weighted sum become very small whereas if i use 32 it
>> becomes very big, trying to understand what might be causing it to be
>> that way.
>
> NUM_WORDS == amount of unsigned long/words
> WORD_BIT_SIZE == amount of bits in a unsigned long
> TQ_LOCAL_WINDOW_SIZE == sum of bits in seq_bits
>
> Nothing really fancy here.
>
>> > you only calculate the weighted sum of a single "word" (which you static
>> > casted to int....?) and not all words.
>>
>> i actually dont understand this very well, how many words does seq_bits[i]
>> have?
>
> a single "word"/unsigned long. seq_bits consist of NUM_WORDS words (words
> are
> defined in context of seq_bits as unsigned long - that's why we removed
> TYPE_OF_WORD completely and just use unsigned long).
>
> Regards,
> 	Sven
>


-- 
Kind Regards
Hlabishi I. Kobo, Mr
B S.c Computer Science (Msc)
University of the Western Cape
Bellville, Cape Town, South Africa
+27 72 840 7719
+27 21 959 2461

Re: [B.A.T.M.A.N.] BATMAN routing

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 1124 bytes --]

hlabishi kobo wrote:
> int weighted_bit_packet_count(TYPE_OF_WORD *seq_bits)
> {
> 	int i,check, count = 0;
> 	TYPE_OF_WORD word;
> 
> 	for (i = 0; i < NUM_WORDS; i++) {
> 		word = seq_bits[i];
> 		int j = WORD_BIT_SIZE, k = 1;
> 
> 		while (j > 0 && k <= 32){

it is wrong to assume that unsigned long is 32 bit long.

>         		check = (word & (1 << j)) >> j;
>        		 	if (check == 1)
>          		   count += k;
> 		j--;
> 		k++;

I would doubt that it is correct to give every set bit the same weight when 
they have the the distance of sizeof(unsigned long)*8. And I cannot find a 
good reason why an "old" unsigned long should get the same weights as the 
"newest" unsigned long - at least not when the actual weights should be 
reduced for "older" bits in a single unsigned long and the overall weights 
should be monotonic decreasing with the age. And using WORD_BIT_SIZE for j is 
like assuming that we only have a single unsigned long in seq_bits... which is 
not true for many architectures.

And the code is overly complicated without any good reason.

Kind regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] BATMAN routing

[hlabishi kobo]

On 4/3/11, Sven Eckelmann <sven@narfation.org> wrote:
> hlabishi kobo wrote:
>> int weighted_bit_packet_count(TYPE_OF_WORD *seq_bits)
>> {
>> 	int i,check, count = 0;
>> 	TYPE_OF_WORD word;
>>
>> 	for (i = 0; i < NUM_WORDS; i++) {
>> 		word = seq_bits[i];
>> 		int j = WORD_BIT_SIZE, k = 1;
>>
>> 		while (j > 0 && k <= 32){
>
> it is wrong to assume that unsigned long is 32 bit long.

> I would doubt that it is correct to give every set bit the same weight when
> they have the the distance of sizeof(unsigned long)*8. And I cannot find a
> good reason why an "old" unsigned long should get the same weights as the
> "newest" unsigned long - at least not when the actual weights should be
> reduced for "older" bits in a single unsigned long and the overall weights
> should be monotonic decreasing with the age.
I am looking at how i can deal with this part.
 And using WORD_BIT_SIZE for j
> is
> like assuming that we only have a single unsigned long in seq_bits... which
> is
> not true for many architectures.
During the debugging i realized that this can handle more than 1
unsigned long in seq_bits, i just need to prioritize the newer ones to
the old.
> And the code is overly complicated without any good reason.
I also thought so but so that it was the simplest i could come with,
still drawing up some other ways hopefully i will improve it with
time.
> Kind regards,
> 	Sven
>

I have been doing some tests using iperf/jperf to simulate traffic
between host. The results show lot of packet loss (though
inconsistent) and i am not sure if this could be the results of
overheads in the network. Is there anyway i could debug the amounts of
overheads on the network? What testing methods do you and your team
use?

-- 
Kind Regards
Hlabishi I. Kobo, Mr
Computer Science (Msc)
University of the Western Cape
Bellville, Cape Town, South Africa
+27 72 840 7719
+27 21 959 2461

Re: [B.A.T.M.A.N.] Fwd: BATMAN routing

[Chris Lang]

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,

-- 
Chris Lang
Gateworks Corporation
3026 S. Higuera, San Luis Obispo, CA 93401
Ph: 805-781-2000 Fax: 805-781-2001
Email: clang@gateworks.com
Web: www.gateworks.com

> 
> > 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.
> 
> 
> > 1. 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).
> 
> 
> > 2. How are the OGM's recorded, is in a form of binary where 1 will
> > represent the received OGM and 0 otherwise?
> 
> Correct.
> 
> 
> > 3. 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 ?
> 
> 
> > 1. 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

[B.A.T.M.A.N.] BATMAN routing

[hlabishi kobo]

I am doing a research on routing in a hybrid (combination of static
and mobile dynamic routers) mesh. I want to use the mesh potatoes as
well as the batphone (android version of batman) to create a mesh
model. due to the mobility and stability we want to add another factor
in the route ranking on the batman, thus the routing decisions not to
be solely based on the OGM's.thus we want to take the current
situation of the network into consideration when routing.
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. I went through the source code so many times and I got few
questions about this:

1. 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?
2. How are the OGM's recorded, is in a form of binary where 1 will
represent the received OGM and 0 otherwise?
3. I looked in the source and still not sure of where the ranking
decisions are made, can you enlighten me on that?

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.

1. How can i get the RSSI/LQI of th neighbor links?
I would really appreciate your opinions and advices in this regard
more specially how to go about implementing changes in BATMAN
protocol.
Thanks
Kind Regards