Subject: [icnrg] Directions on CCNx TimeTLVs: draft-gundogan-icnrg-ccnx-timetlv

From: "Thomas C. Schmidt" <[email-masked]>
Date: Wed, 20 Nov 2019 12:11:44 +0800

Folks,

following up on our presentation of draft-gundogan-icnrg-ccnx-timetlv:

This proposes to replace time deltas in CCNx by logarithmic encodings 
and (maybe) some absolute timer values by deltas w.r.t. the signature time.

We solicit feedback: Do you agree on going this way, or do you suspect 
this to be harmful?

Best,
  Thomas
-- 

Prof. Dr. Thomas C. Schmidt
° Hamburg University of Applied Sciences                  Berliner Tor 7 °
° Dept. Informatik, Internet Technologies Group   20099 Hamburg, Germany °
° http://inet.haw-hamburg.de/members/schmidt      Fon: +49-40-42875-8452 °

---

From: "Mosko, Marc <[email-masked]>" <[email-masked]>
Date: Wed, 20 Nov 2019 06:25:45 +0000

Thomas,

I think having more compact encodings is great!  Here's a few comments on draft-gundogan-icnrg-ccnx-timetlv-00.

1) The caption of Fig 3 cites RFC 4574.  Is that correct?  It's also not in the references section.

2) RFC 5497 is not definitive in the representation of 1 or 2 byte floats, as C must be specified.  In your draft, it would be good to have a section that completely spells out how to go from a timestamp to/from mini/half floats.

3) I agree that playing with the signature time might have unintended security consequences.  The signature time might also be unrelated to other time fields in the packet as it might be generated independently of the content itself, so using it as a time base is not a good idea either.

4) If the RCT becomes relative, then a cache should decrement it.  I'm not a big fan for using relative times here, but it could be done.  I had written up an idea on allowing relative times as an alternative to absolute times in https://tools.ietf.org/html/draft-mosko-icnrg-cachecontrol-00.

5) I think fractions of a second are not important for fields like interest lifetime or RCT, so the exponent does not need to support negatives.  Removing a sign bit and keeping the exponent positive with a normalized form mantissa would have a fairly large range, at least for the 8-bit (a 0.4.4.-0 minifloat).  The 16-bit should keep all the bells and whistles as it has space, and you'd likely use IEEE half precision floats anyway?

Marc

On 11/19/19, 8:12 PM, "icnrg on behalf of Thomas C. Schmidt" <[email-masked] on behalf of [email-masked]> wrote:

    Folks,

    
    
    Best,
      Thomas
    -- 

    _______________________________________________
    icnrg mailing list
    [email-masked]
    https://www.irtf.org/mailman/listinfo/icnrg

---

From: "Thomas C. Schmidt" <[email-masked]>
Date: Wed, 20 Nov 2019 15:02:42 +0800

Hi Marc,

many thanks for the feedback and yes, I think we are in pretty close 
agreement. We will work on the draft and resubmit soonish.

Best,
  Thomas

--

---

From: Cenk Gündoğan <[email-masked]>
Date: Fri, 22 Nov 2019 21:39:21 +0100

Hello Marc,

thank you for the feedback. I have a couple of comments and questions
inlined below.

> 1) The caption of Fig 3 cites RFC 4574.  Is that correct?  It's also not in the references section.

Thanks .. that definitely does not belong there.

> 3) I agree that playing with the signature time might have unintended security consequences.  The signature time might also be unrelated to other time fields in the packet as it might be generated…

hm, both, the expiry and signature times in Content Objects are part of
the security envelope. There is a strong relation between the expiry and
signature times once a signature is generated. I assume that expiry time
is also always > signature time, because of the following quote from
[1]:

 The ExpiryTime is a field that exists within the signature envelope
 of a Validation Algorithm.  It is the UTC time in milliseconds after
 which the Content Object is considered expired and MUST no longer be
 used to respond to an Interest from a cache.  Stale content MAY be
 flushed from the cache.

