NWCRG J. Detchart Internet-Draft E. Lochin Intended status: Experimental J. Lacan Expires: April 30, 2015 ISAE V. Roca INRIA October 27, 2014 Tetrys, an On-the-Fly Network Coding protocol draft-detchart-nwcrg-tetrys-00 Abstract This document describes Tetrys, an On-The-Fly Network Coding (NC) protocol which can be used to transport delay and loss sensitive data over a network. This protocol can be used for unicast, multicast or anycast communications. It recovers lost packets by using added coded packets. Tetrys allows to recover all missing data within a time independent of the RTT and does not rely on a reliable feedback path to transmit data. 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 April 30, 2015. Copyright Notice Copyright (c) 2014 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 Detchart, et al. Expires April 30, 2015 [Page 1] Internet-DraftTetrys, an On-the-Fly Network Coding protocol October 2014 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. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Architecture Reference . . . . . . . . . . . . . . . . . . . 4 4. Tetrys Basic Functions . . . . . . . . . . . . . . . . . . . 4 4.1. Encoding . . . . . . . . . . . . . . . . . . . . . . . . 4 4.1.1. Encoding Vector Formats . . . . . . . . . . . . . . . 5 4.1.2. Encoding Windowing . . . . . . . . . . . . . . . . . 6 4.2. Decoding . . . . . . . . . . . . . . . . . . . . . . . . 7 4.2.1. Acknowledgements . . . . . . . . . . . . . . . . . . 7 5. Encapsulation Packet Format . . . . . . . . . . . . . . . . . 8 5.1. Source Packet Format . . . . . . . . . . . . . . . . . . 8 5.2. Coded Packet Format . . . . . . . . . . . . . . . . . . . 9 6. Security Considerations . . . . . . . . . . . . . . . . . . . 9 7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 10 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 10 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 10.1. Normative References . . . . . . . . . . . . . . . . . . 10 10.2. Informative References . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 1. Introduction This document presents the implementation details of a novel network coding protocol called Tetrys. Network codes introduced in 2000 [AHL-00] have been developed to address the limitations of transmission over the Internet (delay, capacity and packet loss). While the use of network codes in fairly recent in the Internet community, the use of application layer erasure codes in the IETF has already been standardised in the RMT [RMT] and the FECFRAME [FECFRAME] working groups. The protocol presented here can be seen as a network coding extension to standards solutions. The current proposal can be considered as a combination of network coding and feedback mechanisms [Tetrys]. A coded Tetrys packet is a linear combination over a finite field of the data source packets belonging to the coding window. The choice of the finite field of the coefficients is a trade-off between the best performance (with non-binary coefficients) and the system Detchart, et al. Expires April 30, 2015 [Page 2] Internet-DraftTetrys, an On-the-Fly Network Coding protocol October 2014 constraints (the use of binary codes in an energy constrained environment for example) and is driven by the application. The main novelty of the Tetrys protocol is to build coded packets from an coding window the size of which is periodically updated with the receiver's feedbacks. This update is done in such a way that any source packets coming from an input flow is included in the coding window as long as it is not acknowledged. This mechanism allows for losses on both the forward and return paths and for the acknowledgement messages to be lost. 1.1. Requirements Notation 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 [RFC2119]. 2. Terminology The terminology used in this document is presented below. It is aligned with the FECFRAME terminology as well as with recent activities in the Network Coding Research Group. Source symbol: a symbol that has to be transmitted between the ingress and egress of the network. Coded symbol: a linear combination of a set of source symbols. Input symbol: a symbol at the input of the Tetrys Encoding Building Block. In an end-to-end context, the input symbols are always source symbols. Output symbol: a symbol generated by the Tetrys Encoding Building Block. For a non systematic mode, all output symbols are coded symbols. For a systematic mode, output symbols can be the input symbols and a number of coded symbols that are linear combinations of the input symbols + the encoding vectors. Encoding vector: a set of the encoding coefficients and source symbol IDs. Source packet: a source packet contains a source symbol with its associated ID and size. Coded packet: a coded packet contains a coded symbol, the coded symbol's ID, size and encoding vector. Output packet: an output packet is either a coded packet, either a source packet. Detchart, et al. Expires April 30, 2015 [Page 3] Internet-DraftTetrys, an On-the-Fly Network Coding protocol October 2014 Feedback packet: a feedback packet is a packet containing information about the decoded/received source symbols. It can also bring additional information about the Packet Error Rate or the number of various packets in the receiver buffers Elastic Encoding Window: an encoder-side buffer that stores all non- acknowledged source packets used as an input flow to create coded packets. 3. Architecture Reference The architecture used in this document is aligned with the Network Coding Architecture draft [NWCRG-ARCH]. Tetrys uses two building blocks to provide a fully reliable protocol. The Tetrys Encoding Building Block creates some linear combinations of all the non-acknowledged input symbols. Each linear combination is called a coded symbol. It is associated to an encoding vector, which defines the input source symbols and the finite field coefficients used. This encoding mechanism is called an elastic encoding window. Each generated output symbols is encapsulated in an output packet format. A Tetrys Decoding Building Block stores all the received output packets. When it is possible, the coded symbols are decoded to generate the lost source symbols. Regularly, this building block sends a feedback packet containing information about the acknowledgement of received and decoded source symbols. +-----------+ +-----------+ | Tetrys | Output packets | Tetrys | input | Encoding |----------------->| Decoding | source ----------->| Building | Feedback packets | Building |--------> symbols | Block |<-----------------| Block | symbols +-----------+ +-----------+ Figure 1: Tetrys Architecture 4. Tetrys Basic Functions 4.1. Encoding When a Tetrys Encoding Building Block needs to generate a coded symbol, it considers the set of source symbols stored in the encoding windows. These source symbols are the set of source symbols which are not yet acknowledged by the receiver. At the generation of a coded symbol, the Tetrys Encoding Building Block builds an encoding vector containing the IDs of the source symbols stored in the encoding window. For each source symbol in the Detchart, et al. Expires April 30, 2015 [Page 4] Internet-DraftTetrys, an On-the-Fly Network Coding protocol October 2014 encoding window, a finite field coefficient is determined from a deterministic function taking as input the source symbol ID and the coded symbol ID. For example, deterministics coefficients can be obtained from traditional codes such as Reed-Solomon, or other methods. Finally, the coded symbol is the sum of the source symbols multiplied by their corresponding generated coefficients. 4.1.1. Encoding Vector Formats Depending of the signaling type, an encoding packet can contain a list of source symbol IDs. 4.1.1.1. Encoding Vector Format 1 The first encoding vector format uses a deterministic way to generate the coefficients, and a set of blocks for the source symbol IDs. In this format, we need to keep the number of blocks we used, as a 8bits unsigned integer. 0 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Encoding Vector Size | Type | Nb blocks | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Left Edge of 1st Block | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Right Edge of 1st Block | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | / . . . / | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Left Edge of nth Block | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Right Edge of nth Block | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2: Encoding Vector Format 1 Encoding Vector Size: size in bytes for the encoding vector. Type: the type of the encoding vector. MUST be 1 in this case. Nb blocks: the number of blocks stored in the encoding vector. Left Edge of Block: the first source symbol ID of this block. Right Edge of Block: the last source symbol ID of this block. Detchart, et al. Expires April 30, 2015 [Page 5] Internet-DraftTetrys, an On-the-Fly Network Coding protocol October 2014 4.1.1.2. Encoding Vector Format 2 The second option to send en encoding vectors is to send the symbol source IDs and the coefficients used. The IDs are unsigned 32bits integers, and the coefficients are unsigned 8bits integer corresponding to the elements in the finite field. 0 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Encoding Vector Size | Type | Nb packets | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1st Source Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 2nd Source Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | / . . . / | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | nth Source Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | coef 1 | coef 2 | ... | coef n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3: Encoding Vector Format 2 Encoding Vector Size: size in bytes for the encoding vector. Type: the type of the encoding vector. MUST be 2 in this case. Nb packets: the number of packets stored in the encoding vector. Source Symbol ID: unsigned 32bits integer source symbol ID you want to use. coef: a coefficient used for the linear combination. 4.1.2. Encoding Windowing When an input source symbol is passed by the upper layer to the Tetrys Building Block, it is added to the encoding window. In parallel, a copy of this packet can be sent onto the network. As an element of the encoding window, this symbol is included in the linear combinations created to generate coded symbols. As explained below, the receiver sends periodic feedbacks indicating the received or decoded source symbols. In the case of a unicast Detchart, et al. Expires April 30, 2015 [Page 6] Internet-DraftTetrys, an On-the-Fly Network Coding protocol October 2014 transmission, when the sender receives the information that a source symbol was received or decoded by the receiver, it removes this symbol from the encoding window. In a multicast transmission, a source symbol is removed from the encoding window only when all the receivers have received or decoded it. 4.2. Decoding The decoder uses the encoding vectors embedded in each coded packet to obtain the linear system used by the Tetrys Encoding Building Block. If the number of innovative coded symbols is greater than the number of lost source symbols, a classical method to solve the linear system, like e.g. matrix inversion, can be then used to recover the source symbols. 4.2.1. Acknowledgements A Tetrys Decoding Building Block can send back to a Tetrys Encoding Building Block some Acknowledge packets. They contain information about what it is received or decoded, and other information such as a packet loss rate or a size of the decoding buffers. 0 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version| Type | Total Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Nb missing source symbols | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Nb useless coded symbols | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | First Source Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sack size | | +-+-+-+-+-+-+-+-+ + | | / Sack Vector / | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 4: Acknowledgement Packet Format Version: the version of the packet format. MUST be 1. Type: the type of acknowledgement packet. MUSE be 1. Total length: the length of the packet (in bytes). Detchart, et al. Expires April 30, 2015 [Page 7] Internet-DraftTetrys, an On-the-Fly Network Coding protocol October 2014 Nb missing source symbols: the number of missing source symbols in the receiver buffer. Nb useless coded symnbols: the number of useless coded symbols in the receiver buffer. Meaning the number of linear combinations containing at least 2 unknown source symbols. First Source Symbol ID: the first source symbol to acknowledge. Sack size: the size (unsigned integer 8 bits) of the sack vector as a multiple of 32 bits. Ex: if the value is 2, the sack vector is 64 bits. Sack vector: the vector for the acknowledge symbols following the first source symbol ID. 5. Encapsulation Packet Format 5.1. Source Packet Format A source packet is the encapsulation of a source symbol and a packet header. 0 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version| Type | Total Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | / Payload / | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 5: Source Packet Format Version: the version of the packet format. MUST be 1. Type: the packet type. MUST be 1. Total length: size in bytes for the packet. Source Symbol ID: the sequence number to identify a source symbol. Payload: the payload (source symbol) Detchart, et al. Expires April 30, 2015 [Page 8] Internet-DraftTetrys, an On-the-Fly Network Coding protocol October 2014 5.2. Coded Packet Format A coded packet is the encapsulation of a coded symbol, the associated encoding vector and a packet header. 0 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version| Type | Total Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Coded Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | / Encoding Vector / | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Encoded Payload Size | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | / Payload / | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 6: Coded Packet Format Version: the version of the packet format. MUST be 1. Type: the packet type. MUST be 2. Total length: size in byte for the packet. Coded Symbol ID: the sequence number to identify a coded symbol. Encoding Vector: an encoding vector to define the linear combination used (coefficients, and source symbols). Encoded Payload Size: the coded payload size used if source symbols are variable size. Payload: the payload (coded symbol) 6. Security Considerations TBD Detchart, et al. Expires April 30, 2015 [Page 9] Internet-DraftTetrys, an On-the-Fly Network Coding protocol October 2014 7. Privacy Considerations TBD 8. IANA Considerations N/A 9. Acknowledgments We would like to thank Dr Marie-Jose Montpetit from MIT for reviewing and commenting on this draft. 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 [AHL-00] Ahlswede, R., Ning Cai, , Li, S., and R. Yeung, "Network information flow", IEEE Transactions on Information Theory vol.46, no.4, pp.1204,1216, July 2000. [FECFRAME] Watson, M., Begen, A., and V. Roca, "Forward Error Correction (FEC) Framework", Request for Comments 6363, October 2011. [NWCRG-ARCH] NWCRG, , "Network Coding Architecture", TBD TBD. [RMT] Vicisano, L., Gemmel, J., Rizzo, L., Handley, M., and J. Crowcroft, "Forward Error Correction (FEC) Building Block", Request for Comments 3452, December 2002. [Tetrys] Lacan, J. and E. Lochin, "Rethinking reliability for long- delay networks", International Workshop on Satellite and Space Communications 2008 (IWSSC08), October 2008. Authors' Addresses Detchart, et al. Expires April 30, 2015 [Page 10] Internet-DraftTetrys, an On-the-Fly Network Coding protocol October 2014 Jonathan Detchart ISAE 10, avenue Edouard-Belin BP 54032 Toulouse CEDEX 4 31055 France Email: jonathan.detchart@isae.fr Emmanuel Lochin ISAE 10, avenue Edouard-Belin BP 54032 Toulouse CEDEX 4 31055 France Email: emmanuel.lochin@isae.fr Jerome Lacan ISAE 10, avenue Edouard-Belin BP 54032 Toulouse CEDEX 4 31055 France Email: jerome.lacan@isae.fr 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/ Detchart, et al. Expires April 30, 2015 [Page 11]