| IRTF Network Coding Working Group | M. Montpetit |
| Internet-Draft | MIT |
| Intended status: Experimental | V. Roca |
| Expires: September 10, 2015 | INRIA |
| J. Detchart | |
| ISAE | |
| March 9, 2015 |
Dynamic Network Coding
draft-montpetit-dynamic-nc-00
This document presents a network coding approach that allows coding decisions to be based on the instantaneous conditions at the network nodes. It uses dynamic rates and coefficients to constantly adapt to local conditions and to allow for provider and application differentiation.
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 http://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 September 10, 2015.
Copyright (c) 2015 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 (http://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 Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
Network Coding has proven to be an efficient mechanism to provide increased quality of experience for applications depending on Internet Protocols. Current implementations, be them end-to-end or hop-by-hop, depend on a global decision on the type and applicability of the code. However, the heterogeneous nature of IP networks, the differences between transported traffics and the rise of Information Centric Networks (ICN) and multiple in network caches require to define alternatives to current solutions.
Dynamic Network Coding (DNC) intends to use the characteristics of the rising Internet traffic (Internet of Things, streaming, progressive downloads etc.), the use of in-network caching opportunities, customer and policy management and the changing dynamics on wireless links. These characteristics will be used to adapt the network coding scheme, rate and coefficients to provide adaptive behavior, differentiation and varying quality of experience. In addition, it will also allow to support emerging Internet Architectures such as the ICN that are considering network coding solutions [ICN].
This draft provides the basic elements of such a dynamic code.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].
This document uses the following definitions, that are mostly inspired from from [RFC5052], [RFC6363].
This document uses the following notations:
This document uses the following abbreviations:
Network Coding is based on the linear combination of a number of input symbols (at least 1) into a number of output symbols (at least 1), between the ingress and egress of the network. Several such encoding operations can happen in case of in-network re-coding, or there can be a single encoding operation, especially when it is applied end-to-end. In the RLNC [RLNC], Tetrys [I-D.detchart-nwcrg-tetrys], and Dragoncast [I-D.adjih-dragoncast] instances of Network Coding, the linear combination consists in applying a set of coding coefficients to each input symbol of the current encoding window. Here the coding vectors are chosen in a deterministic manner at each encoding node, for instance based on local criteria, or are generated using a PRNG seed chosen locally and carried along with the output symbol.
The DNC proposal extends this process as follows: the set of coding coefficients is determined based on the FEC_Encoding ID, Codepoint, and TS header fields of the various input packets present in the encoding window, plus the local time. The coding decision therefore depends on time, among other pieces of information.
Each DNC Packet contains timing information: this can be the TS field of the DNC header, or the timestamp field of an NTP header if already present in the packet. This timing information (noted TS hereafter, no matter its origin) is used to determine the coding coefficients in a coding node. When several DNC packets are present in the encoding window, originating from one or several sources, a decision on which TS will be sent downstream in the network must be taken. Options include keeping the oldest TS value, the newest TS value, or generating a local TS value. It is assumed that the granularity of the TS in choosing the coding coefficients would be to the second tin order to react to instantaneous condition.
It is also possible to use the TS in a wider sense, to link to network operations and coding based police management. This includes the determination of the coding window, Code Rate, Galois field, etc.
The FEC Encoding ID is used to identify the type of code (i.e., FEC Scheme) to use at each coding node. This is an integer identifier assigned by IANA. The value of the FEC Encoding ID MAY vary over the time, within the same flow, and/or across the same path between several coding nodes. Different coding decisions can be made by different management entities with different operating constraints (for instance content provider versus network operator).
The Codepoint is an opaque value to be used along with the FEC Encoding ID and TS. The {FEC Encoding ID, Codepoint, TS} tuple identifies uniquely the FEC Scheme used and the set of coding coefficients. Examples are provided below on how to do that.
Incoming DNC packets at a coding node are not necessarily of the same fixed size. This size may largely vary over the time, up to a maximum size that is related to the Link MTU and/or Path MTU. This is a problem when Repair Symbols need to be produced by a coding node.
Let us consider the simple case where the FEC Scheme is such that a Repair Symbol necessarily spans the payload of the largest Incoming DNC Packet at the encoding window of the coding node. Let L be equal to the maximum size of the DNC packets in the encoding window plus 2 bytes. The 2 bytes are used to store the original size of the packets. Any DNC packet of size inferior to L-2 bytes MUST be zero padded to achieve the desired length of L bytes. Then any Repair Symbol within the set of Output Symbols is L bytes long. When a Source Symbol is erased and later decoded, the first two bytes of the decoded symbol, that contain the symbol_len field, allows to drop the potential padding.
+------------+-----------------------+------------------------------+ | symbol_len | symbol value | optional padding | +------------+-----------------------+------------------------------+ 2 bytes symbol_len bytes L - 2 - symbol_len bytes <------------------------------- L bytes --------------------------->
Figure 1: Symbol Format, Case of a Single Flow
TBD
For instance it may be interesting to have a feedback flow to enable a receiver to adjust its encoding window according to the received or decoded Source Symbols.
Several technical aspects need to be considered:
The above taxonomy can be used to identify several types of use-cases. In the following we consider some of the potential use-cases and explain how DNC can be applied. This is in no case an exhaustive list and will be adapted in the future as we get more insights on the code usage.
In this use-case, there is a single flow originated by a single source, with intra stream coding that takes place at a single coding node. There can be either a single path or multiple paths, since this situation does not impact the way DNC operates.
This is the simplest use-case, that is very much inline with currently proposed scenarios for end to end streaming.
The following DNC approach / FEC Scheme is appropriate for this simple use-case. However this is only an example and other approaches may be considered, for instance differing in the way the {FEC Encoding ID, Codepoint, TS} tuple is used.
Let us consider a FEC Scheme that defines the G table containing NL lists, each list being populated with NC coefficients over a given Finite Field, say GF(2^^4). This table, G, is contained in the FEC Scheme specification. Each coding and decoding node supports this FEC Scheme (and potentially a certain number of additional FEC Schemes), this latter being identified by an IANA FEC Encoding ID value.
Let r be an integer calculated as r=f(Codepoint, TS, K); where f is a deterministic function that produces an integer in the {0; K-1} range. This function is for instance the result of a hash over {Codepoint, TS} modulo K.
The output Repair Symbol is computed as the XOR sum of each Input Symbol in W multiplied by the corresponding coefficient in row r of G (i.e., the first symbol is multiplied by G[r][0], the second symbol is multiplied by G[r][1], etc. til the last symbol of W).
In this use-case, there is a single flow, originated either by a single source or by multiple source for the same content, with in-network re-coding capabilities. There can be either a single path or multiple paths (e.g., if there are multiple sources). There are multiple sub use-cases, among which the following three ones.
S ==> CN_1 ==> Router ==> D_1
| | source symbols
erasures | v
+======> CN_2 ==> D_2
Figure 2
S_1 ==> CN_1 ==> CN_3 ==> D_1
^
|
S_2 ==> CN_2 =====+
Figure 3
Another scenario is the following, where two sources generate some traffic for the same content:
S ==> CN_1 ==> low losses ==> CN_2 ==> high losses ==> D_1
Figure 4
Finally, with a single flow passing through wired and wireless paths, the following scenario is likely. [QUIC]). Between CN_2 et D_1 the link can be a WIFI or LTE wireless network, potentially experiencing higher losses. Consequently a higher number of Repair Symbols (i.e., lower code rate) can be needed, with potentially a local feedback loop that enables to adapt the code rate based on the instantaneous conditions observed over that lossy link.
Many use-cases remain TBD, for instance to cover the Peer to peer, complex multipath, or storage use-cases.
M-J. Montpetit would like to thank Huawei and in particular Shucheng Liu for supporting the work leading to this draft.
TBD
TBD, see RFC 3552 [RFC3552].
| [RFC2119] | Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. |
IPR aspects if any to be provided later