Slimelite BBS

Re: orig MSGID -> new REPLY

Back to FREE25

From imb@asstdc.scgt.oz.au · 1996-04-09 10:51 · #73019 in FREE25

In reply to Orig Msgid -> new Reply by HECTOR SANTOS

From: imb@asstdc.scgt.oz.au (michael butler)

: First, You have 8 digits for the fidonet msgid serial number. It is not the
: SAME thing at all and if had more room, it alters the entire engineering
: and thinking drastically of current dupe checking systems.  No, it is not
: the same thing.

As I've previously indicated, an eight hexadecimal digit serial number used
at the rate of one message per second from January 1st 1970 will run out of
unique quantities in the year 2036. I fail to see any weakness in the use of
these other than some people's apparent belief that the unix-originated
time_t data type will continue in common use beyond that year .. not *$%@*
likely :-)

: Second, lets consider that the INTERNET is a somewhat of a controlled
: distribution system and dramatically differs from the fidonet distribution
: structure.

Rubbish .. the distribution of internet news is far _less_ controlled than
any FidoNet messaging. It's distributed by "flooding" .. I send any (and
every) message I receive to any and all sites with whom I have a connection
except the one it came from.

What prevents the propagtion of duplicates is the fact that NNTP presents
the message-id first and waits for either a "send-me" (indicating that it
hasn't seen the message before) or a refusal response (to say that it has).

: Your efforts (suggested dupe database structure) is valid and you bring up
: many good points. But in practical terms and design, your suggestion would
: kill fidonet tossers and not be accepted in the fidonet market place.  The
: fidonet market would not accept the overhead and tremendous slowdown
: required in the specific suggestion you presented.

Done properly, the overhead of maintaining real data would certainly not
offer the level of performance that "short-cut" processing provides but 
a value judgement needs to be made .. do we continue to throw away perfectly
good messages based on the "guess" (and it is pure guesswork) that the CRCs
discussed and used to date actually represent unique objects ?

People still quite happily use Windoze even though the DOS command-line
offers significantly superior performance. They do this only because they
believe there is some functional improvement (although I can't think why
:-)). To counter this degradation, they simply go out and buy a faster
machine.

: You must be in academia? <g>  Well, I am an engineer.  

At the risk of sounding overly commercial (and I apologise in advantage to
anyone who takes the following this way) ..

No .. well .. sort of ;-) .. I've been designing commercial computing
systems since the late '70s and only recently ('92) decided that I'd do a
degree part-time (double-major, computing science and electronics). When I
say "systems", I refer to both hardware and software .. I do everything down
to schematics and PCB layouts right through micro-kernels (in C and
assembler) and the data-management that sits over the top of it .. for
myself .. in my own business (http://www.asstdc.com.au).

If anything, my background leans toward doing something right the first time
because it's of significant commercial value to do so. Both correctness (in
the academic sense) and extensibility (in the commercial sense) are high
priorities in all of my "first-cut" designs. Yes, it is more costly to do
things properly and that expense is reflected not only in monetary terms and
"time-to-market". However the resultant product generally has a better than
average maintainability and far fewer "undocumented features".

Undocumented features as applied to CRCs means the arbitrary removal or even
deletion of messages because they happen to be unfortunate enough to have
the same "signature" as some other unrelated message.

: Here are the following issues you havn't considered:

 [ .. ]

: 1) First, the issue of across the board compliance.

This is true .. if message-ids are the sole source of duplicate information,
then ALL systems must generate them ..

:    However, this raises the issue of FTS-9 certification which states:

:      " Finally,  a MSGID is generated only at the time of message
:        creation."  (FTS-9, Jim Nutt)

 .. and, as a progressive step, this specification needs to be changed to
impose this as mandatory.

:    So if a message does not have a MSGID, the mail exporter would
:    be voilating FTS-9 if it added one.  Correct?

Absolutely.

However, I'm not saying that FidoNet should suddenly switch tomorrow. I
think everyone accepts that this is impossible. What should happen is that
all new software be written to implement FTS-0009.

In fact, this was the intent of its adoption as an FTS .. authors are
expected to "improve" over time :-)

: 2) Second, FTS-9 states:

:    "The serial number may be any eight character hexadecimal number, as
:     long as it is unique - no two messages from a given system may have
:     the same serial number within a three years.  The manner in which
:     this serial number is generated is left to the implementor." (FTS-9,
:     Jim Nutt)

