Subject: [AAA-WG]: Request for closure on issue 235

From: <[email-masked]>
Date: Wed, 20 Feb 2002 18:09:10 -0600

Hello,

Issue 235 was discussed at IETF52 and is still open and needs to be
closed. I have not seen any negative views on adding the "D" bit as
part of the base specification. The "D" bit indicates potential
duplicates of accounting messages.

The "D" bit provides performance enhancement w.r.t the process of
checking for duplicate records. While other mechanisms such as
post-processing and brute force (check every record against every
other record) are possible, having the "D" bit would make the nodes
that process these records only check for those records that are
marked as potential duplicates. So the "D" bit can be treated as an
optional mechanism for implementations that would prefer to do
duplicate checking based on this flag.

Resolution on this issue would be one step closer to getting the base
Diameter spec out as PS.

-Basavaraj

The details of the issue and change requested are as follows:

----------------------------------------------------------------

Issue 235: 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
Comment type: T
Priority: 1
Section: 3.0, 9.4
Rationale/Explanation of issue: See below

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)  - these flag bits are reserved for future use, and
                       MUST be set to zero, otherwise an error MUST be
                       sent to the sender.

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 or proxy.
                       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)  - these flag bits are reserved for future use, and
                       MUST be set to zero, otherwise an error MUST be
                       sent to the sender.

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 inspection MUST be performed at least for such records
   that arrived at the Diameter peer specifically in accounting
   messages which have the 'D' bit set.

Rationale/Explanation of issue:
===============================

If a 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. 
With more and more "hot billing" systems and prepaid billing for
packet data becoming prevalent it becomes a requirement for accounting
messages (records) to be sent far more frequently and also enabling
speedy evaluation for accuracy and uniqueness.

For accounting, the section 9.4 (Fault Resilence) 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 with
these identifiers against the others, to detect duplicate accounting
messages.  

However it is far more efficient to o first check if the Accounting
Request sender has flagged the message to be a 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 sending node failure or the receiving node failure or the
communication link itself failing. e.g. physically damaged. When the
sending node is redirecting the traffic to an alternate peer or able
to communicate again after a temporary link failure to the primary
peer, it may send again messages that have not yet been acknowledged
by a recipient node.) 

Duplicates are generated very seldom. (Typically just a few packets,
for eg. after a link failure case.) Therefore duplicate checking
all-against-all, by seems a processing intensive work and one that is
unnecessary to be performed by accounting servers (by the Diameter
server or a billing system). 

The 'D' bit would be 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 at the end system than a non-marked original
accounting message. This is the case with any duplicate occurrence
scenario, but is 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 scheme proposed here does does not limit the Diameter Server or
billing engine to do the uniqueness checking in any other
way. (eg. all accounting records checked against each other, by the
long AVP pair octet strings).

---

From: <[email-masked]>
Date: Thu, 21 Feb 2002 09:56:23 +0200

Hi Basavaraj,

The editors have discussed this issue, and have some possitive
feeling towards this.  I believe that Jari Arkko was giving
this a close examination and should shortly send some comments
to the list.

thanks,
John

> -----Original Message-----
> From: Patil Basavaraj (NET/Dallas) 
> Sent: 21 February, 2002 02:09
> To: [email-masked]
> Subject: [AAA-WG]: Request for closure on issue 235
> 
> 
> 
> Hello,
>

---

From: <[email-masked]>
Date: Mon, 25 Feb 2002 14:09:19 +0200

> From: ext Johan Johansson [mailto:[email-masked]]
> Sent: 25 February, 2002 15:03
> To: Loughney John (NRC/Helsinki)
> Cc: Patil Basavaraj (NET/Dallas); [email-masked]
> Subject: Re: [AAA-WG]: Request for closure on issue 235
> 
> 
> Just one question: why is it limited to accounting messages? 
> As far as I 
> can tell the bit means "resent" and I can't instantly think of why it 
> wouldn't be just as good for non-accounting requests.
> 
> j
> 
> [email-masked] wrote:
> 
> >(possibly) D(uplicated)

---

From: <[email-masked]>
Date: Mon, 25 Feb 2002 14:11:23 +0200

Hi Johan,

- take 2, fingers a bit stiff on a Monday ...

> As far as I can tell the bit means "resent" and I can't instantly think 
> of why it wouldn't be just as good for non-accounting requests.

