Subject: [AAA-WG]: issue: real-time duplicate detection and proposed change.

From: <[email-masked]>
Date: Fri, 11 Oct 2002 18:28:00 +0300

Hi,

here is the proposal that address the real-time duplicate detection issue
I rised in my previous mail.

The proposal is to add the D flag in addition to hashing techniques mentioned
in AnnexC. The D flag falls within the "other schemes" category already
mentioned in the current base protocol specification.

Br
Marco et all

Description of issue: Real-time duplicate detection
Submitter name: Marco Stura 
Submitter email address: [email-masked]
Date first submitted: 11/10/2002
Document: draft-ietf-aaa-diameter-13.txt
Comment type: T
Priority: 1 
Section: Insert_Section_Number_Here 
Rationale/Explanation of issue: 

I apologize to open this discussion so late but in Nokia we just notice 
the we have a problem while discussing the possible error cases for the
draft Diameter Credit Control Application, which is also used in 3GPP 
Rel5 IMS (IP Multimedia subsystem) to realize real-time credit based 
accounting (i.e prepaid accounting, sometime called token based accounting).

The problem we have is related to real-time duplicate detection of event
accounting request. I briefly summarize the problem below.

In Credit Control Application is possible to perform one-time event for three
different purposes: direct debiting, refund and balance check. The problem
appears with direct debiting and refund.
One time event uses accounting request[event] message and basically when the
action is direct debiting the corresponding amount of money is directly
deducted from the user's account and when the action is refund the corresponding
amount of money is credited in the user's account. 

These use cases require real-time duplicate detection of the received event
request in order to avoid multiple debiting or multiple refund for the same
request. The duplicate detection must be performed and the proper answer 
must be given back to the client immediately so as to grant or to not grant
the service to the end user. In short, within few seconds the service need
to be granted or not granted to the end user, if the end user has to wait too
long before being able to use the requested service (e.g. Instant message)
the user experience will suffer too much.

With the current Diameter base protocol, for every single received request 
the Credit Control Server would need to search possible duplicate among other
request received within a certain backward time window (e.g a day). 
In current wireless GSM network there are several milion of prepaid 
subscriber and we have feeling that is an impossible task for the CC server
to perform real-time duplicate detection with the mentioned approach,
performances will suffer and the answer will be sent too late to the client.

