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

From: peter van der Stok <[email-masked]>
Date: Wed, 01 Apr 2015 11:57:45 +0200

Hi all,

Do I understand correctly that,
  (1) Currently, A client has to maintain for every server a table in 
which the identifiers are stored that are rehashed.
  (2) By introducing module identifiers, a client has to maintain a table 
for every module (not server) in which identifiers are stored that are 
rehashed.

Disadvantage of (2) is
  2.1 - the need for standardizing module numbers in a registry
  2.2 - larger uri and payload

Advantage of (2) is not clear to me because you have to maintain rehash 
tables, with the difference that in case (1) you must search in the 
server identifier domain, and in (2) in the module number domain.
In (1) that means the table size is linear in the number of servers and 
in (2) is linear in the number of modules
Given that there may be thousands of servers and hundreds of modules, 
the storage size is 10 time smaller for (2).

Given the frequency of rehash occurrences the advantage of (2) is 
doubtful.

Where do I make mistakes or misunderstand?

Peter

Andy Bierman schreef op 2015-04-01 04:28:
> Hi,
> 
> inline also
> 
> 
> On Tue, Mar 31, 2015 at 11:08 AM, Michel Veillette
> <[email-masked]> wrote:
>> Hi Andy
>> 
>> See [MV] inline
>> 
>> Michel Veillette
>> System Architecture Director
>> Tel: 450-375-0556 ext. 237
>> [email-masked]
>> www.trilliantinc.com
>> 
>> -----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.
> 
> 
> OK -- I will accept that we can come up with optimizations so
> each module-name needs to appear only 1 time.
> 
> 
>> 
>>> 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.
>> 
> 
> 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
> 
> _______________________________________________
> core mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/core

---

From: peter van der Stok <[email-masked]>
Date: Wed, 01 Apr 2015 14:05:36 +0200

HI all,

what is the probability of hash collision?
It is given by the problem of the shared birthday,
Below a table of probabilities with a bit size of 32 (comi hash is 30)
There is a 50% probability of a clash with 7.7 x 10^4 names (80.000
names)

with 3000 names the probability is 1 permil.

So we do not have to worry too much about table sizes according to me.

see table below
or wikipedia (birthday problem)

ength of
hex string		#BITS
hash space
size
(2#bits)		NUMBER OF HASHED ELEMENTS SUCH THAT {PROBABILITY OF AT LEAST
ONE HASH COLLISION ≥ _P_}

		_P_ = 10−18
		_P_ = 10−15
		_P_ = 10−12
		_P_ = 10−9
		_P_ = 10−6
		_P_ = 0.1%
		_P_ = 1%
		_P_ = 25%
		_P_ = 50%
		_P_ = 75%

 		8
 		32
 		4.3×109
 		2
 		2
 		2
 		2.9
 		93
 		2.9×103
 		9.3×103
 		5.0×104
 		7.7×104
 		1.1×105

Peter

Andy Bierman schreef op 2015-04-01 04:28:
>> 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).
>> The solution don't require to organized data nodes by module but an
>>> 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
>>> 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
>> The intent is not to "manually manage the names in the module so there are no hash collisions".
>> 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.
>>
> 
> Actually, I wanted to use your design from the start, but not with strings.
> 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

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 01 Apr 2015 16:36:42 +0200

> the storage size is 10 time smaller for (2).

But you wouldn't store a separate collision table for each server.
Instead, you would quickly find out that, of the 10000 servers you are
talking to, there are only seven makes with three versions each.
Most of these have an empty collision table anyway.  So maybe you have
five different collision tables in total (one of which is empty), to one
of which your per-server state would simply point.  4 bytes or less per
server.  Certainly much less than the security state you need anyway.

I have a strange deja-vu with the discussion of TeRIs at an early stage
of the development of CoAP (they are still documented in the "cemetery"
of draft-bormann-coap-misc [1]).  We decided not to do those because it
created a ton of complexity at the client side.  Hashed YANG-level URIs
are different: You do the collision processing once per set of modules,
and you can amortize the overhead over many resources.  Still, it seems
to imply that clients have to be a bit more powerful, in order to handle
this complexity, so I can understand the push-back from 6TiSCH.

BTW, optimistic approaches to handling collisions have one fatal flaw:
two servers (or a server and its client) may map very different object
references into the same hash, without knowing about the other object
reference.  So just asking for that object via the hash will yield
different results, with no one involved knowing that there was a
collision.  You really need to grab these tables before talking to a server.

A node managing another node probably goes into a relatively long-term
relationship with it.  So even if there is still some complexity, the
overhead of the table processing amortizes quickly.  However, we can
still think about ways to minimize this overhead, e.g. by having a
compact way to say "I don't have a collision at all" during an early
step of setting up the relationship, and by representing non-zero tables
in an efficient way (e.g., just listing the hash code of the collision).
 The re-hashing strategy can also be optimized for minimal complexity,
given that the frequency of its use is likely [2] to be low.

Grüße, Carsten

[1]: https://tools.ietf.org/html/draft-bormann-coap-misc-27#appendix-C.3

