[nwcrg] Some comments on draft-heide-nwcrg-rlnc-background-00

["David R. Oran" <[e-mail]>]

First, thanks for splitting this draft off from the symbol 
representation specification and providing a nice background document 
that can serve as an “entry point” to what will hopefully evolve 
into a coherent set of encoding and algorithmic specifications for 
ongoing standardization work.

I found it nicely structured and easy to read, especially compared to 
the earlier material. I have a few general comments, and then some 
detailed technical comments and nits which I’ve embedded in a snipped 
copy of the associated text from the draft.

General comments:

1. The document points well to the need for concrete encoding 
specifications for symbol representation and gives useful guidance on 
the technical tradeoffs to consider in picking a given representation 
for integration into an enclosing protocol. I wish you had done the same 
for representation and encoding in a protocol of coding parameters, 
where the document basically waffles by saying there are lots of ways to 
do it. You mention the possibility of out-of-band conveyance and 
conveyance together with the encoded symbols, but really don’t give 
good advice on the tradeoffs, as you do with symbol representation. 
There’s some discussion, but I’d really like to see this fleshed out 
in a future revision.

2. As general terminology issue, I found the term “connection” 
creeping in various places (I point out some specific instances my 
detailed comments) where it is either unnecessary or in some cases 
inappropriate, as with multicast. In reading through, I think it’s 
adequate to just talk about “senders” and “receivers” without 
any baggage of two-party state that typically defines a connection. This 
is particularly evident when the material on feedback comes into play, 
as feedback needs to make it to one (or more) senders but does not 
necessarily happen “inside” some connection state (although it might 
in the case of embedding RLNC into connection-orient transport protocols 
like TCP or QUIC).

3. The discussion of security is not adequate, in my opinion. At the 
very least, some discussion in the security considerations is needed to 
address whether cryptographic integrity is assumed from the lower-level 
protocol to protect the coded symbols (and possible coding vectors) from 
manipulation by an attacker. Conversely, if one assumes that RLNC 
provides some degree of robustness against manipulation of coded data 
and parameters by attackers (including foiling both memory or 
computational DoS attacks on the decoders in receivers), one can move 
cryptographic integrity to the enclosing protocol and check only the 
decoded data. In terms of confidentiality, it may be that exposing 
coding parameters and encoded symbols does not represent any privacy 
leakage, but that still needs to have some amount of discussion with 
appropriate justification for whether encryption is needed below RLNC to 
prevent leakage, even if the encoded data is encrypted at a higher 
layer.


Detailed comments and nits:

      Random Linear Network Coding (RLNC): Background and Practical
                              Considerations
                   draft-heide-nwcrg-rlnc-background-00

Abstract

    This document describes the use of Random Linear Network Coding
    (RLNC) schemes for reliable data transport.  Both block and sliding
    window RLNC code implementations are described.  By providing 
erasure
    correction using randomly generated repair symbols, such RLNC-based
    schemes offer advantages in accommodating varying frame sizes and
    dynamically changing connections,

<DO> don’t say connection - say “dynamically changing communication 
conditions”

    reducing the need for feedback, and
    lowering the amount of state information needed at the sender and
    receiver.

<DO> In the main document, I didn’t actually see material showing the 
state reduction. Certainly there is the valuable reduction in overhead 
in *communicating* the state changes, but it would be very helpful to 
give justification (with example or two) of what state is actually 
reduced at the sender and/or receiver.

The practical considerations' section identifies RLNC-

<DO> s/considerations’/considerations/

    encoded symbol representation as a valuable target for
    standardization.

[snip]


1.1.  Random Linear Network Coding (RLNC) Basics

    Unlike conventional communication systems based on the "store-and-
    forward" principle, RLNC allows network nodes to independently and
    randomly combine input source data into coded symbols over a finite
    field [HK03].  Such an approach enables receivers to decode and
    recover the original source data as long as enough linearly
    independent coded symbols, with sufficient degrees of freedom, are
    received.  At the sender, RLNC can introduce redundancy into data
    streams in a granular way.

<DO> Granular could mean either fine or coarse. I’d try to be more 
specific - there are two degrees of freedom here - both symbol size and 
amount of redundancy.

	At the receiver, RLNC enables progressive
    decoding and reduces feedback necessary for retransmission.
    Collectively, RLNC provides network utilization and throughput
    improvements, high degrees of robustness and decentralization,
    reduces transmission latency, and simplifies feedback and state
    management.

<DO> Compared to what? You might get less argument if this were stated 
in non-comparative terms, like “RLNC enables progressive decoding and 
low overhead feedback to manage retransmissions. RLNC is highly 
efficient in network utilization thus improving throughput, while 
providing strong robustness properties and decentralized control. RLNC 
further can improve end-to-end latency while simplifying feedback and 
state management.”

