Subject: [Anima] GRASP issue 56: Change Session-ID to 32 bits?

From: Brian E Carpenter <[email-masked]>
Date: Wed, 19 Oct 2016 09:04:02 +1300

56: Change Session-ID to 32 bits?

MR: Given that CBOR has only 1,2, and 4 byte uintegers, why do we have a 24-bit
session-id?

BC: Well, it's a hangover from the pre-CBOR TLV format. But I think it's true that we'd
increase the average message size by making it 32 bits, since there are a lot more random
numbers between 2^24 and 2^32 than between 1 and 2^24.

MR: okay, hangover that you'd like to save a byte.
But CBOR doesn't let you save that byte, so just make it uint32?

BC: CBOR sends 1, 2 or 4 bytes according to need, as I understand it.

Regards
   Brian

---

From: Michael Richardson <[email-masked]>
Date: Wed, 19 Oct 2016 16:03:54 -0400

Brian E Carpenter <[email-masked]> wrote:
    > MR: Given that CBOR has only 1,2, and 4 byte uintegers, why do we have
    > a 24-bit session-id?

    > BC: Well, it's a hangover from the pre-CBOR TLV format. But I think
    > it's true that we'd increase the average message size by making it 32
    > bits, since there are a lot more random numbers between 2^24 and 2^32
    > than between 1 and 2^24.

    > MR: okay, hangover that you'd like to save a byte.  But CBOR doesn't
    > let you save that byte, so just make it uint32?

    > BC: CBOR sends 1, 2 or 4 bytes according to need, as I understand it.

If my session-id is 0x010000, then CBOR will send 4 bytes.
In the unlikely (1/2^27 + 1/2^24 + 1/ 2^16 chance, less than 0.001%) that a randomly generated
session-id has two or three leading zeros, or is less than 24, CBOR will send
fewer bytes. (I think, sending more bytes is still permissible).

In most cases, it will send 4 bytes, so might as well use them.
See my email today about perhaps using bit 31 to partition the session-id
space between TCP sender and receiver.

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 20 Oct 2016 13:36:41 +1300

> In most cases, it will send 4 bytes, so might as well use them.

Yes, I think you are correct. An easy change if people agree.

> space between TCP sender and receiver.

As I said, I don't really see the issue there. According to
https://tools.ietf.org/html/draft-ietf-anima-grasp-07#section-3.6
the negotiation (or synchronization) session has its own session-id,
distinct from the one used for discovery, even if they did re-use
the same TCP session. Messages for the two transactions (discovery
and negotiation) could be demultiplexed using the session-id,
even if they overlapped in time for some reason. The ids will never
clash, because the same party initiates discovery and negotiation.

    Brian

---

From: Michael Richardson <[email-masked]>
Date: Wed, 19 Oct 2016 22:01:42 -0400

Brian E Carpenter <[email-masked]> wrote:
    > https://tools.ietf.org/html/draft-ietf-anima-grasp-07#section-3.6 the
    > negotiation (or synchronization) session has its own session-id,
    > distinct from the one used for discovery, even if they did re-use the
    > same TCP session. Messages for the two transactions (discovery and
    > negotiation) could be demultiplexed using the session-id, even if they
    > overlapped in time for some reason. The ids will never clash, because
    > the same party initiates discovery and negotiation.

But, can't there be multiple back and forths of M_NEGOTIATE?
As such the same session-id would be sent in an M_NEGOTIATE in both
directions.

If not, then I don't understand negotiation at all.

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 20 Oct 2016 16:05:30 +1300

> As such the same session-id would be sent in an M_NEGOTIATE in both

Exactly. Like my example that I sent. Manually prettified, it reads:

A to B: [M_REQ_NEG, 8280376, ['EX3', 1, 6, ['NZD', 156]]]
B to A: [M_NEGOTIATE, 8280376, ['EX3', 1, 6, ['NZD', 155.5]]]
A to B: [M_END, 8280376, [O_ACCEPT]]

What's the problem? 8280376 is unique in A, and {8280376, A's address}
is unique in B. They can't get confused, even if there are numerous
negotiation steps.

OK, so now I'll make one with multiple steps [pause while I run my
example generator and prettify the results]

A to B: [M_REQ_NEG, 11146801, ['EX2', 1, 6, ['NZD', 393]]]
B to A: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 56.0]]]
A to B: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, 294.75]]
B to A: [M_WAIT, 11146801, 20899]
B to A: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 84.0]]]
A to B: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, 235.8]]
B to A: [M_END, 11146801, [O_DECLINE, 'Insufficient funds']]

I use random numbers to generate the test cases. That was a nice one, it
shows B telling A to wait and it shows a failed negotiation. But since
A and B both know who they are, the fact that the session-id is identical
isn't a problem.

   Brian

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 20 Oct 2016 16:19:26 +1300

Oops, there was a prettifying bug in the previous version...

A to B: [M_REQ_NEG, 11146801, ['EX2', 1, 6, ['NZD', 393]]]
B to A: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 56.0]]]
A to B: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 294.75]]]
B to A: [M_WAIT, 11146801, 20899]
B to A: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 84.0]]]
A to B: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 235.8]]]
B to A: [M_END, 11146801, [O_DECLINE, 'Insufficient funds']]

   Brian

---

From: Michael Richardson <[email-masked]>
Date: Thu, 20 Oct 2016 09:02:03 -0400

