Subject: [AAA-WG]: Issue 128: duplicate packet detection failure case

From: [email-masked]
Date: Wed, 12 Sep 2001 14:59:43 +0300

Hi Pat,

Some comments & also answers embedded.

Summary:
========

0) May I clarify a bit the description of different
steps in an uniqueness checking process. The 'D' bit
usage is not a new, "competing" uniqueness _checking_
method (for the E2E Identifier pair & Origin-Host
AVP pair checkings), but a marker enabling _efficiency_
boost and working in combination with e.g. the
E2E Identifier & Origin-Host-AVP pair checking method.
So there were 3 basic operations that could be used
even in combination, to prevent message multiplication:

  1.- mark the few potential duplicated messages
      (at Diameter message sending nodes)
      This was the minimal step 1 of Issue 128.
      We could have that even if we would not take the step 2
      of Issue 128. Then we would keep the messaging mechanism
      just as is, and only in some very rare cases need
      to set one single bit ('D') at a message sending
      Diameter node, and save for nearly all messages the
      otherwise mandatory uniqueness checking work in the
      Diameter server.

  2.- check the uniqueness of the marked ones
      (at Diameter server, by E2E Id & Origin-Host AVP pairs)

  3.- remove the found duplicates (either by Diameter server,
      or if the issue 128 step 2, i.e. automatic duplicate
      removal by Diameter client - agent cooperation, before
      forwarding to Diameter server would be enough small
      feature). For this step 2) I understood that it would
      be considered affecting the actual protocol and therefore
      "too much" for at least some parties. But we can do without
      that, keep the existing messaging method (protocol),
      and do only the initial step 1 (marking of possible duplicates)
      and we still get an exceptionally big performance boost
      for a feature: even 2 decades checking speed improvement
      is well possible.

1) The usage of the 'D' bit in by Diameter client
when needed enables e.g. 2 decades faster
uniqueness checkings in the Diameter Server,
as there would be typically e.g. 100 times less
processor commands needed at the Diameter server
to check message uniqueness.

2) The Server would mandatorily compare only then
the received message with the slower (E2E Identifier
pair & Origin-Host AVP pair) procedure when the 
'D' bit is set (which would typically happen in
less than one message in a billion (as links are
most of the time ok, and the message sending is
stopped after the link failure, until the link is
again ok.

3) In accounting the duplicate message prevention
is an important must. The big commercial operators
are at least in some major countries audited by
independent auditors who will demand the operator to
*prove* that its accounting system will not produce any
doubled accounting records. Failure in the audit means
that the operator loses its network service license
until it can prove that the unreliability has been
corrected.

> -----Original Message-----
> From: ext Pat Calhoun [mailto:[email-masked]]
> Sent: 06 September, 2001 17:43
> To: Loughney John (NRC/Helsinki)
> Cc: [email-masked]
> Subject: Re: [AAA-WG]: Issue 128: duplicate packet detection failure
> case
> 
> 
> On Tue, Sep 04, 2001 at 05:59:09PM +0300, 
> [email-masked] wrote:
> > Hi Pat,
> > 
> > Sorry for the delay in responding - I have been quite
> > busy - I have another document that just finished
> > last call.  I was a bit rushed when I submitted
> > the issue for Diameter, it had actually 2 different parts that 
> > are easiest to consider separately:
> > 
> > 1) Marking of the possibly duplicated messages.
> 
> but what's the point? How do you know whether the first copy 
> was received? What about the second copy when sending the third?

The point is that the sender knows which packets are sent
a 2nd/3rd/4th... time and should therefore be the potential
duplicates. The sender does not know which of the possible
duplicates are real duplicates. The receiving node (Diameter
Server as the last possible place) on the other hand has
the visibility to all the material it got via the agents
from the Diameter. But here is the difference:

a) Either the Diameter Server has to check every packet
and searches and decodes and checks quite a lot of octets,
belonging to the Origin-Host string of type DiameterIdentity
(octet string of e.g. 70 octets like
aaa://host.abcdefghij-klmnopq.com:6666;transport=tcp;protocol=diameter)
and the End-to-End Identifier (4 octets) by comparing
two value pairs to other ones, or

b) The Diameter Server checks just 1 single bit in
99.9999...% of the cases and only in one case in over
a billion, AVP searchings, decodings and finally the
comparisons of the long Origin-Host string AVP pairs and
the End-to-End Identifier AVPs could be made, by
checking them, octet by octet.

> In any case, duplicate checking beyond the 'D' bit is necessary.

Yes of course. But, since it is only necessary to check the
_possible_ duplicates (marked with the 'D' bit), instead of 
having to process every Diameter packet contents in more detail,
99.999...% of the record detail checking work (for uniqueness)
is saved.