I will let Basavaraj provide the definitive answer, but I do agree
that it could be used elsewhere, but in accounting it may be the
critical place for this functionality.

It is not impossible to delete the first sentence below.

John

---

From: <[email-masked]>
Date: Mon, 25 Feb 2002 16:50:12 -0600

Hello Johan,
Comments inline:

Johan Johansson [[email-masked]] wrote:

>Just one question: why is it limited to accounting messages? As far as I 

The 'D' bit *can* be applied to any diameter message but there is
already a mechanism that uses the e2e identifier in the Diameter
header which helps in duplicate detection of Diameter messages. 
Accounting records have uniqueness constraints extending beyond the
control of the diameter server. The 'D' bit is intended to help
implementations maintaining such uniqueness constraints.

-Basavaraj

---

From: Jari Arkko <[email-masked]>
Date: Tue, 26 Feb 2002 12:39:09 +0200

> Several folks have checked this and believe that this would work.
> So, unless there are any remaining objections, I am going to accept
> this change & modify the base accordingly.

I'm one of those folks. According to my analysis, it
does appear to work. Inclusion in Diameter might not
be clear yet, however and I would appreciate other
people's view on this. Bernard?

1. CORRECTNESS

But let's start with the part about this working.
Basically, the scheme introduces a new bit for
accounting records, to signify when the sender
of a record thinks he may have sent duplicates.
The receiver uses this information to do a faster
duplicate lookup. Given that the records may arrive
in any order, this lookup isn't as trivial as one
might expect, however. Let's study the possible
orderings between the Non-D record (the original)
and the D record (the duplicate), including loss
of packets:

   a. 1) Non-D, 2) D: Here the arrival
      of the D record triggers search
      against all records. Duplicate is found.

   b. 1) D, 2) Non-D: First the D record
      arrives, an all record search is
      performed. The D record goes to a special
      pool, and the Non-D record, when it arrives,
      is checked against this pool and duplicate
      is found.

   c. 1) D: A search against all records is
      performed, but no result hence the record
      is accepted.

   d. 1) Non-D: A search against the pool is
      performed, but no result hence the record
      is accepted.

In conclusion, the method requires the following:
  1. Checking all D-marked records against *all*
     other records.
  2. Checking all regular records against those
     stored in the D-pool.
  3. The D-pool contents must have some expiration
     time after which the records are moved out of
     the pool.

3. ALTERNATIVE SCHEMES

The alternative ways to perform duplicate record matching
include the following:

- Matching all records against each other (current
  base mechanism)
- Matching all records against recent other records
  (in the same time window as the D pool would expire).
  This is an implementation enhancement of the current
  base mechanism. However, as with the pool scheme,
  the period may be unexpectedly long given that
  network partitions can occur and permanent storage
  can be employed by NASes during this period.
- Correlating all records by User-Name first before
  trying to find duplicates. This would reduce the
  search space substantially more than the previous suggestion.
- Relaxing on accounting-level duplication detection
  requirements and performing this latest at the billing
  state. (Diameter end-to-end identifier duplication
  checking would still be necessary.)

4. NEED FOR D BIT

Basically, the D bit reduces the need to check records
against all other records. These all-record searches need
to be done only when D bit records arrive, but not for all
arriving records.

However, it still is necessary to perform all-record searches
in cases a-c described in section 2.

Given this, it also appears that the D bit method should use
the same optimisations as the regular scheme, e.g. doing the
checks only against recent records or just the user's records,
not the history of all possible records. More interestingly,
it does not appear to be possible to do the all record searches
without employing either (1) data base indexing methods or perhaps
(2) User-Name correlation.

In conclusion the D bit method allows us to avoid most all-record
searches. However, some are still needed and as a consequence the
Diameter accounting nodes must employ some sort of database
indexing techniques to perform such searches in reasonable time
anyway. Also, N x N searches were never possible anyway on
the current spec and similar data base searches would have been
necessary there as well. So, the true advantage of the D bit
method can be described as follows. Let's assume a 1% duplicate
rate and a minute where 2000 records arrive (20 duplicates).
Using the current scheme, 2000 data base indexing operations
would have to be performed. With the D bit scheme, 20 data base
indexing operations would be needed to the full data base,
and 2000 operations to search things from the smaller pool.
In practise this would probably be a database operation as well,
though perhaps it could be kept completely in CPU memory so
it would be faster. Assuming similar speed, there'd be no
performance benefit to the D bit method, a 1% CPU time increase
instead. Assuming 1/10 speed, the D bit saves 89% of CPU time.
YMMV.