> Oops, there was a prettifying bug in the previous version...

...

    > example generator and prettify the results]

   1> A to B: [M_REQ_NEG, 11146801, ['EX2', 1, 6, ['NZD', 393]]]
   2> B to A: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 56.0]]]
   3> A to B: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 294.75]]]
   4> B to A: [M_WAIT, 11146801, 20899]
   5> B to A: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 84.0]]]
   6> A to B: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 235.8]]]
   7> B to A: [M_END, 11146801, [O_DECLINE, 'Insufficient funds']]

Lines 2 and 5 look identical to me.
As do lines 3 and 6.

    > A and B both know who they are, the fact that the session-id is identical

Does it work only because line 4 precedes line 5?

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 21 Oct 2016 08:19:25 +1300

> Lines 2 and 5 look identical to me.

Yes, except that B increased its offer from $56 to $84.

> As do lines 3 and 6.

Yes, except that A reduced its request from $294 to $235

> Does it work only because line 4 precedes line 5?

Well, that is B telling A "hang on for 20.9 seconds", so A will extend its
timeout on the current negotiation step. It's an optional message. My test
rig decides at random when to insert it.

There's a state machine at each end which is specific for this particular
objective. I'm a little confused about what's confusing you. (Maybe the
Appendix of examples needs explanatory text?)

   Brian

---

From: Michael Richardson <[email-masked]>
Date: Sun, 23 Oct 2016 16:17:09 -0400

> Yes, except that A reduced its request from $294 to $235

Ah, so this is one negotiation then?
I thought the M_WAIT was the end of a negotiation and 5> was a second thing,
but of course, that makes no sense, it would start with M_REQ_NEG.

    > Appendix of examples needs explanatory text?)

Let me add some messages and interleave a second negotiation n2:

n1  1> A to B: [M_REQ_NEG, 11146801, ['EX2', 1, 6, ['NZD', 393]]]
n2 11> B to A: [M_REQ_NEG, 11146801, ['EX2', 1, 6, ['NZD', 392]]]

Yup, both ends picked the same session-id because cosmic ray hit, and started
negotiation.

n1  2> B to A: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 56.0]]]
n2 21> A to B: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 55.0]]]

n1  3> A to B: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 294.75]]]
n1  4> B to A: [M_WAIT, 11146801, 20899]
n2 31> B to A: [M_NEGOTIATE, 11146801, ['EX2', 1, 6, ['NZD', 292]]]

..

So, is message 31 (which looks the same as (5) above part of n1 or n2?

---

From: Brian E Carpenter <[email-masked]>
Date: Mon, 24 Oct 2016 16:28:05 +1300

> So, is message 31 (which looks the same as (5) above part of n1 or n2?

Two answers:

1. n1 and n2 would be two different TCP sessions, and two different threads
at each end.

2. In any case, the session_ID cache (of all currently valid IDs,
should be implemented with 2-tuples* like {ID, initiator}.)
I coded it with 0 meaning "me", so {11146801,0} would be a session
that I initiated, and {11146801,2406:e007:652c:1:660a:5169:6c66:4669}
would be one that the other guy initiated.
So if you did build a single-threaded implementation, that would be
enough to demultiplex the sessions.

   Brian

*in practice I have more in the session cache. Gory details:

class _session_instance:
    """Internal use only"""
    def __init__(self, id_value, id_active, id_source):
        self.id_value = id_value   #Integer
        self.id_active = id_active #True if active
        self.id_source = id_source #Source locator of ID if needed
        self.id_dq = None          #Queue if discovering
        self.id_sock = None        #Socket if negotiating
        self.id_relayed = False    #True if has been relayed

# Session_ID cache contains
#  - all currently active Session_IDs
#  - foreign source address if any
#  - status for each one (in use or inactive)
#  - as memory permits, all previously seen Session_IDs (status inactive) to avoid reuse

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 25 Oct 2016 15:53:38 +1300

Hi,

Walking to the bus stop just now, I think I finally understood Michael's
concern.

1. We assume the extremely unlikely case that two GRASP peers A and B choose
the same session ID -- let's call it C for 'clash'. This would need to be
at about the same time, too, for the ambiguity to matter.

2. We assume that A sends req_negotiate(C,...) to B, and B sends req_negotiate(C,...)
to A, at about the same time.

Now we have to consider the possible race condition.

- If A's req_negotiate reaches B before B has committed to using the ID value
C for its own req_negotiate, we are OK: B will find that C is already
in use (in its local session cache) and will generate a new value C'. No
race condition, no problem.

- Similarly in the other direction.

- If A's req_negotiate reaches B after B has committed to using the ID value
C, B can detect this, because C is already in its local session cache, tagged
as locally originated. So it can simply drop the req_negotiate (or send back an
M_END[O_DECLINE]).

- Similarly in the other direction. In fact, if the race condition arises
in one direction, it will automatically arise in the opposite direction too.
So both attempted negotiations will fail. That's fine; ASAs need to retry
after failure in any case. In any case it's highly unlikely, unless somebody
uses a really bad PRNG.

Is that correct? If so, it needs to be explained better in the spec.

That said, I think it's quite logical to increase the space to 32 bits, since
as Michael observed it will be stored as a uint32 anyway, in practice, and the impact
on CBOR size is minor.

Regards
   Brian