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

[Michel Veillette <[e-mail]>]

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:[e-mail]]
Sent: Thursday, August 25, 2016 11:34 AM
To: Michel Veillette <[e-mail]>
Cc: David Reid <[e-mail]>; [e-mail]
Subject: Re: [core] draft-bierman-core-yid-00.txt questions



On Thu, Aug 25, 2016 at 7:15 AM, Michel Veillette <[e-mail]<mailto:[e-mail]>> wrote:
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 [e-mail]<mailto:[e-mail]>

Generate the file [e-mail]<mailto:[e-mail]> in attachment.

The command:
  pyang --update-sid-file [e-mail]<mailto:[e-mail]>  [e-mail]<mailto:[e-mail]>

Where is the algorithm explained in enough detail that multiple
independent implementations will all produce the exact same results?


Andy

Generate the file [e-mail]<mailto:[e-mail]> 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:[e-mail]<mailto:[e-mail]>] On Behalf Of David Reid
Sent: Wednesday, August 24, 2016 11:24 PM
To: [e-mail]<mailto:[e-mail]>
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?

>> 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.

> [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.

>>> 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.

> [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
> complex.

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
>> 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?

>> 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.

> [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.

Is the sequential numbering auto-assigned or manually assigned?

-David Reid

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

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