[2]: OK, I already can hear someone bickering about using a
probabilistic method such as hashing in a deterministic network like
6TiSCH.  The cost differential will probably [2] turn out to be low
enough for this to not matter.

---

From: Michel Veillette <[email-masked]>
Date: Wed, 1 Apr 2015 14:39:24 +0000

Hi Andy

I first want to mention that the use of a string based, unmanaged,  top level identifier for a binary protocol is not something uncommon, protocols such Thrift is based on this approach. The main disadvantage is obviously size.

If we prefer binary based, managed identifier, an IANA registry of <ORG> will sense.
Something like:
   - 2 reserve bits
   - 20 bits <ORG>
   - 10 bits <MODULE-ID>

If the IETF is registered as <ORG> = 0, the impact of the URI for standardized module will be one or two characters and most modules impact will be less than 3 characters. For example:

  REQ: GET example.com/mg/JCa:0cNDF

On the payload side, each module identifier can be encoded using 1 to 3 bytes. For example:

  REQ: GET example.com/mg

  RES: 2.05 Content (Content-Format: application/cbor)
  {
    0x6014 : {
      0x3470d0c5 : [
        {
          0x2a33a8b4 : 1,
          0xfe4ad55 : 1,
          0x2515e82f : 1,
          0x9c2f821 : 1,
          0x5057e17 : "Transmit,Timekeeping",
          0xd2a79e8 : 0,
          0x26e3537 : 1,
          0x2efea0b3 : h'0102030000112233',
          0x1e32edaf : 1
        }
      ]
    },
    0x0A : {
      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"
          }
        ]
      }
    }
  }

With the module scope in place, we might want to slightly modify the way we specify reshash to allow assigment of specific short identifier (e..g. Indetifiers 0 to 23). This feature can be used in situations where payload size is very limited and moving form a 5 bytes automatically assigned identifiers to a single byte manually assigned identifier is considered cretical. This is just a thought.

Michel Veillette
Trilliant Inc.

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

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.

>> 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.
>>
>> combinations of vendor and standard modules, then the need for rehashing has not been removed.
>> not ever encounter a collision, but it is still greater than zero.
>
> [MV]
> predictable and uniform within a population of devices independently of the number of modules implemented by them.
>

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.

    <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

---

From: Michel Veillette <[email-masked]>
Date: Thu, 2 Apr 2015 04:09:10 +0000

Hi Peter

When used in a distributed system, devices need to implement both the client side and the server side of CoMI. With the actual approach, each client need to have in storage the string representation of the canonical representation of the object path for every data nodes this client need to interact with. These stings are require to map entries of the “rehash” list with specific data nodes used by this CoMI client.

For the 6 TiSCH modules alone, these strings represents 5323 bytes (See attachment) and this exclude the meta data require to make them useful. In a device implementing 10 modules like 6TiSH which is not something unrealistic, this requirement represents 64 kB of storage space.

We also need to consider that CoMI clients need to dynamically retrieve the “rehash” list of each peer which required extra logic and significant amount of this limited bandwidth. Each entry in the “rehash” list take between 40 to 100 bytes. An unknown number of instances of this “rehash” list then need to be stored.

In comparison, the implementation of the module scope has values require between 2 to 4 bytes in the URI, between 1 to 3 bytes for each module included in the payload and a single registration by organization defining YANG modules. Module scope hash values don’t need to be discovered dynamically, they are known in advance based on the yang module definition and can be statically program in CoMI clients.

In its actual form, COMI don’t seem to be appropriate for distributed applications of constrained devices and I hope to see a resolution of this issue.

Michel Veillette
System Architecture Director
Trilliant Inc.
Tel: 450-375-0556 ext. 237
[email-masked]<mailto:[email-masked]>
www.trilliantinc.com<http://www.trilliantinc.com/>

From: peter van der Stok [mailto:[email-masked]]
Sent: 1 avril 2015 08:06
To: Andy Bierman
Cc: Michel Veillette; [email-masked]; [email-masked]
Subject: Re: [core] COMI hash values globally unique vs. unique within a module

HI all,

There is a 50% probability of a clash with 7.7 x 10^4 names (80.000 names)

see table below

hex string

#bits

hash space
size
(2#bits)

Number of hashed elements such that {probability of at least one hash collision ≥ p}

p = 10−18

p = 10−15

p = 10−12

p = 10−9

p = 10−6

p = 0.1%

p = 1%

p = 25%

p = 50%

p = 75%

8

32

4.3×109

2

2

2

2.9

93

2.9×103

9.3×103

5.0×104

7.7×104

1.1×105

Peter

> <[email-masked]<mailto:[email-masked]>> wrote:

>> [email-masked]<mailto:[email-masked]>

>> www.trilliantinc.com<http://www.trilliantinc.com>

>> Cc: Thomas Watteyne; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>

> [email-masked]<mailto:[email-masked]>

---

From: peter van der Stok <[email-masked]>
Date: Thu, 02 Apr 2015 12:00:07 +0200

Hi Michel,

I understand the problem a bit better.
We always started from the assumption that servers are small and clients 
large.
Knowing your problem, I think to have solutions.
Let me work them out and present them the coming days.

Peter

Michel Veillette schreef op 2015-04-02 06:09:
> Hi Peter
> 
> When used in a distributed system, devices need to implement both the
> client side and the server side of CoMI. With the actual approach,
> each client need to have in storage the string representation of the
> canonical representation of the object path for every data nodes this
> client need to interact with. These stings are require to map entries
> of the “rehash” list with specific data nodes used by this CoMI
> client.
> 
> For the 6 TiSCH modules alone, these strings represents _5323 BYTES_
> (See attachment) and this exclude the meta data require to make them
> useful. In a device implementing 10 modules like 6TiSH which is not
> something unrealistic, this requirement represents _64 KB_ of storage
> space.
> 
> We also need to consider that CoMI clients need to dynamically
> retrieve the “rehash” list of each peer which required extra logic
> and significant amount of this limited bandwidth. Each entry in the
> “rehash” list take between 40 to 100 bytes. An _UNKNOWN NUMBER OF
> INSTANCES OF THIS “REHASH” LIST_ then need to be stored.
> 
> In comparison, the implementation of the module scope has values
> require between 2 to 4 bytes in the URI, between 1 to 3 bytes for each
> module included in the payload and a single registration by
> organization defining YANG modules. Module scope hash values don’t
> need to be discovered dynamically, they are known in advance based on
> the yang module definition and can be statically program in CoMI
> clients.
> 
> In its actual form, COMI don’t seem to be appropriate for
> distributed applications of constrained devices and I hope to see a
> resolution of this issue.
> 
> Michel Veillette
> www.trilliantinc.com [3]
> FROM: peter van der Stok [mailto:[email-masked]]
>  SENT: 1 avril 2015 08:06
>  TO: Andy Bierman
>  CC: Michel Veillette; [email-masked]; [email-masked]
>  SUBJECT: Re: [core] COMI hash values globally unique vs. unique
> within a module
> 
> HI all,
> 
> #BITS
> NUMBER OF HASHED ELEMENTS SUCH THAT {PROBABILITY OF AT LEAST ONE HASH
> COLLISION ≥ _P_}
> 
> _P_ = 10−18
> 
> _P_ = 10−15
> 
> _P_ = 10−12
> 
> _P_ = 10−9
> 
> _P_ = 10−6
> 
> _P_ = 0.1%
> 
> _P_ = 1%
> 
> _P_ = 25%
> 
> _P_ = 50%
> 
> _P_ = 75%
> 
> 8
> 
> 32
> 
> 4.3×109
> 
> 2
> 
> 2
> 
> 2
> 
> 2.9
> 
> 93
> 
> 2.9×103
> 
> 9.3×103
> 
> 5.0×104
> 
> 7.7×104
> 
> 1.1×105
> 
> Peter
> 
>>> www.trilliantinc.com [1]
>> https://www.ietf.org/mailman/listinfo/core [2]
> 
> 
> Links:
> ------
> [1] http://www.trilliantinc.com
> [2] https://www.ietf.org/mailman/listinfo/core
> [3] http://www.trilliantinc.com/

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 02 Apr 2015 14:55:36 +0200

Michel Veillette wrote:
> strings represents */5323 bytes/*

If we want to free the implementations completely of having to use these
strings, we'll need to assign numbers.  This can be done at the module
level, either manually or algorithmically.  Using a per-module hash to
do this is suboptimal; it is much better to fill a small linear space.

We then need a way to compose these numbers with numbers assigned to
module IDs.  SMIv2 had this way to name modules and their components...

Grüße, Carsten

---

From: Andy Bierman <[email-masked]>
Date: Thu, 2 Apr 2015 08:25:32 -0700

Hi,

I should make it clear that I was trying to use a module-id so
the objects in the module could be given a simple integer OID.
The goal was to support identifiers that could fit in 1 or 2 bytes.
But this was dropped when we changed to using hashes.

It might be a huge effort to create and use numeric module IDs,
but YANG module names tend to be long strings. It might be worth
it, if a per-module hash is used.

If the collisions were coupled to specific modules, then they might
be avoided before publication or the client can be hard-wired
to use the rehashed values from the start.

A client would not need to know the XPath strings for any objects.
It could be hard-coded to work with module X, Y, Z, and it would always
work, no matter what additional modules were added to the server.
This does seem very useful for constrained clients.

Andy

---

From: Andy Bierman <[email-masked]>
Date: Thu, 2 Apr 2015 08:30:51 -0700

> This does seem very useful for constrained clients.

A standard, deterministic renaming algorithm would be needed
to make this viable.  If each server is free to choose its own
rehash, then the client still needs to store all the strings, and
resolve the collisions at run-time instead of compile-time.
(So therefore a module-name or module-id would not solve anything).

Andy

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 02 Apr 2015 18:40:41 +0200

I think I'm losing track of what "this" is.
Assigning numbers when doing a (version of a) module should be doable,
even if it requires some additional tooling.
Assigning numbers to modules would require a registry.
No rehashing (or hashing at all) required.
(Now, that registry could be filled using a hash...)

BTW, I'm not sure that the "rehashing" in the current spec is the
easiest way to handle collisions -- I also don't understand how multiple
paths that arrive at the same hash value are handled.

Grüße, Carsten

Andy Bierman wrote:
> 6tisch mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/6tisch
> 
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 2 Apr 2015 17:09:05 +0000

Yes, we asked about that as well. 

It help to have a registry that guarantees the uniqueness of the first element in the path, so as to make it easier to check for collision within one path only.

Cheers,

Pascal

> From: 6tisch [mailto:[email-masked]] On Behalf Of Carsten Bormann
> Sent: jeudi 2 avril 2015 18:41
> To: Andy Bierman
> Cc: Michel Veillette; [email-masked]; [email-masked];
> [email-masked]
> Subject: Re: [6tisch] [core] COMI hash values globally unique vs. unique within a
> module
> 
> Assigning numbers when doing a (version of a) module should be doable, even if
> it requires some additional tooling.
> BTW, I'm not sure that the "rehashing" in the current spec is the easiest way to
> handle collisions -- I also don't understand how multiple paths that arrive at the
> same hash value are handled.
> 
> Grüße, Carsten
> 
> Andy Bierman wrote:
> >> I should make it clear that I was trying to use a module-id so the
> >> objects in the module could be given a simple integer OID.
> >> It might be a huge effort to create and use numeric module IDs, but
> >> YANG module names tend to be long strings. It might be worth it, if a
> >> per-module hash is used.
> >>
> >> be avoided before publication or the client can be hard-wired to use
> >> the rehashed values from the start.
> >>
> >> It could be hard-coded to work with module X, Y, Z, and it would
> >> always work, no matter what additional modules were added to the server.
> > A standard, deterministic renaming algorithm would be needed to make
> > this viable.  If each server is free to choose its own rehash, then
> > the client still needs to store all the strings, and resolve the
> > collisions at run-time instead of compile-time.
> >>> If we want to free the implementations completely of having to use
> >>> these strings, we'll need to assign numbers.  This can be done at
> >>> the module level, either manually or algorithmically.  Using a
> >>> per-module hash to do this is suboptimal; it is much better to fill a small
> linear space.
> >>>

---

From: Michel Veillette <[email-masked]>
Date: Thu, 2 Apr 2015 18:37:37 +0000

If I summarize:

Reducing the scope of uniqueness of YAND hash values to each module allows detection of hash collision(s) at design time instead of at run time.

To reduce this scope, we need to:
- Create a unique module identifier (e.g. 20 bits organization ID registered at IANA, 10 bits module ID)
- Add this module identifier to the URI (e.g. one to five base64 characters)
- Add a map at the root of the CBOR objects carry within the CoAP payload to associate module IDs with modules data nodes (e.g. one to five byes per module)

The problem that still need to be resolved is how we document data nodes rehash offline. 
- One option is to use the description statement of the YANG module or a new YANG statement specifically added for this purpose.
- Another option is create a IANA registry for these rehash values.

Hash collisions within YANG modules are very unlikely to happen and the solution don't need to be highly scalable. In that respect, using a IANA registry might be a good solution since it can be used for already published yang modules and can be use after the fact with any future YANG modules.

Michel Veillette

-----Original Message-----
From: Pascal Thubert (pthubert) [mailto:[email-masked]] 
Sent: 2 avril 2015 13:09
To: Carsten Bormann; Andy Bierman
Cc: Michel Veillette; [email-masked]; [email-masked]; [email-masked]
Subject: RE: [6tisch] [core] COMI hash values globally unique vs. unique within a module

Cheers,

Pascal

> Subject: Re: [6tisch] [core] COMI hash values globally unique vs. 
> unique within a module
> 
> easiest way to handle collisions -- I also don't understand how 
> multiple paths that arrive at the same hash value are handled.
> 
> Grüße, Carsten
> 
> Andy Bierman wrote:
> >> YANG module names tend to be long strings. It might be worth it, if 
> >> a per-module hash is used.
> >>
> >> be avoided before publication or the client can be hard-wired to 
> >> use the rehashed values from the start.
> >>
> >>> We then need a way to compose these numbers with numbers assigned 
> >>> to module IDs.  SMIv2 had this way to name modules and their components...
> >>>
> >>> Grüße, Carsten
> >

---

From: peter van der Stok <[email-masked]>
Date: Mon, 13 Apr 2015 10:34:59 +0200

Dear all,

Trying to work out all your recommendations, I fail to understand the 
need for the solution.

Large clients and small servers is not tru any more.
The assumption is that clients and servers are small, they are not 
dynamically augmented with new modules. They only know about hash values 
and have no knowledge what so ever of the corresponding names.

Let's concentrate on the one module clash first.
Apparently, it is envisaged to load modules that already contain hash 
clashes inside.
For me that is an unsolvable problem: There is one hash value that 
points to different names (memory stores) in the server.
Servers only know about hash values, they have no name tables. Suppose 
one of the names has been rehashed (where? certainly not within the 
server).
We might add a statement in the server that the old hash value goes to 
the new rehashed value.
It is not clear to me how the server can decide which memory location 
goes with the old hash value and which with the new value.

Apparently, something needs to be done before the module is loaded into 
the server. For me that means that only modules can be loaded without 
hash clashes.

Suppose in a given server two names from two modules clash. The solution 
is then that the module ID distinguishes between the two clashing 
values.
It is then proposed that module names are hashed. That solution is the 
same as saying that you need more than 32 bits for a hash value to 
reduce clash probability.

The only valid remaining approach is a registry that maps module name to 
a 32 bit? ID. Transporting the module ID means additional transport 
costs.

I can imagine though that in a given installation the servers and their 
module combinations are known.
Any clashes can be solved before load time. The appropriate code can be 
loaded in the small clients and servers.

The problem arrives when a new server with a set of modules (including a 
new module) finds a clash.
This clash does not affect the old clients and servers (they are not 
aware of the new module)
Consequently, the clash can be solved by renaming the clashing name in 
the newly added module.

All clients, and servers which have to use the clashing name of the new 
module will use the hash value of the renamed name, and do not need to 
be aware of the rehashing.

At the operational level, there are only unique hashes within an 
installation.
At the organization level, the rehash value of the new module needs to 
be registered and used when code for new clients or servers are 
generated.

Consequently, I do not see a need for module IDs.

Any mistakes in the above?

Peter

Michel Veillette schreef op 2015-04-02 20:37:
> If I summarize:
> 
> Reducing the scope of uniqueness of YAND hash values to each module
> allows detection of hash collision(s) at design time instead of at run
> time.
> 
> - Add a map at the root of the CBOR objects carry within the CoAP
> payload to associate module IDs with modules data nodes (e.g. one to
> five byes per module)
> 
> - One option is to use the description statement of the YANG module or
> a new YANG statement specifically added for this purpose.
> Hash collisions within YANG modules are very unlikely to happen and
> the solution don't need to be highly scalable. In that respect, using
> a IANA registry might be a good solution since it can be used for
> already published yang modules and can be use after the fact with any
> future YANG modules.
> 
> Michel Veillette
> It help to have a registry that guarantees the uniqueness of the first
> element in the path, so as to make it easier to check for collision
> within one path only.
> 
> Cheers,
> 
> Pascal
> 
>

---

From: Andy Bierman <[email-masked]>
Date: Mon, 13 Apr 2015 09:14:14 -0700

On Mon, Apr 13, 2015 at 1:34 AM, peter van der Stok <[email-masked]> wrote:
> Dear all,
>
> Trying to work out all your recommendations, I fail to understand the need
> for the solution.
>
> dynamically augmented with new modules. They only know about hash values and
> have no knowledge what so ever of the corresponding names.
>

The term "dynamically loaded" is misleading, because a new
revision of the device, or a device that supports firmware upgrade,
can have new YANG modules added.

> For me that is an unsolvable problem: There is one hash value that points to
> different names (memory stores) in the server.
> Servers only know about hash values, they have no name tables. Suppose one
> of the names has been rehashed (where? certainly not within the server).
> We might add a statement in the server that the old hash value goes to the
> new rehashed value.
> It is not clear to me how the server can decide which memory location goes
> with the old hash value and which with the new value.
>

If a value gets rehashed, it is because there is a collision.
I am not sure if module numbers can be added to YANG,
but it should be possible to either avoid 1-module collisions
or add a YANG extension to the module to resolve the collision
so that every implementation uses the same rehash (known in advance).

> Apparently, something needs to be done before the module is loaded into the
> server. For me that means that only modules can be loaded without hash
> clashes.
>

For modules intended for CoMI, we can certainly
make sure no names used in the module produce any collisions.

> Suppose in a given server two names from two modules clash. The solution is
> then that the module ID distinguishes between the two clashing values.
> It is then proposed that module names are hashed. That solution is the same
> as saying that you need more than 32 bits for a hash value to reduce clash
> probability.
>
> The only valid remaining approach is a registry that maps module name to a
> 32 bit? ID. Transporting the module ID means additional transport costs.
>

It should be possible to come up with a short module-id format,
and only use the long form (full module name) if no short-form exists.

> loaded in the small clients and servers.

This does not allow for the old client/new server scenario to keep working,
if the new server adds a module with a hash collision.

> The problem arrives when a new server with a set of modules (including a new
> module) finds a clash.
> This clash does not affect the old clients and servers (they are not aware
> of the new module)

But what if the module they know about is the one that gets rehashed?
There is no saved or canonical order for processing YANG modules.

> Consequently, the clash can be solved by renaming the clashing name in the
> newly added module.
>

Only if the collision is detected and corrected before
the new module is published.

> module will use the hash value of the renamed name, and do not need to be
> aware of the rehashing.
>
> At the organization level, the rehash value of the new module needs to be
> registered and used when code for new clients or servers are generated.
>

YANG is modular, and different naming authorities (SDOs and vendors)
work at different speeds and publish independently of each other.
Applications can use different modules on the same server without
impacting each other.  Vendors can add their own modules before
or after standard modules are written and added.

If module A and module B both have objects that hash to the same value
then they cannot be used together without re-hashing 1 of the objects.

> Any mistakes in the above?

I think the combinations of modules that will be available
on a given implementation cannot be controlled in advance.
We cannot assume all client devices and server devices can
be upgraded together (flag day upgrade).

Andy

---

From: peter van der Stok <[email-masked]>
Date: Tue, 14 Apr 2015 11:05:31 +0200

Hi Andy,

 From Michel and you I understand that the problems with rehashing come 
from:
- Different manufacturers may provide servers with the same module set, 
but may have chosen different names to rehash in case of clash.
- Servers may be upgraded with modules, and may need rehashing.

Not choosing module identifiers in the name hash, has as consequence 
that in case of clash in a server, the server needs to announce the name 
that is rehashed.
This announcement can be done in a standardized format and pre-loaded 
servers with clashes MUST be accompanied by such a file.

Given that small clients need to be prepared when servers are added or 
modules are added to existing servers, Appropriate code can be loaded in 
these clients when needed.
The existence of rehashes does not unnecessarily complicate this work.

The choice is then between:
- no module IDs: rehashes need to be administrated and taken into 
account when servers are added or functionality is added.
- module ID: Registry needs to be defined, maintained, and the module ID 
must be transported in every exchange.

The module ID is compulsory when the client does an automatic discovery 
of servers and needs to use the same hash values independent of the 
arrival of new servers or the extension of servers.

Is this a correct summary of the arguments involved?

Peter

Andy Bierman schreef op 2015-04-13 18:14:
>> need
>> points to
>> one
>> the
>> goes
>> same
>> aware
>> the
>> be

---

From: Michel Veillette <[email-masked]>
Date: Tue, 14 Apr 2015 16:59:02 +0000

Hi Peter

I’m not sure if your summary capture the impossibility to avoid multiple set of YANG hashes for a same module during a deployment

unless a central repository of hashes is established from the start for all standard and manufacture modules.

For example

·         Let assume the following distribution of YANG hashes

·         Let also assume that modules have no hash clashes or data node identifier re-assignment have been done offline.

·         Let assume that device x implements module C

·         Then, device y implements module B and module C, hash clashes A/C need to be resolved to create Module C’

·         Finally, device z is introduced with support of modules A, B and C, both hash clashes A/C and B/C need to be resolved to create Module C’’

At the end of this sequence, we have three devices (x, y, and z) which all implement module C with three different version of YANG hashes. To make this work, the proposed rehash mechanism is needed and each node need to dynamically discover rehash table from each peer and need tens of kB of URI strings for the lockup in these rehash tables.

Unless we want to put in place this central repository of YANG hashes, scoping the uniqueness of data node identifiers by module seem to be the only solution.

Michel Veillette

Trilliant Inc.

www.trilliantinc.com

-----Original Message-----
From: peter van der Stok [mailto:[email-masked]]
Sent: 14 avril 2015 05:06
To: Andy Bierman
Cc: [email-masked]; Michel Veillette; Pascal Thubert (pthubert); Carsten Bormann; [email-masked]; Core
Subject: Re: [6tisch] [core] COMI hash values globally unique vs. unique within a module

Hi Andy,

from:

- Different manufacturers may provide servers with the same module set, but may have chosen different names to rehash in case of clash.

Not choosing module identifiers in the name hash, has as consequence that in case of clash in a server, the server needs to announce the name that is rehashed.

This announcement can be done in a standardized format and pre-loaded servers with clashes MUST be accompanied by such a file.

Given that small clients need to be prepared when servers are added or modules are added to existing servers, Appropriate code can be loaded in these clients when needed.

- no module IDs: rehashes need to be administrated and taken into account when servers are added or functionality is added.

- module ID: Registry needs to be defined, maintained, and the module ID must be transported in every exchange.

The module ID is compulsory when the client does an automatic discovery of servers and needs to use the same hash values independent of the arrival of new servers or the extension of servers.

Peter

Andy Bierman schreef op 2015-04-13 18:14:

> On Mon, Apr 13, 2015 at 1:34 AM, peter van der Stok

> <[email-masked]<mailto:[email-masked]>> wrote:

>> dynamically augmented with new modules. They only know about hash

>> values and have no knowledge what so ever of the corresponding names.

> The term "dynamically loaded" is misleading, because a new revision of

> the device, or a device that supports firmware upgrade, can have new

> YANG modules added.

>> Servers only know about hash values, they have no name tables.

>> Suppose one of the names has been rehashed (where? certainly not

>> within the server).

>> We might add a statement in the server that the old hash value goes

>> to the new rehashed value.

> I am not sure if module numbers can be added to YANG, but it should be

> possible to either avoid 1-module collisions or add a YANG extension

> to the module to resolve the collision so that every implementation

> uses the same rehash (known in advance).

>> Apparently, something needs to be done before the module is loaded

>> into the server. For me that means that only modules can be loaded

>> without hash clashes.

> For modules intended for CoMI, we can certainly make sure no names

> used in the module produce any collisions.

>> Suppose in a given server two names from two modules clash. The

>> solution is then that the module ID distinguishes between the two

>> clashing values.

>> It is then proposed that module names are hashed. That solution is

>> the same as saying that you need more than 32 bits for a hash value

>> to reduce clash probability.

>> The only valid remaining approach is a registry that maps module name

>> to a

>> 32 bit? ID. Transporting the module ID means additional transport

> It should be possible to come up with a short module-id format, and

> only use the long form (full module name) if no short-form exists.

>> I can imagine though that in a given installation the servers and

>> their module combinations are known.

>> Any clashes can be solved before load time. The appropriate code can

>> be loaded in the small clients and servers.

> This does not allow for the old client/new server scenario to keep

> working, if the new server adds a module with a hash collision.

>> The problem arrives when a new server with a set of modules

>> (including a new

>> Consequently, the clash can be solved by renaming the clashing name

>> in the newly added module.

>> All clients, and servers which have to use the clashing name of the

>> new

>> registered and used when code for new clients or servers are

>>> allows detection of hash collision(s) at design time instead of at

>>> run

>>> - Create a unique module identifier (e.g. 20 bits organization ID

>>> registered at IANA, 10 bits module ID)

>>> - Add this module identifier to the URI (e.g. one to five base64

>>> characters)

>>> The problem that still need to be resolved is how we document data

>>> nodes rehash offline.

>>> - One option is to use the description statement of the YANG module

>>> or

>>> Cc: Michel Veillette; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>;

>>> Subject: RE: [6tisch] [core] COMI hash values globally unique vs.

>>> It help to have a registry that guarantees the uniqueness of the

>>> first

>>>> From: 6tisch [mailto:[email-masked]] On Behalf Of Carsten

>>>> Bormann

>>>> Cc: Michel Veillette; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>;

>>>> Assigning numbers when doing a (version of a) module should be

>>>> doable,

>>>> > On Thu, Apr 2, 2015 at 8:25 AM, Andy Bierman <[email-masked]<mailto:[email-masked]>>

>>>> wrote:

>>>> >> always work, no matter what additional modules were added to the

>>>> >> server.

>>>> >> On Thu, Apr 2, 2015 at 5:55 AM, Carsten Bormann <[email-masked]<mailto:[email-masked]>> wrote:

>>>> >>> per-module hash to do this is suboptimal; it is much better to

>>>> >>> fill a small

>>>> >>> to module IDs.  SMIv2 had this way to name modules and their

>>>> >>> components...

>>>> > [email-masked]<mailto:[email-masked]>

>>>> [email-masked]<mailto:[email-masked]>

---

From: peter van der Stok <[email-masked]>
Date: Wed, 15 Apr 2015 09:00:19 +0200

HI Michel,

Your scenario perfectly fits in with my summary.
The proposal is that each server is accompanied by a file that mentions 
the names that are rehashed for a given device.

Of course, you can generate unique hash values for a whole installation 
for which you need an installation repository, but as pointed out by 
Andy,
new servers with new modules are added and new modules are added to 
existing servers, which invalidates the installation repository.

Assuming that "small" clients do not dynamically discover servers, and 
that the code (or access tables) are generated offline and down-loaded 
into the clients,
you do not need an installation repository but can handle the table 
generation for a client with only the clash information of the involved 
servers.

The disadvantage is that you need a table in the client that gives the 
hash value as function of the server identity.
That table  does not need to be large, given the very low clash 
probability (and may be non-existent for most clients).

However, when clients try to build these tables dynamically, and the 
clients do not have space to store all accessible names, and they 
dynamically discover the servers,
then you need the module identifiers, which need a centrally managed 
repository.

I thought that for 6tisch all servers were kind of fixed with no changes 
to the module contents; and clients were small accessing a non changing 
set of servers.
In that case I would suggest to handle table generation off-line. In the 
clients the hash values can be the same for all servers, with 0-3 
exceptions where a given server uses a different hash.

For the dynamic case, with small clients that cannot store the names, I 
am afraid that using module identifiers is a better solution.
However, we can make the module identifier optional, and specify it in a 
query parameter.
That avoids transporting the module identifier when it is not needed.

Peter

Michel Veillette schreef op 2015-04-14 18:59:
> Hi Peter
> 
> I’m not sure if your summary capture the impossibility to avoid
> multiple set of YANG hashes for a same module during a deployment
> 
> unless a central repository of hashes is established from the start
> for all standard and manufacture modules.
> 
> For example
> 
>  · Let also assume that modules have no hash clashes or data node
> identifier re-assignment have been done offline.
> 
>  · Finally, device z is introduced with support of modules A, B and
> C, both hash clashes A/C and B/C need to be resolved to create Module
> C’’
> 
> At the end of this sequence, we have three devices (x, y, and z) which
> all implement module C with three different version of YANG hashes. To
> make this work, the proposed rehash mechanism is needed and each node
> need to dynamically discover rehash table from each peer and need tens
> of kB of URI strings for the lockup in these rehash tables.
> 
> Unless we want to put in place this central repository of YANG hashes,
> scoping the uniqueness of data node identifiers by module seem to be
> the only solution.
> 
> Michel Veillette
> 
>  Cc: [email-masked]; Michel Veillette; Pascal Thubert
> (pthubert); Carsten Bormann; [email-masked]; Core
> - Different manufacturers may provide servers with the same module
> set, but may have chosen different names to rehash in case of clash.
> 
> that in case of clash in a server, the server needs to announce the
> name that is rehashed.
> 
> modules are added to existing servers, Appropriate code can be loaded
> in these clients when needed.
> 
> - module ID: Registry needs to be defined, maintained, and the module
> ID must be transported in every exchange.
> 
> The module ID is compulsory when the client does an automatic
> discovery of servers and needs to use the same hash values independent
> of the arrival of new servers or the extension of servers.
> 
>> <[email-masked]> wrote:
> 
>>> Dear all,
> 
>>> 
> 
>>>>> > On Thu, Apr 2, 2015 at 8:25 AM, Andy Bierman
> <[email-masked]>
> 
>>>>> wrote:
> 
>>>>> >> Hi,
> 
>>>>> >>
> 
> to
>>>>> > https://www.ietf.org/mailman/listinfo/6tisch [2]
> 
>>>>> >
> 
>>>>> >
> 
>>>>> 
> 
>>>>> https://www.ietf.org/mailman/listinfo/6tisch [2]
> 
> Links:
> ------
> [2] https://www.ietf.org/mailman/listinfo/6tisch

---

From: Michel Veillette <[email-masked]>
Date: Wed, 15 Apr 2015 14:07:20 +0000

===== About this concept of "handle table generation off-line".

I don’t understand how this approach work, this seem a chicken and egg issue

The table need to have:
- A identifier of a peer CoMI server (IPv6 address)
- The rehash value use on this server (Unsigned 32 bits)
- The identifier of the attribute affected (If not the canonical representation of the path identifier, what it is?)

Considering also the number of peer CoMI servers in some application space (thousands of peers in a NAN network for example), I don't see this as a viable solution.

===== About "we can make the module identifier optional, and specify it in a query parameter"

How can we make the module identifier optional and avoid interoperability issues?
If we accept the introduction of a managed module identifier, I recommend to make it mandatory.

===== About " avoids transporting the module identifier when it is not needed"

For me, the current discussion is about managed vs. unmanaged identifiers, not about protocol overhead.
If we want to discuss overhead, we should create an independent thread on this subject to discuss things like
support of managed data node identifiers which can reduce significantly the payload size even with the presence
of the module identifier.

Michel Veillette

-----Original Message-----
From: peter van der Stok [mailto:[email-masked]] 
Sent: 15 avril 2015 03:00
To: Michel Veillette
Cc: [email-masked]; Andy Bierman; Pascal Thubert (pthubert); Carsten Bormann; [email-masked]; Core
Subject: RE: [6tisch] [core] COMI hash values globally unique vs. unique within a module

HI Michel,

Your scenario perfectly fits in with my summary.
The proposal is that each server is accompanied by a file that mentions the names that are rehashed for a given device.

Of course, you can generate unique hash values for a whole installation for which you need an installation repository, but as pointed out by Andy, new servers with new modules are added and new modules are added to existing servers, which invalidates the installation repository.

Assuming that "small" clients do not dynamically discover servers, and that the code (or access tables) are generated offline and down-loaded into the clients, you do not need an installation repository but can handle the table generation for a client with only the clash information of the involved servers.

The disadvantage is that you need a table in the client that gives the hash value as function of the server identity.
That table  does not need to be large, given the very low clash probability (and may be non-existent for most clients).

However, when clients try to build these tables dynamically, and the clients do not have space to store all accessible names, and they dynamically discover the servers, then you need the module identifiers, which need a centrally managed repository.

I thought that for 6tisch all servers were kind of fixed with no changes to the module contents; and clients were small accessing a non changing set of servers.
In that case I would suggest to handle table generation off-line. In the clients the hash values can be the same for all servers, with 0-3 exceptions where a given server uses a different hash.

For the dynamic case, with small clients that cannot store the names, I am afraid that using module identifiers is a better solution.
However, we can make the module identifier optional, and specify it in a query parameter.
That avoids transporting the module identifier when it is not needed.

Peter

Michel Veillette schreef op 2015-04-14 18:59:
>  · Finally, device z is introduced with support of modules A, B and C, 
> both hash clashes A/C and B/C need to be resolved to create Module C’’
>

---

From: peter van der Stok <[email-masked]>
Date: Fri, 17 Apr 2015 08:45:09 +0200

Hi Michel,

short answers in text.

> - The identifier of the attribute affected (If not the canonical
> representation of the path identifier, what it is?)
> 
> Considering also the number of peer CoMI servers in some application
> space (thousands of peers in a NAN network for example), I don't see
> this as a viable solution.
> 

To be certain: we talk about very small clients with no storage space 
for YANG names or host names.
Let's agree to disagree:
To me: Administrating in the this client 1-2 groups of servers with 1-2 
re-hashes looks like a much smaller problem (at least in storage size) 
than
the already compulsory administering in the client of
thousands (probably changing) IPv6 addresses of servers and their 
associated (also changing) YANG nodes (hash values).

I am sure lots of optimizations can be invented for the latter, but 
similar things can be done for the first as well.

> recommend to make it mandatory.

Not make it optional from implementation  point of view but from a 
request specification point of view.

Greetings,

Peter