Subject: [AAA-WG]: Issue 235 and another potential fast duplicate check method

From: Jari Arkko <[email-masked]>
Date: Thu, 28 Feb 2002 20:57:30 +0200

(sorry for the resend if you get this twice...)

Another method to do a fast duplicate check at an
accounting server. This method doesn't need any
protocol modifications, has a very high likelihood
of never needing *any* record searches unless
duplicates are indeed around, is reliable even
if there are sender implementation problems or reboots,
and requires O(constant) amount of work per received
record.

Or at least I think so -- you are welcome to shoot this
down! I may well missed something and I'm writing this
while participating in a boring teleconference [;-)]

Approach: Use a hash table to find out if an equivalent
session id has been seen earlier (or collision in the
hash values).If the hash table indicates nothing has
been seen, no record search is performed. If it does
indicate something has been seen, then a full search
will be done. The hash table is updated as new records
come in, and as the duplicate window (e.g. a day) moves
further.

Data structures: 1) A fixed size table with counters
as elements. Size of table can be chosen freely. 2) A
database of all records, with two cursors pointing to
the beginning of the duplicate window (a day old record)
and to the most recent record.

Initialization: The table is initialized with all zeroes.
Database is empty.

Duplicate check: Take the session id from the received
record and produce a hash value H=hash(sessionId) from it.
If table[H] == 0, there is no need to do any record
searches. If table[H] > 0, do a search for the session id
from the data base. Unless a duplicate is found in this
search, put the new record to the database. Then
increase the counter related to this session id hash
by table[H]++.

Advancing the duplicate window: Move the duplicate window
cursor ahead by one, and produce a hash value H=hash(sessionId).
Then decrement the relevant counter by table[H]--.

Jari