Network Coding Research Group (NWCRG) I. Amdouni Internet-Draft C. Adjih Intended status: Informational Inria Expires: January 5, 2015 July 4, 2014 Coding Interval-based Sliding Encoding Window draft-amdouni-nwcrg-cisew-00 Abstract This document details an online coding method for network coding called CISEW: Coding Interval-based Sliding Encoding Window. The method is proposed as a building block that could be integrated in a complete network coding protocol. This building block is responsible of: - decoding: maintaining and decoding of the set of received coded payloads, - recoding: selecting the content of generated coded payloads, - signaling: allowing for nodes to collect the information on the state of their neighbors. CISEW is based on a sliding window method; it generates coded payloads using only a small subset of original payloads. This allows for some real-time decoding (online decoding). CISEW is a overhaul and redesign of a similar method called SEW, part of the previously proposed protocol DRAGONCAST. CISEW refines the signaling and algorithms of SEW, and makes them more general. CISEW offers a general framework for online network coding, with associated signaling. From this framework, several online coding policies can be implemented. 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 Amdouni & Adjih Expires January 5, 2015 [Page 1] Internet-Draft CISEW July 2014 material or to cite them other than as "work in progress." This Internet-Draft will expire on January 5, 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 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 . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Context and Protocol Overview . . . . . . . . . . . . . . . . 5 3.1. Context . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2. Overview about CISEW . . . . . . . . . . . . . . . . . . . 6 3.3. Overview of CISEW Advertizement . . . . . . . . . . . . . 7 4. CISEW Design and General Rules . . . . . . . . . . . . . . . . 8 4.1. Signaling . . . . . . . . . . . . . . . . . . . . . . . . 8 4.2. CISEW Components . . . . . . . . . . . . . . . . . . . . . 10 4.2.1. Determination of the Encoding Window and the Coding Intervals . . . . . . . . . . . . . . . . . . . 10 4.2.2. Generation of Payloads . . . . . . . . . . . . . . . . 11 4.2.3. Processing of Payloads . . . . . . . . . . . . . . . . 12 5. Specification of Proposed Policies and Algorithms for CISEW . 12 5.1. Applicability Statement . . . . . . . . . . . . . . . . . 13 5.2. CISEW Heuristics . . . . . . . . . . . . . . . . . . . . . 13 5.2.1. Description of the Payload Set . . . . . . . . . . . . 13 5.2.2. Algorithm: Determination of the Coding Intervals . . . 16 5.2.3. Algorithm: Determination of the Encoding Window Interval . . . . . . . . . . . . . . . . . . . . . . . 18 5.2.4. Algorithm: Processing . . . . . . . . . . . . . . . . 19 5.2.5. Algorithm: Management of the Payload Set Overflow . . 20 5.2.6. Algorithm: Decoding and Gauss Elimination . . . . . . 21 6. Security Considerations . . . . . . . . . . . . . . . . . . . 21 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 8. Informative References . . . . . . . . . . . . . . . . . . . . 21 Amdouni & Adjih Expires January 5, 2015 [Page 2] Internet-Draft CISEW July 2014 1. Introduction The goal of this document is to describe CISEW, a building block for network coding: Coding Interval-based Sliding Encoding Window. CISEW is an overhaul and replacement for the SEW module that was previously proposed for the network coding protocol DRAGONCAST [draft-adjih-dragoncast-00]. DRAGONCAST itself, is a protocol for broadcast in wireless networks with network coding and is best suited to multi-hop wireless networks. For applications where a single source sends a large volume of information to the entire network, this information will be split in several payloads, which will then be broadcast to the entire network through network coding. In DRAGONCAST, SEW is responsible for the encoding and decoding of the coded payloads. It is based on a sliding window that determines which payloads should be encoded. The objective is to allow a real- time decoding, instead of decoding a whole generation at once. CISEW keeps the same general philosophy and objectives as SEW. In addition, CISEW is more general: protocol aspects and policies are separated. Accordingly, the presentation of CISEW in this document is done in two parts: a general framework with rules, followed by proposals for policies. The proposed policies can also be well adapted to real-time applications: for instance CISEW handles losses (i.e. when a node unable to follow real-time decoding due to insufficient amount of received payloads). The signaling of CISEW is modified compared to the signaling of SEW. In particular, the nodes advertize more finely their state, and original payloads they have or need (wanted payloads, urgent payloads, etc). This allows CISEW to handle cases that were not taken into account in SEW. 2. Terminology Throughout this document, the terminology used is derived from the network coding taxonomy Internet-Draft [draft-firoiu-nwcrg-network-coding-taxonomy-01]. The following table summarizes the abbreviations used in this draft. Amdouni & Adjih Expires January 5, 2015 [Page 3] Internet-Draft CISEW July 2014 +--------------+----------------------------------------------------+ | Abbreviation | Definition | +--------------+----------------------------------------------------+ | CISEW | Coding Interval-based Sliding Encoding Window | | DRAGON | Dynamic Rate Adaptation from Gap with Other Nodes | | DRAGONCAST | Dynamic Rate Adaptation from Gap with Other Nodes | | | for broadCAST | | SEW | Sliding Encoding Window | +--------------+----------------------------------------------------+ Table 1 The following table summarizes the definitions and notations used in this draft. +----------------+--------------------------------------------------+ | Name | Definition | +----------------+--------------------------------------------------+ | index (of | the order number of this original payload | | original | | | payload) | | | indices | a sequence of contiguous original payload | | interval | indices | | unwanted index | an index of original payload unwanted by the | | | sender | | decoded index | index of original payload which was already | | | decoded | | undecoded | an index of undecoded payload | | index | | | urgent index | an index of undecoded payload that a node wants | | | to decode in near future | | Black interval | advertized interval of unwanted indices | | Grey interval | advertized interval of indices that the node is | | | not interested in, but would not harm decoding | | White interval | advertized interval of indices that the node is | | | interested in | | Gold interval | advertized interval of indices that the node is | | | interested in, in the near future | | MAX_GOLD | the maximum size of the Gold interval | | MAX_WHITE | the maximum size of the White interval | +----------------+--------------------------------------------------+ Table 2 Amdouni & Adjih Expires January 5, 2015 [Page 4] Internet-Draft CISEW July 2014 3. Context and Protocol Overview CISEW is designed as a redesign of the SEW module in the previously proposed network coding protocol DRAGONCAST ([CA08a], [CA08b], [C08]). 3.1. Context DRAGONCAST is a protocol for broadcasting a set of payloads from one source to the entire network with network coding. The protocol is distributed and requires minimal coordination between nodes to ensure real-time decoding (or online decoding as in [LU10] and [PT11]). The base functioning is simple: the broadcast is initiated by transmissions from the source. Every node in the network retransmits coded payloads with indices within a given window. This window may change and hence slides between transmissions. At the same time, every node collects received coded payloads and performs decoding as they are received. Finally, termination is automatically detected when all the nodes have successfully received and decoded all data. DRAGONCAST has several building blocks: o Signaling needed to run the protocol in a distributed way. o Local Information Base which contains information about the node itself, its neighbors, the flows and the decoding process. o Rate adaptation policy to adjust the rate of transmission of the payload at each node depending on the decoding level of its neighbors. o SEW (Sliding Encoding Window): a policy that consists in constraining the content of the generated payload using a sliding window in order to ensure a real-time decoding. Indeed, SEW relies on two rules: - SEW coding rule: The general idea of SEW is that it restricts the mixed original payloads with indices from a window of a fixed size. Specifically, the node generates a payload starting from the minimum index of the undecoded payloads of its neighbors. This allows a real-time decoding as nodes are not obliged to decode all the original coded payloads once. This window is sliding: an index disappears from any node window whenever all neighbors of this node decode the payload having this index. Amdouni & Adjih Expires January 5, 2015 [Page 5] Internet-Draft CISEW July 2014 - SEW decoding rule: decoding is done via a modified Gaussian elimination, where the pivot is the highest possible index of original payload (instead of lowest possible index in classical Gaussian elimination). The property the decoding process does not "add" higher indices when processing received coded payloads, and this helps re-using them when recoding (within a window). The Section 3.2, we will give an overview about CISEW and the difference between CISEW and SEW. 3.2. Overview about CISEW Like SEW, CISEW aims at providing a real-time decoding via cooperation between neighbors. Every node, when it sends (re-)coded payloads also piggybacks informations about its state, and specifically its decoding state (e.g. current matrix). CISEW enriches the signaling information used by SEW with additional information defined in this draft. CISEW processes received coded payload with the same decoding rules as SEW. The difference comes from CISEW state advertizement, which is much richer, and is based on describing intervals of original payload indices, as indicated in next section, Section 3.3. As for SEW, this summarized state of the node is piggybacked on the coded payloads (along with encoding vector), and at each packet receival, CISEW updates and maintains the information on its neighbors (it stores every indices interval on per node basis). Then, upon coded payload generation (re-coding), based on these intervals, the node determines the Encoding Window, that is the index interval of payloads it should encode. The intent of CISEW is to generate a coded payload that fits at best the requested intervals of these neighbors (with different possible policies for "at best"). Setting and processing the index intervals and determining the Encoding Window is a policy. Hence, CISEW design is general. Different policies are possible, and as a reference, we will specify some possible policies in Section 5. Compared to SEW, the benefits of CISEW are: 1. A finer adjustment of the coded payload to the decoding progress and the buffer state of neighboring nodes. 2. An enhancement of the decoding possibilities upong receiving each coded payload. Amdouni & Adjih Expires January 5, 2015 [Page 6] Internet-Draft CISEW July 2014 3. A management of the buffer overflow. 4. A more extensive handling of buffer state cases, allowing for instace, for dropping part of the decoding buffer when a node "falls behind". 5. CISEW design is general which makes it suitable to general applications. 3.3. Overview of CISEW Advertizement CISEW main improvement starts with a much richer advertizement of the state of the node. The starting point is, the exact state of one node in its decoding buffer (that is, the matrix of Gaussian elimination). It is characterized as follows; each original payload, corresponding to an index, is one of: o original payloads that were decoded, but are no longer available (i.e. old, discarded, original payloads), o original payloads that were decoded, and are still available, o original payloads that are not yet decoded, but are present in coded payloads in the buffer (some of them are "seen", i.e. correspond to a pivot), o original payloads that are not yet decoded, and are not in any received coded payload. CISEW invents the concept of Interval-based Coding, where the state of the node is concisely summarized by sets of intervals, with more precision than SEW (which only specifies the index of the first non- decoded payload). Indeed, each node indicates (to its neighbors) which indices it needs, which ones it needs urgently, which ones it does not need, etc. To do so, CISEW determines and advertizes four types of index intervals: o Black: advertized interval of unwanted indices; o Grey: advertized interval of indices that the node is not interested in, but would not harm decoding; o Gold: advertized interval of indices that the node is interested in, in the near future. Amdouni & Adjih Expires January 5, 2015 [Page 7] Internet-Draft CISEW July 2014 o White: advertized interval of indices that the node is interested in; Thus, for instance, the "black interval" would typically correspond to old decoded original payloads that were already discarded: they can no longer be used by the node to decode newly received coded payloads, hence should be avoided. Upon generation, the received, and stored, intervals of neighbors are taken into account. For instance, we can imagine that any node should not generate a payload with an index in the Black interval of all its neighbors, because this index is unwanted by all of them. However, it should try to mix payloads from the Gold interval of its neighbors. 4. CISEW Design and General Rules In this section, we describe the design features of CISEW. 4.1. Signaling CISEW uses the same type of local information base as defined in DRAGONCAST, specified in this document [draft-adjih-dragoncast-00], and which maintains the state of the neighbors. However, some additional information are updated or added, reflecting the richer state advertizement of CISEW: * The Neighbor Information Set consists of Neighbor Tuples. For a given flow and for a given coding block, each neighbor tuple 'Neighbor Tuple' contains: * N_min_black_index: the minimum index of payloads in Black interval of this neighbor. * N_max_black_index: the maximum index of payloads in Black interval of this neighbor. It corresponds also to the start index of the Grey interval-1. * N_min_grey_index: the minimum index of payloads in Grey interval of this neighbor. It corresponds also to the end index of the Black interval+1. * N_max_grey_index: the maximum index of Grey payloads of this neighbor. It corresponds also to the start index of the Gold interval-1. * N_min_gold_index: the minimum index of payloads in Gold interval of this neighbor. It corresponds also to the end Amdouni & Adjih Expires January 5, 2015 [Page 8] Internet-Draft CISEW July 2014 index of the Grey interval+1. * N_max_gold_index: the maximum index of Gold payloads of this neighbor. It corresponds also to the start index of the White interval-1. * N_min_white_index: the minimum index of payloads in White interval of this neighbor. It corresponds also to the end index of the Gold interval+1. * N_max_white_index: the maximum index of White payloads of this neighbor. It corresponds also to the end index of all payloads of this neighbor. Notice that it is possible that any neighbor has an empty Black, Grey, Gold or White interval. In this case, the minimum and maximum indices associated to this interval are set to -1. * Payload Information Base: For each coding block, a node maintains a Payload Information Base with the following content: * D_payload_set: a set of coded and decoded payloads. For each, the node maintains: + Coding vector + Coded payload content * D_min_black_index: the minimum index of Black interval of this node. * D_max_black_index: the maximum index of Black interval of this node. It corresponds to the start index of its Grey interval-1. * D_min_grey_index: the minimum index of Grey interval of this node. It corresponds to the end index of its Black Interval+1. * D_max_grey_index: the maximum index in Grey interval of this node. It corresponds to the start index of its Gold interval-1. * D_min_gold_index: the mimimum index of Gold interval of this node. It corresponds to the end index of its Grey interval+1. * D_max_gold_index: the maximum index of Gold interval of this node. It corresponds to the start index of its White interval-1. Amdouni & Adjih Expires January 5, 2015 [Page 9] Internet-Draft CISEW July 2014 * D_min_white_index: the minimum index in White Interval of this node. It corresponds to the end index of its Gold interval+1. * D_max_white_index: the maximum index in White Interval of this node. It corresponds to the end index of all payloads in the payload set of this node. Notice that it is possible that any node has an empty Black, Grey, Gold or White interval. In this case, the minimum and maximum indices associated to this interval are set to -1. 4.2. CISEW Components Figure 1 represents the organization of the different building blocks of CISEW. +----------------------------+ | | | Determination of | | the Encoding Window | | and the Coding Intervals | | | | | +-------------^--------------+ | Policy | ...............|........................ Protocol | v +----------------------------+ +-----------------------+ | | | | | Generation of Coded | | Processing and Real- | | Payload | | Time Decoding | | | | | +----------------------------+ +-----------------------+ Figure 1: CISEW Components Now, we detail these components. 4.2.1. Determination of the Encoding Window and the Coding Intervals This module is responsible for the determination of: 1. The encoding window: when any node attempts to generate a coded payload, this module starts by determining the index interval of the coded payload to be generated. Amdouni & Adjih Expires January 5, 2015 [Page 10] Internet-Draft CISEW July 2014 2. The coding intervals (Black, Grey, Gold and White intervals) that each node should advertize. This module is a policy for CISEW; hence CISEW rules can be applied to different policies. In Section 5.2 we propose sample heuristics for the implementation of this module. In practice, setting these intervals on a given node depends on: o The computing and the storage capacity of this node: as previously detailed, the intervals that the node advertizes indicate the indices it needs and the indices it does not need, etc. Hence, for instance, if the node advertizes a large Gold interval, it may receive a high number of undecoded indices that it should store and decode. Clearly, this is not suitable when the node has low computing and storage capacity. o The application requirements: as an example, we consider a real- time application and a code distribution application. A real-time application requires a real time decoding. Hence, nodes should evolve in parallel in their decoding. To ensure this, nodes should advertize coding intervals that are not too far apart. For instance, if a node notices that it is too late in the decoding process compared to all its neighbors (that is, its neighbors have already decoded many indices after its highest decoded index), it can increase its Gold interval even if it will never decode some payloads (and drop the older part of its decoding buffer). This prevents this node from delaying the global network. o In another type of application, such as code distribution (Over The Air reflashing of wireless sensor nodes), all original payloads must be decoded. Hence, any node should still request the same indices of its undecoded payloads even if its neighbors are much more progressed compared to it. 4.2.2. Generation of Payloads Each time the protocol DRAGONCAST requires a payload generation, it triggers CISEW that triggers itself this module. If for a given flow and coding block, no neighbor is known to require coded payloads (all neighbors have already decoded all original payloads), the payload is empty. Otherwise, a coded payload is generated. The CISEW procedure for generating a coded payload has the following rules: Amdouni & Adjih Expires January 5, 2015 [Page 11] Internet-Draft CISEW July 2014 1. The procedure has as an entry the encoding window interval determined by the previous component (see Section 4.2.1). 2. All decoded or undecoded payloads from D_payload_set having indices in the encoding window interval are mixed. Example: Consider a Decoding Information base containing the following payloads: q(1) = a(3) P(3) + a(5) P(5) q(2) = a(2) P(2) + a(6) P(6) q(3) = a(2) P(2) + a(3) P(3) Assume that the encoding window is the Interval [3, 6]. Hence, the node generates a random linear combination of payloads q(1) and q(2) but not q(3) since it includes the index 2. 4.2.3. Processing of Payloads Whenever a node receives an encoded payload, CISEW: 1. Stores the coded payload received in this message. This step implies the management of the Coding Information Base, in particular the overflow of the payload set. Indeed, if the node receives a coded payload while its coded payload set, D_payload_set, is full, it should manage the situation. Many solutions are possible. For instance, this node may ignore the received payload, replace an old decoded payload by this payload, or replace another coded payload by the received one, etc. The choice of the best strategy is a policy for CISEW. We propose one in Section 5.2. 2. If the received payload is not ignored, CISEW: 1. Updates its Information Base related to the associated flow and neighbor. 2. Performs real-time decoding via a Gauss elimination applied to coded paylods stored in its D_payload_set. 5. Specification of Proposed Policies and Algorithms for CISEW In this section, we propose specific policies, algorithms and heuristics for CISEW. We start by presenting one class of applications, deployment scenario, and associated assumptions, which inspired their design. Amdouni & Adjih Expires January 5, 2015 [Page 12] Internet-Draft CISEW July 2014 5.1. Applicability Statement One typical class of application and scenario for our proposed policies and algorithm would be a real-time diffusion of content on nodes with limited resources. A prime example is the real time code update over a wireless sensor network. Regarding CISEW design, this context implies some considerations: 1. With limited computing capacity (such as with wireless sensors), CISEW should keep low decoding complexity. In particular, nodes should not decode in a very large encoding window. 2. With limited memory (such as on sensor nodes), the decoding buffer will not hold the all decoded original payloads (and should drop them). We further assume that the DRAGONCAST protocol cannot use the secondary storage (e.g flash of sensors: this assumption holds because the flash access is time-consuming which is not preferable in a real time application). 3. In a real-time application, the source generates coded payloads regularly and intermediate nodes decode these payloads. As discussed above, to guarantee that the global network evolves in parallel, every node should maintain a good decoding progress. For illustration, we give an example. Imagine a network with a late starting node. Assume that its neighbors have decoded the 10 first original payloads sent by the source and that these payloads are no longer stored by these nodes. The late node would request these payloads from its neighbors. However, in this case, it is not worthy for these neighbors to try to redecode these payloads. Because this may delay the whole network by prohibiting these neighbors to transmit random linear combinations of new payloads. Furthermore, it would be preferable for the late node to catch up other nodes rather than decoding old payloads. All these considerations are taken into account to define heuristics for CISEW as proposed in Section 5.2. 5.2. CISEW Heuristics In this section, we will specify the CISEW algorithms. 5.2.1. Description of the Payload Set Before specifying the procedures of CISEW, let us describe the payload set at any node denoted i. Each node i has a payload set to store the decoded and undecoded Amdouni & Adjih Expires January 5, 2015 [Page 13] Internet-Draft CISEW July 2014 payloads. However, it may be possible that this node withdraw some payloads. This happens for instance in case of memory overflow, or when the node judges that some payloads are no longer useful. Hence, we assume that each node i stores an admissibility variable denoted a(i) that is defined as follows: o a(i) the minimum index of payloads that the node i stores and can process. Consequently, at any instant, all index payloads smaller than a(i) are ignored. Payloads with indices >= a(i) can be decoded, undecoded or unheard. The state of the payload set of any node i is described in Figure 2. h(i) s(i) u(i) e(i) +--------------------+---------------+---------------+ | unheard | decoded | | | (undecoded) | | | | | | | +----------------------------------------------------+ Figure 2: A buffer state of any node i. We use the following notations, o s(i): ("coded payload set Start") minimum index of all payloads (decoded and undecoded) in the coded payload set of node i. o h(i): ("minimum unHeard") minimum index of unheard payloads having indices strictly smaller than the payloads in the coded payload set. Assume for instance that the source broadcasts payloads from index 1, and the node has as payloads: a(2)P(2) + a(3)P(3) and a(4)P(4) + a(5)P(5). Then h(i) is equal to 1, since the index 1 does not appear in any linear combination at node i. If there are not unheard payloads with indices smaller than the present payloads, then h(i) is set to -1. o u(i): ("minimum Undecoded") minimum index of undecoded payloads in the coded payload set. o e(i): ("coded payload set End") maximum index of payloads in the coded payload set at node i. With these definitions, we have the following remarks: o If h(i) is != -1 then we have always h(i) < s(i) by definition. Amdouni & Adjih Expires January 5, 2015 [Page 14] Internet-Draft CISEW July 2014 o If h(i) is != -1 then the interval [h(i), s(i)] corresponds to unheard payloads (off course undecoded ones). o We have always s(i) <= u(i). o We can have s(i) = u(i) when the node i has not decoded any payload yet. o If s(i) < u(i), then the interval [s(i), u(i)] corresponds to decoded payloads. o The first index in the interval [u(i), e(i)] corresponds to a decoded payload, the following ones are either decoded or undecoded. To summarize, we can have one of the following schemas: Case 1: h(i) = -1 and s(i) = u(i) This case corresponds to the initial state of any node. Initially, nodes receive undecoded payloads, store them but they are generally not able to decode them immediately. Also, for large Galois fields, the probability to mix payloads with low indices before payloads with higher indices is high, hence, h(i)=-1. s(i)=u(i) e(i) +---------------+ | | +---------------+ Figure 3: Case 4 Case 2: h(i) =-1 This case corresponds to the scenario where the node i has started decoding some coded payloads. So, it is the normal case after a number of message exchanges. s(i) u(i) e(i) +---------------+---------------+ | | | +-------------------------------+ Figure 4: Case 2 Amdouni & Adjih Expires January 5, 2015 [Page 15] Internet-Draft CISEW July 2014 Case 3: s(i) = u(i) The scenario that corresponds to this case is when the node i has not decoded any payload yet, and it did not heard some indices smaller than the indices it has stored. This scenario may correspond to the initial case where high indices are coded before low ones or for a late node that missed initial payloads transmitted in the network. h(i) s(i)=u(i) e(i) +---------------+---------------+ | | | +-------------------------------+ Figure 5: Case 3 Case4: h(i) < s(i) < u(i) This case may correspond to a late node that missed some payloads. However, this node succeeds to decode payloads because its neighbors are more progressed than it. h(i) s(i) u(i) e(i) +--------------------+---------------+---------------+ | | | | +----------------------------------------------------+ Figure 6: Case 1 5.2.2. Algorithm: Determination of the Coding Intervals Consider any node i. The purpose of this algorithm is to determine the Coding Intervals that the node should advertize. The algorithm depends on the cases described in Section 5.2.1. 1. Case 1: 1. Black = [1,s(i)[. 2. Grey = empty. 3. Gold = [u(i), u(i)+MAX_GOLD]. 4. White = [u(i)+MAX_GOLD, u(i)+MAX_GOLD+MAX_WHITE]. 2. Case 2: Amdouni & Adjih Expires January 5, 2015 [Page 16] Internet-Draft CISEW July 2014 1. Black = [1,s(i)[. The node i has not the indices strictly smaller than s(i). Hence, all these indices are unwanted. Note that this interval starts from 1 because we assume that the source generates coded payloads starting from 1. 2. Grey = [s(i), u(i)]. This is because, all the payloads in [s(i), u(i)] are decoded. 3. Gold = [u(i), u(i)+MAX_GOLD]. 4. White = [u(i)+MAX_GOLD, u(i) + MAX_GOLD+MAX_WHITE]. 3. Case 3: 1. Black = empty. 2. Grey = empty. 3. Gold = [u(i), u(i)+MAX_GOLD]. MAX_GOLD is the maximum size of this interval. 4. White = [u(i)+MAX_GOLD, u(i)+MAX_GOLD+MAX_WHITE]. An arbitray choice of the maximum size of the White interval is set to MAX_WHITE. 4. Case 4: 1. Black = empty; this node needs all the payloads with indices starting from h(i). Hence, Black interval is empty. 2. Grey = [s(i), u(i)]. This is because, all the payloads in [s(i), u(i)] are decoded. Consequently, they are not useful for the node, but does not harm the decoding. Indeed, when a node receives a linear combination with decoded payloads, it will replace these payloads by their stored value. 3. Gold = [h(i), h(i)+MAX_GOLD]. First, the node i needs to receive linear combinations of payloads that it has not heard, that is in [h(i), s(i)]. Second, the undecoded payloads start at index u(i). Hence, the node needs to receive linear combinations starting at this index. Third, linear combinations in [s(i), u(i)] are not needed. However, for simplicity, we include them in the Gold interval. 4. White = [u(i)+MAX_GOLD, u(i)+MAX_GOLD+MAX_WHITE]. White payloads are useful in the future. Hence, the White interval starts at the end of the Gold interval. Amdouni & Adjih Expires January 5, 2015 [Page 17] Internet-Draft CISEW July 2014 5.2.3. Algorithm: Determination of the Encoding Window Interval When a sender node attempts to generate a coded payload, it needs to determine the encoding window for the payload it should generate. To do so, CISEW adopts the following general rules: 1. The selected encoding window should have a maximum size. Dealing with sensor networks, decoding has to keep a low complexity. Hence, the window size should not exceed a given threshold. Also, large encoding window increases the probability to include new payload indices in the coded payload generated. As a consequence, the least advanced node from decoding point of view (called latest node) would have new undecoded payloads instead of higher decoding opportunities. Let MAX_WINDOW_SIZE be the maximum size of the encoding window. 2. Given an encoding window, any node may fail to generate a coded payload within this window. This happens when all the payloads of this node include an index outside this window. In this case, the algorithm should adjust this window in order to avoid the generation of empty coded payload. The aim is to increase the number of neighbors whose rank is increased by receiving this payload. To determine the encoding window interval, any sender node proceeds as follows: Any node determines the encoding window based on the advertized coding intervals of its neighbors. Note that the coding intervals of these neighbors may be overlapped or completely disjoint. For the use case described above, our strategy is to take into account the advertized state of the latest neighbor, that is the neighbor with the smallest value of h(i) if h(i) != -1, or the smallest value of s(i) otherwise. We say that the encoding window is associated to this node. Note that given the coding intervals associated to the latest node, the sender node may fail to generate a coded payload. This happens when all coded and undecoded payloads at this sender node contain at least one index outside the coding intervals of its latest neighbor. In this case, the sender node proceeds in two steps: 1. The sender node increases the encoding window (as we will see hereafter) and tries again to generate a coded payload within this modified window. 2. If the node fails to generate a coded payload at the end of the first step, it considers the second latest node and try to Amdouni & Adjih Expires January 5, 2015 [Page 18] Internet-Draft CISEW July 2014 generate a coded payload associated to this node. If it fails again, it considers the third neighbor, etc. The node repeats this procedure while looping through the neighbors starting from the latest ones, until it generates a non empty payload. The detailed algorithm is as follows: 1. Initialisation: S is empty 2. WHILE there are non visited neighbors and S is empty DO 1. Let N be the latest node among non visited neighbors. 2. W = union of Gold and White intervals of N without exceeding MAX_WINDOW_SIZE; that is W=[N.N_min_gold_index, minimum(N.N_min_gold_index+MAX_WINDOW_SIZE, N.N_max_white_index)] 3. S = set of coded payloads with indices in W 4. If S is not empty, then return W 5. Otherwise, the coding intervals of N may be in one of the cases detailed in Section 5.2.2. Setting W depends on these cases as follows: 1. Case1: (Black|Gold|White) or Case 3: (Gold|White) - We cannot extend W in this case, so come back to the step 1 in the loop (select the next node N). 2. Case2: (Black|Grey|Gold|White) or Case4: (Grey|Gold| White) - Increase W to include the Grey interval of node N in addition to its Gold and White intervals, without exceeding MAX_WINDOW_SIZE; that is W = [N.N_min_grey_index, minimum(N.N_min_grey_index+ MAX_WINDOW_SIZE, N.N_max_white_index)]. - If S is still empty, then come back to the step 1 in the loop (select the next node N). 5.2.4. Algorithm: Processing Let P a received payload at any node i. To process this payload, i proceeds as follows: Amdouni & Adjih Expires January 5, 2015 [Page 19] Internet-Draft CISEW July 2014 o If P includes indices that are lower than a(i), then P is ignored. o If the payload set is not full then i stores P in its payload set and performs Gauss elimination. o If the buffer is full, then i should decide whether it should keep P or ignore it. Hence, i starts by evaluating whether the payload P may help it to decode other payloads in the near future or not. If it is the case, then P is kept. Furthermore, the node i should empty memory space and discard another payload to be able to store the payload P. The procedure of the management of the payload set is detailed in Section 5.2.5. If upon applying this procedure, the payload P is kept, then P is stored and Gauss elimination is performed. 5.2.5. Algorithm: Management of the Payload Set Overflow Before detailing the procedure for the management of the payload set overflow, we introduce the following notations relative to any payload. o min_index: the minimum index of this payload if it is undecoded. Otherwise, if this payload is decoded, then min_index is the index of this payload. o max_index: the maximum index of this payload if it is undecoded. Otherwise, if this payload is decoded, then max_index: the index of this payload. This procedure is called when any node i receives a payload P while its payload set is full. Hence the node i proceeds as follows: o If P is in the Grey or Gold Interval of node i, then P is useful. Hence, i should discard the oldest decoded payload and store P. o If P is in Gold and White Interval of node i, then: * If P is "rather Gold" (that is: |i.N_max_gold_index - min_index| >= |max_index - i.N_min_white_index|) then P is kept and the oldest decoded payload is ignored. * If P is "rather White" (that is: |i.N_max_gold_index - min_index| < |max_index - i.N_min_white_index|) then P is ignored. Amdouni & Adjih Expires January 5, 2015 [Page 20] Internet-Draft CISEW July 2014 5.2.6. Algorithm: Decoding and Gauss Elimination CISEW keeps the same decoging rule of SEW. Indeed, when decoding, CISEW performs a Gaussian elimination, in such a way that one coded payload is only used to eliminate the source payload with the highest possible index (i.e. the latest source payload). The intent of the CISEW decoding rule is to guarantee proper functioning of the Gaussian elimination. As an example, assume that node v has received payloads q(1) and q(2), for instance q(1) = P(1) + P(9) and q(2) = P(1) + P(2) + P(3). Then q(1) would be used to eliminate P(9) for newly incoming payloads (the highest possible index is 9), and q(2) would be used to eliminate P(3) from further incoming payloads. On the contrary, if the CISEW decoding rule was not applied and if q(1) were used to eliminate P(1), then it would be used to eliminate it in q(2), and would result into the computation of q(2) - q(1) = P(2) + P(3) - P(9); this quantity now requires elimination of P(9), an higher index than the initial one in q(2). In contrast, the CISEW decoding rule guarantees the following invariant: during the Gaussian elimination process, the highest index of every currently undecoded payload will always stay identical or decrease. 6. Security Considerations This document does not have any security considerations. 7. IANA Considerations This document does not have any IANA actions. 8. Informative References [draft-adjih-dragoncast-00] Adjih, C., "Broadcast With Network Coding: DRAGONCAST", draft- adjih-dragoncast-00 (work in progress), July 2013. [CA08a] Cho, S-Y. and C. Adjih, "Wireless Broadcast with Network Coding: Dynamic Rate Selection", Conference Amdouni & Adjih Expires January 5, 2015 [Page 21] Internet-Draft CISEW July 2014 MedHocNet 2008, June 2008. [CA08b] Cho, S-Y. and C. Adjih, "Wireless Broadcast with Network Coding: DRAGONCAST", Inria Research Report RR- 6569, July 2008. [C08] Cho, S-Y., "Efficient Information Dissemination in Wireless Multi-Hop Networks", Ecole Polytechnique PhD thesis, Sept 2008. [LU10] Lucani, D-E., Medard, M., and M. Stojanovic, "Online network coding for time-division duplexing", Globecom 2010 Conference, Dec 2010. [PT11] Tournoux, P-U., Lochin, E., Lacan, J., Bouabdallah, A., and V. Roca, "On- the-fly erasure coding for real-time video applications", Journal IEEE Transactions on Multimedia, Aug 2011. [draft-firoiu-nwcrg-network-coding-taxonomy-01] Firoiu, V., Adamson, B., Roca, V., Adjih, C., Bilbao, J., Fitzek, F., Masucci, A., and M. Montpetit, "Network Coding Taxonomy", dr Amdouni & Adjih Expires January 5, 2015 [Page 22] Internet-Draft CISEW July 2014 aft-firoiu-nwcrg- network-coding- taxonomy-01 (work in progress), March 2014. Authors' Addresses Ichrak Amdouni Inria Phone: +33-136-635-357 EMail: Ichrak.Amdouni@inria.fr Cedric Adjih Inria Phone: +33-136-635-215 EMail: Cedric.Adjih@inria.fr Amdouni & Adjih Expires January 5, 2015 [Page 23]