[olsr-dev] OLSRD Basic Multicast Plugin

Wed May 17 05:19:08 CEST 2006

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

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.

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.

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

>
> > 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
>
>
>
> On 5/14/06, Andreas Tønnesen <(spam-protected)> wrote:
> >
> > This plugin is now part of main olsrd and lives under lib/bmf.
> > sourceforge has had some cvs problems as of lately so if anybody
> > experiences problems updating/checking out/building please let us know.
> >
> > And thanks for sharing this cool plugin Erik!
> >
> > - Andreas
> >
> > > Hello All,
> > >
> > > I am proud to present you a basic multicast forwarding plugin
> > > for OLSR: BMF. BMF was developed at Thales Communication,
> > > Huizen, Netherlands.
> > >
> > > The Basic Multicast Forwarding Plugin floods IP-multicast and
> > > IP-local-broadcast traffic over an OLSRD network. It uses the
> > > Multi-Point Relays (MPRs) as identified by the OLSR protocol
> > > to optimize the flooding of multicast and local broadcast packets
> > > to all the nodes in the network. To prevent broadcast storms, a
> > > history of packets is kept; only packets that have not been seen
> > > in the past 3-6 seconds are forwarded.
> > >
> > > To build and use the plugin you need at least OLSRD version 0.4.10.
> > >
> > > You may get a copy of the source code on:
> > >
> > > http://home.tiscali.nl/~levab001/olsr-bmf.tar.gz
> > >
> > > In due time I will have a sourceforge.net project in which I will
> > > do maintenance of the code.
> > >
> > > Here is how to install it:
> > >
> > > Download the above olsr-bmf.tar.gz file into your OLSRD base install
> > > directory.
> > >
> > > Change directory (cd) to your OLSRD base install directory.
> > >
> > > At the command prompt, type:
> > >
> > >   tar -zxvf ./olsr-bmf.tar.gz
> > >
> > > then type:
> > >
> > >   make build_all
> > >
> > > followed by:
> > >
> > >   make install_all
> > >
> > > Next, read the readme file:
> > >
> > >   more ./lib/bmf/README_BMF.txt
> > >
> > > Have fun with it!
> > > Erik Tromp
> > >
> > > _______________________________________________
> > > olsr-dev mailing list
> > > (spam-protected)
> > > https://www.olsr.org/mailman/listinfo/olsr-dev
> > >
> >
> >
> >
> > _______________________________________________
> > olsr-dev mailing list
> > (spam-protected)
> > https://www.olsr.org/mailman/listinfo/olsr-dev
> >
>
> _______________________________________________
> olsr-dev mailing list
> (spam-protected)
> https://www.olsr.org/mailman/listinfo/olsr-dev
>
> _______________________________________________
> olsr-dev mailing list
> (spam-protected)
> https://www.olsr.org/mailman/listinfo/olsr-dev
>