---

From: <[email-masked]>
Date: Tue, 26 Feb 2002 14:27:03 -0600

Comment below:

><PRC> The conclusion that I came up with is that a search is required 
>regardless of whether the D bit was set or not, because you cannot 
>guarantee the order in which the packets are received. 
>
>So what is the gain here? 
 
Rather than checking every record against every other record, you
would only check a very small set of records that are marked with the
"D" bit against every other record.
 
>PatC 
 
-Basavaraj

---

From: <[email-masked]>
Date: Tue, 26 Feb 2002 14:49:10 -0600

Jari Arkko [[email-masked]] wrote:

>Barney Wolff [[email-masked]] wrote:
>
>>The D-bit is an optimization, so we are entitled to assume that another
>>optimization, namely using User-Name as a primary search key, is also
>>taken.  

But the User-Name does not necessarily indicate that it is a possible
duplicate. 

>>In that case, the two searches are likely to take the same time.
>
>I think one of the central question to answer is why the User-Name
>optimization is not sufficient. Basavaraj, can you comment on that?

Simply because the "D" bit based optimization mechanism is a
significant improvement in terms of performance. And by this I am
refering to the number of records that need to be checked. So if a
server needs to determine duplicates (outside the premises of
post-processing methods), having the "D" bit would make this
processing more optimal. 

>Jari

-Basavaraj

---

From: <[email-masked]>
Date: Wed, 27 Feb 2002 10:06:58 -0600

Pat R. Calhoun [[email-masked]] wrote:
 
>> 
>> My problem with the D-bit is that it invites doing something in 
>> real  time that does not need to be done in real time, and puts a 
>> burden on  the sender while saving very little if anything for the 
>> receiver. The  biller is going to sort the records anyway, and 
>> finding adjacent 
>> duplicates is trivial with or without the D-bit. 
>> 
>> Barney Wolff 
>
>But there are cases when billing actually takes place in real time, 
>called prepaid charging. So the usage of the D-bit would make a 
>significant performance improvement for the receiver in these cases. 
>
><PRC> I seriously don't understand the insistence on using User-Name 
>for the lookup. 
>
>Not only is there a Session-Id, which is unique, but 
>there is also an accounting record number. Those two items are 
>guaranteed to be unique, and therefore are a great way of checking 
>for dups. I don't understand the mechanism by which records are put 
>in a "temporary" buffer, as opposed on written on disk. You need to 
>write ALL records in this "temporary" buffer (if it even exists) in 
>order to check for duplicates. 
>
>What really confuses me here is how the checks are done. Using a 
>single bit 'D' isn't really useful for a lookup. 
 
It is useful. Either you believe that every record is a potential
duplicate and hence do duplicate checks of every record against every
other record (records within a certain duration +/- 24 hrs for eg.) or
you do the check for duplicates only on records that have the "D" bit
marked explicitly. So the "D" bit improves the performance by a
significant enough margin.
 
>Some additional data is required, and whether the 'D' bit is set or
>not, the message must be cached for duplicate check (to handle out of
>order packets).  
 
I agree, but repeating what I have been saying, the "D" bit reduces
the number of records that are checked for duplicates.
 
>Confused, 
 
Let me see if I can send a more detailed explanation that would
help. 

-Basavaraj

---

From: <[email-masked]>
Date: Wed, 27 Feb 2002 11:07:35 -0600

Jari Arkko [[email-masked]] wrote:

>The prepaid case is a valid one. So D-bit is useful when
>the following condition is fulfilled:
>
>RealTimeBilling AND PoolLookUpFasterThanSessionIdLookUp AND
>PoolLookUpFasterThanUserNameLookUp
>
>Since the D-bit method also requires SessionId look-ups in
>certain cases, we always need a reasonably fast look-up
>anyway i.e. linear list of all records is not acceptable for
>D-bit either. So this really boils down to the question of
>whether the pool lookup (small and likely in RAM) is faster
>than a real record lookup (likely on disk but index likely
>in RAM).