> 
> > 2) Removal of duplicate messages.
> > 
> > Step 1 is a minimal functionality for enabling the
> > duplicate message checking to be efficient as possible.
> > The Diameter client knows (after hearing no response) 
> > that it is sending the message a 2nd (or 3rd etc.)
> > time (either to the original peer node or an alternate node).
> > 
> > Enhancing the efficiency of checking is the main
> > benefit but it may improve a bit the reliability too. 
> > It also improves the reliability somewhat since the
> > Diameter client has in End-to-End Identifier only 12
> > low order bits of the local time when booting. That is
> > 4096 seconds which is a bit over a hour.
> 
> I'd argue that if a message takes a bit over an hour to make it to the
> server, then the response is moot (and something in the 
> network is broken).

Since the Diameter Base protocol is a basic module
that can be in future extended in ways that are today
even not seen, the Base protocol should be made as
reliable as possible. It could not now easily be assumed
that e.g. message duplication could be less than
maximally prevented. Also, it could likely be 
somewhat premature for us to assume that now and
also in future, any delayed responses are moot.
It would look like a very simple solution if
the 'D' bit would always be set when the message
is a potential duplicate.

Here I was not concerned in first place about a response
but about the sending. Here was a case of sending party
being down.

My issue here was about:
1) effectiveness (number) of comparisons per one message and
2) amount of comparisons done in total for all the messages
   transferred to the Diameter server and
3) reliability if the sending node goes down for 4092
   seconds or for a multiple of that time.

With the 'D' bit usage for the pending packets that
the Diameter client may have in its non-volatile
memory, and packet contents comparison for the 'D'-marked
packet at the receiving end, a duplicate packet would be
identified and found efficiently, also in the case that
the sending Diameter client was down 4092 seconds
(or its multiple). The End-to-End Identifier (and
Origin-Host AVP) pairs could
not do alone this as it is typically changed after
every boot for the next packets to be sent.
(Or otherwise the Diameter should have some other
kind of protocol logic than it currently has.)

Since the 'D' bit would be set only to the possible
duplicates but not to the original, the 'D' bit
provides additional information that the E2E Identifier
does not alone offer: The original (first) message
is differentiated from it duplicates. This gives
useful information about where and when
the duplicates were generated. When using the
E2EIdentifier, the duplicated messages look
all the same, also the original message.
Therefore it is likely a bit more difficult
to track the event that triggered the duplicates,
to improve the network against message duplication
tendency.

(Actually, it would even seem that the way to do
most reliably the duplicate markings and later removal,
the sending Diameter client should use 'D' bit
for marking, and the Diameter Server should
compare more than the Origin-Host & End-to-End
Identifier pairs of a suspected duplicate packet.
Even the whole packet contents of 'D'-marked
packet should be checked, as the job is done
extremely seldom and End-to-End Identifier
is usually different every time after a Diameter
client boot-up after e.g. a Diameter client node
failure.)

> 
> > 
> > This means that with very bad luck, a Diameter client
> > that goes down and wakes up after 4096 seconds MAY send
> > a message with the same End-to-End Identifier, taking from 
> > non-volatile memory an earlier sent (but not yet answered) 
> > pending message and produces a duplicate. Unless, it has 
> > this capability to mark with 'D' bit that the pending message 
> > now resent may be a duplicate.)
> 
> right, but now you have the same problem, right? If a client 
> reboots twice,
> exactly 4096 seconds apart, then the IDs will be similar, and 
> the 'D' bit
> becomes irrelevant since once doesn't really know if it is 
> for the first hour,
> the second hour, etc.

