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
Abstract
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.
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 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 Notice
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
Montpetit, et al. Expires September 10, 2015 [Page 1]
Internet-Draft Dynamic Network Coding March 2015
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.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Requirements Language . . . . . . . . . . . . . . . . . . . . 3
3. Definitions, Notations and Abbreviations . . . . . . . . . . 3
3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 3
3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 4
3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 4
4. Dynamic Network Coding (DNC) Principles . . . . . . . . . . . 5
4.1. About the Use of Timestamps in DNC . . . . . . . . . . . 5
4.2. About the FEC Encoding ID, Codepoint and Coding Decisions 6
5. Dynamic Network Coding (DNC) Procedures . . . . . . . . . . . 6
5.1. Input Symbol Creation . . . . . . . . . . . . . . . . . . 6
5.2. Other Procedures TBD . . . . . . . . . . . . . . . . . . 7
6. Application of Dynamic Network Coding to Various Use-cases . 7
6.1. Single Flow, Single Source, End-to-end, Single Path or
Multi Paths Use-Case . . . . . . . . . . . . . . . . . . 8
6.1.1. Example of DNC Implementation for this Use-Case . . . 8
6.2. Single Flow with In-network Re-Coding . . . . . . . . . . 10
6.3. Other Use Cases . . . . . . . . . . . . . . . . . . . . . 11
7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11
9. Security Considerations . . . . . . . . . . . . . . . . . . . 11
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11
10.1. Normative References . . . . . . . . . . . . . . . . . . 11
10.2. Informative References . . . . . . . . . . . . . . . . . 11
Appendix A. Appendix: IPR aspects . . . . . . . . . . . . . . . 12
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12
1. Introduction
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
Montpetit, et al. Expires September 10, 2015 [Page 2]
Internet-Draft Dynamic Network Coding March 2015
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.
2. Requirements Language
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].
3. Definitions, Notations and Abbreviations
3.1. Definitions
This document uses the following definitions, that are mostly
inspired from from [RFC5052], [RFC6363].
-- Editor's note: most of the definitions should be moved to the
future NC Architectural document. --
Input Symbol: a unit of data that is provided as an input to the
coding process, in a given coding node. It may be a source symbol
or an already encoded repair symbol
Output Symbol: a unit of data that is produced as an output of the
coding process, in a given coding node
Source Symbol: an original unit of data, before any coding process
is applied
Repair Symbol: an Output Symbol that is not a Source Symbol
Code Rate: the ratio between the number of Input Symbols and the
number of Output Symbols at given coding node. The Code Rate
belongs to a ]0; 1] interval. A Code Rate close to 1 indicates
that a small number of Output Symbols have been produced during
the encoding process
Systematic Code: NC code in which the Source Symbols are part of
the Output Symbols
Montpetit, et al. Expires September 10, 2015 [Page 3]
Internet-Draft Dynamic Network Coding March 2015
DNC Packet: a packet (e.g., carried as the payload of a UDP
datagram) containing a given Output Symbol plus its associated DNC
header.
Packet Erasure Channel: a communication path where packets are
either dropped (e.g., by a congested router or because the number
of transmission errors exceeds the correction capabilities of the
physical layer codes) or received. When a packet is received, it
is assumed that this packet is not corrupted
To Be Completed
-- Editor's note: Should we consider the possibility of having
several symbols per packet? The DNC packet should be updated
accordingly in that case. --
3.2. Notations
This document uses the following notations:
CR denotes the Code Rate
To Be Completed
3.3. Abbreviations
This document uses the following abbreviations:
The following definitions are compatible with the FECFRAME
framework [RFC6363] and the NC architecture (COMMENT: reference to
be added when available).
NC: Network Coding
DNC: Dynamic Network Coding
PRNG: Pseudo-Random Number Generator
TS: Time Stamp
ESI: Encoding Symbol ID
To Be Completed
Montpetit, et al. Expires September 10, 2015 [Page 4]
Internet-Draft Dynamic Network Coding March 2015
4. Dynamic Network Coding (DNC) Principles
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.
4.1. About the Use of Timestamps in DNC
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.
-- Editor's note: This extension is left for future specifications
as it requires closer coordination between network management.
policy and coding. --
Montpetit, et al. Expires September 10, 2015 [Page 5]
Internet-Draft Dynamic Network Coding March 2015
4.2. About the FEC Encoding ID, Codepoint and Coding Decisions
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).
-- Editor's note: Having the possibility to change the coding
decisions can have major practical technical implications that are
not considered for the moment. --
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.
5. Dynamic Network Coding (DNC) Procedures
5.1. Input Symbol Creation
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
Montpetit, et al. Expires September 10, 2015 [Page 6]
Internet-Draft Dynamic Network Coding March 2015
-- Editor's note: in presence of multiple flows, an additional
FlowID field may be prepended in order to identify the flow this
Input Symbol belongs to. The details are TBD. --
5.2. Other Procedures TBD
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.
6. Application of Dynamic Network Coding to Various Use-cases
-- Editor's note: This section contains material that may be more
appropriate in a future NC Architecture document. --
Several technical aspects need to be considered:
o Intra-flow encoding: (single flow) here all the Source Symbols
belong to the same and unique flow;
o Inter-flow encoding: (multiple flows) here the Source Symbols
belong to two or more flows. This situation is more complex, in
particular because it requires to remember the flow a given source
symbol belongs to in case this latter gets lost and is recovered
by a decoding node;
o End to end: (single coding node) here there is a single coding
node and a single decoding node. However the coding and/or
decoding nodes are not necessarily the source and destination
nodes. For instance these operations can be performed by middle
boxes, or coding may be done in a middle box while decoding is
performed at the destination node, or vice-versa. The nature of
the coding and decoding nodes should not significantly impact the
way DNC operates;
-- Editor's note: This claim is TBC. --
o In network re-coding: (composability) here several coding nodes
exist along the path. This situation significantly impacts the
way DNC operates, in particular in terms of signaling. Indeed a
decoding node MUST be able to identify the exact manner in which a
given Repair Symbol has been generated, recursively since this
Repair Symbol MAY be the result of several coding operations, at
different coding nodes;
Montpetit, et al. Expires September 10, 2015 [Page 7]
Internet-Draft Dynamic Network Coding March 2015
o Multi-source: here several traffic sources exist. They either
jointly contribute to the same data flow, all sources sending
traffic related to the same content, or they contribute to
multiple data flows, sources sending traffic for different
contents;
o Multi-paths: here the traffic follows multiple paths. This
traffic can be originated from a unique source (e.g., with multi-
path TCP, MPTCP), or with multiple sources which is the more
general case;
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.
6.1. Single Flow, Single Source, End-to-end, Single Path or Multi Paths
Use-Case
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.
6.1.1. Example of DNC Implementation for this Use-Case
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.
o Encoding process: Let W be the encoding window, containing K Input
Symbols (constructed as specified in Section 5.1). It is required
that K be at most equal to the number of coefficients in each row
of G. If this is not the case, an appropriate number of symbols
are removed from window W until this property holds. Let TS be
Montpetit, et al. Expires September 10, 2015 [Page 8]
Internet-Draft Dynamic Network Coding March 2015
the timestamp corresponding to the current time at the coding
node. Let Codepoint be the current integer value of a counter
that is managed sequentially, starting a 0 upon initializing the
DNC coding node instance, and wrapping to 0 upon reaching the
maximum counter value.
-- Editor's note: The counter field size, in bits, is not
specified in this version of the document. 32 bits or 16 bits
are two possible values. --
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.
-- Editor's note: The FEC Scheme specification fully specifies
this f function. --
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).
o Transmitted Output Symbol: The FEC Encoding ID is communicated in
the DNC packet header. The {Codepoint, TS} tuple can be used to
uniquely identify the Repair Symbol produced by the coding
process. This tuple is communicated in the DNC packet header.
The ESI of each packet currently in W is communicated in the DNC
packet header. This information can consist of a list of ESIs, or
in the simple case where they are all in sequence, the {first ESI,
K} tuple can be communicated, or a sequence of such tuples can be
sent in the case where ESIs are mostly in sequence with a limited
number of gaps, of the first ESI along with a bit field (e.g., of
size 64 bits if K is at most 64) can be communicated.
-- Editor's note: Many other pieces of information will be
transmitted for other features. The DNC header format also
remains TBD. --
o Processing at the decoding node: Upon receiving this Repair
Symbol, an additional equation is added to the current linear
system. The FEC Encoding ID enables the decoding node to identify
the FEC Scheme used by the coding node, as well as the G matrix.
The {Codepoint, TS} tuple enables the decoding node to identify
the set of coding coefficients used by the coding node.
o Decoding process: If the linear system enables it, a decoding
process is used to recover an erased Source Symbol. The first two
Montpetit, et al. Expires September 10, 2015 [Page 9]
Internet-Draft Dynamic Network Coding March 2015
bytes of the decoded symbol is read and used to identify the
initial length of the Source Symbol and to remove padding if
needed. The decoded Source Symbol is then communicated to the
receiving node (or receiving application).
6.2. Single Flow with In-network Re-Coding
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
In this first scenario CN_1 et CN_2 are two NC encoders. The flow
arriving in CN_2 from the router is impacted by erasures. However
this is not the case of the links to destination D_1, that has
decoded the packets and this node retransmits the source symbols
received or recovered towards D_2. In CN_2 all symbols are
recombined and sent to D_2. This could be a scenario that combines
wired and wireless paths.
Another scenario is the following, where two sources generate some
traffic for the same content:
S_1 ==> CN_1 ==> CN_3 ==> D_1
^
|
S_2 ==> CN_2 =====+
Figure 3
Here S_1 and S_2 are transmitting the same content. The flow coming
from S_1 (resp. S_2) is encoded at CN_1 (resp. CN_2), and the two
encoded flows are later re-encoded in CN_3, a third NC encoder, on
their way to D_1.
Finally, with a single flow passing through wired and wireless paths,
the following scenario is likely.
Montpetit, et al. Expires September 10, 2015 [Page 10]
Internet-Draft Dynamic Network Coding March 2015
S ==> CN_1 ==> low losses ==> CN_2 ==> high losses ==> D_1
Figure 4
Between CN_1 and CN_2, the network is a wired internet and a high
rate code (i.e., adding a limited number of encoded packets) can be
used (e.g., it may be a simple XOR of packets as in QUIC [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.
6.3. Other Use Cases
Many use-cases remain TBD, for instance to cover the Peer to peer,
complex multipath, or storage use-cases.
7. Acknowledgements
M-J. Montpetit would like to thank Huawei and in particular Shucheng
Liu for supporting the work leading to this draft.
8. IANA Considerations
TBD
9. Security Considerations
TBD, see RFC 3552 [RFC3552].
10. References
10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
10.2. Informative References
[I-D.adjih-dragoncast]
Adjih, C., Cho, S., and E. Baccelli, "Broadcast With
Network Coding: DRAGONCAST", draft-adjih-dragoncast-00
(work in progress), July 2013.
Montpetit, et al. Expires September 10, 2015 [Page 11]
Internet-Draft Dynamic Network Coding March 2015
[I-D.detchart-nwcrg-tetrys]
jonathan.detchart@isae.fr, j., Lochin, E., Lacan, J., and
V. Roca, "Tetrys, an On-the-Fly Network Coding protocol",
draft-detchart-nwcrg-tetrys-00 (work in progress), October
2014.
[ICN] Montpetit, M., Wesphal, C., and D. Trossen, "Network
coding meets information-centric networking: an
architectural case for information dispersion through
native network coding", Proceedings of the 1st ACM
workshop on Emerging Name-Oriented Mobile Networking
Design - Architecture, Algorithms, and Applications
(NOM'2012), June 2012.
[QUIC] Roskind, JR., "QUIC: Quick UDP Internet Connections
Multiplexed Stream Transport", IETF-88 TSV Area
Presentation, November 2013.
[RFC3552] Rescorla, E. and B. Korver, "Guidelines for Writing RFC
Text on Security Considerations", BCP 72, RFC 3552, July
2003.
[RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error
Correction (FEC) Building Block", RFC 5052, August 2007.
[RFC6363] Watson, M., Begen, A., and V. Roca, "Forward Error
Correction (FEC) Framework", RFC 6363, October 2011.
[RLNC] Ho, T., Koetter, R., Medard, M., Karger, D., Effros, M.,
Shi, J., and B. Leung, "A Random Linear Network Coding
Approach to Multicast", IEEE Transactions on Information
Theory Vol. 52 No. 10, October 2006.
Appendix A. Appendix: IPR aspects
IPR aspects if any to be provided later
Authors' Addresses
Marie-Jose Montpetit
MIT
Cambridge, MA 02138
USA
Email: mariejo@mit.edu
Montpetit, et al. Expires September 10, 2015 [Page 12]
Internet-Draft Dynamic Network Coding March 2015
Vincent Roca
INRIA
655, av. de l'Europe
Inovallee; Montbonnot
ST ISMIER cedex 38334
France
Email: vincent.roca@inria.fr
URI: http://privatics.inrialpes.fr/people/roca/
Jonathan Detchart
ISAE
10, avenue Edouard-Belin
BP 54032
Toulouse CEDEX 4 31055
France
Email: jonathan.detchart@isae.fr
Montpetit, et al. Expires September 10, 2015 [Page 13]