If I am not mistaken, then there should never be expired Content Objects
in the network. Expiry time can therefore be expressed as a (positive
only) time delta to the signature time .. or is there any valid use case
where expired Content Objects get a new signature (and therefore have an
expiry time < signature time)?

[1] https://tools.ietf.org/html/rfc8569#section-4

> 5) I think fractions of a second are not important for fields like interest lifetime or RCT, so the exponent does not need to support negatives.  Removing a sign bit and keeping the exponent positi…

I put together this little visualization [2] to show the ranges of
different time encodings. I assume an 8-bit float without sign bit and
exponent bias. The legend shows configurations in the typical form:
(sign bits, exponent bits, mantissa bits, bias).

Let's assume that a time value represents seconds. Then we are obviously
not able to represent sub-second floats. Though, milliseconds might be
interesting for some use cases (e.g., to quickly delete a PIT trail for
unsatisfied, but time-sensitive data).

The configurations (0,3,5,0) and (0,6,2,0) have IMO either a very low
range, or a rather unnecessarily huge range.

(0,4,4,0) can at max represent ~17 hours (63488 seconds).
(0,5,3,0) has a max time value of ~127 years (4026532000 seconds).

If we assume milliseconds as base unit, then above values change to:

(0,4,4,0): max ~1 minute
(0,5,3,0): max ~46 days

~46 days as a max value for lingering PITs are IMO reasonable .. and we
gain 80 sub-second values (out of 255 possible time codes).

In previous slides there was also the constant C set to (1/1024). The
beauty of having (1/1024) instaed of (1/1000, milliseconds) as base is
that it yields integer values in the seconds range for power-of-2 values
(1s,2s,4s,...). An application would more likely want to encode "4s",
instead of "4.096s".

I like the idea of using an IEEE half precision float for the 16-bit
variant.

The next question (to the group) is how we want to encode them:
T_INTLIFE is actually unbounded (as per RFC). It can use a time value of
arbitrary octets, although the usefulness for 1- and 2-octet time values
in milliseconds is questionable [3]. So, this TimeTLV draft would not
just add new functionality, but would *replace* the current behavior, if
we use it in T_INTLIFE with Length==1 OR LENGTH==2. Is that something we
want?

Cheers,
Cenk

[2] https://cgundogan.github.io/minifloat/
[3] https://github.com/icnrg/draft-gundogan-icnrg-ccnx-timetlv/issues/3

---

From: "Mosko, Marc <[email-masked]>" <[email-masked]>
Date: Sat, 23 Nov 2019 01:04:42 +0000

On 11/22/19, 12:39 PM, "icnrg on behalf of Cenk Gündoğan" <[email-masked] on behalf of mail=2Bietf=[email-masked]> wrote:

    Hello Marc,

    

    

    
    
There may be expired content objects in two conditions.  One is in-flight content objects that expire before reaching a consumer.  That's a corner case.  The publisher or cache initiating the transmission thought it was not expired and it expired during transit.  Two is locally stored content object.  They can expire, and there is no mandate to purge them; it is only a mandate to not transmit them on the network.  A consumer could keep them around for as long as it wants.

The issue with using the expiry time as a delta from the signature is that someone could strip the signature off a content object and re-sign it.  This would attach a new signature time.  If one knew that a certain field was a delta from the signature time, it might be possible to re-calculate it.  This could be a single publisher updating the signature on a content object or manifest to extend it or a 3rd party re-publishing a content object.

Another potential issue is that a content object might have co-signatures, or multiple signature blocks.  This is not in the draft, but it is a technique used in SDSI for cascading signatures and parallel signatures.  If such a feature were introduced in CCNx, one would need a way to express which signature is the time base.  This is not an issue as-is, just something to consider for the future.

Not all ValidationInfos have a signature time.  Some, like a CRC or SHA256 or HMAC, do not have the field.  Some content object, such as those referenced by hash in a manifest that use the root manifest's signature as the trust root, do not have a validation section at all.  So if those want to use an Expiry time, for example, they need to use an absolute time.  So, would it be possible to have a 1 or 2 byte float and be able to tell if it was relative or absolute?  Maybe the 2-byte could have a bit for that.

