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

From: "Patil Basavaraj (NET/Dallas)" <[email-masked]>
Date: Fri, 9 Nov 2001 22:35:58 -0600

Issue XXX: Enabling efficient accounting record uniqueness checking
Submitter name: Basavaraj Patil
Submitter email address: [email-masked]
Date first submitted: November 9, 2001
Reference: 
Document: Base-08-alpha02
Comment type: T
Priority: 1
Section: 3.0, 9.4
Rationale/Explanation of issue: 

If the Diameter server does not have any indicator in the received
Accounting Requests for the message being potentially duplicated,
the Diameter server (or a separate Accounting System) would have
to do a vast amount of unnecessary work just for the Accounting
Request uniqueness checking. Currently the issue of billing is becoming
more and more critical. Applications that include prepaid billing for
packet data
requires very frequent accounting messages to be  sent. (and
speedy evaluations in the receiving end system).

For accounting, section 9.4 (Fault Resilience) defines
that duplication detection must be based on the
inspection of the Session-Id and Accounting-Record-Number
AVP pairs. The current draft text assumes that every
accounting message would be cross-checked this way against
the others, to detect duplicate accounting messages.

It could potentially be of the order of  many tens of times more
efficient
uniqueness
checking to first check if the Accounting Request sender
has flagged the message to be potential duplicate.

(Duplicate messages may be generated in the
exceptional cases when a communication link between
Diameter peers goes down. This could happen due to
the sender node crash or the recipient node crash or
the communication link itself becoming e.g. physically
damaged. When the sender is redirecting the traffic
to an alternate peer or able to communicate again
after temporary link failure to the promary peer,
then it send again such messages that had not yet
been responded by a recipient node.)

The section 8.8 defines the Session-Id AVP format as:
<DiameterIdentity>;<high 32 bits>;<low 32 bits>[;<optional value>]
= <DiameterIdentity> + 4 + 4 + N octets.

And, the Diameter Identity is (after the compulsory
addition of possibly absent default values prior
to the comparison) in the example of section 4.4:
aaa://host.abc.com:6666;transport=tcp;protocol=diameter
= 55 octets.

Using the section 8.8 example for the optional value
at the end of a DiameterIdentity we get:
aaa://host.abc.com:6666;transport=tcp;protocol=diameter;[email-masked]
8
= 73 octets.

Accounting-Record-Number is Unsigned32 = 4 octets.

=> The two AVPs (Session-Id and Accounting-Record-Number)
would have to be searched from every single accounting message
and compared to sorresponding AVP pairs in other accounting
messages received by the end system. This means that
e.g. 77 octets of every acconting message would
have to be compared to e.g. 77 octets of the other
accounting messages (received withing a resonable
time frame, e.g. withing 24 hours), to detect
duplicate accounting messages caused by e.g. temporary
Diameter client node failures (that typically are corrected
at least within one day).

Duplicates are generated very seldom. (Typically
just a few packets, not from emptyness but after a
link failure case. This means e.g. less than one
duplicate message per a billion unique messages.)
Therefore duplicate checking all-against-all, by
70-80 octet strings, seems much too massive work
and unnecessary to be performed in accounting
(by the Diameter server or a billing system).

The 'D' bit is being set for all such accounting
requests that were pending an application layer ack
when the connection went down, whether they are
resent on a connection to the same peer or an alternate
peer.

In failover scenarios, duplicate checking may not necessarily
be done in the Diameter Server. It may alternatively
be done in a billing engine. In that case the
billing engine should get the 'D' bit information
from the Diameter header, as delivered together with
the payload.

(It should be noted that the potentially duplicated
accounting message may arrive earlier to the end system
than a non-marked original accounting message. This is
the case with any duplicate occurance scenario, but
not a problem as the end system should anyway have
some time buffer, e.g. 24h or 12h, for the received
accounting records to be checked for duplicates.)

