Internet DRAFT - draft-amdouni-nwcrg-cisew

draft-amdouni-nwcrg-cisew






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]