[B.A.T.M.A.N.] TTL yes, TTL no

[B.A.T.M.A.N.] TTL yes, TTL no

[Antonio Quartulli]

Hello folks!

In these days I was wondering whether the TTL field in the OGM packet is
really useful or not...Due to hop_penalty an OGM will be discarded as
soon as the TQ will reach 0 (which is a sort of TTL mechanism itself).
At this point why is the TTL field needed?

Someone could probably say that a node far at least TTL hops will never
be reached by a unicast packet, then it is meaningless to let it know
about me. But then it could be possible to recalibrate the TTL such that
it has to be equal to the maximum length in number of hops of the longest 
path the OGM can traverse.

Bye! :)

-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara

Re: [B.A.T.M.A.N.] TTL yes, TTL no

[Marek Lindner]

Hi,

> In these days I was wondering whether the TTL field in the OGM packet is
> really useful or not...Due to hop_penalty an OGM will be discarded as
> soon as the TQ will reach 0 (which is a sort of TTL mechanism itself).
> At this point why is the TTL field needed?

uhm.., you probably are right. As long as there is a hop penalty it also 
functions as a TTL. Keep in mind that it is possible to set the hop penalty to 
zero. With the current default hop penalty of 10 the maximum number of hops is 
limited to 25.


> Someone could probably say that a node far at least TTL hops will never
> be reached by a unicast packet, then it is meaningless to let it know
> about me. But then it could be possible to recalibrate the TTL such that
> it has to be equal to the maximum length in number of hops of the longest
> path the OGM can traverse.

Not quite sure what you are proposing. A TTL of TQ_MAX / hop penalty ?

Cheers,
Marek

Re: [B.A.T.M.A.N.] TTL yes, TTL no

[Andrew Lunn]

On Sat, Mar 26, 2011 at 04:31:42PM +0100, Marek Lindner wrote:
> 
> Hi,
> 
> > In these days I was wondering whether the TTL field in the OGM packet is
> > really useful or not...Due to hop_penalty an OGM will be discarded as
> > soon as the TQ will reach 0 (which is a sort of TTL mechanism itself).
> > At this point why is the TTL field needed?
> 
> uhm.., you probably are right. As long as there is a hop penalty it also 
> functions as a TTL. Keep in mind that it is possible to set the hop penalty to 
> zero. With the current default hop penalty of 10 the maximum number of hops is 
> limited to 25.

Humm, i could be wrong here.....

static uint8_t hop_penalty(const uint8_t tq, struct bat_priv *bat_priv)
{
        int hop_penalty = atomic_read(&bat_priv->hop_penalty);
        return (tq * (TQ_MAX_VALUE - hop_penalty)) / (TQ_MAX_VALUE);
}

So 10% is deducted, not 10 absolute. So assuming perfect links, TQ
will be:

255
245
235
226
217
208
200
192
184
177
170
163
157
151
145
139
134
129
124
119
114
110
106
102
98
94
90
86
83
80
77
74
71
68
65
62
60
58
56
54

etc...

Depending on how the rounding works, i think somewhere after hop 72
the TQ is always 12.

But maybe i'm not understanding something correctly....

    Andrew

Re: [B.A.T.M.A.N.] TTL yes, TTL no

[Antonio Quartulli]

Hello,

On sab, mar 26, 2011 at 04:31:42 +0100, Marek Lindner wrote:
> 
> Hi,
> 
> > In these days I was wondering whether the TTL field in the OGM packet is
> > really useful or not...Due to hop_penalty an OGM will be discarded as
> > soon as the TQ will reach 0 (which is a sort of TTL mechanism itself).
> > At this point why is the TTL field needed?
> 
> uhm.., you probably are right. As long as there is a hop penalty it also 
> functions as a TTL. Keep in mind that it is possible to set the hop penalty to 
> zero. With the current default hop penalty of 10 the maximum number of hops is 
> limited to 25.

I think it is wrong: TQ is not decremented by hop_penalty each time, but it is
multiplied by (TQ_MAX-hop_penalty/TQ_MAX), then the number of hops is
bigger than what you said. With hop_penalty = 10 we can probably reach
~135 hops (raw calculus 255*(TQ_MAX-hop_penalty/TQ_MAX)^135) =~ 0)

> 
> 
> > Someone could probably say that a node far at least TTL hops will never
> > be reached by a unicast packet, then it is meaningless to let it know
> > about me. But then it could be possible to recalibrate the TTL such that
> > it has to be equal to the maximum length in number of hops of the longest
> > path the OGM can traverse.
> 
> Not quite sure what you are proposing. A TTL of TQ_MAX / hop penalty ?
> 

Looking at the calculus above, I'm proposing to use TTL = ~135

Bye!

-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara

Re: [B.A.T.M.A.N.] TTL yes, TTL no

[Andrew Lunn]

> I think it is wrong: TQ is not decremented by hop_penalty each time, but it is
> multiplied by (TQ_MAX-hop_penalty/TQ_MAX), then the number of hops is
> bigger than what you said. With hop_penalty = 10 we can probably reach
> ~135 hops (raw calculus 255*(TQ_MAX-hop_penalty/TQ_MAX)^135) =~ 0)