The significant benefit achieved achieved here
is the decrease of uniqueness checking processing
comparisons 1) from e.g. 77 octets to 1 bit and
2) from cross-comparing all accounting messages
in the time buffer against each other to comparing
just the very few (e.g. one in a billion or less)
potentially duplicated accounting messages to all
other accouting messages in the uniqueness checking
time buffer.

The End-to-End Identifier could in theory be also
utilized by the uniqueness checkings in accounting
but has not been defined there the method. Additionally,
the End-to-End Identifier has recently been considered
to be unique only during a very limited time period,
e.g. 4 minutes, which would not be always enough
when e.g. a sending Diameter client node is in temporary
isolation due to a network failure for several hours.

The proposed efficient checking does not forbid
the Diameter Server or billing engine to do the
uniqueness checkings also in the massive way
(all accounting records checked against each other,
by the long AVP pair octet strings), but that would
be left a voluntary task if some Diameter servers or
end systems are wanted to do it in that (extremely
thorough, but also quite processor effort consuming) way.

A bit related email discussion history:
There was a bit related email discussion in a small
side branch of the Issue 128 commenting.
It was wished by some that no new protocol messages would be
added (and therefore no new messages nor any new octets
to be sent are proposed in this new issue).
Anyhow there was a question if an indicator
('D' flag) would be used to indicate potential
duplicates. It was commented by the Diameter draft
editor that for authentication late sent messages
(e.g. after a hour) could be considered moot. But
for accounting he did not have a particular issue
but was willing to listen to the WG but that
item ('D' bit check for accounting messages) did
not get yet much discussion or a clear resolution.

Requested change: 

In section 3.0  Diameter Header

...
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |R P E r r r r r|                  Command-Code                 |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

would be:

      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |R P E D r r r r|                  Command-Code                 |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

and

         E(rror)     - If set, the message contains a protocol error,
                       and the message will not conform to the ABNF
                       described for this command.  Messages with the
                       'E' bit set is commonly referred to as an error
                       message. This bit MUST NOT be set in request
                       messages. See section 7.2.
         r(eserved)  - this flag bit is reserved for future use, and
                       MUST be set to zero.

would get one new flag bit 'D':

         E(rror)     - If set, the message contains a protocol error,
                       and the message will not conform to the ABNF
                       described for this command.  Messages with the
                       'E' bit set is commonly referred to as an error
                       message. This bit MUST NOT be set in request
                       messages. See section 7.2.
         (possibly) D(uplicated)
                     - This bit is defined only for Accounting Requests,
                       sent by a Diameter node.
                       If set, the message is possibly a duplicate,
                       and must be later checked by a recipient node
                       if it really is a duplicate. If sending a
                       message for first time, this bit MUST be cleared.
                       This bit MUST NOT be set if an answer message
                       (about e.g. a protocol error) has been got for
                       an earlier similar message. It can be used only
                       in cases where no answer has been got from the
                       primary agent for a message and the message is
                       sent again (e.g. due to a failover, to an
                       alternate agent or to a recovered primary peer
                       node).
         r(eserved)  - this flag bit is reserved for future use, and
                       MUST be set to zero.

and in section 9.4  Fault Resilience

   ...
   Diameter peers acting as clients MUST implement the use of failover
   to guard against server failures and certain network failures.
   Diameter peers acting as agents or related off-line processing
   systems MUST detect duplicate accounting records caused by the
   sending of same record to several servers and duplication of messages
   in transit. This detection MUST be based on the inspection of the
   Session-Id and Accounting-Record-Number AVP pairs.

the above paragraph would get one sentence to its end:

   The inspect MUST be performed at least for such records
   that arrived to the Diameter peer in accounting messages
   having the 'D' bit set.

---

From: "Jari Arkko" <[email-masked]>
Date: Sat, 10 Nov 2001 08:22:28 +0200

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.

    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).
    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? 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?

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

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?

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

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

---

From: Bernard Aboba <[email-masked]>
Date: Sat, 10 Nov 2001 08:41:22 -0800 (PST)

Yes, these are the issues that seem to mitigate against use of a 'D' bit.