From imb@asstdc.scgt.oz.au · 1996-04-03 09:33 · #73049 in FREE25
In reply to orig MSGID -> new REPLY by Paul Edwards
From: imb@asstdc.scgt.oz.au (michael butler)
II> A simple sequential counter is far more effective and, computationally,
II> exceedingly "cheap". All FidoNet's developers (are there any left?)
II> need to do is to take a simple counter _in_combination_with_ the
II> originating node number to uniquely identify any message.
: IT WON'T WORK!!!!!! Do you know that word "WORK"?
Please don't tell the 35+ million internet systems around the globe this as
that's what they use - effectively, a simple sequential counter and it most
certainly does work. Admittedly, they also aren't limited by character set
or length as much but the basic priciple is the same.
: I think what you are failing to SEE is that YOU are not considering
: "Networks and Echos" and the introduction of other applications into the
: picture. For the sake of simplicity, lets say your "serial #" is 1, it
: is entirely possible to have a serial number #1 in ECHO X and in ECHO Y?
: Are they they same message?
Sure, but not for the purposes of duplicate detection in FTN networks .. see
below ..
: How do you handle cross posting?
Very simply, by maintaining message_id + originating_node + echo_tag as
components to your key in the duplicate database. To be explicit ..
struct dupe {
struct dupe *next; /* next rec in hash bucket */
unsigned long message_id; /* seq. no. */
unsigned short originating_node[4]; /* 4d ftn address */
unsigned short domain; /* index into domain table */
unsigned short echo_tag; /* index into echo table */
} dupe_table[];
struct dupe *dupe_hash_bucket[SOME_SUITABLE_SIZE];
If you want to use something really expensive to generate the hash function,
sure, use CRCs and _expect_ collisions like any other hashing function.
Simply adding all the bytes in the record together modulo SOME_SUITABLE_SIZE
is _much_ faster, however, preferably with a single-bit shift or rotate
between additions to bring in some order dependency and spread of
distribution.
Note that the above (in 80x86 large model) requires 14 bytes per dupe record
yet preserves _all_ of the unique information about every message.
Obviously, you can get really fancy and dynamically "grow" the hash table
when you get too many chains which are too long but I leave that as an
(intermediate) exercise for the reader.
Another (advanced) exercise is to place the entire hash table on disk.
Please see the C-news or INN DBZ code for classic examples of how this is
already being done in every unix-based internet news system.
: And if you want to keep threading is "ECHO" a factor in the thread?
"echo" or "netmail" doesn't come into it at all. Every message MUST have a
unique identifier.
: In summary, a 32-CRC of the following is among the BEST you will be able
: to do in FidoNet:
: To+From+Subject+Date+EchoTag
: The odds are EXTREMELY better than your incremential serialization and
: in the END RESULT, in practical terms, more applications can work in
: harmony and independent of any "commonly stored seed number" factor.
Mathematically, this is pure rubbish. Please re-read what I wrote in
conjunction with Paul's probability table in order to comprehend why CRCs
are significantly worse .. or better yet, derive your own probability
equation for your input stream.
As I said, mangling the five input fields with folded case, a limited
character set to start with and limited length into a 32 bit quantity is
very much worse than a CRC-32 on an arbitrary chunk of binary data taken out
of a ZIP file, for instance. It does not exhibit either the same output
range or distribution with such limited input data sets .. the probablity of
collision is "better" when you fold the case of the header fields and, since
some mail processors do this, other CRC-based dupe detection systems have to
take this utter stupidity into account :-(
Example .. if I need to represent one (alphabetic) character from the ranges
'A' through 'Z' and 'a' through 'z', I need at most six bits (52 unique
states). If, however, I create an equivalence class where 'A' is equal to
'a' through 'Z' being equal to 'z', I now only need five bits (26 unique
states) and I've doubled my chances of a collision. Now extend that to a
field of 32 characters and perform the same probability calculation with and
without the equivalence class created by ignoring the case of each letter ..
to repeat .. utter stupidity.
As for your obvious concern about the time elapsed before the serial number
repeats, if a message id is constrained to be an eight character field per
FTS-0009, then I could've started generating messages at midnight on the 1st
January, 1970 at the rate of one per second and I won't "wrap" around until
the year 2036. I suspect that this model might just be sufficient for
FidoNet's purposes and quite sensible,
michael
--- ifmail v.2.8a/p4
* Origin: Assorted C Software (3:712/400@fidonet)