Great!  I was thinking of doing that myself.  Are you still assuming that 0x00 is defined as 0 (instead of 1)?  I guess I'm asking would one use denormalized numbers with a 0 exponent?

    

    (0,4,4,0): max ~1 minute
    (0,5,3,0): max ~46 days

Yes, the ~46 day range /1000 or /1024 sounds like a good option for things like expiry time or cache time, especially for the IoT environment.

If you denormalize (0,6,3,0), the 0 exponent values are 0.00, 0.25, 0.50, 0.75, 1.00, 1.25, 1.50, 1.75 without playing with a C factor.  If you denormalize (0,4,4,0), it goes in 1/8th increments from [0 .. 4], then in 1/4th [4,8], then 1/2th [8,16], etc.

    
    Cheers,
    Cenk

---

From: Cenk Gündoğan <[email-masked]>
Date: Mon, 25 Nov 2019 12:37:25 +0100

Hello Marc,

> If you denormalize (0,6,3,0), the 0 exponent values are 0.00, 0.25, 0.50, 0.75, 1.00, 1.25, 1.50, 1.75 without playing with a C factor.  If you denormalize (0,4,4,0), it goes in 1/8th increments fr…

I did include subnormal numbers in [1]. If we go with seconds as base
unit (and without a C constant), then I get the same values you wrote.

With this setup, we would have a maximum value of ~17 hours for
(0,4,4,0) and ~127 years for (0,5,3,0). 17 hours might be a little less
.. and 127 years a little bit too much.

Instead, we could also apply a bias to (0,5,3,0), let's say -7. This
yields a maximum value of roughly 1 year. At the same time, it allows us
to encode a few more sub-second values (starting at ~1.9 ms).

What do you think about (0,5,3,-7)? Are 56 sub-seconds values too much?

[1] https://cgundogan.github.io/minifloat/

>     we use it in T_INTLIFE with Length==1 OR LENGTH==2. Is that something we

Any ideas or concerns regarding the integration? Is replacing the
existing functionality defined in the CCNx RFC desireable?

Cheers,
Cenk

---

From: "Mosko, Marc <[email-masked]>" <[email-masked]>
Date: Mon, 25 Nov 2019 18:30:42 +0000

Replies below.  I edited down the history to make it a bit more concise.

    
    With this setup, we would have a maximum value of ~17 hours for
    (0,4,4,0) and ~127 years for (0,5,3,0). 17 hours might be a little less
    ... and 127 years a little bit too much.

    
I think the (0,5,3, [-5, ... -7]) range looks good.  -5 is just under 4 years, -7 is just under 1 year.  At the low end -5, is about 8msec resolution, whereas -7 is about 2 msec.  -6 is ~ 2 years range and about 4 msec resolution at the low end.

For expiry time, I think 1 second resolution is plenty, and 4 years (for IoT use case) is also pretty good, considering that one could use a 2-byte or 8-byte value if one really needed more.   Same for recommended cache time.

For Interest lifetime, I personally are not a fan of trying to use very short Internet lifetime for PIT expiry at packet RTTs -- it's too easy for the standard deviation of arrival times to make small values counter-productive.  So I'm OK with a lower resolution like -5 vs -7 to get more range.

I think I would tend to let the 1-byte minifloat be less precise and have more range.  If one really needs precision, then use a 2-byte half float.

For the 2-byte encoding, I suggested using the standard IEEE half-float, but I now realize that it uses a -15 bias, so the maximum value is only 65519.  Maybe we want to use something more like (1, 5, 10, -12) or something to get more range if we are using seconds as the unit.  I've not plotted out the values for this.

These encodings work for relative times.  We still need to conjure up a time base.  Interest Lifetime is already a relative value, so that works OK.  The cache times either need a time base or we need to allow a relative encoding using Age style fields.  

Here are some options for relative times.  I think I prefer #1 or #4, but it needs more thinking through.

