The document is well written, provides algorithms which could be used to address identified problems. One  could add some text covering TCP timestamps.

Section 1 states:
"Recent history indicates that when new protocols are standardized or
new protocol implementations are produced, the security and privacy
properties of the associated identifiers tend to be overlooked,..."
How does this related to recent/current activities like SCTP/DTLS or QUIC?

The Algorithms in 7.1.1 and 7.1.2 can be substantially simplified when check_suitable_id() always returns true. Why are not the simplified algorithms shown?

The algorithm in 7.3 (and later) uses a function F and it is stated that F must be a cryptographically-secure hash function. Couldn't you also use something like SipHash.

When reading the algorithm in 7.4.1, I had the impression that it should also work with id_inc > 1 (by just changing that parameter). If that is true, I guess you would need to change "if (next_id == max_id)" to "if (max_id - next_id < id_inc) {" and also "next_id = min_id;" to "next_id = min_id + (id_inc - (max_id - next_id + 1));".  If you don't want to be that generic, you might want to remove id_inc and just use 1.

The algorithm in 7.4.1 also calls "store_counter(CONTEXT, next_id)" when returning ERROR. Why?

The algorithms given before 9.4 are given in C code. The Algorithm in 9.4 breaks with this rule. Is this intended?

Nits:
Page 10: if(check_suitable_id(next_id)) -> if (check_suitable_id(next_id))
Page 11: if(check_suitable_id(next_id)) -> if (check_suitable_id(next_id))
Page 12: if(check_suitable_id(next_id)) -> if (check_suitable_id(next_id))
Page 14: if(lookup_counter(CONTEXT) == ERROR){ -> if (lookup_counter(CONTEXT) == ERROR) {
Page 14: if (check_suitable_id(next_id)){ -> if (check_suitable_id(next_id)) {
Page 14: }\n else { -> } else {
Page 16: if(check_suitable_id(next_id)) -> if (check_suitable_id(next_id))
Page 18: if(check_suitable_id(next_id)) -> if (check_suitable_id(next_id))
Page 24: linear(CONTEXT_2)= linear(CONTEXT_2) + increment(); -> linear(CONTEXT_2) = linear(CONTEXT_2) + increment();
Page 24: if(check_suitable_id(next_id)) -> if (check_suitable_id(next_id))