Use of hashing techniques or other schemes help to eliminate the need to do 
full search of received accounting request within a time window as mentioned
in AnnexC.
However, the hashing approach to address real-time duplicate detection hasn't been 
tried in practise and hasn't been evaluated in full.
We beleive that hashing introduce additional complexity to server implementation and
also in finding the proper hashing function, hash table size etc. to minimize
for example collision cases. In contrast other techniques for duplicate detection
are already used, proven to work and operational in live networks with millions of
subscribers(e.g. 3GPP GPRS charging protocol).
This techniques consist in the client marking the possible duplicate upon re-transmission
of the messages. For those not familiar with this technique I suggest to read
the 3GPP technical specifications 32.215
(http://www.3gpp.org/ftp/Specs/archive/32_series/32.215/). Implementations in 3GPP use
this mechanism to also support hot-billing where real-time duplicate detection
is required and is proven to work in operational networks.

For the above mentioned reasons we think that there might be implementation that 
do not make use of hashing techniques and that even do not plan to support these 
techniques in near future.
Thus we believe that a more simple tool to enable optimization of real-time 
duplicate detection should be provided by the base protocol in addition to
hashing techniques or other complex schemes that a server may chose to implement.

We propose that the base protocol to mark re-transmitted messages by dedicating one reserved
bit of the Diameter header to this purpose, server may use D-bit or hashing according
to their implementation. Please note that the way the server implement duplicate
detection (use of D-bit or not) is implementation dependent and does not affect 
interoperability at all.
This proposal was already discussed sometime ago (named D-bit)and was rejected because
the real-time duplicate detection was not seen necessary, we beleive that this requirement 
is now existing due to the above mentioned reasons and proven to work tool to implement 
simple real-time duplicate detection in the server (without adding implementation complexity)
should be offered by the base protocol.

Requested change:

Change chapter 3 as follow

3  Diameter Header 

   A summary of the Diameter header format is shown below. The fields
   are transmitted in network byte order.
	0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |      Ver      |                 Message Length                |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |R P E D r r r r|                  Command-Code                 |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Application-ID                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Hop-by-Hop Identifier                    |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      End-to-End Identifier                    |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |  AVPs ...
      +-+-+-+-+-+-+-+-+-+-+-+-+-

   Version
      This Version field MUST be set to 1 to indicate Diameter Version
      1.

   Message Length
      The Message Length field is three octets and indicates the length
      of the Diameter message including the header fields.

   Command Flags
      The Command Flags field is eight bits.  The following bits are
      assigned:

         R(equest)   - If set, the message is a request. If cleared, the
                       message is an answer.
         P(roxiable) - If set, the message MAY be proxied, relayed or
                       redirected. If cleared, the message MUST be
                       locally processed.
         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 are commonly referred to as an error
                       messages. This bit MUST NOT be set in request
                       messages. See section 7.2.
	   D(uplicate) - If set, the message is a possible duplicate request 
			     due to failover/failback process or re-sending of 
                       record in storage. This flag MUST NOT be set in 
			     answer messages.

         r(eserved)  - these flag bits are reserved for future use, and
                       MUST be set to zero, otherwise an error MUST be
                       sent to the sender.

5.5.4  Failover and Failback Procedures

 Change the paragraph

  When a transport failure is detected, all messages in the queue are
   sent to an alternate agent, if possible. 
  .....etc..

  to

  When a transport failure is detected, all messages in the queue are
   sent to an alternate agent with the D flag set, if possible. 
  ......etc..

8.2  Accounting Session State Machine

  Change the line

  Idle      Records in storage             Send       PendingB
                                           record

  of CLIENT, ACCOUNTING to

  Idle      Records in storage             Send       PendingB
                                           record
							 with D
							 flag set

Change appendix C as follow.

Appendix C.  Duplicate Detection

   As described in section 9.4, accounting record duplicate detection is
   based on the session identifiers. Duplicates can appear for various
   reasons:

      - Failover to an alternate server. Where we close to real-time
      performance is expected, failover tresholds need to be kept low
      and this may lead to a relatively large likelihood of duplicates.

      - A crash of a client at the time it just had managed to send a
      record from a non-volatile memory would likely cause the same
      record to be sent soon after the client has rebooted.

      - Duplicates received from RADIUS gateways.

      - Implementation problems and misconfiguration.

   In some cases the Diameter accounting server can delay the duplicate
   detection and accounting record processing until a post-processing
   phase takes place. At that time records are likely to be sorted
   according to the User-Name contained in them and duplicate elimina-
   tion is easy in this case.

   In other situations it may be necessary to perform real-time dupli-
   cate detection, e.g. when the credit limits or fraud attempts are
   being monitored in real time.

   In general, only the duplicate generation at failover or re-sending of
   record in storage cases is something that can be reliably detected by 
   the Diameter client or Diameter agents. In such cases the Diameter
   client and the Diameter agents mark the request message as possible
   duplicate by setting the D flag. The Diameter server is therefore 
   responsible for the duplicate detection process. When real-time duplicate
   detection is required, this implies a database-like search functionality
   to find duplicate records. Implementors are advised, however, that there 
   exists ways to avoid expensive all-record searches. 

   For instance, it can be usually safely assumed that duplicates appear
   within a time window of longest imaginable network partition, perhaps 
   a day as an example. So only records within this time window need to be
   looked at. Secondly, hashing techniques or other schemes, such as the use
   of the D flag in the received messages, may be used to eliminate the need 
   to do a full search even in this set except for rare cases. 

   The following is an example of how the D flag may be used by the server to 
   detect duplicate records.
   
   Diameter server MAY check the D flag of the received message to determine
   if this record is a possible duplicate. If the D flag is set in the request
   message, the server search for the duplicate within the above mentioned time
   window. This way database search is only required for those received records 
   whose the D flag is set. Since in today networks link failures, server breakdown
   or other similar events are very rare, this simple approach efficiently 
   optimize performances of the duplicate detection process.
   It may happen that the original record is received after the D flag marked
   record because they did experience different delay in their way to the
   server. For this reason it is necessary for the server to buffer the D flag
   marked records for a short time period, as an example 10 or 15 minutes, and
   check every record received within this time period against the buffered
   D flag marked records.

---

From: Bernard Aboba <[email-masked]>
Date: Fri, 11 Oct 2002 13:30:18 -0700 (PDT)

Assigned Issue 372.