1) 2-byte encoding:  <1-byte uint8_t offset from year 2000> + <1-byte mini-float> or 3-byte encoding <1-byte offset from year 2000> + <2-byte half float>.  This would use the 0th second of year 2000, 2001, ..., 2255 as the base of the mini/half float.  If the spec survives until year 2200 or so, we can update the definition __  If one uses (0, 5, 3, -7), you get pretty good resolution over the 1-year time bases.  I'm not convinced one needs the 3-byte encoding using this method.

2) Define a new TimeBase field to designate the year to use as the base and keep the other encodings as 1-byte or 2-bytes. The TimeBase would define the offset to the year epoch (say a year 2000 base?).  This requires an extra 4 bytes of TLV overhead so it would be at least +5 bytes, whereas encoding the year base in #1 is only +1 or +2 extra bytes (2 extra bytes if you have both ExpiryTime and RCT).  Or #4 that requires 0 extra bytes.

3) Use an exponential timebase, such as 2000 + 2^(n/k), where we get to pick the constant k.  As opposed to the additive method in #1 or #2, this is essentially unbounded. One could even choose a smaller offset, like 1900 instead of 2000.  This gets pretty complicated and very poor precision as the years go out in the future.

4) Use (0, 5, 3, 0) relative to year 2000 (i.e. years 2000 - 2127), or (0, 5, 3, +1) relative to 2000 for times in years 2000 - 2255.  Small encoding, but poor resolution as you go out in years.

5) Use an Age-style relative cache time.

I am hesitant to have the type of a value determined by its length -- for both Interest Lifetime and the cache times.  But I am not coming up with a more cleaver solution.

For hash values, we used a TLV inside a TLV.  That's 4 extra bytes to define the hash type, but that is relative to 32-byte (256 bit) values, so the relative overhead is not too bad.  But a TLV inside a TLV does not make sense for 1 or 2 byte values.

One could do a self-describing Number type, such as with a 4-bit or 8-bit header, then re-define various TLVs to use the Number type encoding.  This would let us encode all the standard formats (uint8_t, int8_t, uint16_t, ..., int64_t, float32, float64, (0, 5, 3, 0) float, ...).  This means that Number type TLVs would always be, say, 1-byte larger than the encoding, but you get a lot of flexibility.  An more importantly, the type is no longer defined by the length.  It also means that you can use whatever encoding is most suitable for the field usage for any particular message.  The downside is that comparisons can no longer be done with memcmp() in many cases.  On the bright side, the fast path of the forwarder does not evaluate any of the time fields, so it is only a hit on end systems or caches or firewalls filtering on values.

Marc

---

From: Cenk Gündoğan <[email-masked]>
Date: Tue, 26 Nov 2019 20:53:37 +0100

Hello,

> For the 2-byte encoding, I suggested using the standard IEEE half-float, but I now realize that it uses a -15 bias, so the maximum value is only 65519.  Maybe we want to use something more like (1,…

so, to sum up:

* for the 1-octet case: (0,5,3,-5) is favorable, because it yields a
  wide range (up to 4 years) and has an acceptable ~8 msec resolution in
  the lower end. I would also agree on that.

* for the 2-octet case: (1,5,10,-12) may be a candidate. For the sake of
  completeness, I added (1,5,10,-12), (1,5,10,-15) and (1,5,10,-5) to
  [1] (in linear scale). (1,5,10,-12) yields a max of roughly 12 days
  and provides micro seconds precision in the lower range. (1,5,10,-5)
  on the other hand provides a max. of approx. 4 years and is thus more
  aligned to the 1-octet (0,5,3,-5) case. I would favor -5 over -12,
  because of the increased range and we would still have (sub) milli
  second precision on the lower end.

> 5) Use an Age-style relative cache time.

These are good alternatives. We definitely need more discussion here
.. We also may need different strategies for different time
values. E.g., one strategy might work very well for SigTime, the other
for ExpiryTime.

> One could do a self-describing Number type, such as with a 4-bit or 8-bit header, then re-define various TLVs to use the Number type encoding.  This would let us encode all the standard formats (ui…

This very much sounds like what is happening in CBOR [2]. We could try
to use a CBOR encoded time representation. Possibly following the
encoding rules you outlined above in, e.g., #1, #3, and #4.

[2] https://cbor.io/

Cheers,
Cenk