[Aside: RLNC can’t actually reduce transmission latency; that’s a 
property of the channel]

    To encode using RLNC, original source data are divided into symbols
    of a given size and linearly combined.  Each symbol is multiplied
    with a scalar coding coefficient drawn randomly from a finite field,
    and the resulting coded symbol is of the same size as the original
    data symbols.

    Thus, each RLNC encoding operation can be viewed as creating a 
linear
    equation in the data symbols, where the random scalar coding
    coefficients can be grouped and viewed as a coding vector.
    Similarly, the overall encoding process where multiple coded symbols
    are generated can be viewed as a system of linear equations with
    randomly generated coefficients.  Any number of coded symbols can be
    generated from a set of data symbols, similarly to expandable 
forward
    error correction codes specified in [RFC5445] and [RFC3453].  Coding
    vectors must be implicitly or explicitly transmitted from the sender
    to the receiver for successful decoding of the original data.  For
    example, sending a seed for generating pseudo-random coding
    coefficients can be considered as an implicit transmission of the
    coding vectors.  In addition, while coding vectors are often
    transmitted together with coded data in the same data packet, it is
    also possible to separate the transmission of coding coefficient
    vectors from the coded data, if desired.

<DO> why would I desire this? See my general comment above.

    To reconstruct the original data from coded symbols, a network node
    collects a finite but sufficient number of degrees of freedom for
    solving the system of linear equations.  This is beneficial over
    conventional approaches as the network node is no longer required to
    gather each individual data symbol.

<DO> Isn’t the misleading? No decent coding scheme requires you 
“gather each individual data symbol”. I think you mean that the 
network node is not required get specific data symbols, any combination 
with enough degrees of freedom will do.

    In general, the network node
    needs to collect slightly more independent coded symbols than there
    are original data symbols, where the slight overhead arises because
    coding coefficients are drawn at random, with a non-zero probability
    that a coding vector is linearly dependent on another coding vector,
    and that one coded symbol is linearly dependent on another coded
    symbol.  This overhead can be made arbitrarily small, provided that
    the finite field used is sufficiently large.

    A unique advantage of RLNC is the ability to re-encode or "recode"
    without first decoding.  Recoding can be performed jointly on
    existing coded symbols, partially decoded symbols, or uncoded
    systematic data symbols.  This feature allows intermediate network
    nodes to re-encode and generate new linear combinations on the fly,
    thus increasing the likelihood of innovative transmissions to the

<DO> “Innovative”? I know that one can use the word this way but 
perhaps it would be better to say “increasing likelihood that the 
receiver obtains enough linearly independent symbols”

    receiver.  Recoded symbols and recoded coefficient vectors have the
    same size as before and are indistinguishable from the original 
coded
    symbols and coefficient vectors.

    In practical implementations of RLNC, the original source data are
    often divided into multiple coding blocks or "generations" where
    coding is performed over each individual generation to lower the
    computational complexity of the encoding and decoding operations.
    Alternatively, a convolutional approach can be used, where coding is
    applied to overlapping spans of data symbols, possibly of different
    spanning widths, viewed as a sliding coding window.  In generation-
    based RLNC, not all symbols within a single generation need to be
    present for coding to start.  Similarly, a sliding window can be
    variable-sized, with more data symbols added to the coding window as
    they arrive.  Thus, innovative coded symbols can be generated as 
data
    symbols arrive.  This "on-the-fly" coding technique reduces coding
    delays at transmit buffers, and together with rateless encoding
    operations, enables the sender to start emitting coded packets as
    soon as data is received from an upper layer in the protocol stack,
    adapting to fluctuating incoming traffic flows.  Injecting coded
    symbols based on a dynamic transmission window also breaks the

<DO> s/breaks/reduces/

    decoding delay lower bound imposed by traditional block codes and is
    well suited for delay-sensitive applications and streaming 
protocols.

    When coded symbols are transmitted through a communication network,
    erasures may occur, depending on channel conditions and interactions
    with underlying transport protocols.

<DO> it may be worth saying that RLNC assumes that bit or burst errors, 
when they occur either on a communication channel, via memory 
corruption, or by security attacks, are converted into erasures by 
lower-layer error detection procedures.

    RLNC can efficiently repair
    such erasures, potentially improving protocol response to erasure
    events to ensure reliability and throughput over the communication
    network.  For example, in a point-to-point connection, RLNC can

