Subject: Re: [6tisch] [core] COMI hash values globally unique vs. unique within a module

From: Thomas Watteyne <[email-masked]>
Date: Tue, 31 Mar 2015 09:15:48 +0200

[adding 6TiSCH]

Andy,

I believe the issue Michel highlights is that the hash collisions depends
on the modules that are implemented in the CoMI endpoint.

That is, if nodeA implements the [/6t,/foo] modules, and nodeB the
[/6t,/bar] modules, the hash collisions can be different, even in the same
"6t" module. In the case of 6top, the YANG model describes the module
completely. It would be awfully nice to be able to just rely on that YANG
model to predict the hash collisions within that module.without having to
discover the rehash-map on a server each time.

IIRC, today, a client accessing any resource using CoMI needs to first
retrieve the hash-map? The client needs to do this for each node is
manages, potentially periodically if new modules are added on-the-fly? This
seems like a lot of uncessary overhead.

One way could be fr the server to return some error code when the client
accesses a resource with a hash that is ambiguous.

Your insight on this is very welcome.

Thomas

On Tue, Mar 31, 2015 at 3:46 AM, Andy Bierman <[email-masked]> wrote:

> On Mon, Mar 30, 2015 at 12:43 PM, Michel Veillette
> <[email-masked]> wrote:
> > Currently, CoMI object identifiers (YANG hash) are globally unique
> within a CoMI server. Devices implementing different set of modules may
> have different YANG hash conflicts and may have a different set of object
> identifiers affected by rehash. In an application like 6TiSH, this means
> that the list of rehash values can't be known in advance based on the
> published YANG module, rehash values need to be discover and manage by each
> node involved in the timeslots reservation process.
> >
> > Reducing the scope of the YANG hash to the context of a single module
> (data nodes defined by a module + data nodes added to that module by the
> augment statement) can mitigate this issue. The question is how this can be
> accomplished and if the overhead required make this change acceptable.
> >
>
> I don't think this will work.
> The probability of collisions is the same whether 100 objects
> are defined in 1 module or 10 objects are defined in each of 10 modules.
>
> The client must implement the rehash algorithm even though there is
> a low probability it will be used.
>
>
> Andy
>
>
> > Impacts on the URI
> > ===============
> > Currently, the CoAP path consist of:
> >  "/mg/<hash-value>"
> >
> > Considering that the YANG hash is unique only within the context of a
> module, the CoAP path needs to include the module name:
> > "/mg/data" or
> >  "/mg/data/<moduleName>: <hash-value>"
> >
> > Impacts on the CBOR content
> > ========================
> > If the CoAP path target a specific module (e.g. "/mg/data/<moduleName>:
> <hash-value>"), the current CBOR encoding rules should apply unmodified.
> >
> > If the CoAP path target multiple modules (e.g. "/mg/data"), CoMI objects
> need to be associated to their respective module context. A CBOR map added
> to the root of the CBOR object can be used to establish this relationship.
> >
> > For example
> > ==========
> > Assuming:
> > - hash of "/6top:CellList" =  0x3470d0c5, base64 "0cNDF"
> > - hash of "/6top:CellList/6top:CellID" = 0x2a33a8b4
> > - hash of "/6top:CellList/6top:SlotframeI" = 0xfe4ad55
> > - hash of "/6top:CellList/6top:SlotOffset" = 0x2515e82f
> > - hash of "/6top:CellList/6top:ChannelOffset" = 0x9c2f821, base64 "Jwvgh"
> > - hash of "/6top:CellList/6top:LinkOption" = 0x5057e17
> > - hash of "/6top:CellList/6top:LinkType" = 0xd2a79e8
> > - hash of "/6top:CellList/6top:CellType" = 0x26e3537
> > - hash of "/6top:CellList/6top:TargetNodeAddress" = 0x2efea0b3
> > - hash of "/6top:CellList/6top:TrackID" = 0x1e32edaf
> >
> > The "/6top:CellList/6top:ChannelOffset" data node can be requested as
> follow:
> >
> >   REQ: GET example.com/mg/data/6top:Jwvgh
> >
> >   RES: 2.05 Content (Content-Format: application/cbor)
> >   {
> >     0x9c2f821 : 5
> >   }
> >
> > The content of the "/6top:CellList"  list can be requested as follow:
> >
> >   REQ: GET example.com/mg/data/6top:0cNDF
> >
> >   RES: 2.05 Content (Content-Format: application/cbor)
> >   {
> >     0x3470d0c5 : [
> >       {
> >         0x2a33a8b4 : 1,
> >         0xfe4ad55 : 1,
> >         0x2515e82f : 1,
> >         0x9c2f821 : 1,
> >         0x5057e17 : "Transmit,Timekeeping",
> >         0xd2a79e8 : 0,
> >         0x26e3537 : 1,
> >         0x2efea0b3 : h'0102030000112233',
> >         0x1e32edaf : 1
> >       }
> >     ]
> >   }
> >
> > And the content of the datastore can be requested as follow:
> >
> >   REQ: GET example.com/mg/data
> >
> >   RES: 2.05 Content (Content-Format: application/cbor)
> >   {
> >     "6top" : {
> >       0x3470d0c5 : [
> >         {
> >           0x2a33a8b4 : 1,
> >           0xfe4ad55 : 1,
> >           0x2515e82f : 1,
> >           0x9c2f821 : 1,
> >           0x5057e17 : "Transmit,Timekeeping",
> >           0xd2a79e8 : 0,
> >           0x26e3537 : 1,
> >           0x2efea0b3 : h'0102030000112233',
> >           0x1e32edaf : 1
> >         }
> >       ]
> >     },
> >     "IP-MIB" : {
> >       0x30b7bc3f : {
> >         0x1067f289 : [
> >           {
> >             0x00d38564 : 1,
> >             0x2745e222 : "ipv4",
> >             0x387804eb : "10.0.0.51",
> >             0x1a51514a : "00:00:10:01:23:45",
> >             0x03f95578 : "2333943",
> >             0x24ade115 : "static",
> >             0x09e640ef : "reachable",
> >             0x3b5c1ab6 : "active"
> >           },
> >           {
> >             0x00d38564 : 1,
> >             0x2745e222 : "ipv4",
> >             0x387804eb : "9.2.3.4",
> >             0x1a51514a : "00:00:10:54:32:10",
> >             0x03f95578 : "2329836",
> >             0x24ade115 : "dynamic",
> >             0x09e640ef : "unknown",
> >             0x3b5c1ab6 : "active"
> >           }
> >         ]
> >       }
> >     }
> >   }
> >
> > Is it a real issue and is it a viable solution?
> >
> > Michel Veillette
> > System Architecture Director
> > Trilliant Inc.
> > Tel: 450-375-0556 ext. 237
> > [email-masked]
> > www.trilliantinc.com
> >
> >
> > _______________________________________________
> > core mailing list
> > [email-masked]
> > https://www.ietf.org/mailman/listinfo/core
>
> _______________________________________________
> core mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/core
>

---

From: Thomas Watteyne <[email-masked]>
Date: Tue, 31 Mar 2015 13:51:13 +0200

Michel,

+1 on all, which echoes the e-mail I sent to the 6TISCH and CoRE MLs this
morning.

On Tue, Mar 31, 2015 at 1:42 PM, Michel Veillette <
[email-masked]> wrote:

> Hi Andy
>
> The goal of this proposal is to allow YANG hash duplicates between
> modules. To accomplish this goal, the module name is added to the URI and
> to the root CBOR object when multiple module contexts are accessed, see
> examples bellow.
>
> The probability of collisions within a module is lower and more
> importantly, the set of collisions will be the saame on all devices
> independently of the number of module hosted by these devices.
>
> I added Thomas Watteyne in cc which is part of the 6TiSCH group and also
> concerned about this issue. Thomas, do you have anything to add about the
> rational of such modification to COMI.
>
> Michel Veillette
> -----Original Message-----
> From: Andy Bierman [mailto:[email-masked]]
> Sent: 30 mars 2015 21:47
> To: Michel Veillette
> Cc: [email-masked]
> Subject: Re: [core] COMI hash values globally unique vs. unique within a
> module
>
> On Mon, Mar 30, 2015 at 12:43 PM, Michel Veillette <
> [email-masked]> wrote:
> The probability of collisions is the same whether 100 objects are defined
> in 1 module or 10 objects are defined in each of 10 modules.
>
> The client must implement the rehash algorithm even though there is a low
> probability it will be used.
>
>
> Andy
>
>
> > Impacts on the URI
> > ===============

---

From: Andy Bierman <[email-masked]>
Date: Tue, 31 Mar 2015 06:30:07 -0700

On Tue, Mar 31, 2015 at 12:15 AM, Thomas Watteyne
<[email-masked]> wrote:
> [adding 6TiSCH]
>
> Andy,
>
> I believe the issue Michel highlights is that the hash collisions depends on
> the modules that are implemented in the CoMI endpoint.
>

But hash collisions can occur within a module or across modules.
Allowing collisions across modules does not change the probability
of a collision.  It does not remove the need to check for a collision.

What problem are you trying to solve?
If it is to remove the possibility of a collision ever occurring
then keep trying.  Why is it better to change the scope
of the object hash to be per module name?

The goal of the YANG hash is to lower the identifier size to
a 4 byte number.  Adding the 10 - 20 byte module name to
every identifier really doesn't help lower the identifier size
at all.

Andy

> retrieve the hash-map? The client needs to do this for each node is manages,
> potentially periodically if new modules are added on-the-fly? This seems
> like a lot of uncessary overhead.
>
>> > within a CoMI server. Devices implementing different set of modules may have
>> > different YANG hash conflicts and may have a different set of object

---

From: Michel Veillette <[email-masked]>
Date: Tue, 31 Mar 2015 14:50:39 +0000

Hi Andy

The intent is not to reduce the number of collisions but make these collisions predictable and uniform within a population of devices independently of the number of modules implemented by them. This is especially important in distributed applications such 6TiSH timeslot management. In such applications, each constrained device need to interact with multiple other constrained devices using CoMI. With the current YANG hash approach, each constrained device need to retrieve and maintain the rehash list for each peer.

If the scope of YANG hash is reduced to the module level (data nodes defined by a module + data nodes added to that module by the augment statement), collisions within this module can be determined based of the YAND definition of this module and specific rehash values can be mandated or recommended if needed.

Michel Veillette

-----Original Message-----
From: core [mailto:[email-masked]] On Behalf Of Andy Bierman
Sent: 31 mars 2015 09:30
To: Thomas Watteyne
Cc: [email-masked]; [email-masked]
Subject: Re: [core] COMI hash values globally unique vs. unique within a module

On Tue, Mar 31, 2015 at 12:15 AM, Thomas Watteyne <[email-masked]> wrote:
> [adding 6TiSCH]
>
> Andy,
>
> I believe the issue Michel highlights is that the hash collisions 
> depends on the modules that are implemented in the CoMI endpoint.
>

But hash collisions can occur within a module or across modules.
Allowing collisions across modules does not change the probability of a collision.  It does not remove the need to check for a collision.

What problem are you trying to solve?
If it is to remove the possibility of a collision ever occurring then keep trying.  Why is it better to change the scope of the object hash to be per module name?

The goal of the YANG hash is to lower the identifier size to a 4 byte number.  Adding the 10 - 20 byte module name to every identifier really doesn't help lower the identifier size at all.

Andy

> [/6t,/bar] modules, the hash collisions can be different, even in the 
> same "6t" module. In the case of 6top, the YANG model describes the 
> module completely. It would be awfully nice to be able to just rely on 
> that YANG model to predict the hash collisions within that 
> module.without having to discover the rehash-map on a server each time.
>
> manages, potentially periodically if new modules are added on-the-fly? 
> This seems like a lot of uncessary overhead.
>
> One way could be fr the server to return some error code when the 
> client accesses a resource with a hash that is ambiguous.
>
>> > within a CoMI server. Devices implementing different set of modules 
>> > may have different YANG hash conflicts and may have a different set 
>> > of object identifiers affected by rehash. In an application like 
>> > 6TiSH, this means that the list of rehash values can't be known in 
>> > advance based on the published YANG module, rehash values need to 
>> > be discover and manage by each node involved in the timeslots reservation process.
>> >
>> > Reducing the scope of the YANG hash to the context of a single 
>> > module (data nodes defined by a module + data nodes added to that 
>> > module by the augment statement) can mitigate this issue. The 
>> > question is how this can be accomplished and if the overhead required make this change acceptable.
>> >
>>
>> The probability of collisions is the same whether 100 objects are 
>> defined in 1 module or 10 objects are defined in each of 10 modules.
>>
>> The client must implement the rehash algorithm even though there is a 
>> low probability it will be used.
>>
>>
>> Andy
>>
>>
>> > Impacts on the URI
>> > ===============
>> > Considering that the YANG hash is unique only within the context of 
>> > a module, the CoAP path needs to include the module name:
>> > "/mg/data" or
>> > If the CoAP path target multiple modules (e.g. "/mg/data"), CoMI 
>> > objects need to be associated to their respective module context. A 
>> > CBOR map added to the root of the CBOR object can be used to establish this relationship.
>> >
>> > For example
>> > ==========
>> > Assuming:

---

From: peter van der Stok <[email-masked]>
Date: Tue, 31 Mar 2015 16:50:47 +0200

Thomas,

I agree with Andy, that adding the module name means going back to 
square one; i.e having long identifiers that we want to remove.
The rehash may occur at loading time and does not change as long as 
modules are not reloaded.
Consequently, each client can learn the rehash values at start-up and 
use them without rechecking all the time.

OR, do you expect constant changes to the module configurations in the 
servers?

Is your problem that for the same identifier in two different servers 
the rehash may be different; and you need to maintain lists per server?

Anyway, at a central server one can simulate the loading in a given 
server and see if there is a collision.
Using the same algorithm as on the server, the central server can 
already provide all the rehash values for all servers to the clients.

Peter

Andy Bierman schreef op 2015-03-31 15:30:
>> depends on
>> same
>> manages,
>> client

---

From: Michel Veillette <[email-masked]>
Date: Tue, 31 Mar 2015 15:53:15 +0000

Hi Andy

- About your comment " Nodes from module X that augment module Y are not known by module Y, when module Y is compiled or deployed."

If a data node 'y' added by module 'Y' to module 'X' create a YANG hash conflict, data node 'y' will need to be rehash. This don't affect YANG hash values of the data nodes already defined by module 'X'.

- About your comment " You seem to be suggesting that the 6TISCH WG will control all YANG modules on a device, even modules from vendors or other SDOs."

This is not the case, devices are free to implement any number of YANG modules needed. By creating a distinct hash space for each module, we can minimize impacts when integrating multiple modules within a single server.

- About your comment " Most deployment scenarios allow for the vendor to select the set of modules that are supported by a device. YANG is designed to be modular and extensible, without requiring a single, centralized naming authority."

The intent is to reinforce this model and improve its scalability.

Michel Veillette

-----Original Message-----
From: Andy Bierman [mailto:[email-masked]] 
Sent: 31 mars 2015 11:29
To: Michel Veillette
Cc: Thomas Watteyne; [email-masked]; [email-masked]
Subject: Re: [core] COMI hash values globally unique vs. unique within a module

> If the scope of YANG hash is reduced to the module level (data nodes defined by a module + data nodes added to that module by the augment statement), collisions within this module can be determined…

Nodes from module X that augment module Y are not known by module Y, when module Y is compiled or deployed.

You seem to be suggesting that the 6TISCH WG will control all YANG modules on a device, even modules from vendors or other SDOs.

Most deployment scenarios allow for the vendor to select the set of modules that are supported by a device. YANG is designed to be modular and extensible, without requiring a single, centralized naming authority.

Andy

>> module completely. It would be awfully nice to be able to just rely 
>> on that YANG model to predict the hash collisions within that 
>> IIRC, today, a client accessing any resource using CoMI needs to 
>> first retrieve the hash-map? The client needs to do this for each 
>> node is manages, potentially periodically if new modules are added on-the-fly?
>>> > within a CoMI server. Devices implementing different set of 
>>> > modules may have different YANG hash conflicts and may have a 
>>> > different set of object identifiers affected by rehash. In an 
>>> > application like 6TiSH, this means that the list of rehash values 
>>> > can't be known in advance based on the published YANG module, 
>>> > rehash values need to be discover and manage by each node involved in the timeslots reservation process.
>>> >
>>> > Considering that the YANG hash is unique only within the context 
>>> > of a module, the CoAP path needs to include the module name:
>>> > "/mg/data" or
>>> > objects need to be associated to their respective module context. 
>>> > A CBOR map added to the root of the CBOR object can be used to establish this relationship.
>>> >
>>> > For example
>>> > ==========
>>> > Assuming:

---

From: Michel Veillette <[email-masked]>
Date: Tue, 31 Mar 2015 16:42:42 +0000

Hi Andy

> But YANG module names tend to be 15 to 30 bytes long, which really defeats the purpose
>  of using short identifiers.  If the solution makes the names longer than they would have been
> without any hash, then perhaps it is not the right solution.

I agree there is an impact but this impact seem limited.

For a single data node access, the overhead consist of adding the module name once in the URI.

For a complete datastore access, the overhead consist of adding each module name once in a CBOR map.

Michel Veillette

-----Original Message-----
From: Andy Bierman [mailto:[email-masked]] 
Sent: 31 mars 2015 12:30
To: Michel Veillette
Cc: Thomas Watteyne; [email-masked]; [email-masked]
Subject: Re: [core] COMI hash values globally unique vs. unique within a module

> If a data node 'y' added by module 'Y' to module 'X' create a YANG hash conflict, data node 'y' will need to be rehash. This don't affect YANG hash values of the data nodes already defined by modul…

Sorry I responded to the comment about augment.
It doesn't matter if the conflict is from an augment or a disjoint object.

> This is not the case, devices are free to implement any number of YANG modules needed. By creating a distinct hash space for each module, we can minimize impacts when integrating multiple modules w…

I guess if the YANG designers ran the hashes when they were written then they could make gratuitous name changes to undo hash collisions.

But YANG module names tend to be 15 to 30 bytes long, which really defeats the purpose of using short identifiers.  If the solution makes the names longer than they would have been without any hash, then perhaps it is not the right solution.

Andy

>>> [/6t,/bar] modules, the hash collisions can be different, even in 
>>> the same "6t" module. In the case of 6top, the YANG model describes 
>>> the module completely. It would be awfully nice to be able to just 
>>> rely on that YANG model to predict the hash collisions within that 
>>>> > Currently, CoMI object identifiers (YANG hash) are globally 
>>>> > unique within a CoMI server. Devices implementing different set 
>>>> > of modules may have different YANG hash conflicts and may have a 
>>>> > [email-masked] www.trilliantinc.com
>>>> >
>>>> >

---

From: Michel Veillette <[email-masked]>
Date: Tue, 31 Mar 2015 18:08:37 +0000

Hi Andy

See [MV] inline

Michel Veillette

-----Original Message-----
From: Andy Bierman [mailto:[email-masked]] 
Sent: 31 mars 2015 13:07
To: Michel Veillette
Cc: Thomas Watteyne; [email-masked]; [email-masked]
Subject: Re: [core] COMI hash values globally unique vs. unique within a module

> Hi,
>
> YANG module names are a bit longer than your example (like ietf-6top).
> Data is not required to be organized or retrieved by module.

[MV]
The solution don’t require to organized data nodes by module but an
implementation that do so will minimize payload overhead.

> I don't think it is very practical for YANG module writers to manually manage
> the names in the module so there are no hash collisions.  For SMIv2 modules
> already published and converted to YANG, this is not an option.
>
> Unless the collision probability is zero for all possible combinations of vendor
> and standard modules, then the need for rehashing has not been removed.
> The probability is already low enough that a constrained device will not ever
> encounter a collision, but it is still greater than zero.

[MV]
The intent is not to "manually manage the names in the module so there are no hash collisions".
The intent is not to remove the "need for rehashing".

The intent is to reduce the scope of YANG hash to make collisions predictable and uniform within
a population of devices independently of the number of modules implemented by them.

---

From: Andy Bierman <[email-masked]>
Date: Tue, 31 Mar 2015 08:29:02 -0700

> If the scope of YANG hash is reduced to the module level (data nodes defined by a module + data nodes added to that module by the augment statement), collisions within this module can be determined…

Nodes from module X that augment module Y are not known by module Y,
when module Y is compiled or deployed.

You seem to be suggesting that the 6TISCH WG will control all
YANG modules on a device, even modules from vendors or other SDOs.

Most deployment scenarios allow for the vendor to select the
set of modules that are supported by a device. YANG is designed to be modular
and extensible, without requiring a single, centralized naming authority.

Andy

---

From: Andy Bierman <[email-masked]>
Date: Tue, 31 Mar 2015 09:30:11 -0700

> This is not the case, devices are free to implement any number of YANG modules needed. By creating a distinct hash space for each module, we can minimize impacts when integrating multiple modules w…

I guess if the YANG designers ran the hashes when they were written
then they could make gratuitous name changes to undo hash collisions.

But YANG module names tend to be 15 to 30 bytes long, which really
defeats the purpose of using short identifiers.  If the solution makes
the names longer than they would have been without any hash,
then perhaps it is not the right solution.

Andy

---

From: Andy Bierman <[email-masked]>
Date: Tue, 31 Mar 2015 10:07:01 -0700

Hi,

YANG module names are a bit longer than your example
(like ietf-6top).  Data is not required to be organized or
retrieved by module.

I don't think it is very practical for YANG module
writers to manually manage the names in the module so there
are no hash collisions.  For SMIv2 modules already published
and converted to YANG, this is not an option.

Unless the collision probability is zero for
all possible combinations of vendor and standard modules,
then the need for rehashing has not been removed.

The probability is already low enough that a constrained device
will not ever encounter a collision, but it is still greater than zero.

Andy

---

From: Andy Bierman <[email-masked]>
Date: Tue, 31 Mar 2015 19:28:54 -0700

Hi,

inline also

> implementation that do so will minimize payload overhead.

OK -- I will accept that we can come up with optimizations so
each module-name needs to appear only 1 time.

> a population of devices independently of the number of modules implemented by them.

Actually, I wanted to use your design from the start, but not with strings.
Temporary numeric mappings do not help, so I gave up.

When I started working on YANG Hash and the ietf-yang-library module,
I wanted to put a uint32 "module-id" in the module entry, but this needs
to be a globally assigned number so all servers return the same mappings.

The numbers are arbitrary so they can be assigned by IANA or by algorithm.
Since there are so few YANG modules in RFCs, I wonder if an IANA registry
for module-id mappings would work.

Could a 2-number module-id work:

    <ORG>.<MODULE-ID>

   ORG == reserved space:  1 for IETF, 2 for IEEE, etc.
                 enterprise space:  SMI enterprise ID  + (reserverd
range offset)
   MODULE-ID == permanent module number assigned to the module

Maybe an algorithm to convert arbitrary SMI MIB root OIDs to module-ids
could be found so SMIv2 converted to YANG will work automatically.

Andy