Subject: [core] Your cool presentation on friday core meeting

From: peter van der Stok <[email-masked]>
Date: Wed, 18 Nov 2015 09:09:31 +0100

Hi Alexander,

I like to react to your presentation of CoMI during the Friday CoRE 
meeting.  That is necessary for me to understand the underlying factual 
discussion.

Your statement “A hash clash 5 years down the road can break your 
network” needs some clarification. I interpret that, out of the blue, a 
hash clash can occur and lead to problems in the network. This is simply 
not true. A new hash clash may occur when modules are changed and 
recompiled in a server. At that moment and before the server is made 
operational hash clashes are detected and remedial actions can be taken.

Your next statement “hashes are underspecified” also needs some 
clarification. I understood from you that the remark was motivated by 
the absence of a full-proof process defining the solution of hash 
clashes. Such a process is not necessary to assure inter-operability. 
Once solved, the server returns the unique rehashed values and there is 
no need to specify how the rehash values are reached. Nevertheless, the 
draft suggests that a tilde is prefixed to the YANG name, after which it 
is rehashed. There is a very small probability that the new hash clashes 
with another one. Actually, you said to be afraid that the hashing 
algorithm may continuously generate the same set of clashing values 
independent of the prefix. I have no idea if this is true, and do not 
propose to check it for murmur.

I agree that for efficiency reasons the same rehash process should be 
followed in all servers such that all servers with the same set of 
module versions arrive at the same rehash values. An approach different 
from rehashing is to assign the lowest not assigned natural number to 
the clashing names in lexicographical order. That will generally mean 
that two colliding names get the values 1 and 2 assigned, and very 
rarely the values 3 and 4 may be used.

Last I should like to make a remark about probabilities. The whole world 
around us is based on probabilities. For example, there is a finite 
probability that a fatal fault will occur in an airplane during one hour 
of flight. Or that during digital transmission bits are toggled without 
detection by the checksum. These probabilities are calculated and should 
be smaller than a given probability value. This is a well-established 
engineering practice. Therefore, the clash probabilities are calculated 
in appendix E of the CoMI draft. It shows that for the targeted hash 
size and number of names, the probability that more than one clash 
occurs is 10^-3 smaller than the probability of one clash. These are 
quite small values.

By the way, by relying on identifier assignment, there is also a finite 
probability that the same identifier is allocated to names on different 
modules (a hidden clash), due to power failures, undetected transmission 
errors, or simply copying mistakes.
I recommend that in the security section of the identifier assignment 
draft, it is discussed how modules are detected with an identifier that 
has been assigned without going through the registration process.

Hope this will stimulate further discussion.

Peter
-- 
Peter van der Stok
vanderstok consultancy
mailto: [email-masked]

---

From: Alexander Pelov <[email-masked]>
Date: Wed, 18 Nov 2015 15:23:02 +0100

Hi Peter,

I'm quite busy these days. I would like to send you a detailed response, 
but unfortunately this will be impossible today.

Please, see in-line for some initial remarks.

Le 18/11/2015 09:09, peter van der Stok a écrit :
> meeting.  That is necessary for me to understand the underlying 
> factual discussion.
>
> network” needs some clarification. I interpret that, out of the blue, 
> a hash clash can occur and lead to problems in the network. This is 
> simply not true. A new hash clash may occur when modules are changed 
> and recompiled in a server. At that moment and before the server is 
> made operational hash clashes are detected and remedial actions can be 
> taken.
One of the specific cases I cited is, when you have your network running 
for months, maybe several years, before updating a YANG module, which 
leads to hash clash. This leads to unexpected protocol exchanges (e.g. 
clash-file loading), unexpected memory allocations (the clients must 
learn that some of its servers have these new clashes, while others have 
some other clashes, and so forth), bugs that have not been tested for 
long time, ...

> Once solved, the server returns the unique rehashed values and there 
> is no need to specify how the rehash values are reached. Nevertheless, 
> the draft suggests that a tilde is prefixed to the YANG name, after 
> which it is rehashed. There is a very small probability that the new 
> hash clashes with another one. Actually, you said to be afraid that 
> the hashing algorithm may continuously generate the same set of 
> clashing values independent of the prefix. I have no idea if this is 
> true, and do not propose to check it for murmur.
I've though on how to handle this specific question for a long time, and 
unfortunately you cannot guarantee that re-hashing will no guarantee new 
hash clash. Which could, in turn, generate new clashes. Each clash leads 
to two new names that need to be rehashed.

> module versions arrive at the same rehash values. An approach 
> different from rehashing is to assign the lowest not assigned natural 
> number to the clashing names in lexicographical order. That will 
> generally mean that two colliding names get the values 1 and 2 
> assigned, and very rarely the values 3 and 4 may be used.