<DO> It might be better to say “two-party” rather than 
“point-to-point” as the latter tends to describe a channel rather 
than a communication relationship which might occur over a multi-hop, 
multi-path network. Similarly, as noted in general comments, avoiding 
the word “connection” by saying “for example, in two-party 
communication scenarios…”

    proactively compensate for packet erasures by generating Forward
    Erasure Correcting (FEC) redundancy, especially when a packet 
erasure
    probability can be estimated.  As any number of coded symbols may be
    generated from a set of data symbols, RLNC is naturally suited for
    adapting to network conditions by adjusting redundancy dynamically 
to
    fit the level of erasures, and by updating coding parameters during 
a
    session.  Alternatively, packet erasures may be repaired reactively
    by using feedback requests from the receiver to the sender, or by a
    combination of FEC and retransmission.  RLNC simplifies state and
    feedback management and coordination as only a desired number of
    degrees of freedom needs to be communicated from the receiver to the
    sender, instead of indications of the exact packets to be
    retransmitted.  The need to exchange packet arrival state 
information
    is therefore greatly reduced in feedback operations.

<DO> in order to quantify “greatly”, an example with actual numbers 
would be useful.

    The advantages of RLNC in state and feedback management are apparent
    in a multicast setting.  In this one-to-many setup, uncorrelated
    losses may occur, and any retransmitted data symbol is likely to
    benefit only a single receiver.  By comparison, a transmitted RLNC
    coded symbol is likely to carry a new degree of freedom that may
    correct different errors at different receivers simultaneously.
    Similarly, RLNC offers advantages in coordinating multiple paths,
    multiple sources, mesh networking and cooperation, and peer-to-peer
    operations.

    A more detailed introduction to network coding including RLNC is
    provided in the books [MS11] and [HL08].

1.2.  Generation-Based RLNC

    This section describes a generation-based RLNC scheme.

    [snip]

    For any protocol that utilizes generation-based RLNC, a setup 
process
    is necessary for establishing a connection and conveying coding
    parameters from the sender to the receiver.

<DO> I wouldn’t couch this as a “setup process”, nor use the word 
“connection” as noted in my general comment. Instead say something 
like “For any protocol that utilizes generation-based RLNC, the coding 
parameters used to create the coded symbols must be conveyed to the 
receiver(s) before decoding can occur. This can be done either as part 
of the packets containing the coded symbols, via separate packets sent 
prior to the packets with coded symbols in the same packet flow, or 
out-of band using a separate protocol”

    Such coding parameters
    can include one or more of field size, code specifications, index of
    the current generation being encoded at the sender, generation size,
    code rate, and desired feedback frequency or probability.

<DO> this is nice, but just as with symbol representation, more guidance 
and hopefully pointers to one or more actual specifications (to be 
produced) would really make this more complete. Additionally, just as 
with the symbol representation, this is a good place to describe the 
options and tradeoffs for how the conveyance of coding parameters are 
embedded into a containing transport or application protocol. Section 
2.1.2 covers only part of this - the part dealing with the interaction 
of coding parameters with the matrix size (and some MTU considerations 
which probably belong separately since they apply to both symbol size 
and coding parameters).

    Some
    coding parameters are updated dynamically during the transmission

<DO> s/are/may be/ ?

    process, reflecting the coding operations over sequences of
    generations, and adjusting to channel conditions and resource
    availability.  For example, an outer header can be added to the
    symbol representation specified in [Symbol-Representation] to
    indicate the current generation encoded within the symbol
    representation.  Such information is essential for proper recoding
    and decoding operations, but the exact design of the outer header is
    outside the scope of the current document.

<DO> Well, so is the actual symbol representation since we decided to 
split it off, so this needs a bit of re-write. Also, casting this as an 
“outer header” is only one option as it may be either prepended, 
interleaved, or appended when creating coded packets, sent separately, 
or sent out-of band.

    At the minimum, an outer
    header should indicate the current generation, generation size,
    symbol size, and field size.  Section 2 provides a detailed

<DO> Might be more specific and say section 2.1.2 instead of just 
section 2.

    discussion of coding parameter considerations.

1.3.  Sliding Window RLNC

    This section describes a sliding-window RLNC scheme.  Sliding window
    RLNC was first described in [SS09].

    In sliding-window RLNC, input data as received from an upper layer 
in
    the protocol stack is segmented into equal-sized data symbols for
    encoding.  In some implementations, the sliding encoding window can
    expand in size as new data packets arrive, until it is closed off by
    an explicit instruction, such as a feedback message that 
re-initiates
    the encoding window.