I agree with the principle. However, you need to take rounding into
effect. The kernel does integer arithmetic and TQ is always an integer
value. I also got it wrong in my last post. I used the wrong round
function when calculating the values. Using rounddown() i get:

255
245
235
225
216
207
198
190
182
174
167
160
153
147
141
135
129
123
118
113
108
103
98
94
90
86
82
78
74
71
68
65
62
59
56
53
50
48
46
44
42
40
38
36
34
32
30
28
26
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

After 73 hops, TQ will be zero.

> Looking at the calculus above, I'm proposing to use TTL = ~135

TTL of 73 would be more accurate i think.

Which leads me to a new question. At WBM we talked about moving the
HNAs out of the OGMs. If we had a really big mesh, with more than 73
hops from side to side, do we get into a situation where we have HNAs
from more than 73 hops away, but no idea how to route to them since
OGMs got dropped when TQ reached 0?

     Andrew

Re: [B.A.T.M.A.N.] TTL yes, TTL no

[Antonio Quartulli]

On Sat, Mar 26, 2011 at 06:45:48PM +0100, Andrew Lunn wrote:
> > I think it is wrong: TQ is not decremented by hop_penalty each time, but it is
> > multiplied by (TQ_MAX-hop_penalty/TQ_MAX), then the number of hops is
> > bigger than what you said. With hop_penalty = 10 we can probably reach
> > ~135 hops (raw calculus 255*(TQ_MAX-hop_penalty/TQ_MAX)^135) =~ 0)
> 
> I agree with the principle. However, you need to take rounding into
> effect. The kernel does integer arithmetic and TQ is always an integer
> value. I also got it wrong in my last post. I used the wrong round
> function when calculating the values. Using rounddown() i get:
> 

[cut]

> 
> After 73 hops, TQ will be zero.

You are right, my raw calculus was too raw :p
> 
> > Looking at the calculus above, I'm proposing to use TTL = ~135
> 
> TTL of 73 would be more accurate i think.

Yes.

> 
> Which leads me to a new question. At WBM we talked about moving the
> HNAs out of the OGMs. If we had a really big mesh, with more than 73
> hops from side to side, do we get into a situation where we have HNAs
> from more than 73 hops away, but no idea how to route to them since
> OGMs got dropped when TQ reached 0?
> 

Mh..The HNA request is triggered by the TTVN carried into the OGM. Then a node
far more than 73 hops should never ask for HNAs it cannot reach..
Moreover, a route toward a client is never allocated if we don't have
its orig_node in our DB.


Bye

-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara

Re: [B.A.T.M.A.N.] TTL yes, TTL no

[Antonio Quartulli]

Hi,

On Sat, Mar 26, 2011 at 06:45:48PM +0100, Andrew Lunn wrote:
> Which leads me to a new question. At WBM we talked about moving the
> HNAs out of the OGMs. If we had a really big mesh, with more than 73
> hops from side to side, do we get into a situation where we have HNAs
> from more than 73 hops away, but no idea how to route to them since
> OGMs got dropped when TQ reached 0?
> 

I have another question: why do we use a HOP_PENALTY instead of an
additional HOP_COUNT field? In this way the OGM is spread as long as
possible. Is there any problem in this concept I'm not seeing?

Bye!

-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara

Re: [B.A.T.M.A.N.] TTL yes, TTL no

[Antonio Quartulli]

On Sat, Mar 26, 2011 at 06:45:48PM +0100, Andrew Lunn wrote:
> > I think it is wrong: TQ is not decremented by hop_penalty each time, but it is
> > multiplied by (TQ_MAX-hop_penalty/TQ_MAX), then the number of hops is
> > bigger than what you said. With hop_penalty = 10 we can probably reach
> > ~135 hops (raw calculus 255*(TQ_MAX-hop_penalty/TQ_MAX)^135) =~ 0)
> 
> I agree with the principle. However, you need to take rounding into
> effect. The kernel does integer arithmetic and TQ is always an integer
> value. I also got it wrong in my last post. I used the wrong round
> function when calculating the values. Using rounddown() i get:
> 

[cut]

> 
> After 73 hops, TQ will be zero.

You are right, my raw calculus was too raw :p
> 
> > Looking at the calculus above, I'm proposing to use TTL = ~135
> 
> TTL of 73 would be more accurate i think.

Yes.

> 
> Which leads me to a new question. At WBM we talked about moving the
> HNAs out of the OGMs. If we had a really big mesh, with more than 73
> hops from side to side, do we get into a situation where we have HNAs
> from more than 73 hops away, but no idea how to route to them since
> OGMs got dropped when TQ reached 0?
> 

Mh..The HNA request is triggered by the TTVN carried into the OGM. Then a node
far more than 73 hops should never ask for HNAs it cannot reach..
Moreover, a route toward a client is never allocated if we don't have
its orig_node in our DB.


Bye

-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara