Subject: [core] draft-bierman-core-yid-00.txt questions

From: David Reid <[email-masked]>
Date: Wed, 24 Aug 2016 16:35:26 -0400

I read draft-bierman-core-yid-00.txt and have a few questions.

Will all IETF standard yang modules be included in the YANG identifier 
registry or just ones that might be used on constrained devices? 

In order to assign numbers, is it correct that I need the first revision of 
the module or else the current revision and the registry assignments for the 
previous revision?

What is the benefit of assigning values using hashing over sequentially 
assigning values? 

When there is a hash collision, would it be possible to rehash the value
to get a unique number so that we never have to manually assign numbers and
thus never need to register the numbers in the registry?

Why does module-id need to be added to the YANG module names registry since
it is also in the YANG identifier registry? 

Would it make sense to put the module-id inside the yang module with a yid 
extension so that I would not have to go lookup that information from a 
registry? 

Would it be possible to assign the module-id based on information in the 
module, for example a hash of the namespace and maybe the revision date. 
That way, a module-id would not have to be assigned and maintained in a 
registry.

If I want to handle private modules, do I have to create my own registry?
It seems important that private modules be supported. Could we re-use the
SMI enterprise number assignments for creating module-ids for private modules?

Who will assign the local-id numbers? Is that done by the working group that 
defines the YANG module?

-David Reid

---

From: Andy Bierman <[email-masked]>
Date: Wed, 24 Aug 2016 14:22:47 -0700

> registry or just ones that might be used on constrained devices?

I think all modules.
We want to support unconstrained devices on constrained networks.

> the module or else the current revision and the registry assignments for

I think in all numbering schemes (as Michel pointed out) you need
the current registration entry and the new module revision.

> What is the benefit of assigning values using hashing over sequentially

There is overhead ir reading and processing a giant list of mappings.
Automatic assignment is risky because both sides need to agree on
the object to number mapping.  Detecting these issues is very difficult.

The YANG Hash algorithm is designed to use the path string,
which is permanent and cannot change no matter how the
YANG is refactored.  The murmur hash is a stable algorithm.
There is not a lot that can go wrong for the 2 peers to disagree
on the hashes (except for collisions)

> thus never need to register the numbers in the registry?

yes, this has been suggested.
The problem with auto-rehashing before was inter-module clashes.
Now those are not possible so automatic rehashing is feasible.

> it is also in the YANG identifier registry?

I guess it is not needed since the module name is in both registries already

> extension so that I would not have to go lookup that information from a

I suppose -- but how to prevent duplicates and cut-and-paste errors?

> That way, a module-id would not have to be assigned and maintained in a

I think private module-id would be better, using a range reserved for
temporary
assignments.

How do you resolve hash collisions for module-id?

> SMI enterprise number assignments for creating module-ids for private

The ietf-yid module has a schema for the entire registry.
How to use the registry is a protocol issue that needs to be decided.
If the server advertises  its own registry vs. a public registry,
then it is using a private registry.  If all devices in the system agree
on which registry to use, then everything works.

> Who will assign the local-id numbers? Is that done by the working group

I would expect IETF modules to use hashes by default but for
some modules that seem useful to constrained devices, then
manual numbering could be done instead by the WG.

> -David Reid

Andy

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

---

From: Michel Veillette <[email-masked]>
Date: Wed, 24 Aug 2016 23:22:43 +0000

Hi David, Hi Andy

[MV] Inline

From: core [mailto:[email-masked]] On Behalf Of Andy Bierman
Sent: Wednesday, August 24, 2016 5:23 PM
To: David Reid <[email-masked]>
Cc: Core <[email-masked]>
Subject: Re: [core] draft-bierman-core-yid-00.txt questions

On Wed, Aug 24, 2016 at 1:35 PM, David Reid <[email-masked]<mailto:[email-masked]>> wrote:
I read draft-bierman-core-yid-00.txt and have a few questions.

I think all modules.

[MV] The request we got so far is all YANG modules published in RFCs.

[MV] I disagree, see my previous email which explain why all YIDs/SIDs need to be registered even if generated using a hash.

[MV] Just adding the module ID in the yang file is not sufficient to use a .yang file, all YIDs/SIDs need to be added.
[MV] Having YIDs/SIDs in yang files will make their maintenance more complex.
[MV] BTW, a pyang plugin already exist to automatically generate and update a .sid file from a .yang file
[MV] See https://github.com/core-wg/yang-cbor/blob/master/sid.py

I think private module-id would be better, using a range reserved for temporary
assignments.

[MV] To obtain a smaller encoding, I personally believe that the sequential numbering will be used.
[MV] With sequential numbering, all current YANG modules defined in RFCs can be assigned within the first 6500 SIDs which will be encoded as 3 bytes for the first reference and typically as 1 bytes for the following ones using delta encoding.
[MV] With hashes, only one YANG module can be assigned within that range.

-David Reid

Andy

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

---

From: David Reid <[email-masked]>
Date: Wed, 24 Aug 2016 23:24:29 -0400

>> There is overhead ir reading and processing a giant list of mappings.

The assignment only happens one-time, so I don't see a problem with a
little overhead (which I think would be minimal anyway).

>> on the hashes (except for collisions)

I would think we could write an algorithm that would guarantee the same
number every time. Although I have not thought through all the issues that 
come up with revisions, maybe this is harder than I think.

> [MV] I disagree, see my previous email which explain why all YIDs/SIDs
> need to be registered even if generated using a hash.

As long as I have either all revisions of a module or the YIDs from
the previous revision, I can generate the numbers for the module. I don't
think I need it to be in a central registry.

>>> extension so that I would not have to go lookup that information
>>> from a registry?

>> I suppose -- but how to prevent duplicates and cut-and-paste errors?

We would still need a registry to prevent duplicates. But only the
module writer would need to access the registry. The module users would
have the information in the yang module and would not have to look at the
registry.

> [MV] Just adding the module ID in the yang file is not sufficient to
> use a .yang file, all YIDs/SIDs need to be added.

If YIDs are generated by hashing with auto rehashing on collisions, the
YIDs would not have to be explicitly listed in the module. They could be
auto-generated and stored in a different file.

> [MV] Having YIDs/SIDs in yang files will make their maintenance more

Yes, it makes it more complex for the module writers. But it is easier on
the users of the module.

> [MV] See [2]https://github.com/core-wg/yang-cbor/blob/master/sid.py

>> temporary assignments.

I think you are right. I was just hoping we could avoid requiring module
writers to register a module-id by finding a way to auto assign it.

>> How do you resolve hash collisions for module-id?

I don't have a good solution. I was hoping the probability of collision
would be low enough to be acceptable, or we could add the first revision
in the number to further reduce collisions. But I don't have a way
to resolve collisions.

>>> Who will assign the local-id numbers? Is that done by the working
>>> group that defines the YANG module?

> [MV] With sequential numbering, all current YANG modules defined in
> RFCs can be assigned within the first 6500 SIDs which will be encoded
> as 3 bytes for the first reference and typically as 1 bytes for the
> following ones using delta encoding.

> [MV] With hashes, only one YANG module can be assigned within that

Is the sequential numbering auto-assigned or manually assigned?

-David Reid

---

From: Andy Bierman <[email-masked]>
Date: Wed, 24 Aug 2016 20:50:48 -0700

> come up with revisions, maybe this is harder than I think.
So many YANG statements are unordered.
There is no order to how imports and includes are processed,
which severely affects statement order.  Top level statements
have no order and can change at any time.

Augment statements can change order and be refactored at any time.
There is no order to any augmented node (at any level).
Only RPC input and output nodes require descendant nodes to stay
in the same relative order.

Import or include without revision of groupings, etc. is not deterministic,
The revision that gets used depends on the implementation.
Almost all imports and includes are without revision-date, so
this is a significant problem.

> think I need it to be in a central registry.

Any algorithm that relies on statement order to decide which node is
rehashed
will not work.  Maybe it would be possible to rehash all collisions and
change the path for each (e.g., prepend '_') , and keep doing it until N
new hashes are found.

> Yes, it makes it more complex for the module writers. But it is easier on

I agree that the number of tools that have to know all the
complex numbering algorithms should be minimized.
The [local-id, path] tuples work no matter how the local-id was assigned.
The registry reader tool can be simple.

> > sequential numbering will be used.

what is sequential about nested lists and choices?
Siblings may end up far apart.

Andy

---

From: Michel Veillette <[email-masked]>
Date: Thu, 25 Aug 2016 14:15:52 +0000

Hi David

About " Is the sequential numbering auto-assigned or manually assigned? "

If you use a tool such the pyang plugin, they will be automatically assigned.

For example, the command:
   pyang --generate-sid-file 20000:100 [email-masked]

Generate the file [email-masked] in attachment.

The command:
  pyang --update-sid-file [email-masked]  [email-masked]

Generate the file [email-masked] in attachment.

It is important to note that sequential numbering doesn't means that two data nodes defined sequentially in .yang file will receive consecutive IDs.
As you known, order may change and grouping may be introduced between versions.
It means that IDs are assigned sequentially from 1 using some arbitrary order.
If a .yang module have 14 YANG items, they will be numbered from 1 to 14.
If the next version add 5 YANG items, they will be numbered from 15 to 19.

Regards,
Michel

-----Original Message-----
From: core [mailto:[email-masked]] On Behalf Of David Reid
Sent: Wednesday, August 24, 2016 11:24 PM
To: [email-masked]
Subject: Re: [core] draft-bierman-core-yid-00.txt questions

>>> What is the benefit of assigning values using hashing over 
>>> sequentially assigning values?

>> There is overhead ir reading and processing a giant list of mappings.

The assignment only happens one-time, so I don't see a problem with a little overhead (which I think would be minimal anyway).

>> Automatic assignment is risky because both sides need to agree on the 
>> object to number mapping.  Detecting these issues is very difficult.
>> The YANG Hash algorithm is designed to use the path string, which is 
>> permanent and cannot change no matter how the YANG is refactored.  
>> The murmur hash is a stable algorithm.
>> There is not a lot that can go wrong for the 2 peers to disagree on 
>> the hashes (except for collisions)

I would think we could write an algorithm that would guarantee the same number every time. Although I have not thought through all the issues that come up with revisions, maybe this is harder than I think.

>>> When there is a hash collision, would it be possible to rehash the 
>>> value to get a unique number so that we never have to manually 
>>> assign numbers and thus never need to register the numbers in the registry?

> need to be registered even if generated using a hash.

As long as I have either all revisions of a module or the YIDs from the previous revision, I can generate the numbers for the module. I don't think I need it to be in a central registry.

>>> Would it make sense to put the module-id inside the yang module with 
>>> a yid extension so that I would not have to go lookup that 
>>> information from a registry?

>> I suppose -- but how to prevent duplicates and cut-and-paste errors?

We would still need a registry to prevent duplicates. But only the module writer would need to access the registry. The module users would have the information in the yang module and would not have to look at the registry.

> use a .yang file, all YIDs/SIDs need to be added.

If YIDs are generated by hashing with auto rehashing on collisions, the YIDs would not have to be explicitly listed in the module. They could be auto-generated and stored in a different file.

> [MV] Having YIDs/SIDs in yang files will make their maintenance more 

Yes, it makes it more complex for the module writers. But it is easier on the users of the module.

> [MV] BTW, a pyang plugin already exist to automatically generate and 
> update a .sid file from a .yang file [MV] See 
> [2]https://github.com/core-wg/yang-cbor/blob/master/sid.py

>>> Would it be possible to assign the module-id based on information in 
>>> the module, for example a hash of the namespace and maybe the revision date.
>>> That way, a module-id would not have to be assigned and maintained 
>>> in a registry.

>> I think private module-id would be better, using a range reserved for 

I think you are right. I was just hoping we could avoid requiring module writers to register a module-id by finding a way to auto assign it.

>> How do you resolve hash collisions for module-id?

I don't have a good solution. I was hoping the probability of collision would be low enough to be acceptable, or we could add the first revision in the number to further reduce collisions. But I don't have a way to resolve collisions.

>> I would expect IETF modules to use hashes by default but for some 
>> modules that seem useful to constrained devices, then manual 
>> numbering could be done instead by the WG.

-David Reid

---

From: Andy Bierman <[email-masked]>
Date: Thu, 25 Aug 2016 08:33:56 -0700

>   pyang --update-sid-file [email-masked]  [email-masked]
Where is the algorithm explained in enough detail that multiple
independent implementations will all produce the exact same results?

Andy

> It is important to note that sequential numbering doesn't means that two
> data nodes defined sequentially in .yang file will receive consecutive IDs.
> As long as I have either all revisions of a module or the YIDs from the
> previous revision, I can generate the numbers for the module. I don't think
> I need it to be in a central registry.
>
> We would still need a registry to prevent duplicates. But only the module
> writer would need to access the registry. The module users would have the
> information in the yang module and would not have to look at the registry.
>
> would be low enough to be acceptable, or we could add the first revision in
> the number to further reduce collisions. But I don't have a way to resolve
> collisions.
>

---

From: Michel Veillette <[email-masked]>
Date: Thu, 25 Aug 2016 15:54:51 +0000

Hi Andy, Hi David

There is no requirement to have multiple tools or algorithms producing the same result.
The only requirements we have for YIDs/SIDs are:
- To be unique (Within the allocated range without duplicate)
- To be permanent (Registered within a private or public registry)

As demonstrated in one of my last email, all YIDs/SIDs must be registered even if generated from a hash.
The algorithm don’t need to be mandated, the registered YIDs/SIDs are the IDs to use.

The currently recommended algorithm is described in
https://tools.ietf.org/html/draft-somaraju-core-sid-01#section-3

   o  A tool extracts the different items defined for a specific YANG
      module.

   o  The list of items is ordered by type and label.

   o  SIDs are assigned sequentially for the entry point up to the size
      of the registered SID range.  It is important to note that
      sequentially assigning SIDs optimizes the CBOR serialization due
      to the use of delta encoding.

   o  If the number of items exceeds the SID range(s) allocated to a
      YANG module, an extra range is added for subsequent assignments.

   SIDs are assigned permanently, items introduced by a new revision of

   a YANG module are added to the list of SIDs already assigned.  This

   process can also be automated using the same method described above

   except that the assignment need to be restarted from the highest SID

   already assigned.

Since the file is fully defined, ordering the list within this file and assigning sequentially IDs to these
entries can be performed by different tools with the same result.

Regards,
Michel

From: Andy Bierman [mailto:[email-masked]]
Sent: Thursday, August 25, 2016 11:34 AM
To: Michel Veillette <[email-masked]>
Cc: David Reid <[email-masked]>; [email-masked]
Subject: Re: [core] draft-bierman-core-yid-00.txt questions

On Thu, Aug 25, 2016 at 7:15 AM, Michel Veillette <[email-masked]<mailto:[email-masked]>> wrote:
Hi David

For example, the command:
   pyang --generate-sid-file 20000:100 [email-masked]<mailto:[email-masked]>

Generate the file [email-masked]<mailto:[email-masked]> in attachment.

The command:
  pyang --update-sid-file [email-masked]<mailto:[email-masked]>  [email-masked]<mailto:[email-masked]>

Andy

Generate the file [email-masked]<mailto:[email-masked]> in attachment.

Regards,
Michel

-----Original Message-----
From: core [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of David Reid
Sent: Wednesday, August 24, 2016 11:24 PM
To: [email-masked]<mailto:[email-masked]>
Subject: Re: [core] draft-bierman-core-yid-00.txt questions

-David Reid

---

From: Alexander Pelov <[email-masked]>
Date: Thu, 25 Aug 2016 18:01:09 +0200

Hi Andy,

> Le 25 août 2016 à 17:33, Andy Bierman <[email-masked]> a écrit :
> 
> 
> 
> On Thu, Aug 25, 2016 at 7:15 AM, Michel Veillette <[email-masked] <mailto:[email-masked]>> wrote:
> Hi David
> 

You don’t need this explicitly. You’ll need the SID file generated by the tool. There is a description on the way the current implementation works of course.

Of course, you may imagine Registries that choose policies / allocations that COULD provide for ways of deterministically generating on the fly your identifiers. But the most common denominator should be the SID file.

Example (which I am inventing on the go, so you can modify it according to your vision):
A Hash-based Registry (HREG) is created and IANA allocates SIDs 0x00010000-0x000F0000.
HREG publishes as its official policy that all modules registered under it must generate their SID files using the murmur32 hash, and the size of the hash must be at least 10 bits. (for the sake of the example). The registry MAY also specify that no hash collisions are allowed, e.g. any modification of a module must result in different hashes for each element. If by chance, there is a hash collision, it is up to the author to change the naming in such a way, as to be collision-free. 
HREG may provide its own SID-generating tool, which performs the hash generation, verifies that there are no collisions, and outputs a standard SID file (where the IDs are generated by hashing).

Once this is done, depending on the policy of HREG, it may publish the SID file for interoperability with the whole world, or potentially keep it private. The meta-data publishes by the HREG you could have only thing like: module entry point + range size (10 bits.. or more - could be flexible per module) + some metadata (e.g. indicating that this is no_collision_hash_generated).

This, however, is in my opinion, out of the scope of this draft. We should provide the minimal functions which allow these systems to be built, to coexist and to interoperate. 

Best,
Alexander

> From: core [mailto:[email-masked] <mailto:[email-masked]>] On Behalf Of David Reid
> To: [email-masked] <mailto:[email-masked]>
> > [2]https://github.com/core-wg/yang-cbor/blob/master/sid.py <https://github.com/core-wg/yang-cbor/blob/master/sid.py>
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/core <https://www.ietf.org/mailman/listinfo/core>
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/core <https://www.ietf.org/mailman/listinfo/core>
> 
>

---

From: Andy Bierman <[email-masked]>
Date: Thu, 25 Aug 2016 09:02:58 -0700

> There is no requirement to have multiple tools or algorithms producing the

Then it isn't auto-numbering.
It is just an offline tool to assign numbers to YANG statements.
So there is no need to standardize SID at all.
There is just a list of [id, path] mappings in a registry entry,
which is what the YID draft proposes.  (centralized or distributed list of
mappings).

Andy

> *From:* Andy Bierman [mailto:[email-masked]]
> *Sent:* Thursday, August 25, 2016 11:34 AM
> *To:* Michel Veillette <[email-masked]>
> *Cc:* David Reid <[email-masked]>; [email-masked]
> *Subject:* Re: [core] draft-bierman-core-yid-00.txt questions
>
>
>
>
>
>
>
> On Thu, Aug 25, 2016 at 7:15 AM, Michel Veillette <Michel.Veillette@
> trilliantinc.com> wrote:
>
> Hi David
>

---

From: Alexander Pelov <[email-masked]>
Date: Thu, 25 Aug 2016 18:14:48 +0200

Hi Andy,

> Le 25 août 2016 à 18:02, Andy Bierman <[email-masked]> a écrit :
> 
> 
> 
> On Thu, Aug 25, 2016 at 8:54 AM, Michel Veillette <[email-masked] <mailto:[email-masked]>> wrote:
> Hi Andy, Hi David
> 
>  
> 

It is a way to assign numbers… automatically. Auto-numbering.

> which is what the YID draft proposes.  (centralized or distributed list of mappings).

I think we agree here. The YID draft proposes a subset of what can be achieved by the SID draft. The YID draft proposes a more complex process, which does not ensure interoperability, and which puts enormous strain on IANA, with no description of how a more generic system will work.

Everything you can do with YID you can do with SID. Not everything you can do with SID can be achieved with YID.
SID is simpler.
SID cares for ID exhaustion.
SID has running code.

I think that at this point we should continue the work on SID, and see how on a next stage to specify the things you want to achieve with YID. I am not sure this needs an additional draft (or maybe - an informational one).

Best,
Alexander

> https://tools.ietf.org/html/draft-somaraju-core-sid-01#section-3 <https://tools.ietf.org/html/draft-somaraju-core-sid-01#section-3>
>  
> 
> From: Andy Bierman [mailto:[email-masked] <mailto:[email-masked]>] 
> To: Michel Veillette <[email-masked] <mailto:[email-masked]>>
> Cc: David Reid <[email-masked] <mailto:[email-masked]>>; [email-masked] <mailto:[email-masked]>
>    pyang --generate-sid-file 20000:100 [email-masked] <mailto:[email-masked]>
> 
> Generate the file [email-masked] <mailto:[email-masked]> in attachment.
> 
> The command:
>   pyang --update-sid-file [email-masked] <mailto:[email-masked]>  [email-masked] <mailto:[email-masked]>
>  
> 
> Generate the file [email-masked] <mailto:[email-masked]> in attachment.
>

---

From: Michel Veillette <[email-masked]>
Date: Thu, 25 Aug 2016 16:23:06 +0000

Hi Andy

So far, nobody found a "auto-numbering" (or implied numbering) which work.
Even hashes require some manual intervention to register the assigned YID/SID and to resolve clashes.

Regards,
Michel

Sent: Thursday, August 25, 2016 12:03 PM

On Thu, Aug 25, 2016 at 8:54 AM, Michel Veillette <[email-masked]<mailto:[email-masked]>> wrote:
Hi Andy, Hi David

Andy

   already assigned.

Regards,
Michel

From: Andy Bierman [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Thursday, August 25, 2016 11:34 AM
To: Michel Veillette <[email-masked]<mailto:[email-masked]>>
Cc: David Reid <[email-masked]<mailto:[email-masked]>>; [email-masked]<mailto:[email-masked]>
Subject: Re: [core] draft-bierman-core-yid-00.txt questions

The command:

Andy

Regards,
Michel

-----Original Message-----
From: core [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of David Reid
Sent: Wednesday, August 24, 2016 11:24 PM
To: [email-masked]<mailto:[email-masked]>
Subject: Re: [core] draft-bierman-core-yid-00.txt questions

-David Reid

---

From: peter van der Stok <[email-masked]>
Date: Mon, 29 Aug 2016 09:18:46 +0200

Alexander Pelov schreef op 2016-08-25 18:14:
>> On Thu, Aug 25, 2016 at 8:54 AM, Michel Veillette
>> <[email-masked]> wrote:
>> 
>>> Hi Andy, Hi David
>>> 
> I think we agree here.

I am also convinced there is much overlap in the SID and YID drafts
The conclusions by Alexander are a bit fast for me.

What happened to the discussion about module number reservation against 
SID range reservation?
I don't think the strains on IANA (enormous or not) are an issue, but 
the strains on the module writers and what rules they are willing to 
follow.
For me it is the process of establishing identifiers, with a discussion 
about freedom of choice to companies, and scopes of inter-operability 
(world-wide, SDO wide,--), that is central here.

The YID draft proposes a subset of what can be
> achieved by the SID draft. The YID draft proposes a more complex
> process, which does not ensure interoperability, and which puts
> enormous strain on IANA, with no description of how a more generic
> system will work.
> 
> Everything you can do with YID you can do with SID. Not everything you
> can do with SID can be achieved with YID.
> SID is simpler.