Subject: [Anima-signaling] GRASP Session ID analysis

From: Brian E Carpenter <[email-masked]>
Date: Fri, 27 Nov 2015 13:43:22 +1300

Hi,

I wish we had a whiteboard...

> <t>38. Is Session ID sufficient to identify relayed responses?
> Isn't the originator's address needed too?</t>
> 
> BC: I am afraid that Joel is correct about this, and we will have
> to change the the protocol accordingly. Although the probability
> of ID collision is very low, it is non-zero.

The GRASP Session ID is needed so that in a multi-threaded and distributed
environment, a particular GRASP interaction can be identified by each node.
(Note that we can't use transport-layer connections for this, because
some interactions might start with an outbound UDP packet but continue
with a TLS or TCP connection. So we need a session layer identifier.)

Even though the Session ID is defined as a 24 bit pseudo-random value,
there is a finite chance of collision between IDs from different
nodes. If GRASP is a success and is implemented on millions of nodes at
thousands of sites, the chance of collisions will be significant (because
the birthday paradox applies). Therefore we must solve this problem.

There are two cases to consider:

1) Unicast interactions. In this case, if Node A and Node B both start
an interaction with Node C using the same Session ID value X, all Node C
needs to do is tag each session with its source address as well as with X.
The messages themselves don't need to change.

(This would even work if C picked the same Session ID value X for yet
another unicast session, because C would tag it with its own address.)

2) Multicast interactions (discovery flooding and synchronization
flooding).

When a router relays one of these flooded LL multicasts, it needs to
preserve the Session ID as part of the protection against multiplication
and looping, and in the case of discovery, the discovery response also
needs to preserve the Session ID.

If A and B both launch a LL multicast with Session ID X, and they are both
relayed by the same router, the relayed copies will both have the same
source address (the router's, not A or B). So the two sessions cannot be
distinguished.

Possible fixes:

1. When the router relays a LL multicast, it generates a new Session ID.

+ no protocol overhead.
- breaks the current loop prevention method. We would have to rely more
  on the loop count for loop prevention.
- adds complexity to the state kept by the relay logic.

2. Add a 'source address' field to every GRASP message.

+ simple
- extra overhead even when not needed

3. Request ACP to supported routed multicast instead of using LL multicast.

- major feature request for ACP, and problematic for non-ACP scenario

4. Add a 'source address' field, but only when needed.
However, in this case some Response messages will carry the source
address and others will not.

+ only adds overhead when needed
- a bit complicated

5. Like #4, but give synchronization flooding its own message type.
Then only discovery and flooding will use LL multicast and carry
the source address.

+ simpler than #4

Comments and opinions please...

    Brian