[aprssig] Aprx v2 beta, now with Viscous Digipeater

[Matti Aarnio]

On Thu, Oct 22, 2009 at 11:12:05AM -0500, Jason KG4WSV wrote:
> On Thu, Oct 22, 2009 at 11:07 AM, Scott Miller <scott at opentrac.org> wrote:
> 
> > The T2 uses a list of 16-bit hashes for tracking dupes, with an 8-bit
> > time-to-live for each, so that's 3 bytes per entry.  Currently the list is
> > 15 entries long, so 45 bytes of storage total.
> >
> > To implement this on the T2 shouldn't require more than one extra bit of
> > storage per entry.
> 
> I was thinking more of the buffer for the packets being held for
> delayed digipeating.  Matti's web page refers to a "4-8 second" hold,
> which sounds reasonable in operation, but that means a worst case of
> up to eight 256 byte packets, or 2k RAM.  Even a minimum 4s hold is 1k
> of buffer space.  This is all in addition to the dupe hash table.

I am unsure of universality of the observation that I have here..
but with my high antenna location the viscousness results in about
80-95% of packets being removed from delay buffer while they still
are waiting.  At peaks I see 40 packets per minute - which are coming
in rapid bursts with long quiets in between.  I really do not need
all that many packets in my viscousness queue,  3 small ones, 1 larger.

On some 24 hour sample of full feeds pulled from APRSIS the packet
length statistics looked like this:

    <=  80:  about  25%
    <=  90:  about  36%
    <= 100:  about  73%
    <= 110:  about  89%
    <= 120:  about  94%
    <= 130:  about  97%
    <= 140:  about  98.7%
    <= 150:  about  99.4%

I don't have similar statistics for AX.25 frames in radio networks,
although that original sample could be used to produce AX.25 length
estimate data as well.


I did some studies over various "rapid hash algorithms", how well
they distributed their results  -  of what I had been recommended
to use by other people, worst ones did result in about 25% of
value space getting any hits at all, and even smaller fraction
getting most hits.  As a young man then, that did tech me not to
trust hearsay, and want to do validation with _my_ data.

There are very few "good" hash algorthms, and they tend to be called
"Cryptographic Hash XYZ".   But your first task on storage constrained
case like T2 is to feed a few million APRS packets to candicate algorithm
and see how even the resulting distribution is, and then to see ratio
of false positives.  If you can not keep whole packet around for
comparison against false hash hits, then you need to know the ratio
of false hits with your usual environments, and perhaps use different
hash.

By the way, I chose 32-bit FNV-1 hash instead of CRC16 or CRC32,
and that is merely to supply dupe checker hash index table with
the initial index value.  My dupe storage carries whole packets,
and copies of dupe comparison data, but I do have a megabyte or
so to play with.  (FNV-1 is quicker to compute than CRC, but that
too is rather moot point if you are doing embedded 8-bit
microprocessor work instead of high-end server...) So many
tradeoffs...

> -Jason
> kg4wsv

73 de Matti, OH2MQK