Subject: RE: [AAA-WG]: Issue 93: End-to-End Identifier

From: "Bob Kopacz" <[email-masked]>
Date: Fri, 12 Oct 2001 15:42:25 -0400

Hi Pat,

I'm sorry to dredge this up, but I think there is a flaw here, so would
like to re-open issue#93 and propose a solution.

Base-Draft-08-alpha01 says:

   End-to-End Identifier
      The End-to-End Identifier is used to detect duplicate messages.
      Upon reboot, the high order 12 bits are initiated to contain the
      low order 12 bits of current time, while the low order 20 bits is
      set to a random value.  Senders of request or answer messages MUST
      insert a unique identifier on each message, by incrementing the
      identifier by one (1).

I'm thinking that, if the goal of the 12 time bits is to guarantee
unique identifiers across reboots, then the end-to-end identifier's
high-order 12-bits would need to be set to the current time's low order
12 bits every time an end-to-end identifier is generated, not just upon
reboot.

Then you would be guaranteed to produce unique identifiers across
reboots provided that you meet the following criteria (which I lifted
from earlier emails discussing this issue):

1. the device takes longer than a second to reboot

2. no transaction is kicking around for longer than an hour or so 
   (2 ^ 12 seconds)

3. the transaction rate (the rate at which the identifier is incremented) 
   is no greater than a million per second (2 ^ 20).

The flaw: If the end-to-end identifier's 12 high-order bits are
initialized only upon reboot, then there is no guarantee that upon
reboot, a node wouldn't be sending the same end-to-end identifiers he
was sending just a few seconds before the reboot.  For example, suppose
a node initializes his end-to-end identifier's 12 high-order bits only
upon reboot.  Suppose this node is booted at time T, stays up for 4095
(=2^12-1) seconds, and is rebooted at time T+4096.  Then in each of
these incarnations, the node would be using the same value for the 12
high-order bits of the end-to-end identifier.  And the end-to-end
identifiers used in the last few seconds of its previous life might be
reused in the early transactions of its new life.

Of course, if the end-to-end identifier's 12 high-order bits are updated
every second, then the end-to-end identifier jumps by about 2^20 every
second.

I don't think there are any time bits that will help if you only want to
init the high-order End-to-End Identifier bits upon reboot, so either go
with updating the high-order bits every second, or get rid of it
altogether and just init the End-to-End Identifier to a 32-bit random
number upon reboot.

The other comment I have to make is about the sentence "Senders of
request messages MUST ... increment ... the identifier by one (1)".  The
"increment by 1" requirement seems to be an over-specification which
imposes restrictions on the message originator's implementation, is
undetectable by the message's recipient, and doesn't benefit the
message's recipient.  The previous thread concluded that a receiver
could not make use of the "increment by 1".  Chiefly, a recipient may
receive an unordered and vanishingly small percentage of a client's
Diameter messages.

An end-to-end identifier which jumps by about 2^20 every second makes
the unuseful "increment by 1" even less useful, so I propose getting rid
of it altogether.

Revise the End-to-End Identifier specification as follows:

   End-to-End Identifier

      The End-to-End Identifier is used to detect duplicate messages.
      Whenever an End-to-End Identifier is generated, the high order
      12 bits are set to contain the low order 12 bits of current
      time, while the low order 20 bits are set to a value that ensures
      a unique identifier on each message.

Bob K.

---

From: Mark Eklund <[email-masked]>
Date: Sun, 14 Oct 2001 10:06:13 -0400

Bob,

 >       a unique identifier on each message.

I agree the current implementation doesn't work, but wouldn't your
suggestion limit Diameter to around a million calls per second?  I'd
prefer something like

   End-to-End Identifier

      The End-to-End Identifier is used to detect duplicate messages.
      Upon reboot, the End-to-End Identifier SHOULD be initialized to
      a number that would come after the last End-To-End identifier
      before reboot.  Note that since wraparound is possible, if the
      last End-To-End identifier is 0xffffffff, 0 would be a valid
      initializer after reboot.  If it is not possible to maintain
      identifier state between reboots, the identifier SHOULD be
      initialized to a random value.

If there is some way to combine sentence two and three using some magic
term that means after, but allowing wraparound, please suggest it.

Also note that my wording doesn't require the new End-To-End
identifier to be exactly one greater than the last End-To-End
identifier before reboot.  This allows you to checkpoint once every
million times I.E.

main()
{
    int e2e;
    int e2echeckpoint;

    e2e = read_checkpoint();
    e2echeckpoint += 1000000;
    write_checkpoint(e2echeckpoint);

    while (true) {
        /* packet create code */
        if (++e2e == e2echeckpoint) {
            e2echeckpoint += 1000000;
            write_checkpoint(e2echeckpoint)
        }
        /* other code */
    }
}

-mark

---

From: Pat Calhoun <[email-masked]>
Date: Sun, 14 Oct 2001 16:33:07 -0700

hmmm... I'm torn. I think that Bob's suggestion solves the problem, but
Mark's seems to be on a completely different track. What does the WG
think is best?

PatC

---