<DO> I’m clearly missing something unless sliding window is only 
intended to work two party, and not with multicast. If that’s the 
case, say so. If multicast is supposed to work, we need some more 
description of how window closure is supposed to be managed across 
multiple receivers (especially in the presence of stragglers).

    In some implementations, the size of the
    sliding encoding window is upper bounded by some parameter, fixed or
    dynamically determined by online behavior such as packet loss or
    congestion estimation.  Figure 3 below provides an example of a
    systematic finite sliding window code with rate 2/3.

[snip]

    For any protocol that utilizes sliding-window RLNC, a setup process
    is necessary for establishing a connection and conveying coding
    parameters from the sender to the receiver.  Such coding parameters
    can include one or more of field size, code specifications, symbol
    ordering, encoding window position, encoding window size, code rate,
    and desired feedback frequency or probability.

<DO> Repeat same comments I made above in the generational RLNC 
material.

    Some coding
    parameters can also be updated dynamically during the transmission
    process in accordance to channel conditions and resource
    availability.  For example, an outer header can be added to the
    symbol representation specified in [Symbol-Representation] to
    indicate an encoding window position, as a starting index for 
current
    data symbols being encoded within the symbol representation.  Again,
    such information is essential for proper recoding and decoding
    operations, but the exact design of the outer header is outside the
    scope of the current document.  At the minimum, an outer header
    should indicate the current encoding window position, encoding 
window
    size, symbol size, and field size.  Section 2 provides a detailed
    discussion of coding parameter considerations.

<DO> Ditto - repeat same comments I made above in the generational RLNC 
material.

    Once a connection is established, RLNC coded packets comprising one
    or more coded symbols are transmitted from the sender to the
    receiver.

<DO> Ditto - repeat same comments I made above in the generational RLNC 
material with respect to the word “connection”.

    The sender can transmit in either a systematic or coded

<DO> coding cognoscenti will know that you mean here, but somewhere 
(probably earlier in the general RLNC Intro), you should have a few 
sentences about how RLNC can work as either a systematic or 
non-systematic code. It comes out of the blue here (and interestedly 
wasn’t brought up in the generational RLNC material).

    fashion, with or without receiver feedback.  In progressive decoding
    of RLNC coded symbols, the notion of "seen" packets can be utilized
    to provide degree of freedom feedbacks.  Seen packets are those
    packet that have contributed to a received coded packet, where
    generally the oldest such packet that has yet to be declared seen is
    declared as seen [SS09].

<DO> [SS09] talks about TCP. What about other protocols? I’m mostly 
reacting to the word “oldest” in the above text, which might mean 
different things in different protocols, particularly ones that do not 
rigorously enforce in-order delivery like TCP does.

[snip]

2.  Practical Considerations

    This is an open section describing various practical considerations
    such as standardization approaches and implementation-related 
topics.

2.1.  Symbol Representation

    This sub-section argues for the specification of symbol
    representation as a starting point for network coding 
standardization

<DO> s/as a starting point for/as one critical element of/

    and provides relevant coding parameter design considerations.

2.1.1.  Symbol Representation as a Standardization Approach

    Symbol representation specifies the format of the symbol-carrying
    data unit that is to be coded, recoded, and decoded.  In other 
words,
    symbol representation defines the format of the coding-layer data
    unit, including header format and symbol concatenation.

    Network Coding has fundamentally different requirements from
    conventional point-to-point codes.

<DO> I find this as just asking for somebody to argue. Reword? Maybe 
“Network coding has a multi-dimensional structure in terms of coding 
field size, symbol size, dynamic modification, etc. This leads to 
requirements for a highly reconfigurable symbol set.”

    Network coding owes its distinct
    requirements to its dynamic structure, leading to a highly
    reconfigurable symbol set.  For example:

    o  Coefficient Location: RLNC's encoding, recoding, and decoding
       process requires coefficients and payload to go through identical
       coding operations.

<DO> I found this a bit confusing - why do the coefficients go through 
“identical coding operations”?

       These operations are independent from the
       location of the coefficients.  As a consequence, coefficient
       location is flexible.  While some designs cluster coefficients
       together, other designs may distribute them throughout the 
payload
       in a manner that is specific to a given protocol.  [SS09]

    o  Number of coefficients: RLNC is designed to allow coding and
       recoding even when the number of input symbols is dynamic, 
leading
       to varying code density.  As a consequence, the number of
       coefficients and source data symbols need not be fixed.

    o  Payload Size: Although an identical size of symbols is desirable
       when performing coding operations, padding and fragmentation are
       viable not only at the source but also throughout the network, as
       illustrated in the example of Figure 5.  This allows flexibility
       in the payload size.

    o  Field: Although the finite field is typically a fixed system
       variable,