I think that Structured IDs provide a way of handling this in a 
reasonable manner. We've already discussed how in a structured ID you 
can have hashes.
>
> Last I should like to make a remark about probabilities. The whole 
> world around us is based on probabilities. For example, there is a 
> finite probability that a fatal fault will occur in an airplane during 
> one hour of flight. Or that during digital transmission bits are 
> toggled without detection by the checksum. These probabilities are 
> calculated and should be smaller than a given probability value. This 
> is a well-established engineering practice. Therefore, the clash 
> probabilities are calculated in appendix E of the CoMI draft. It shows 
> that for the targeted hash size and number of names, the probability 
> that more than one clash occurs is 10^-3 smaller than the probability 
> of one clash. These are quite small values.
>
What constitutes a "small probability" is a relative question. 10E-3 is 
typically considered quite elevated (not to say - unacceptably high) 
collision probability. Given that you can have hundreds of entries, this 
probability is even worst. Given that each collision requires 
re-hashing, which could provoke other collisions, we end up with a 
problem I consider to be quite dangerous.

> By the way, by relying on identifier assignment, there is also a 
> finite probability that the same identifier is allocated to names on 
> different modules (a hidden clash), due to power failures, undetected 
> transmission errors, or simply copying mistakes.
> draft, it is discussed how modules are detected with an identifier 
> that has been assigned without going through the registration process.
>
That's a non-issue.

> Hope this will stimulate further discussion.
Thanks for the useful remarks. I am glad when we have constructive 
discussion. Sorry, for the brevity.

Best,
Alexander

---

From: peter van der Stok <[email-masked]>
Date: Thu, 19 Nov 2015 08:43:32 +0100

Hi Alexander

see between <pvds> and </pvds>

Alexander Pelov schreef op 2015-11-18 15:23:
> Hi Peter,
> 
> I'm quite busy these days. I would like to send you a detailed
> response, but unfortunately this will be impossible today.
> 
> One of the specific cases I cited is, when you have your network
> running for months, maybe several years, before updating a YANG
> module, which leads to hash clash. This leads to unexpected protocol
> exchanges (e.g. clash-file loading), unexpected memory allocations
> (the clients must learn that some of its servers have these new
> clashes, while others have some other clashes, and so forth), bugs
> that have not been tested for long time, ...

<pvds>
I do not share your concern. hashes are generated before loading of the 
module, hash clashes are easily verified, and rehashes are also done 
before loading of the module.
The rehash protocol concerns one client and one server and can be tested 
in isolation.
Hash clashes are easily simulated.
</pvds>
> I've though on how to handle this specific question for a long time,
> and unfortunately you cannot guarantee that re-hashing will no
> guarantee new hash clash. Which could, in turn, generate new clashes.
> Each clash leads to two new names that need to be rehashed.
> 
>> 
<pvds>
I showed that the problem above (continuous generation of hashes) can be 
easily avoided.
</pvds>
> What constitutes a "small probability" is a relative question. 10E-3
> is typically considered quite elevated (not to say - unacceptably
> high) collision probability. Given that you can have hundreds of
> entries, this probability is even worst. Given that each collision
> requires re-hashing, which could provoke other collisions, we end up
> with a problem I consider to be quite dangerous.
<pvds>
Appendix E cites different numbers than you do above.
For a server with 1000 hashed YANG names and a hash of 30 bits, the 
probability of a single clash in a given server is 5*10^-4.
That means that in an installation with 2000 servers containing disjunct 
sets of 1000 YANG names (total of 2 million YANG names), there is on 
average one server with one clash.
There being more than one clash has a probability that is 10^-3 lower.
In my opinion these are acceptably low probabilities, because they 
promise quite small rehash information in the clients (In this case: no 
rehash or one server with one clash)
BTW Andy has hashed all YANG names in all to him known modules and no 
clash occurred.
</pvds>

>> that has been assigned without going through the registration process.
<pvds>
I regret that you take this issue so lightly.
When there is no SDO that makes YANG name number allocation part of the 
certification process, YANG module writers are not very motivated to 
pass through a registry and assign the registered numbers.
Consequently, servers may use identical numbers for different YANG 
objects.
This means that the extension of your installation with a server runs 
the risk of duplicate identifiers.
You need a procedure to test this, or at least write text that this a 
reasonable hazard.
</pvds>

---

From: Alexander Pelov <[email-masked]>
Date: Thu, 19 Nov 2015 09:22:08 +0100

Dear Peter,

Once again, sorry for the brievity.

Important remarks to keep in mind:
1) there is a seamless way in which you can include hashes within a Structured ID (hashes are a subset of structured IDs).
2) hashes are incompressible. Structured IDs are very-well adapted to compression.

As we are working on converging on the CoOL and CoMI approaches, it seems to me that 1) and 2) allow for a graceful cooperation in this area.

See inline.

> Le 19 nov. 2015 à 08:43, peter van der Stok <[email-masked]> a écrit :
> 
> Hi Alexander
> 
>>> I like to react to your presentation of CoMI during the Friday CoRE meeting.  That is necessary for me to understand the underlying factual discussion.
>>> Your statement “A hash clash 5 years down the road can break your network” needs some clarification. I interpret that, out of the blue, a hash clash can occur and lead to problems in the network. This is simply not true. A new hash clash may occur when modules are changed and recompiled in a server. At that moment and before the server is made operational hash clashes are detected and remedial actions can be taken.
> I do not share your concern. hashes are generated before loading of the module, hash clashes are easily verified, and rehashes are also done before loading of the module.
> The rehash protocol concerns one client and one server and can be tested in isolation.