I may overlook something, but it seems that there is a difference:
The first message is not marked with a 'D' bit so that is
different (=unique) if that exists. If the 'D' marked set
of duplicates do not have a one unduplicated "master" message,
then they may look the same after 4092 seconds, as with E2E
Identifier. But, there is a major (e.g. 2 decades) difference
in the uniqueness checking work at the Diameter server end,
since the 'D' bit is so much more efficient to test
(to see whether the slower E2E Identifier & Origin-Host AVP
pairs' search&decoding&string comparisons are needed at all.
Most of the time, there would be no 'D' bit and no need to do
the slower checks therefore.
A Diameter server may have to serve a very big number of 
Diameter clients (which have thus different high order
12 bits in the E2E Identifier => A lot of slower comparisons
needed at Diameter server unless the 'D' bit is used to help
the identification of possible duplicates.
 
> So I am convinced that the protocol is fine as-is, and 
> duplicate checks is
> a little more complicated than just setting a 'D' bit in a header.

Please consider the 2 decades efficiency boost at the
Diameter server, too. Can anyone state a more efficient
(or even equally efficient way here?

'D' bit would be an indicator for 2 decades efficiency boost,
not even intended to cover the whole uniqueness checking alone.

> >   
> > Step 2 is a solution where in addition to the minimal
> > solution of marking the possibly duplicated packets, the
> > duplicates are also removed form the network as quickly
> > as possible, with minimal amount of double-checking.
> > 
> > This mail presents only a simplified way of step 1, as it
> > can be used also as a stand-alone feature (just an additional 
> > flag bit in the Diameter header). Please review the following
> > description, it would help the Diameter Server to avoid
> > the obligation to do a mandatory cross check every single
> > received request message - which should save on processing.
> > 
> > The needed small changes for the step 1)
> > (marking of possibly duplicated packets) to the
> > draft-ietf-aaa-diameter-07.txt are the following:
> > 
> > 
> > 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)
> >                      - 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 is 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 failover, to an
> >                        alternate agent).
> >          r(eserved)  - this flag bit is reserved for future use, and
> >                        MUST be set to zero.
> > 
> > 
> > In:
> > 
> > 5.5.4  Failover/Failback Procedures
> > 
> > ...
> >    It is important to note that multiple identical request 
> or answer MAY
> >    be received as a result of a failover. The End-to-End Identifier
> >    field in the Diameter header along with the Origin-Host 
> AVP MUST be
> >    used to identify duplicate messages.
> > 
> > the above paragraph would be amended as:
> > 
> >    It is important to note that multiple identical request 
> or answer MAY
> >    be received as a result of a failover. The 
> possibly-Duplicated flag
> >    MUST be set by the Diameter client node that performs 
> failover, to
> >    mark those packets that it had sent with no answer 
> message coming from
> >    the primary agent, and which it therefore forwards to an 
> alternate
> >    node. The final destination node of a message MUST check those
> >    messages that have the 'D' bit set, if they can be identified as
> >    actually duplicated messages. The intermediate nodes MAY check
> >    the messages with the 'D' bit set, if they can be identified
> >    as duplicate messages. The End-to-End Identifier field in the
> >    Diameter header along with the Origin-Host AVP MUST be used to
> >    identify duplicate messages among the marked possibly duplicated
> >    messages.
> > 
> > and in:
> > 
> > 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.
> > 
> > paragraph would get one sentence to its end:
> > 
> > ....
> >    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 inspection
> >    MUST be performed at least for such records that arrived to the
> >    Diameter peer in messages having the 'D' bit set.
> 
> well, I don't have a particular issue with the above proposed 
> text, but do question it's need.

   Since it is only necessary to check the _possible_
duplicates (marked with the 'D' bit) that form an extremely small
minority of all the packets transferred, instead of having to
process every Diameter packet contents in more detail,
99.999...% of the accounting record detail checking work
(for uniqueness) is saved.

If the two Session-Id (AVP 263) and Accounting-Record-Number
(AVP 485) pairs would be needed to be mandatorily checked
also for every non-duplicated packet (=nearly all of the
packets) mandatorily, it would mean unnecessary work for
nearly every packet as link failures could be expected to
occur much less often than for one packet in a billion.

If the Diameter client sending packets is booted
due to a temporary failure, and there is only one
working link to an Diameter agent or Server, then
as defined in chapter 9.4, there are possibilities
to still continue:
   "Diameter clients MAY have non-volatile memory
for the safe storage of accounting records over
reboots or extended network failures, network
partitions, and server failures.  If such memory
is available the    client SHOULD store new accounting
records there as soon as the records are created and
until a positive acknowledgement of their reception
from the Diameter Server has been received."
And  after a reboot, the client MUST starting
sending the records in the non-volatile
memory to the accounting server.

  Now, the resending of a packet to the Diameter
agent or Server would be possible (also in the
one link available only -case) if only the
duplicates could be indicated.

  Anyhow, as defined in chapter 3.0 about the
End-to-End Identifier, its high order 12 bits are
initiated to contain the low order 12 bits of
current (boot) time, while the low order 20 bits is
set to a random value. Thus, the End-to-End Identifier
is (usually) different after every boot in the
Diameter logic. This means that e.g. the End-to-End
Identifier would not be usable for the accounting
record duplicate checking. Anyhow, the 'D' bit would
be still possible to mark a possible duplicate
and 'D' bit checking per packet is much faster
than checking every Session-Id (and UTF8String)
and Accounting-Record-Number AVP pair against the
other pair(s), as 99.9999...% of the time no more
than one ('D') bit only needs to be compared.

The sender of a packet always knows if it resends a
packet (to any link that it has or will establish).
Therefore it knows that in the 2nd, 3rd, etc. 
sending, the packet might appear as a duplicate
in a end system, and should therefore get the
'D' bit set as to request the cross-checking
for that particular packet.

> I'm willing to listen to the WG on this one.
> 
> PatC
> 

John