[olsr-dev] OLSRD Basic Multicast Plugin

[Erik Tromp]

> ----- Original Message ----- 
> From: "spoggle" <(spam-protected)>
> To: "OLSR development" <(spam-protected)>
> Sent: Wednesday, May 17, 2006 5:19 AM
> Subject: Re: [olsr-dev] OLSRD Basic Multicast Plugin
> 

> On 5/16/06, Erik Tromp <(spam-protected)> wrote:
> >
> > > So it looks like you're using the CRC-16 to index a two-bit entry,
> > > this is very memory efficient, but it would seem to me that the CRC-16
> > > is quite a bit of overhead, plus is dependent upon packet size.  Have
> > > you had any issues with collisions?  With a worst case 6 second
> > > timeout, it would seem to me that your chances are pretty good under
> > > load.  It seems you also have to run the CRC twice on forwarded
> > > packets, once to check the received packet against history, and the
> > > once on the transmitted packet (because you've modified the TTL).
> > >

The CRC is run only once. TTL is decremented only when packets are
received or sent on non-OLSR interfaces. The CRC is calculated before
the TTL is modified. As I see it, all OLSR nodes together form one
(repaired) broadcast domain, in which TTL does not need to be
decremented.


> > > In a previous life we implemented a very similar thing but used the IP
> > > address, the group address, and the IP ID to identify packets.  This
> > > has the advantage of being really really hard to have a collision
> > > (would require a wrap-around of the ID on a single stream), sucked up
> > > memory, and only required that we run the calculation once on a
> > > forwarded packet (since changing TTL had no effect on the criteria we
> > > used to determine the history of the packet).
> > >
> >
> > I have tried to not use a CRC algorithm since I was also concerned
> > about performance. In the #if 0 section of the CalcCrcCcitt function
> > ( PacketHistory.c) you can see I also tried using source, destination
> > and ID. It appeared however that quite some protocols do not use
> > IP-ID, and just set it to 0. On the other hand, having BMF overwriting
> > the IP-ID may be a risk to other protocols which might use it. So I'm
> > not sure what would be best here.
> >
> > Another solution may be to use a wider CRC, or even just store
> > all the received packets in a list and build a hash-table into that list.
> > This is an area of research.
> 
> Which protocols don't change the ID?  I may have some rethinking to do
> (and a highly paid consultant to chastize) :-)
> 
> I was discussing this with a colleague and we think that there is
> another potential flaw with using CRCs the way you are - if a packet
> is sent and then passes through one or more routers that would
> decrement the TTL, then that packet would not be recognized by a
> router earlier in its path.

Yes, packets that have traversed the OLSR MANET and come back
with a decremented TTL (and IP checksum updated), will traverse the
OLSR MANET again. However, I would normally not expect multicast
routers to send back multicast packets on the interface on which they
were received? Or do they? If so, do we want to block the traversal
of these packets?


> 
> You might consider testing for traffic types that do and don't change
> the ID and handling each by the most efficient method.  Plus, since
> TTL is guaranteed to be modified in the course of routing, you might
> want to skip the first 12 bytes of IP packets (the protocol field
> would be nice, but a pain to pick and choose bytes) and start the CRC
> at the source IP address.

Yep. good point. Depends on whether we want to block traversal
of packets which other multicast routers receive from the OLSR MANET
and send back into the OLSR  MANET, see above.

> 
> I'd also play with limiting the length of the data that you actually
> run through the CRC as a way to bound the computation time, this might
> help offset some of the time you'd lose by going to CRC-32.
> 

Good idea! Working on it now, as we speak :))

> >
> > > For performance I think the IP info is superior (and could easily be
> > > retrofitted into your code to test), if you're memory constrained your
> > > method nicely copes.
> >
> > Yes, I agree.

> Too bad it isn't perfect... :-)

;-)


> >
> > > I'm concerned that you're using a thread to do the packet capturing
> > > and forwarding in a thread in the routing daemon.  Someone (Andreas?)
> > > took threading out of olsrd (look in the CHANGELOG), does anyone know
> > > if the reason was pure portability, or were there design issues with
> > > threading?
> >
> > Yes, there were design issues. The initial implentation used polling, and it
> > was very slow in forwarding packets. The current implementation can
> > forward packets in comparable time to kernel forwarding, at least up
> > to 40 packets/sec, as I quickly tested.

> What was the hardware?  40pps seems really slow - or is that the
> applications rate?

hmmm, your talking to a poor man here. Using Debian Linux on an intel PC.
40 pps is 4 times the maximum packet rate of our lousy "Multicast Tester"
app which generates 10 pps per running instantiation. As I said it was a
quick test just to see if it works.

> >
> > > I guess I'd like to see the capture and forwarding handled outside of
> > > the routing daemon, preferably in kernel.
> >
> > I agree. Any suggestions?
> >
> > > Out of curiosity, have you benchmarked your code?  I suppose there
> > > would be interest in knowing what the overhead and throughput
> > > difference is between unicast and multicast...
> >
> > No, no benchmarks yet. There is still quite some work to do here...
> >
> >
> >
> > >
> > > thanks again for your work!
> 
> retiterate the above,
> 
> >
> > dave c
> >
> >
> >

Thank you for your feedback!

Erik