[ndn] TLV List Encoding

[justincpresley]

Overview

In Computer Science, A list is a primitive abstract data structure that represents a finite linear uniform collection of elements that retain order. While there are many different implementations of a list such as an array or linked list, a list is found in almost every programming language and is possibly the most popular data structure.

A TLV is the fundamental data type of NDN and makes communication structured. Naturally, the concept of a TLV List comes into the picture. The task may seem simple, it is simply a list of TLVs: [TLV, TLV, TLV, TLV]. Yet, there are interesting decisions that must be made in the creation of a TLV List.

The first decision is whether the TLV List is a TLV itself such that the value is the list. This decision is perhaps the easiest to make as by doing so, we reestablish the communication structure. The second is perhaps more debatable, whether the TLVs in a TLV List are required to be of the same type. In other words, Is the type in each TLV contained in the list the same or different?

Homogeneous Encoding

The Type (T) and Length (L) of a TLV can be thought of as metadata information. TLVs already act this way. When you think of a NDN Name, you think of the Value (V) ex. /edu/uni/clemson. We simply exclude the Type and Length in our example of NDN Names yet a Name is a TLV. Thus, when building structures using TLVs, it makes logical sense to abstractly exclude the Type and Length in the definition. This results in TLV Lists being Homogeneous as every element in a list must be uniform. Our list element in this case is the Value (V) .

TLV Layering

Due to the requirement of having uniform TLVs in our encoding, we have to create a layer of uniformity in the case of having a Heterogeneous collection. While this layer can make sense in the application context, it adds redundant information. For example, in the case of a SVS StateVector; we can properly assume that a StateVector is comprised of StateVector Entries, yet for every entry we are including this information. This redundant information bloats encoding and slows both encoding and decoding.

Optimization Through LV

A tempting optimization is to cut the Type (T) of list elements. A TLV List would be a TLV containing a list of LVs. This breaks the fundamental TLV structure at the benefit of a reduced encoding. However, the motivation of a Homogeneous encoding is to establish consistency, and this can be seen as antithetical to that motivation. Additionally, it only prevents bloating with the initial uniform layer, yet subsubstructures may exist.

Examples and Usage

It seems that Homogeneous encoding is more often used in specifications and in the early ages of NDN.
For example, the StateVectorSync specification.
In this code-base, Homogeneous encoding can be achieved by setting FormalEncoding to true in svs.

Heterogeneous Encoding

By subscribing to the idea that a TLV is one structure and a type itself, we arrive at Heterogeneous encoding. By allowing Heterogeneous encoding, we can more efficiently encode a TLV List in general. Not only does this encoding allow Hetergeneous collections to be efficient but also it allows for "flattening". Our list element in this case is the full TLV.

Flattening and Parsing

Heterogeneous encoding allows for "flattening" a complicated structure onto the TLV List to reduce space and make encoding and decoding more performant. For example, the first element could be a Name while the second a unsigned integer, yet our higher application context could have both of these elements linked into a structure. The only caveat is that when decoding, the TLV List has to be parsed into those structures. Lucky, NDN libraries can automatically do this for developers and provide a more layered API.

Examples and Usage

It seems that the NDN community is moving towards Heterogeneous encoding, and the incorporation of Homogeneous is simply for compatibility.
In this code-base, Heterogeneous encoding can be achieved by setting FormalEncoding to false in svs.