Subject: RE: [AAA-WG]: [Issue] Enabling efficient accounting record uniqueness checking

From: "Patil Basavaraj (NET/Dallas)" <[email-masked]>
Date: Sun, 11 Nov 2001 17:18:52 -0600

Responses inline:
> 
> 
> Hi! A few questions:
> 
> 1) The first sent record will not be a duplicate and you will only
>      later send the duplicate(s) and set the 'D' bit. Therefore,
>      you have 1 non-D record with id N and at least 1 D record with
>      the same id going around somewhere.

Or, to be very detailed, one could say that the number
of the non-D records with the same id might also be 0,
since it is possible that after the original account record
has been sent, the recipient node (or the link to it) collapsed
just before receiving/storing properly the Accounting Request
message.

>     So, let's assume the D record gets to the server first, 
> is being checked for duplicate status (it is the first packet to
> arrive, so it isn' really a duplicate).

Yes, this can happen. Since it has the D bit on,
it would be sent towards the accounting record uniqueness
checking operations, as a record whose duplicate would be
searched among the other received accounting records
within the (configurable) "accounting record uniqueness
comparison time zone" (+-, i.e. the implementation
should look a bit backward & forward on the time line).

Such accounting records with D bit set would likely
be put to a separate buffer where the D records (a tiny
minority) are waiting to be compared against all the
others within (+-) the uniqueness comparison time limit.

>     Then, let's assume for some proxy server downtime or 
> network congestion  reason the non-D (i.e. the first) packet gets to
> the server too. What will the server do when it receives the record?

The server would just forward it to the storage area
for the received accounting records (i.e. the place
for the overwhelming majority of the accounting records).

They would wait there, classified/indexed by e.g.
the minute or hour when they came and only if >1
D records also appear for the same per node
configurable "time zone" (e.g. +- N hours),
the D records would _have to_ be compared against
the non-D records (and the other D records),
using the Session-Id and Accounting-Record-Number
AVP pairs. Even then, all accounting records would
not *have to* be cross-compared against *all*
other accounting records.

   All in all, this issue "Enabling efficient
accounting record uniqueness checking" would NOT
deny the ability to do such heavy checking where ALL
accounting records are compared against ALL the
other accounting records, but that should not
be a mandatory (MUST) thing to do since it is
an expensive operation and it is rather simpler to focus
just to search duplicate records for the very few and
seldom appearing 'D' marked accounting records.

> It doesn't have the 'D' bit on, so we don't need to do anything? No,
> we do need to do something  and I find it hard to see what that
> something could possibly be other than identity uniqueness
> check. But perhaps the earlier 'D' record was treated somehow
> special to ease our task when the non-D record arrives? 

Yes, I fully agree that an implementation needs to do
something for the non-D accounting records, but not
much :-). They would be just put to a buffer/database
of the receiving Diameter Server or end system, for
the duration of the (configurable) time zone length,
e.g. +-N hours. It must be noted that the
comparison time zone length should be measured per
accounting records that appeared e.g. during a
certain "time zone" so that it contains equally long
timestamp comparison zone backward *and* forward
as per a D-flagged accounting record.
(Please see also to the previous answer text paragraph.)

> 2) Wouldn't we have to specify rules also for
> proxies to deal with 'D' bits?

Yes I agree, that is a very consistent thing to do.
A very simplistic way to do that is to just add the words
"or proxy" to the end of this original issue text sentence:
"    - This bit is defined only for Accounting Requests,
       sent by a Diameter node."

> 3) If a duplicated record arrives, is there something that 
> forces us to do an immediate check (as in before sending a reply),
> or can  we postpone the check later?

What comes to the application level (charging) 
is partly a question of the service level offered.
For hot billing, Prepaid and Advice of Charge services
it would be beneficial to have the charging status
per subscriber calculated on an as generated basis.

At the Diameter accounting level, it would be beneficial if the
response messages were sent even before the application data
correctness (such as duplication) is investigated.
(In an earlier discussion there was a suggestion that
at the protocol level it should include messages to negotiate
in the downstream nodes the ability to check for duplicates, but
since it was preferred to not introduce new
messages, the duplicate accounting message
checking is left to the receiving end system.)

