Subject: [core] Questions on CoMI rehash map

From: Rodney Cummings <[email-masked]>
Date: Mon, 27 Jul 2015 16:37:11 -0500

Hello,

I have some potentially naive questions on the rehash map specified in 
sections 5.2 and 5.3 of the latest CoMI draft 07:
        https://datatracker.ietf.org/doc/draft-vanderstok-core-comi/
I apologize if these questions have already been discussed.

If we can find ways to get the client and server "in sync" with regard to 
hash collisions, we could remove the need for the ietf-yang-hash module. 
Removing ietf-yang-hash would result in more efficient and constrained 
processing, such as removing the need to store extra "path" objects when 
multiple objects in a module collide.

Some questions:
1. Is it possible to mandate a mechanism for the server to report all 
supported data nodes to the client?
2. Is it possible to specify the traversal algorithm that both client and 
server use to create hashes for data nodes?
3. When a hash collision occurs, is it possible to specify the algorithm 
to create a new hash repetitively until a non-colliding hash is found?

For item #1, if the CoAP interfaces of section 3 are not sufficient, we 
could potentially use the new YANG package proposal. Regardless of 
challenges with the hash collision, this seems like something that the 
server should deliver to the client with a clear mechanism, so that the 
client knows what is supported in the server. This needs to be mandatory, 
in order to avoid the situation in which the client accesses a data node 
that the server is unfamiliar with, resulting in an unexpected hash 
collision. Error detection/reporting on access to unsupported objects is 
best performed at the client, not the server.

Once we have used item #1 to bring client and server in sync on the data 
nodes to be hashed, items #2 and #3 are intended to ensure that client and 
server resolve the hash collisions in exactly the same order and the same 
way. Item #2 specifies the order in which modules are evaluated for hash 
(e.g. alphabetical), as well as the order in which each module's data 
nodes are traversed (e.g. breadth first). Item #3 specifies how to rehash 
in order to avoid collision (e.g. increment the seed for murmur3_32 until 
collision free). 

If both client and server use exactly the same traversal and the same 
collision resolution, the ietf-yang-hash module is no longer needed.

Maybe I am missing something fundamental?

Thanks

----------------------------
Rodney Cummings
Principal Software Architect, Industrial/Embedded Networks
National Instruments
Tel: (512) 683-8544
Fax: (512) 683-8661
Email: [email-masked]

---

From: Andy Bierman <[email-masked]>
Date: Mon, 27 Jul 2015 15:21:11 -0700

> multiple objects in a module collide.

The rehash mechanism is being reworked (again), but it does not go away.
Can you explain your solution in more detail?

> supported data nodes to the client?

There is a resource /mg/mod.uri that indicates the URI of the YANG library
data
for the server. This is how YANG reports all the supported data nodes.

> server use to create hashes for data nodes?

No because YANG allows data to be added in the middle of a sibling-set.
YANG also supports sub-modules and the order they are parsed
could affect module order.

One important property of the YANG Hash is that is does not
change over time. If /foo/bar is defined in version 1,
then it has to remain the same value in version 2, 3, etc.
This allows clients compiled in firmware against version 1
to keep working.

3. When a hash collision occurs, is it possible to specify the algorithm to
> create a new hash repetitively until a non-colliding hash is found?
>

This may be possible, but it assumes the client knows the full set of hashes
on the server.

Michel has proposed a rehash scheme (offline) that is being discussed.
It fixes some problems with rehash, but cost an extra "rehash" bit in the
ID,
which makes rehashed IDs 31 bits, not 30.

> (e.g. alphabetical), as well as the order in which each module's data nodes
> are traversed (e.g. breadth first). Item #3 specifies how to rehash in
> order to avoid collision (e.g. increment the seed for murmur3_32 until
> collision free).
>

This may work. There might be some rehash info that needs to be
sent if a rehashed ID is used by the client.

> Thanks

Andy

> _______________________________________________
> core mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/core
>
>

---

From: Rodney Cummings <[email-masked]>
Date: Tue, 28 Jul 2015 12:45:59 -0500

> Can you explain your solution in more detail?

I'd be happy to provide more detail, but I suspect that I may be 
misinterpreting some fundamental assumptions for the CoMI client/server
interaction. I'd like to check those assumptions first (see below).

> There is a resource /mg/mod.uri that indicates the URI of the YANG 
> library data

Great. I wasn't sure if this covered conditional data nodes (if-feature).

> On Mon, Jul 27, 2015 at 2:37 PM, Rodney Cummings <[email-masked] 
wrote:
>> 2. Is it possible to specify the traversal algorithm that both 
>> client and server use to create hashes for data nodes? 

> This allows clients compiled in firmware against version 1

This is probably the fundamental issue.

For a given version of the server's firmware, the server knows its 
own data node hierarchy, and therefore it can determine where rehash
is needed.

When the server's firmware upgrades from version 1 to version 2, it is
safe for the server to assume that the client is aware of this upgrade. 
If the client did not perform the firmware upgrade itself, 
it can query the version when CoMI starts up.

The question seems to be:
        When the server upgrades from version 1 to 2, what can the client 
        assume regarding the hash values of data nodes supported in both
        version 1 and 2?

You seem to be saying that the client can assume that the hash values
for version 1 data nodes are not changed. In other words, the client can 
assume
that the server orders its traversal of the hierarchy as oldest-first.
My concern is that I don't see that mandated in the draft. As a client, 
I cannot really assume this sort of thing unless I go outside the scope
of the standard (i.e. product-specific). 

If I don't want to make product-specific assumptions as a client, 
my alternative is to re-evaluate all hash values when I detect version 2.

In other words, I assumed that the client performs the following steps:
1. Check to see if the server's data nodes have changed (/mg/mod.uri, 
server version, etc).
2. If data nodes have not changed, re-use hash values from a previous 
session with this server.
3. If data nodes changed, read ietf-yang-hash and re-calculate hash values 
for all data nodes.

It sounds like my assumption is incorrect. If so, it might be helpful to 
clarify in the next draft.