[B.A.T.M.A.N.] Unused structs in Catwoman packet buffers

[B.A.T.M.A.N.] Unused structs in Catwoman packet buffers

[Martin Hundebøll]

Hi all,

I trying to figure out when to free an unused struct in the catwoman (network coding) packet buffer. Below I will try to describe the principal question, but it all comes down to: Should I use a timeout or just remove it right away.

Heres a short description of the buffering in catwoman:

When a packet arrive at a node and is to be forwarded, catwoman searches a hash-table for packets that can be combined with the just arrived packet. If a match is found, the two packets are combined and transmitted as one; if not, the just arrived packet is added to the buffer, so that the next arriving packet might be combined with it.

To reduce the complexity when searching for packets in the hash table, hash indexes are generated from a key consisting of a mac-source XOR'ed with a mac-destination like this:

   int i;
   uint8_t key[ETH_ALEN];

   for (i = 0; i < ETH_ALEN; i++)
       key[i] = src[i] ^ dst[ETH_ALEN-1-i];

This reduces complexity because catwoman needs only to search a few paths (src-dst-pairs) for possible matching packets. The reverse order of dst makes the key direction-specific.

Each entry in a hash-bin-hlist is denoted a coding_path, which contains the src and dst of the path i question and a reference to list of packets. This list of packets, is where packets are buffered when waiting for a coding opportunity as described above.

Every 10 ms, the hash table is traversed and packets that have been buffered for more than 10 ms are transmitted without being coded. (This gives an avarage buffer time of 15 ms, I know...)

Now here's the question:
When a list of a certain coding_path becomes empty, should I free the coding_path right away, or should I timestamp it and mark it for removal at a later time. The thing is that I don't know whether a new packet for the same coding_path will arrive in a short moment. If I have just freed the coding_path struct, I would have to spend ressources to initialize it again...

It is probably a micro-optimiziation and the simplest solution would be to just free it right away, but I would like to have your comments anyways.

-- 
Kind regards
Martin Hundebøll

+45 61 65 54 61
martin@hundeboll.net

Nordborggade 57, 2. tv
8000 Aarhus C
Denmark

Re: [B.A.T.M.A.N.] Unused structs in Catwoman packet buffers

[Antonio Quartulli]

Hello Martin,

and thank you for the explanation.

On Mon, Oct 17, 2011 at 03:16:25 +0200, Martin Hundebøll wrote:
> Now here's the question:
> When a list of a certain coding_path becomes empty, should I free the coding_path right away, or should I timestamp it and mark it for removal at a later time. The thing is that I don't know whether a new packet for the same coding_path will arrive in a short moment. If I have just freed the coding_path struct, I would have to spend ressources to initialize it again...
> 
> It is probably a micro-optimiziation and the simplest solution would be to just free it right away, but I would like to have your comments anyways.

In my opinion it would be better to _keep_ the struct even if the corresponding
packet list is empty.

Imagine there are two packet flows going through a relay
node R. If the two coding paths of the two flows have an high coding correlation
at R (coding opportunity?), one of the two packet lists on R will be emptied
several times during the data transmission.

For this reason I think it would be better to wait a fixed time before freeing
such structure. The overhead given by the freeing/reallocating/reinitialising
operation could become not negligible.

I hope that I correctly understood the problem and that my idea was clear :-)

Cheers,


-- 
Antonio Quartulli

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

Re: [B.A.T.M.A.N.] Unused structs in Catwoman packet buffers

[Martin Hundebøll]

Hi Antonio,

On 2011-10-17 18:37, Antonio Quartulli wrote:
> Hello Martin,
>
> and thank you for the explanation.
>
> On Mon, Oct 17, 2011 at 03:16:25 +0200, Martin Hundebøll wrote:
>> Now here's the question:
>> When a list of a certain coding_path becomes empty, should I free the coding_path right away, or should I timestamp it and mark it for removal at a later time. The thing is that I don't know whether a new packet for the same coding_path will arrive in a short moment. If I have just freed the coding_path struct, I would have to spend ressources to initialize it again...
>>
>> It is probably a micro-optimiziation and the simplest solution would be to just free it right away, but I would like to have your comments anyways.
>
> In my opinion it would be better to _keep_ the struct even if the corresponding
> packet list is empty.

I agree. I have just made a housekeeping task to clean up other elements, so it shouldn't be a problem to add the coding_path here :)

Thanks!

-- 
Kind regards
Martin Hundebøll

+45 61 65 54 61
martin@hundeboll.net

Nordborggade 57, 2. tv
8000 Aarhus C
Denmark

Re: [B.A.T.M.A.N.] Unused structs in Catwoman packet buffers

[Simon Wunderlich]

[-- Attachment #1: Type: text/plain, Size: 2096 bytes --]

Hey Martin,

just my two cents: I agree to Antonio to keep the packet list struct alive at least
for a few seconds. If your packet stream has less than 100 packets per second 
(which is quite common IMHO) for your 10ms send-and-free scenario, many packet list 
structs would be destroyed and reinitialized over the time.In worst case, 
this would happen for every single packet which comes by, for example if you have a 
steady 50 packets/s stream (typical VoIP streams with 20ms packetization).

Cheers 
	Simon

On Mon, Oct 17, 2011 at 06:37:55PM +0200, Antonio Quartulli wrote:
> Hello Martin,
> 
> and thank you for the explanation.
> 
> On Mon, Oct 17, 2011 at 03:16:25 +0200, Martin Hundebøll wrote:
> > Now here's the question:
> > When a list of a certain coding_path becomes empty, should I free the coding_path right away, or should I timestamp it and mark it for removal at a later time. The thing is that I don't know whether a new packet for the same coding_path will arrive in a short moment. If I have just freed the coding_path struct, I would have to spend ressources to initialize it again...
> > 
> > It is probably a micro-optimiziation and the simplest solution would be to just free it right away, but I would like to have your comments anyways.
> 
> In my opinion it would be better to _keep_ the struct even if the corresponding
> packet list is empty.
> 
> Imagine there are two packet flows going through a relay
> node R. If the two coding paths of the two flows have an high coding correlation
> at R (coding opportunity?), one of the two packet lists on R will be emptied
> several times during the data transmission.
> 
> For this reason I think it would be better to wait a fixed time before freeing
> such structure. The overhead given by the freeing/reallocating/reinitialising
> operation could become not negligible.
> 
> I hope that I correctly understood the problem and that my idea was clear :-)
> 
> Cheers,
> 
> 
> -- 
> Antonio Quartulli
> 
> ..each of us alone is worth nothing..
> Ernesto "Che" Guevara
> 

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]