Alternative Delta Time Encoding for CCNx Using Compact Floating-Point Arithmetic

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 2 March 2024.¶

Copyright Notice

Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶

Table of Contents

1. Introduction

CCNx is well suited for Internet of Things (IoT) applications [RFC7927]. LoWPAN adaptation layers (e.g., [RFC9139]) confirm the advantages of a space-efficient packet encoding for low-power and lossy networks. CCNx utilizes absolute and delta time values for a number of functions. When using CCNx in resource-constrained environments, it is valuable to have a compact representation of time values. However, any compact time representation has to sacrifice accuracy or dynamic range. For some time uses this is relatively straightforward to achieve, for other uses, it is not. As a result of experiments in bandwidth-constrained IEEE 802.15.4 deployments [ICNLOWPAN], this document discusses the various cases of time values, proposes a compact encoding for delta times, and updates [RFC8609] to utilize this encoding format in CCNx messages.¶

This document has received fruitful reviews by the members of the research group (see the Acknowledgments section). It is the consensus of ICNRG that this document should be published in the IRTF Stream of the RFC series. This document does not constitute an IETF standard.¶

4. A Compact Time Representation with Logarithmic Range

This document uses the compact time representation of ICNLoWPAN (see section 7 of [RFC9139]) that is inspired by [RFC5497] and [IEEE.754.2019]. Its logarithmic encoding supports a representation ranging from milliseconds to years. Figure 1 depicts the logarithmic nature of this time representation.¶

|| |  |   |    |     |      |       |        |         |          |
+-----------------------------------------------------------------+
milliseconds                                                  years

Time codes encode exponent and mantissa values in a single byte, but in contrast to the representation in [IEEE.754.2019], time codes only encode non-negative numbers and hence do not include a separate sign bit. Figure 2 shows the configuration of a time code: an exponent width of 5 bits, and a mantissa width of 3 bits.¶

<---          one byte wide          --->
+----+----+----+----+----+----+----+----+
|      exponent (b)      | mantissa (a) |
+----+----+----+----+----+----+----+----+
  0    1    2    3    4    5    6    7

The base unit for time values are seconds. A time value is calculated using the following formula (adopted from [RFC5497] and [RFC9139]), where (a) represents the mantissa, (b) the exponent, and (C) a constant factor set to C := 1/32.¶

Subnormal (b == 0):

(0 + a/8) * 2 * C¶

Normalized (b > 0):

(1 + a/8) * 2^b * C¶

The subnormal form provides a gradual underflow between zero and the smallest normalized number. Eight time values exist in the subnormal range [0s,~0.0546875s] with a step size of ~0.0078125s between each time value. This configuration also encodes the following convenient numbers in seconds: [1, 2, 4, 8, 16, 32, 64, ...]. Appendix A further includes test vectors to illustrate the logarithmic range.¶

An example algorithm to encode a time value into the corresponding exponent and mantissa is given as pseudo code in Figure 3. Not all time values can be represented by a time code. For these instances, the closest time code is chosen that is smaller than the value to encode.¶

 input: float v    // time value
output:   int a, b // mantissa, exponent of time code

(a, b) encode (v):

    if (v == 0)
        return (0, 0)

    if (v < 2 * C)                              // subnormal
        a = floor (v * 4 / C)                   // round down
        return (a, 0)
    else                                        // normalized
        if (v > (1 + 7/8) * 2^31 * C)           // check bounds
            return (7, 31)                      // return maximum
        else
            b = floor (log2(v / C))             // round down
            a = floor ((v / (2^b * C) - 1) * 8) // round down
            return (a, b)

As an example: No specific time code for 0.063 exists, but this algorithm maps to the closest valid time code that is smaller, i.e., exponent 1 and mantissa 0 (the same as for time value 0.0625).¶

5. Protocol Integration of the Compact Time Representation

A straightforward way to accommodate the compact time approach is to use a 1-byte length field to indicate this alternative encoding while retaining the existing TLV registry entries. This approach has backward compatibility problems, but is still considered for the following reasons:¶

• Both CCNx RFCs are experimental and not Standards Track, hence expectations for forward and backward compatibility are not as stringent. "Flag day" upgrades of deployed CCNx networks, while inconvenient, are still feasible.¶
• The major use case for these compressed encodings are smaller-scale IoT and/or sensor networks where the population of consumers, producers, and forwarders is reasonably small.¶
• Since the current TLVs have hop-by-hop semantics, they are not covered by any signed hash and hence may be freely re-encoded by any forwarder. That means a forwarder supporting the new encoding can translate freely between the two encodings.¶
• The alternative of assigning new TLV registry values does not substantially mitigate the interoperability problems anyway.¶

                     1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
|           T_INTLIFE           |           Length = 1          |
+---------------+---------------+---------------+---------------+
| COMPACT_TIME  |
+---------------+
                     1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
|           T_INTLIFE           |           Length > 1          |
+---------------+---------------+---------------+---------------+
/                                                               /
/                      Lifetime (Length octets)                 /
/                                                               /
+---------------+---------------+---------------+---------------+

                     1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
|          T_CACHETIME          |           Length = 1          |
+---------------+---------------+---------------+---------------+
| COMPACT_TIME  |
+---------------+
                     1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
|          T_CACHETIME          |           Length = 8          |
+---------------+---------------+---------------+---------------+
/                                                               /
/                    Recommended Cache Time                     /
/                                                               /
+---------------+---------------+---------------+---------------+

6. IANA Considerations

This document has no IANA actions.¶

7. Security Considerations

This document makes no semantic changes to [RFC8569], nor to any of the security properties of the message encodings of [RFC8609], and hence has the same security considerations as those two existing documents. Additional considerations need to be made in networks that deploy forwarders with support (updated forwarder) and without support (legacy forwarder) for this compact time representation:¶

Interest Lifetime:

A legacy forwarder interprets a time code as an Interest lifetime between 0 and 255 milliseconds. This may lead to a degradation of network performance, since Pending Interest Table (PIT) entries timeout quicker than expected. An updated forwarder interprets short lifetimes set by a legacy forwarder as time codes, thus configuring timeouts of up to 4 years. This leads to an inefficient occupation of state space.¶

Recommended Cache Time:

A legacy forwarder considers a Recommended Cache Time with length 1 as a structural or syntactical error and it SHOULD discard the packet (section 10.3.9 [RFC8569]). Otherwise, a legacy forwarder interprets time codes as absolute time values far in the past, which impacts cache utilization.¶

Appendix A. Test Vectors

The test vectors in Table 1 show sample time codes and their corresponding time values according to the algorithm outlined in Section 4.¶

Appendix B. Efficient Time Value Approximation

A forwarder frequently converts compact time into milliseconds to compare Interest lifetimes and the duration of cache entries. On many architectures, multiplication and division perform slower than addition, subtraction, and bit shifts. The following equations approximate the formulas in Section 4, and scale from seconds into the milliseconds range by applying a factor of 2^10 instead of 10^3. This results in an error of 2.4%.¶

b == 0:

2^10 * a * 2^-3 * 2^1 * 2^-5
= a << 3¶

b > 0:

(2^10 + a * 2^-3 * 2^10) * 2^b * 2^-5
= (1 << 5 + a << 2) << b¶

Authors' Addresses