Which leaves the possibility of having two different systems using the same
serial number. They are distinguishable because they are from different
systems .. a fact which is readily identified from the address field in the
message-id control ('kludge') line. As I read it, this was always the
intention of this FTS.

: 3) Third, more direct to your technical suggestion is what are the primary
:    and/or secondary keys or factors in order to do searching in the table?

The whole object as I described is required to be unique. The method of
finding one (or several) that _may_ match an incoming message is a quite
valid use of a CRC. In this example, the CRC is only used to find the
correct "hash-bucket" (containing a simple linked-list) of those messages
with the same signature. The comparison to determine if the message really 
matches is done on the objects found via that bucket.

:    So my first point is, why the other factors?

All of the data I used, in combination, do uniquely identify a message.
Removal of any of them will result in false collisions.

:    Where would you get the DOMAIN from the message?  Must FTS-9 change the
:    address have the domain in it? 

This is the next piece of FTS-0009 that needs clarification. The address
field should contain a domain, since domain gates are quite consistent in
this respect, its absence implies that the message originates within one of
your own native domains and which can be readily determined by matching from
the zone number.

You simply don't get the instance of a node being known as 99:12/34@dom1 and
99:12/34@dom2 .. it just doesn't happen.

:    You have DATABASE lookup #1 to find a matching ECHO TAG.

The intention, in my example, was that echos are readily looked up using a
straight index into a table. You can optimise this and the comparison of the
domain by comparing all the other data elements first and, only when a true
match is found, comparing the things that are expensive to look up. That's
why I list them at the end of the structure.

Considering the number of real duplicates present in a properly configured
environment, this should be one "hit" in thousands. Hardly a significant
penalty.

: 4) What is the table capacity on a TOTAL BASIS and on PER ECHO BASIC?

:    The 3 year factor of the FTS-9 specification now comes into place
:    now.

Oh no .. duplicate databases on the internet are rarely held for longer than
14 or 30 days .. this is sane as it's unusual to see propagation times in
excess of 7 to 10 days. Likewise, we should only expect to maintain
duplicate information for reasonable periods.

If a "reasonable" propagation time for a message is, say 14 days, then we
simply keep 45 days worth of dupe history and refuse to propagate messages
older than that. This last bit is important !

: Lets bring out reality:

: Many mail tossers will reject mail if its older than 30-45 days. Thats
: definable by the sysop but alot are programmed to allow for this. This
: nullifies FTS-9 3 year concept.  So a MAIL TOSSER/EXPORTER who claims to be
: compliant with FTS-9 is breaking the specs if he allows for AGE rejections
: less than 3 years.

Do you really want to keep information about messages beyond their use-by
date ? Most have ceased to be relevant within 7 days.

Another point .. what happens when someone manages to clobber their sequence
number container .. do we now refuse all his/her messages until they post
one that exceeds our previously recorded "high-water mark". The "test of
reasonableness" says otherwise.

: In my implementation, to compensate for systems that don't support MSGID, A
: CRC is generated based on the concatentation of the following string:

:            TO+
:            FROM+
:            SUBJECT
:            ASCIIZ DATE
:            ECHO TAG

: The result is then checked in my DUPE table. If a match is found, it
: is a DUPE. If not, it is inserted.

 .. but this results in false collisions as discussed if you use the CRC as
the only mechanism of comparison.

Used as a mechanism to get to the limited number of messages that share the
same signature, it valid .. but you _must_ compare all of the fields from
which the CRC was generated to validate the "hit".

: Understand that you are not dealing with the Internet, but with fidonet,
: there is no such thing of having a message with Multiple "echo tags" in it
: and in my opinion, you should only be concern with the message of where it
: is actually placed in FidoNet, in this case, - an echo.  The fact, that a
: SERIAL number matches one in another echo, shouldn't mean its a dupe.

With WinNT and Win95 cross-posting in this manner is a very real possibility
.. I'm led to believe that both support the appearance of a single file in
two different directories (POSIX specified "hard-links").

: Computer Scientist don't learn this stuff, do they? <g>.

You'd be surprised at what they're teaching "kids" these days .. <bg>

    michael
--- ifmail v.2.8a/p4
 * Origin: Assorted C Software (3:712/400@fidonet)