In certain cases, the pool lookup (in RAM) would be preferred and
hence the need to have the "D" bit.  I agree with your assesment of
when the "D" bit is applicable.

-Basavaraj

---

From: <[email-masked]>
Date: Wed, 27 Feb 2002 13:43:10 -0600

Jari Arkko [[email-masked]] wrote: 

>>RE: [AAA-WG]: Request for closure on issue 235> <PRC> But what about
>>packets that are received out of order (D bit is received First)?
>
>1. D bit record is first received, and you search all records, no
>match. you also search the pool, no match. you put it to a pool.
>
>2. non-D bit record is received after that, and you search the pool
>(not all records)
>
>So, using the current scheme you do 2 all-records searches
>total. Using the d-bit method you do 1 all-records search and 2
>pool searches. Worth it? If the pool searches are significantly faster.
>(Basavaraj, you do have to make some full searches anyway!)
>

Yes. But it is always preferable to do these checks for duplicates on
a small set of "D" marked records as opposed to checking every
received record against every other record all the time.

-Basavaraj

---

From: "Pat R. Calhoun" <[email-masked]>
Date: Wed, 27 Feb 2002 16:17:04 -0800

> Do people believe generating the D-bit reliably is a trivial burden
> on the sender?  If  so then it does no harm, because the receiver
> can always ignore it.  But I don't think  it's that trivial.  As a
> receiver I'd be very wary of depending on the sender to trigger 
> the dup check.

Check, and if receivers aren't likely to trust the sender to inform
it of a duplicate, does having this in the protocol even make sense?

PatC

---

From: <[email-masked]>
Date: Thu, 28 Feb 2002 09:59:37 -0600

Barney Wolff [[email-masked]] wrote:

>Consider gateways from RADIUS or other AAA protocols.  Consider a rebooting
>NAS - is it sure what it might have sent before it crashed?
>
>As a sender, what's my liability because you as receiver double
>charged or locked out some customer because I failed to set the
>D-bit and you relied on my perfection?  Guess what - if it's not
>$0.00 I'm going to set the D-bit on *every* record.

Hopefully there are no lawyers snooping on the communication lines :)
but for the sender there is no obligation other than complying to the
specification. So the liability is absolutely $0.00, at least when one
does what is specified to be the proper behavior in a failover case by the
specification.  

After a link/node failover, the Diameter node that is sending
accounting records, may have in a buffer
"sent-but-not-yet-acknowledged" accounting records a few records  
remaining.
If (and when) the node decides to send them after failover procedures,
then it should mark them with the D-bit as possible duplicates (for
safety). That is all it needs to do. The sender has no other
responsibility  here, and even that "task" is to be performed for eg.
one record for every billion or even less often, the actual ratio
depends on how many packets on an average are sent between a link/node
crashes. 

>Barney

-Basavaraj

---

From: <[email-masked]>
Date: Thu, 28 Feb 2002 16:27:30 -0600

Jari Arkko [[email-masked]] wrote:

>Ok, so after watching the mailing list discussion and having wondered
>about this for a while also in a conference call with the authors
>yesterday... and my proposed secondary method... I think we are not
>going to get consensus for this. Instead, we should add some text in
>the Base that discusses duplicate elimination.
>

I believe the "D" bit method for duplicate checking is quite simple
and hence surprised that no concensus could be reached. The "D" bit
would be quite useful in scenarios where real-time (or near RT)
accounting is required. But I have made all these arguments previously
as well. So....

>Some of the comments said that the method does not work. Maybe
>we could have finally agreed that it does work, because it does appear
>to work, at least my analysis said so. But even so, two concerns have
>been raised that are harder to agree on:
> 1) true benefit of the RAM check vs. the index check and

There are benefits.

> 2) behaviour in reboot, RADIUS interoperability etc. situations.

Behavior in reboot can be specified. I cannot say that I have looked
at the RADIUS interoperability issue.

>
>All is not lost however, for the D-bit forever. Specific applications
>*can* introduce an AVP for the same purpose, if they like. However,
>I hope the new text builds some understanding of the issues as well
>so extension designers and implementors can take a wider understanding
>of the issue. 

Well, I hope so, but I am not very optimistic.

>If my proposed scheme works -- I'm not 100% sure --
>I would think that would be preferred, though.

Well, if you ask me, the "D" bit is preferabble :)

-Basavaraj