As an accounting record time buffer is anyway needed
in the receiving node (to be able to cross-check records
for duplicates when there arises a need to do so),
bottlenecks would arise unless at the basic protocol
level it is allowed to operate independently, providing
quick Accounting-Answer messages.

Therefore the answer to your question would be
that we can postpone the uniqueness checking a bit later
(than accounting protocol response messages). This
is also in the spirit of the current base alpha02 text.

> 4) Do we need to check uniqueness to all possible records, or just
>      records from a particular time (or time period)?

All possible records would be the theoretical ideal,
but I feel that for the uniqueness checking to be
reasonably effective, just a "large enough" time
period would be enough. Since miscellaneous kinds of
node and link failures could leave some Diameter
clients temporarily isolated (with max window amount
of unacknowledged accounting messages as sent-but-not-yet-
responded), and even human intervention could be
needed to analyze and repair and/or configure the
failed links and/or nodes and boot them after
successful fault search and recovery procedures.

   The accounting record memory time period should
optimally be a configurable value in the nodes, since
the time memory length is dependent on the nature of
the node and on the nature of the failure
repair/recovery times in the particular network.

> 5) As an implementation mechanism, hashing or database indexing
>     techniques seem much more reasonable for checking uniqueness
>     than comparison. Say, if you use a hash table you'll be 
>     xoring in all the bytes from the identity (propably a 'long' at
>     a time) to a hash, then looking up the table to see if there's a
>     similar entry.  
>     If there isn't, you're done. If there is, which is relatively
>     infrequent, you'll do a complete check which has some likelihood
>     of producing a YES answer. 
> 
> Jari

Yes, one could try various ways to implement hashing
and database indexing techniques when the total amount
of AVP octet comparisons could be smaller in the
accounting message uniqueness checkings. But, we
must note that one Diameter server would
often serve a great number of Diameter clients
and the number of sending identities (with different
Diameter-Identity part in the Session-Id) may be
therefore great. That would imply that there would
also be a great number of buffers or database
entries (one per accounting records of each
DiameterIdentity).
   Before sorting the Diameter-Ids, they should
be normalized, since in section 4.4 it is stated
that any absent fields should be added to the
Diameter-IDs (with default values) before usage.
   Whatever implementation one would
plan for the handling of the various parts of
the Session-Id and Accounting-Record-Number
pairs, the constant database maintenence
also costs a real amount of processing effort.
   Still, handling Session-Id AVPs and the
Accounting-Record-Number AVPs and normalizing
the Diameter-Identities and maintaining all
the time the accounting records in an indexed
and multi-record sorted database (instead of
just keeping the time zone amount of accounting
records in a roughly by time stamp classified
general buffer) consumes also processing power.
  And, that may be in many operator networks
unnecessary. If the operator network has a
node/link crash influencing the Diameter
clients e.g. once per month, it would be enough
to compare the D flagged accounting records
(if such records occured) and do uniqueness
comparions only between the few D records
and only such that the received accounting records
belonging to the relevant time zone
(having e.g. a 24-12 hours size) around
the crash / link downtime event.
  This would save a huge amount of processing
effort when comparing to the full-time database
maintenance effort and cross-checking of all-
accounting-records-against-all-other-accounting-
records.

So the principle would be to do heavy processing and
significant database operations and uniqueness checkings
1) only when it is needed due to a network failure, and
2) only for the possibly duplicated accounting records.

  The bottom line of this issue is to just allow
economical and efficient implementations what comes
to the accounting record uniqueness checking, as
the uniqueness checking is anyhow just a minor part
from the total network functionality perspective.
Preferably no more processor command cycles than
absolutely necessary should be invested per packet.
  One must also note that the amount of accounting
packets is vastly bigger than the number of
accounting packets in a network.
  The support of the efficient uniqueness checking
would be achieved without adding any new messages
or octets to be sent. Just the setting of 1 bit
in the Diameter header flag set is enough,
typically less often than for one packet in a
billion packets, because the node/link failures
are only very rare and are exception cases. 
  And, this issue is not preventing any Diameter
server or end system performing even the extra
heavy checking, where every accounting record
is compared every time, against every other
accounting record, if someone would like to
do things that way.

-Basavaraj