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

Sven Eckelmann
2011-02-28T12:03:05Z

[-- 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 --]