As indicated, the problem is not that your resource-unconstrained, human-operated compiler will not work flawlessly. It certainly will! 

The problem is that you have your hundreds of devices, coming from different manufacturers, working in a given manner, until one day you update some of them, which provokes all these unseen exchanges (rehashing), and CAN break your network 5 years down the road. (the statement of my presentation).

The biggest problem is actually thing-to-thing communication. With hashes you have no rendez-vous points within the hashed space.

>>> Your next statement “hashes are underspecified” also needs some clarification. I understood from you that the remark was motivated by the absence of a full-proof process defining the solution of hash clashes. Such a process is not necessary to assure inter-operability. Once solved, the server returns the unique rehashed values and there is no need to specify how the rehash values are reached. Nevertheless, the draft suggests that a tilde is prefixed to the YANG name, after which it is rehashed. There is a very small probability that the new hash clashes with another one. Actually, you said to be afraid that the hashing algorithm may continuously generate the same set of clashing values independent of the prefix. I have no idea if this is true, and do not propose to check it for murmur.
>>> I agree that for efficiency reasons the same rehash process should be followed in all servers such that all servers with the same set of module versions arrive at the same rehash values. An approach different from rehashing is to assign the lowest not assigned natural number to the clashing names in lexicographical order. That will generally mean that two colliding names get the values 1 and 2 assigned, and very rarely the values 3 and 4 may be used.
> I showed that the problem above (continuous generation of hashes) can be easily avoided.

The problem is not the generation of hash-free clash-files. I am more then persuaded that you can do this. 

The problem is that the collision probability increases.

> </pvds>
>>> Last I should like to make a remark about probabilities. The whole world around us is based on probabilities. For example, there is a finite probability that a fatal fault will occur in an airplane during one hour of flight. Or that during digital transmission bits are toggled without detection by the checksum. These probabilities are calculated and should be smaller than a given probability value. This is a well-established engineering practice. Therefore, the clash probabilities are calculated in appendix E of the CoMI draft. It shows that for the targeted hash size and number of names, the probability that more than one clash occurs is 10^-3 smaller than the probability of one clash. These are quite small values.
> For a server with 1000 hashed YANG names and a hash of 30 bits, the probability of a single clash in a given server is 5*10^-4.
> That means that in an installation with 2000 servers containing disjunct sets of 1000 YANG names (total of 2 million YANG names), there is on average one server with one clash.
> In my opinion these are acceptably low probabilities, because they promise quite small rehash information in the clients (In this case: no rehash or one server with one clash)
> BTW Andy has hashed all YANG names in all to him known modules and no clash occurred.

As I am quite lazy, I like using tools. http://davidjohnstone.net/pages/hash-collision-probability <http://davidjohnstone.net/pages/hash-collision-probability>
With a hash value over 30 bits, with 20 servers with 1000 YANG names the probability of a collision is 17%. Actually, I was using your numbers, and I do not consider that this will be a major problem by itself. The implications are that you WILL have hashes. 

> </pvds>
> 
>>> By the way, by relying on identifier assignment, there is also a finite probability that the same identifier is allocated to names on different modules (a hidden clash), due to power failures, undetected transmission errors, or simply copying mistakes.
>>> I recommend that in the security section of the identifier assignment draft, it is discussed how modules are detected with an identifier that has been assigned without going through the registration process.
>> That's a non-issue.
> <pvds>
> When there is no SDO that makes YANG name number allocation part of the certification process, YANG module writers are not very motivated to pass through a registry and assign the registered numbers.
> Consequently, servers may use identical numbers for different YANG objects.
> This means that the extension of your installation with a server runs the risk of duplicate identifiers.
> You need a procedure to test this, or at least write text that this a reasonable hazard.

Too long to develop here, but the crux of the matter is that the way YANG modules are used in constrained devices should influence the system design. The main points are:
1) we need 100% RESTCONF / YANG compatibility
2) we don’t need 100% compression of all YANG modules (most actually do not concern constrained networks)
3) people / SDOs / system integrators that want to run a given YANG module in a constrained network are quite interested in having their identifiers compressed

The reason I claim this is a non-issue is because there are many ways in which we can guarantee that identifiers are not assigned to different SDOs / YANG modules / etc. etc. 

>> discussion. Sorry, for the brevity.

To conclude, I think that we’ve initiated a very important process of splitting the CoMI/CoOL proposals and converging on a common ground (which is actually quite straightforward). Some details must be clarified, of course, but in general I don’t see any major issues.

The only real issues/questions will actually be solved by simply considering:
1) the constraints of constrained networks and devices (the REASON why there is CoMI/CoOL)
2) the way people use YANG/RESTCONF

Best,
Alexander

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