From: Barney Wolff <[email-masked]>
Date: Mon, 15 Oct 2001 00:59:03 -0400

Making the identifier start random on reboot is no better and no worse
than making the hi-order 12 bits depend on time and the rest random, as
the reboot interval is itself random.

Making the id depend on the time of the request depends on ensuring
that time can never go backward or noticing when it does and adjusting
the remaining bits to compensate.  Yes, I have seen NTP go backward,
when network paths or queues make forward and reverse one-way delays
significantly different for a while.

If one is going to require no duplicates within an hour at a 
request rate of a million per second then a 32-bit id is just
barely adequate even with perfect state memory across reboots, so any
algorithm that does not assume state memory will necessarily fail.

The only solution I see is to make the id longer.  A 64-bit id started
at a random value on reboot would give a negligible probability of
duplication.

The point of incrementing by 1 each time is to avoid exhausting the
id space faster than necessary.  Obviously it does not have to be
done perfectly, but I cannot imagine an implementation deliberately
choosing a larger increment.

Barney Wolff

---

From: Mark Eklund <[email-masked]>
Date: Mon, 15 Oct 2001 09:42:30 -0400

---

From: "Bob Kopacz" <[email-masked]>
Date: Mon, 15 Oct 2001 10:25:09 -0400

Hi,

> choosing a larger increment.

I was thinking that the "increment by 1" might cause complications
for multi-process Diameter implementations.

For example, imagine a Diameter server implemented as three
communicating processes: The NASREQ application is one process.  The
Mobile-IP application is a second process.  And there is a third
lower-level process which handles the Diameter base protocol and the
TCP/SCTP connections.  When the NASREQ application or Mobile-IP
application originate a message, they pass it to the lower-level
process for transmission.

If there is an "increment by 1" rule, then the applications would
need to access some common "end-to-end-identifier allocator".  Or
the applications would have to let the lower-level process assign
the end-to-end-identifier and return it to the application process.

If there wasn't an "increment by 1" rule, than each application
could manage its own end-to-end-identifier allocation, as long as it
didn't clash with the end-to-end-identifiers allocated by other
processes.  To ensure a non-clash in this example, the NASREQ
application could assign even-numbered end-to-end-identifiers, while
the Mobile-IP application could assign odd-numbered
end-to-end-identifiers.  In this case, then, each application would
be incrementing by two rather than one.

Bob K.

---

From: Mark Eklund <[email-masked]>
Date: Mon, 15 Oct 2001 11:18:22 -0400

Barney,

 > the reboot interval is itself random.

Agreed.

 > significantly different for a while.

Good point.

 > algorithm that does not assume state memory will necessarily fail.

Is this a reasonable requirement?  Should we expect that when we are
processing a million of packets a second that there will be an one
hour network latency?  

 > at a random value on reboot would give a negligible probability of

Can we assume that at whatever rate we send requests, the round trip
time will never be so long that you will have 2^32 outstanding
packets?  If this is not true, we MUST use your suggested method.

The other solution (if the answer to the above is yes) is to
checkpoint the generated identifiers between reboots.  If a server is
capable of handling millions of packets a second, I would assume it
could also checkpoint where it is.  For slower servers, a random
number should be sufficient.  For example, a server that only generates
one thousand of packets a second and a network latency of 60 seconds
would have a 1/35791 chance of repeating the same numbers when using a
random 32 bit initializer.  (60 * 1000) / 0xffffffff = 1/35791

-mark

---

From: Mark Eklund <[email-masked]>
Date: Mon, 15 Oct 2001 11:19:34 -0400

---

From: Barney Wolff <[email-masked]>
Date: Mon, 15 Oct 2001 13:47:36 -0400

> processing a million of packets a second that there will be an one

Well, it didn't come from me. :)  The catch is that reasonable numbers
leave a significant chance of duplication with a 32-bit id, if there
is no non-volitile storage.  Not significant for a single client, but
in a large network over time it would surely happen.

> packets?  If this is not true, we MUST use your suggested method.

The problem is not RTT, but MSL - how long something can be stuck
somewhere in the chain of things between client and server.  With
random ids, you don't need 2^32 to start to have a risk of a false
duplicate.

I'm not pushing strongly for a 64-bit id, because I don't think missing
a duplicate is such a catastrophic event as to require it.  But if
people are going to put extreme requirements on Diameter, that's the
only solution in the absence of NV storage.  (Of course it's the client,
not the server, that is likely to be lacking such.)

Barney Wolff

---

From: "Bob Kopacz" <[email-masked]>
Date: Mon, 15 Oct 2001 16:56:26 -0400

Hi Mark,

> -----Original Message-----
> From: Mark Eklund [mailto:[email-masked]]
> Sent: Sunday, October 14, 2001 10:06 AM
> To: Bob Kopacz
> Cc: Pat Calhoun; aaa-wg
> Subject: RE: [AAA-WG]: Issue 93: End-to-End Identifier
> 
> 
> Bob,
> 
> Bob Kopacz writes:
>  > Hi Pat,
>  >
>  > [... blah blah blah]
>  >

This didn't occur to me.  So your idea is probably better.