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

Cenk Gündoğan <mail+ietf@gundogan.net> Tue, 26 November 2019 19:53 UTC

Return-Path: <mail+ietf@gundogan.net>
X-Original-To: icnrg@ietfa.amsl.com
Delivered-To: icnrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1673A1208E5 for <icnrg@ietfa.amsl.com>; Tue, 26 Nov 2019 11:53:43 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.699
X-Spam-Level:
X-Spam-Status: No, score=-1.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_INVALID=0.1, DKIM_SIGNED=0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=fail (2048-bit key) reason="fail (bad RSA signature)" header.d=gundogan.net
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6FGgYyl9o1Qg for <icnrg@ietfa.amsl.com>; Tue, 26 Nov 2019 11:53:41 -0800 (PST)
Received: from mail.localdomain (trantor.gundogan.net [37.120.167.193]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CB3BE120018 for <icnrg@irtf.org>; Tue, 26 Nov 2019 11:53:40 -0800 (PST)
Received: from localhost (unknown [141.22.28.164]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) (No client certificate requested) by mail.localdomain (Postfix) with ESMTPSA id 78DA0294EC for <icnrg@irtf.org>; Tue, 26 Nov 2019 20:48:41 +0100 (CET)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=gundogan.net; s=201712; t=1574797721; bh=zNphbczAn13V/GfRJcKJiuDGoqc1eu6uZ73mWD4+gUI=; h=References:From:To:Subject:In-reply-to:Date:From; b=c2Cvw6FXwVfadwXHXP+rhu8LO/+xUjf8xOYKBIYcIsiVo6o4YPYuJ7Grx0HiWuI5P oj29ExmlqAHPAZOiCh48gXqn/A0ECD0Hgo1RIEw0ZwLRKLdjpQIOekvQCs6EC7WdMC a1qSW0tbQNbKgPaAOqHeFD+qvhcfv966eElWp9/i6CmvGZ4Ks0QxIWrzattEGx/Q1C iBtZ33lWI7kJSwEhtsZHrZQVD+Kz9p3Fg8N0JS9Kph+9qjRFSb9Pt830wIpcvbMyKV OaOQHIERgxqrdkIq42jEYj5ao7i8kNDVDjN+opXBKSfAB/onP1/17GgB9L5ObFFFxa gQas3zaI/7ldg==
References: <73a5a9ff-03c2-3b63-576d-8811c84b90c4@haw-hamburg.de> <9AB2EAD4-4458-4BD3-B263-A8C9BDAAB25B@parc.com> <87r21zy7ba.fsf@gundogan.net> <2823BFCD-3228-4E8D-8B7F-D27C9FF046CA@parc.com> <87blt0191m.fsf@gundogan.net> <2ED76739-6CE3-4476-8F1A-1A7297DF9F77@parc.com>
User-agent: mu4e 1.2.0; emacs 26.3
From: Cenk Gündoğan <mail+ietf@gundogan.net>
To: icnrg@irtf.org
In-reply-to: <2ED76739-6CE3-4476-8F1A-1A7297DF9F77@parc.com>
Date: Tue, 26 Nov 2019 20:53:37 +0100
Message-ID: <87k17m9zy6.fsf@gundogan.net>
MIME-Version: 1.0
Content-Type: multipart/signed; boundary="=-=-="; micalg="pgp-sha256"; protocol="application/pgp-signature"
Archived-At: <https://mailarchive.ietf.org/arch/msg/icnrg/9KAoQ2S-SWvNzya_hkVKe0c3axg>
Subject: Re: [icnrg] Directions on CCNx TimeTLVs: draft-gundogan-icnrg-ccnx-timetlv
X-BeenThere: icnrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Information-Centric Networking research group discussion list <icnrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/icnrg>, <mailto:icnrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/icnrg/>
List-Post: <mailto:icnrg@irtf.org>
List-Help: <mailto:icnrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/icnrg>, <mailto:icnrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 26 Nov 2019 19:53:43 -0000

Hello,

On Mon, Nov 25 2019 at 19:30 +0100, Mosko, Marc wrote:

> Replies below.  I edited down the history to make it a bit more concise.
>
> On 11/25/19, 3:37 AM, "icnrg on behalf of Cenk Gündoğan" <icnrg-bounces@irtf.org on behalf of mail=2Bietf=40gundogan.net@dmarc.ietf.org> wrote:
>     >
>     > 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.
>
>     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?
>
> 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.

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.

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

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

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.

>     >     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?
>     >
>
>     Any ideas or concerns regarding the integration? Is replacing the
>     existing functionality defined in the CCNx RFC desireable?
>
> 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.
>

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

> Marc
>
>
>
> _______________________________________________
> icnrg mailing list
> icnrg@irtf.org
> https://www.irtf.org/mailman/listinfo/icnrg