<DO> saying “system” here begs the question of what exactly is the 
“system”. Maybe say “fixed for a given application instance and 
protocol embedding”?

       this is not necessarily the case.  Network coding need
       not specify a single field for all payload components, as
       different symbols may belong to different fields (e.g., packet
       concatenation).  This feature does not necessarily complicate
       coding, since finite field operations defined in a given field 
are
       typically valid in multiple other fields.

[snip]

    Useful symbol representations should include provisions for the 
major
    coding functions that are relevant to the application, such as
    recoding, feedback, or inter-session network coding.  For example,
    recoding requires the coefficients to be accessible at the
    intermediate recoding nodes.  Hence, architectures and protocols
    requiring recoding must specify coefficient location.

<DO> Here’s a particular place (recoding by intermediaries) where 
interaction with crypto may come into play, not necessarily to discuss 
here, but maybe to forward-point to some security considerations. It 
seems the privacy issues around what in the end-to-end communication is 
exposed to intermediaries needs to be spelled out.

[snip]

    The absence of information on coefficient location has important
    implications.  One such implication is that any additional coding
    needs to be carried out within a new coding layer, potentially
    leading to higher computational and transport overheads.

<DO> use of the term “layer” here can be confusing - you could be 
referring to “layer” in the sense protocol people do as a protocol 
encapsulation, or “layer” as coding people do in the sense of 
“layered coders”.

    The elements discussed above demonstrate that the design choices
    related to symbol representation have a direct impact on the
    viability of protocols, topologies, and architecture. The importance
    of symbol representation is illustrated in Figure 5, where the term
    "architecture" includes coding architecture (e.g., generation or
    sliding window), the layer placement of coding operations, and 
coding
    objectives (e.g., erasure correction, multisourcing, etc.).

                     +---------------+
                     |Architecture   |
                     |               |     Symbol
                     |               |     Representation
                     |               |
         +-------------------+       |          ^
         |Topology   |       |       |          |
         |           |  +-------------------+   |
         |           |  |----|       |      |   |
         |           |  |----| <----------------+
         |           |  |----|       |      |
         |           +---------------+      |
         |              |    |              |
         +-------------------+              |
                        |                   |
                        |           Protocol|
                        +-------------------+

    Figure 5: The specification of symbol representation has major
    implications on system architecture, topology, and protocol.

    Since symbol representation has implications on core design 
elements,
    it is expected that coding implementations that share protocol,
    architecture, and topology elements

<DO> I found this pretty confusing.  What is the “topology” impact? 
In the case of topology are you saying I need to know the network 
topology in order to choose a good coding symbol representation? Or 
conversely that if I choose the “wrong” symbol representation coding 
won’t work well in my specific topology? The diagram above didn’t 
help me…


    are likely to reuse the same
    symbol representation.  For example, implementations with security
    requirements can reuse a common symbol representation that hides
    coefficient locations.

<DO> sorry… I’m having trouble seeing the connection between hiding 
coefficient locations and security requirements. This would seem to be 
saying you can hide coefficient locations and that makes your security 
considerations different? More basically, how do you “hide” the 
coefficient locations without using crypto in the first place?

    Another example can be found in [Symbol-Representation], which
    specifies symbol representation designs for generation-based and
    sliding window RLNC implementations.  These designs introduce highly
    reusable formats that concatenate multiple symbols and associate 
them
    with a single symbol representation header.

2.1.2.  Coding Parameter Design Considerations

[snip]

    The generation size or coding window size is a tradeoff between the
    strength of the code and the computational complexity of performing
    the coding operations.  With a larger generation/window size, fewer
    generations or coding windows are needed to enclose a data message 
of
    a given size, thus reducing protocol overhead for coordinating
    individual generations or coding windows.  In addition, a larger
    generation/window size increases the likelihood that a received 
coded
    symbol is innovative with respect to previously received symbols,
    thus amortizing retransmission or FEC overheads.  Conversely, when
    coding coefficients are attached, larger generation/window sizes 
also
    lead to larger overheads per packet.  The generation/window size to
    be used can be signaled between the sender and receiver when the
    connection is first established.

<DO> s/when the connection/when communication/

    Lastly, to successfully decode RLNC coded symbols, sufficient 
degrees
    of freedom are required at the decoder.  The maximum number of
    redundant symbols that can be transmitted is therefore limited by 
the
    number of linearly independent coding coefficient vectors that can 
be
    supported by the system.  For example, if coding vectors are
    constructed using a pseudo-random generator, the maximum number of
    redundant symbols that can be transmitted is limited by the number 
of
    available generator states.[RFC5445]

3.  Security Considerations

    This document does not present new security considerations.

<DO> New compared to what?

[snip]

DaveO