[Docs] [txt|pdf|xml|html] [Tracker] [Email] [Nits]

Versions: 00

Network Coding Research Group (NCWCRG)                          C. Adjih
Internet-Draft                                                     Inria
Intended status: Informational                                   SY. Cho
Expires: January 16, 2014                Samsung Electronics Co.,LTD.(*)
                                                             E. Baccelli
                                                           July 15, 2013

               Broadcast With Network Coding: DRAGONCAST


   This document describes a Network Coding (NC) based broadcast
   protocol suitable mainly for wireless networks, including mobile ad
   hoc networks (MANET).  It provides data dissemination from a single
   source, based on intra-flow network coding and for Internet Protocol
   (IP).  It is designed to minimize the assumptions over the working
   environment and thus may operates over dynamically evolving

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on January 16, 2014.

Copyright Notice

   Copyright (c) 2013 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

Adjih, et al.           Expires January 16, 2014                [Page 1]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   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  . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Protocol Overview  . . . . . . . . . . . . . . . . . . . . . .  5
     3.1.  General Functioning  . . . . . . . . . . . . . . . . . . .  6
     3.2.  Protocol Principles and Definitions  . . . . . . . . . . .  7
   4.  DRAS: DRAGONCAST Signaling . . . . . . . . . . . . . . . . . .  8
   5.  DRALIB: DRAGONCAST Local Information Base  . . . . . . . . . . 11
   6.  DRAGONCAST Protocol Functioning  . . . . . . . . . . . . . . . 13
     6.1.  Source Packet Generation . . . . . . . . . . . . . . . . . 14
     6.2.  Packet Processing  . . . . . . . . . . . . . . . . . . . . 14
     6.3.  Packet Generation  . . . . . . . . . . . . . . . . . . . . 14
   7.  DRAGON: Packet Rate Selection  . . . . . . . . . . . . . . . . 14
     7.1.  DRAGON Rationale . . . . . . . . . . . . . . . . . . . . . 14
     7.2.  DRAGON (Dynamic Rate Adaptation from Gap with Other
           Nodes) . . . . . . . . . . . . . . . . . . . . . . . . . . 15
   8.  Real-time Decoding: Sliding Encoding Window (SEW)  . . . . . . 16
   9.  Security Considerations  . . . . . . . . . . . . . . . . . . . 18
   10. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 18
   11. Informative References . . . . . . . . . . . . . . . . . . . . 18
   Appendix A.  Network Coding Fundamentals . . . . . . . . . . . . . 19
     A.1.  Linear Coding  . . . . . . . . . . . . . . . . . . . . . . 19
     A.2.  Random Linear Coding . . . . . . . . . . . . . . . . . . . 20
     A.3.  Decoding, Vector Space, and Rank . . . . . . . . . . . . . 20
   Appendix B.  Acknowledgements  . . . . . . . . . . . . . . . . . . 21

Adjih, et al.           Expires January 16, 2014                [Page 2]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

1.  Introduction

   The goal of this document is to describe a protocol for broadcast in
   wireless networks with network coding.

   It is best suited to multi-hop wireless networks.  Compared to wired
   networks, they have specific properties, see for instance
   [I-D.baccelli-multihop], including:

      - Wireless 'neighborcast': one wireless transmission by a node may
      reach several receivers.  This property may be used to optimize

      - Time-variation: the visibility between two nodes may evolves
      with time, due to node mobility, physical changes in the
      propagation environment or other reasons.

      - Unreliability of wireless communications: due to wireless
      channel conditions or properties, transmissions losses (packet
      erasures) potentially occur.

   In wireless networks, applications sometimes require the
   communication primitive of broadcasting information to the entire
   network.  As an example, in the context of MANETs, the Simplified
   Multicast Forwarding (SMF) [RFC6621] has been proposed for this

   For applications where a single source sends a large volume of
   information to the entire network, it will be split in several
   packets, which will then be broadcast to the entire network.  In this
   case, network coding can provide two features: natural error
   correction, and efficiency (in terms of the number of transmissions).
   A large literature on this topic has evidenced the benefits of
   network coding and explored design and implementation aspects.

   In this document, we present DRAGONCAST (D.R.A.G.O.N., "Dynamic Rate
   Adaptation from Gap with Other Nodes"), one such protocol for
   broadcasting with network coding.

   It is based on intra-flow coding.  It attempts to maximize simplicity
   and universality: it does not use explicitly or implicit knowledge
   relative to the topology (such as the direction or distance to the
   source, the loss rate of the links, ...), hence is perfectly suited
   to the most dynamic wireless networks.

Adjih, et al.           Expires January 16, 2014                [Page 3]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

2.  Terminology

   | Abbreviation | Definition                                        |
   | MANET        | Mobile Ad Hoc Network                             |
   | NHDP         | Neighborhood Discovery Protocol                   |
   | OLSR         | Optimized Link State Routing                      |
   | SMF          | Simplified Multicast Forwarding                   |
   | TLV          | Type-Length-Value encoding                        |
   | DRAGON       | Dynamic Rate Adaptation from Gap with Other Nodes |
   | SEW          | Sliding Encoding Window                           |
   | PME          | Protocol Message Element                          |
   | F-PME        | Flow Protocol Message Element                     |
   | S-PME        | State Protocol Message Element                    |
   | ED-PME       | Encoded Data Protocol Message Element             |

                                  Table 1

   The following table summarizes the definitions and notations related
   to network coding in general and to DRAGONCAST.  More details on
   network coding can be found in Appendix A.

   | Name           | Definition                                       |
   | Coded Packet   | Linear combination of source packets             |
   | Encoding       | Coefficients in the linear combination of source |
   | Vector         | packets                                          |
   | Vector         | abbrev. for "Information Vector", coded packet   |
   | Innovative     | A coded packet that brings new information       |

                                  Table 2

   | Name                        | Notation                            |
   | Source packets              | P(1), ..., P(k)                     |
   | Linear combination of       | a(1) P(1) + ... + a(k) P(k)         |
   | packets                     |                                     |
   | Set of coded packets at a   | q(v,i) = a(v,i,1) P(1) + ... +      |
   | node v                      | a(v,i,M) P(M)                       |

                                  Table 3

Adjih, et al.           Expires January 16, 2014                [Page 4]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

3.  Protocol Overview

   DRAGONCAST is a protocol for broadcasting a set of packets from one
   source to a entire network with network coding (various parts are
   described in [CA08a], [CA08b], [C08]).  The protocol is distributed
   and requires minimal coordination.

   The base functioning is simple: the broadcast is initiated by
   transmissions for the source.  Every node in the network retransmits
   coded packets with a changing interval between transmissions.  At the
   same time, every node collects received coded packets, and performs
   decoding as they are received.  Finally, termination is automatically
   detected when all the nodes have successfully received all data.

   DRAGONCAST is based on several building blocks that are in two
   categories.  The first category concerns the protocol aspects

   o  DRAS (DRAgoncast Signaling): the signaling for the control plane
      for DRAGONCAST.  The signaling is mostly present on a header to
      each coded packet (e.g piggybacking).  It includes with
      information relative to the state of the node, in addition to the
      packet encoding information.  This allows each node to maintains
      information about the state of its neighbors.

   o  DRALIB (DRAgoncast Local Information Base): this information base
      maintains information about the flows, the decoding process, and
      the state of the neighbors

   o  DRAGONCAST: the protocol itself with message generation and
      message processing

   The second category is relative to policy, that is building blocks
   that define high level protocol behavior:

   o  DRAGON: a dynamic packet rate adjustment policy.  Every node is
      retransmitting coded packets with a certain packet rate; this rate
      is adjusted dynamically.  Essentially, the rate of the node
      increases if it detects some nodes in the current neighborhood are
      "falling behind" in the decoding process.  This is called a
      "dimension gap", and the proposed adaptation algorithm is a
      Dynamic Rate Adjustment from Gap with Other Nodes (DRAGON), a

   o  SEW: a real-time decoding method denoted SEW (Sliding Encoding
      Window).  It does not requires the concept of generation; instead,
      the knowledge of the state of neighbors is used to constrain the
      content of generated coded packets and allow real-time decoding.

Adjih, et al.           Expires January 16, 2014                [Page 5]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

      SEW maintains a buffer of the currently undecoded packets.

   The Figure 1 represents the organization of the different building

                                                  Application (source)
     +---------------------------+    +---------------------------+
     |                           |    |                           |
     |         DRAGON            |    |           SEW             |
     |                           |    |                           |
     |   Packet Rate Selection   |    |    Packet Encoding and    |
     |                           |    | Real-time Packet Decoding |
     +---------------------------+ +->|                           |
                  ^                |  +---------------------------+
   Policy         |         +------+               ^
   Protocol       V         v                      v
     +---------------------------+    +---------------------------+
     |                           |    |                           |
     |        DRAGONCAST         |    |          DRALIB           |
     |                           +<--->                           |
     |         Protocol          |    |   Local Information Base  |
     |                           |    |                           |
     +---------------------------+    +---------------------------+
                  |                      .............................
                  v                      .          Operating System
     +--------------+------------+       .
     |                           |       .     +--------------+
     |          DRAS             |       .     |              |
     |                           +<----------->+   IP Stack   |
     |       Signaling           |       .     |              |
     |                           |       .     +--------------+
     +---------------------------+       .

         Figure 1: Organization of the DRAGONCAST Building Blocks

3.1.  General Functioning

   The source initiates broadcasting by sending its original data
   packets with a format specified in Section 4.

   When the source sends data packets, it produces packets of a
   predefined, constant size, using padding if necessary.  Other nodes
   initiate transmission of encoded data upon receiving the first coded
   packet, and stay in a transmission state where they will retransmit

Adjih, et al.           Expires January 16, 2014                [Page 6]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   coded packets with an interval decided by packet rate selection
   algorithms.  Precisely, when intermediate nodes receive a data packet
   that is a source packet or a coded packet, they start scheduling
   encoded data transmission.

   The scheduling interval is decided by the policy DRAGON from
   Section 7.  Transmitted packets by intermediate nodes are coded
   packets generated using random linear coding with a header specified
   in Section 4.  Data transmission continues until nodes detect the
   termination condition, i.e. that themselves and all their neighbors
   have successfully decoded the data stream.

   General operations of the protocol are described in the following

   1.  Source data transmission scheduling: the source transmits
       sequentially D vectors (packets) of a generation with rate C

   2.  Nodes' data transmission start condition: the nodes start
       transmitting a vector when they receive the first vector.

   3.  Nodes' data storing condition: the nodes store a received vector
       in their local buffer only if the received vector has new and
       different information from the vectors that the nodes already

   4.  Nodes' termination conditions: the nodes continue transmitting
       until themselves and their current known neighbors in their local
       information base have enough vectors to recover the D source

   5.  Nodes' data transmission scheduling: every node retransmits
       linear combinations of the vectors in its local buffer after
       waiting for a delay computed from the rate selection.

   6.  Nodes' data transmission restart condition: When one node
       receives a notification indicating that one neighboring node
       requires more vectors to recover the D source packets and it has
       already stopped data transmission, the node re-enters in a
       transmission state.

3.2.  Protocol Principles and Definitions

   DRAGONCAST uses the following concepts and definitions:

   o  Source: a source is a node that will broadcast information to the
      network.  This information is called a "flow".  A source may have
      an arbitrary number of flows, however each flow will be coded

Adjih, et al.           Expires January 16, 2014                [Page 7]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

      independently (intra-flow coding).

   o  Flow: a flow is the unit of transmission of the protocol
      DRAGONCAST.  The flow represents a sequence of bytes at the source
      that need to be broadcast.  The source divides the flow in a
      sequence of packets of equal size (padding may be used).  The
      packets are numbered, and can be identified by their packet index.
      The packets of one flow may optionally divided in several
      generations (one per default).

   o  Generation: a generation is a subset of a consecutive packets of
      one flow.

4.  DRAS: DRAGONCAST Signaling

   DRAGONCAST uses one single packet format based on a sequence of Type-
   Value including several protocol elements.  The general packet format
   is represented in Figure 2.

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     |          Packet size          |                               |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
     |                                                               |
     |               Protocol Message Element (PME)                  |
     |                                               +-+-+-+-+-+-+-+-+
     |                                               |               |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+               |
     |                                                               |
     :                              ...                              :
     |                                                               |
     |                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                               |                               |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               |
     |                                                               |
     |               Protocol Message Element (PME)                  |
     |                                               +-+-+-+-+-+-+-+-+
     |                                               |

                                 Figure 2

   The following protocol elements are defined:

   o  The Flow Protocol Message Element (F-PME), Figure 3: it specifies
      information identifying the flow and associated (constant)

Adjih, et al.           Expires January 16, 2014                [Page 8]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   o  The State Protocol Message Element (S-PME), Figure 4: it specifies
      information relative to the state of the sender with respect to
      the decoding process.

   o  The Encoded Data Protocol Message Element (ED-PME), Figure 5: it
      specifies parameters of the encoding, along with the coding vector
      and include the coded packet data.

   They are used as the basis for DRAGONCAST Packets.  Control
   information is sent in-band, prepended to encoded packets.  In the
   normal flow of the protocol, the majority of transmitted packets are
   "Data Packets".  In the current version of the specification, the
   packet MUST respect exactly one of the following formats:

   o  A regular data packet (with coded content): it MUST include the
      three following elements, in this order exactly: F-PME, S-PME, ED-

   o  A termination control packet (e.g. without coded content): it MUST
      first include the two following elements, in this order exactly:
      F-PME, S-PME.

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     | Type: FLOW                    |                               |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
     |                     Flow Identifier (64 bits)                 |
     |                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                               |     Generation Identifier     |
     |      Source Packet Rate       | Generation Number of Packets  |
     | Sliding Encoding Window Size  |

                     Figure 3: Format of the Flow PME

   The Flow PME includes the following fields:

   o  Flow Identifier (Flow-ID): an identifier of size 8 bytes for the
      flow.  Its semantics is opaque to DRAGONCAST.

   o  Generation Identifier: DRAGONCAST includes support for splitting a
      flow (with a given Flow-ID), which allows flows with more than
      65535 packets, and also allows to optionally operate with

Adjih, et al.           Expires January 16, 2014                [Page 9]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   o  Source Packet Rate: expressed as the average inter-departure of
      the coded packets in milliseconds (e.g. "10 packets per second"
      yields the value 100).

   o  Generation Number of Packets: total number of packets in the
      Generation with the given Generation ID.

   o  Sliding Encoding Window Size: the size of the encoding window,
      when generating coded packets.

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     | Type: STATE                   |      Rank of Transmitter      |
     |           Lifetime            |     Number of Neighbors       |
     |          High Index           |          Low Index            |
     |                                                               |
     |                     Transmitter Address                       |
     |                                                               |

                     Figure 4: Format of the State PME

   The State PME specifies state information of transmitter with respect
   to the generation identified by a preceding F-PME and includes:

   o  Rank of Transmitter: denotes the current amount of innovative data
      of the transmitter for the generation.

   o  Lifetime: denotes duration during which the information in this
      packet (that is, the rank and the fact that transmitter is a
      neighbor of a node receiving this packet) is considered valid
      (after this it will expire).

   o  Number of neighbors: denotes the number of neighbors heard, that
      are not yet expired.

   o  High Index: specifies the highest index present in a undecoded
      linear combination in the decoding table.

   o  Low Index: specifies the lowest index present in a undecoded
      linear combination in the decoding table.  Hence all source
      packets with lower indices have been decoded.

Adjih, et al.           Expires January 16, 2014               [Page 10]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   o  Transmitter Address: the IP address of the transmitter of the

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     |Type: ENCODED_DATA             | Encoding Type and Parameters  |
     |   Encoding Vector Data Size   |     Coded Packet Data Size    |
     | Encoding Vector Index Offset  |                               |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               |
     |                     Encoding Vector Data                      |
     :                              ...                              :
     |                       Coded Packet Data                       |
     :                              ...                              :

                 Figure 5: Format of the Encoded Data PME

   The Encoded Data PME holds actual coded packet content:

   o  Encoding Type and Parameters: in this version of the
      specification, the fields contains one of the constants
      This represents the fact that the fields GF(2), GF(4), GF(16), or
      GF(256) respectively are used as basis for the linear combination.
      As a result, the coefficients are respectively coded on 1, 2, 4 or
      8 bits.

   o  Encoding Vector Data Size: the size of the information
      representing the encoding vector, in bytes.  As indicated above,
      one byte will hold an integral number of vector coefficients.

   o  Coded Packet Data Size: the size of data packets.

   Constants: ENCODING_GF_2 = 0 ENCODING_GF_4 = 1 ENCODING_GF_16 = 2
   ENCODING_GF_256 = 3

5.  DRALIB: DRAGONCAST Local Information Base

   A node maintains a Local Information Base that records information
   about its decoding process, and the state of the neighbors.

   The protocol state is maintained per flow: a flow is uniquely
   identified by a flow identifier.  In addition, DRAGONCAST supports

Adjih, et al.           Expires January 16, 2014               [Page 11]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   the concept of partitioning a flow into generations.  In this version
   of the specification, each generation is considered as an independent

   The different information bases of DRALIB are structured
   hierarchically as follows:

   o  Flow Information Set. Each flow is independently associated a Flow
      Information Tuple, which contains one or several generations.
      Their state is maintained in a:

      *  Generation Information Set. Each generation contains the state
         of the neighbors with respect to the propagation and the
         decoding of the generation, stored in a:

         +  Neighbor Information Set, describing the neighbors.  Such
            information may also be provided by another protocol, such
            as OLSR [RFC3626] or NHDP [RFC6130]

         In addition, for decoding purposes, it includes the:

         +  Decoding Information Base

   Each node maintains a Flow Information Set, which contains collected
   information about current flows.  Specifically, the Flow Information
   Set consists of Flow Information Tuples each which records:

   o  Flow Information Tuple

   o  F_flow_identifier: the identifier of the flow

   o  F_source_rate: the packet rate of the source

   o  F_generation_set: the Generation Information Set associated to the

   Each node maintains, for each of its Flow Information Tuple, a
   Generation Information Set, which contains information specific to a

   o  Generation Information Tuple

   o  G_generation_identifier: an integer (generations are numbered from

   o  G_generation_size: number of coded packets in the generation

Adjih, et al.           Expires January 16, 2014               [Page 12]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   o  G_encoding_window_size: the size of the sliding encoding window
      (for SEW)

   o  G_decoding: the Decoding Information Base associated to this

   o  G_neighbor_set: the Neighbor Information Set associated to this

   For each generation, a node maintains a Neighbor Information Set,
   which contains its known neighbors (with an expiration time), and
   information related to their state.

   Specifically, the Neighbor Information Set consists of Neighbor
   Tuples, each of which contain information about a single neighbor,
   for a given flow and for a given generation, as follows:

   o  Neighbor Tuple

   o  N_neighbor_address: address of the neighbor (heard) node

   o  N_neighbor_rank: the rank of the neighbor

   o  N_high_index: high index of the neighbor

   o  N_low_index: low index of the neighbor

   o  N_validity_time: the validity time of the tuple (after which it

   For each generation, a node maintains a Decoding Information Base
   with the following content:

   o  D_coded_packet_set: a set of coded packets.  For each, the node

      *  Encoding vector

      *  Coded packet content

   During the decoding process, the decoding module (SEW) performs real-
   time decoding by performing Gaussian elimination on the list of coded

6.  DRAGONCAST Protocol Functioning

Adjih, et al.           Expires January 16, 2014               [Page 13]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

6.1.  Source Packet Generation

   A node that acts as a data source for a flow, also runs a instance of
   the DRAGONCAST protocol for that flow (e.g. has a Flow Tuple with all
   associated information).

   In addition, it adds periodically source packets in the associated
   Flow Information Base respecting the source rate.

6.2.  Packet Processing

   Whenever a node receives an encoded packet:

   o  It updates its Flow Information Base related to the associated
      flow.  This includes rank and expiration time.

   o  It notifies SEW for real-time decoding.  In turn, SEW will forward
      any decoded packets to the application.

   o  It notifies DRAGON which may update the transmission packet rate
      of the flow.

6.3.  Packet Generation

   For every "active" flow in its Flow Information Base, a node will
   generate coded packets, with an interval between packets defined by
   DRAGON (from the computed packet rate).

   If for a given flow and generation, in the associated neighbor set,
   no neighbor is known to require coded packets, the packet is
   generated without encoded packet (without Encoded Data PME).

   From information in its Local Information Base, every node is able to
   determines if it needs to sends packets, as described in [C08].

7.  DRAGON: Packet Rate Selection

   In this section, we describe one packet rate selection algorithms,
   proposed for DRAGONCAST.

7.1.  DRAGON Rationale

   The heuristic DRAGON has been proposed and analyzed in [CA08a], and
   is inspired by Fragouli et al.  [FWB06].  We briefly summarize it in
   this section for completeness.  The starting point of our heuristic
   DRAGON, is that the observation that, for real-time decoding, the
   rank of nodes inside the network should be close to the index of the
   last source packet, and that in any case, they should at least evolve

Adjih, et al.           Expires January 16, 2014               [Page 14]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   in parallel.

   Thus, one would expect the rank of a node to grow at the same pace as
   the source transmission, as in the example of optimal rate selections
   for static networks.  Decreasing the rates of intermediate nodes by a
   too large factor, would not permit the proper propagation of source
   packets in real time.  On the contrary, increasing excessively their
   rates, would not increase the rate of the decoded packets (naturally
   bounded by the source rate) while it would decrease energy-efficiency
   (by increasing the amount of redundant transmissions).

   The idea of the proposed rate selection is to find a balance between
   these two inefficient states.  As we have seen, ideally the rank of a
   node would be comparable to the lastly sent source packet.  Since we
   wish to have a simple decentralized algorithm, instead of comparing
   with the source, we compare indirectly the rank of a node with the
   rank of all its perceived neighbors.

   The key idea is to perform a control so that the rank of neighbor
   nodes would tend to be equalized: if a node detects that one neighbor
   had a rank which is too low in comparison with its own, it would tend
   to increase its rate.  Conversely, if all its neighbors have greater
   ranks than itself, the node need not to send packets in fact.

7.2.  DRAGON (Dynamic Rate Adaptation from Gap with Other Nodes)

   In this section, we describe the proposed heuristic, DRAGON, as a
   packet rate selection.  It is based on the following definitions.
   Precisely, let:

   o  D(v,t) denote the rank of a node v at time t

   o  N(v,t) denote the number of neighbors of one node

   o  g(v,t) denote the maximum gap of rank with its neighbors,
      normalized by the number of neighbors

   Then g(v,t) is evaluated as:

   o  g(v,t) = maximum, for all neighbors u, of { (D(v,t) - D(u,t)) /
      N(u,t) }

   We propose the following rate selection, DRAGON (Dynamic Rate
   Adaptation from Gap with Other Nodes), which adjusts the rates
   dynamically, based on that gap of rank between one node and its
   neighbors as follows: The packet rate of node v is set to C(v,t) at
   time t as:

Adjih, et al.           Expires January 16, 2014               [Page 15]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   o  if g(v,t) > 0 then: C(v,t) = A g(v,t) where A is some constant.

   o  Otherwise, the node stops sending encoded packets until g(v,t)
      becomes larger than 0.

   When computing the packet rate selection, DRAGONCAST Local
   Information Base supplies the information necessary: for each
   neighbor, the rank and the number of neighbors of the last packet
   received, are maintained in the Neighbor Set. Although they might not
   necessarily reflect the exact values at the computation time, they
   are provide an estimate.

8.  Real-time Decoding: Sliding Encoding Window (SEW)

   In this section, we describe the method of DRAGONCAST for real-time
   decoding, which allows recovery of some source packets without
   requiring to decode all source packets at once.  It is related to the
   method from Sundararajan et al.  [SSMMB09] described for TCP.

   The real-time decoding method, Sliding Encoding Window (SEW) relies
   on implicit cooperation between neighbor nodes, in order to ensure
   the possibility of decoding.  (Technically, as described in [CA08a],
   it ensures the existence of a low triangle in global encoding vectors
   saved in a node during the online Gauss elimination process).

   The key of SEW, is to ensure the existence of an early decoding part;
   to do so, every node in DRAGONCAST keeps track of the state of its
   neighbors, in order to only send packets, The method SEW relies on
   two principles:

   o  SEW coding rule: generates only coded packets that are linear
      combinations of the first L source packets, where L is a quantity
      that increases with time.

   o  SEW decoding rule: when decoding, performs a Gaussian elimination,
      in such a way that one coded packet is only used to eliminate the
      source packet with the highest possible index (i.e. the latest
      source packet).

   Before detailing the insights behind these rules, we first give
   definition: the high index of a node, and the low index of a node.
   As explained in Appendix A, a coded packet is a linear combination of
   source packets.  We define the highest and lowest index of a linear
   combination, as the minimum and maximum of the coded packets
   respectively.  For instance, a packet Q = P(3) + P(5) + P(7) + P(8),
   the highest index is 8 and the lowest index is 3.

   Because all encoded packets have their own highest index and lowest

Adjih, et al.           Expires January 16, 2014               [Page 16]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   index, we can also compute the maximum of the highest index of all
   not-yet decoded packets in a node, as well as the minimum of the
   lowest index.  We refer to the maximum and the minimum as high index
   of a node and low index of a node.  Notice that a node will generally
   have decoded the source packets from 1 up to its low index.

   The intent of the SEW coding rule is to use knowledge about the state
   of neighbors of one node, namely their high and low index.  A node
   restricts the generated packets to a subset of the packets of the
   source, until it is confirmed that perceived neighbors of the node
   are able to decode nearly all of them, up to a margin K. Notice that
   once all its neighbors may decode up to the first L-K packets, it is
   unnecessary for the node to include packets P(1), ...  P(L) in its
   generated combinations.

   Hence, the general idea of SEW is that it restricts the mixed
   original packets within an encoded packet from a window of a fixed
   size K. In other words, a node encodes only source packets inside a
   fixed Encoding Window as:

      i-th generated packet q(v,i) = a(v,i,k) P(k) + .... + a(v,i,k_K)

   where the { P(j) } is the set of packets generated by the source, The
   sequence of coefficients for q(v,i) is the following global encoding
   vector: [ 0, 0, ..., a(v,i,k), a(v,i,k+1), ..., a(v,i,k+K), ...,0,0].
   A node will repeat transmissions of new random combinations within
   the same window, until its neighbors have progressed in the decoding

   The intent of the SEW decoding rule, is to guarantee proper
   functioning of the Gaussian elimination.  An example of SEW decoding
   rule is the following: assume that node v has received packets 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
   packets (the highest possible index is 9), and q(2) would be used to
   eliminate P(3) from further incoming packets.  On the contrary, if
   the SEW 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 SEW decoding rule
   guarantees the following invariant: during the Gaussian elimination
   process, the highest index of every currently non-decoded packet will
   always stay identical or decrease.

   Provided that neighbor state is properly exchanged and known, as a
   result, the combination of the SEW coding rule and the SEW decoding

Adjih, et al.           Expires January 16, 2014               [Page 17]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   rule, guarantee that ultimately every node will be able to decode the
   packets in the window starting from its lowest index; that is, they
   guarantee early decoding.

   Notice that improper knowledge of neighbor state might impact the
   performance of the method but not its correctness: if a previously
   unknown neighbor is detected (for instance due to mobility), the
   receiving node will properly adjust its sending window.  Conversely,
   in DRAGONCAST, obsolete neighbor information, for instance about
   disappeared neighbors, will ultimately expire.

9.  Security Considerations

   This document does not have any security considerations.

10.  IANA Considerations

   This document does not have any IANA actions.

11.  Informative References

   [RFC3626]                Clausen, T. and P. Jacquet, "Optimized Link
                            State Routing Protocol (OLSR)", RFC 3626,
                            October 2003.

   [RFC6130]                Clausen, T., Dearlove, C., and J. Dean,
                            "Mobile Ad Hoc Network (MANET) Neighborhood
                            Discovery Protocol (NHDP)", RFC 6130,
                            April 2011.

   [RFC6621]                Macker, J., "Simplified Multicast
                            Forwarding", RFC 6621, May 2012.

   [I-D.baccelli-multihop]  Baccelli, E. and C. Perkins, "Multi-hop Ad
                            Hoc Wireless Communication", draft-baccelli-
                            manet-multihop-communication-02 (work in
                            progress), July 2013.

   [CA08a]                  Cho, S-Y. and C. Adjih, "Wireless Broadcast
                            with Network Coding: Dynamic Rate
                            Selection", Conference  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

Adjih, et al.           Expires January 16, 2014               [Page 18]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

                            Dissemination in Wireless Multi-Hop
                            Networks", Ecole Polytechnique PhD thesis,
                            Sept 2008.

   [HKMKE03]                Ho, T., Koetter, R., Medard, M., Karger, D.,
                            and M. Effros, "The Benefits of Coding over
                            Routing in a Randomized Setting",
                            International Symposium on Information
                            Theory 2003, Jun 2003.

   [CWJ03]                  Chou, P., Wu, Y., and K. Jain, "Practical
                            Network Coding", Forty-third Annual Allerton
                            Conference on Communication, Control, and
                            Computing 2003, Oct 2003.

   [FWB06]                  Fragouli, C., Widmer, J., and J. Le Boudec,
                            "A Network Coding Approach to Energy
                            Efficient Broadcasting", INFOCOM 2006,
                            Apr 2006.

   [SSMMB09]                Sundararajan, J., Shah, D., Medard, M.,
                            Mitzenmacher, M., and J. Barros, "Network
                            Coding Meets TCP", INFOCOM 2009, Apr 2009.

Appendix A.  Network Coding Fundamentals

   This section introduces network coding concepts and terminology.

   Network coding differs from classical routing by permitting coding at
   intermediate nodes.  One possible coding algorithm is linear coding
   that performs only linear transformations through addition and
   multiplication Precisely, linear coding assumes identically sized
   packets and views the packets as vectors on a fixed Galois field.  It
   becomes then possible to perform linear combination of packets.

A.1.  Linear Coding

   In the case of single source broadcast, all packets initially
   originate from one source: the source has k packets, which may be
   seen equivalently as k vectors P(1), ..., P(k) from the vector space
   over a Galois Field.

   With network coding, any coded packet received by node, at any point
   of time, is a linear combination of some source packets.  The i-th
   received coded packet at a node v is necessarily a linear combination
   of the source packets P(1), ....  P(k) and can be written as:

Adjih, et al.           Expires January 16, 2014               [Page 19]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

      q(v,i) = a(v,i,1) P(1) + ... + a(v,i,k) P(k)

   The sequence of coefficients for a coded packet q(v,i) (denoted
   "information vector", or simply "vector") is itself a vector
   [a(v,i,1), a(v,i,2), ..., a(v,i,n)] (denoted "global encoding

   With linear coding, when one node generates a coded packet, it
   performs a linear combination of the packets that it possesses (the
   set of received packets { q(v,i) }) with some set of coefficients
   (g(1), ...., g(M)).  It then transmits the result:

      generated_coded_packet = g(1) q(v,1) + ... + g(M) q(v,M).

   Since the vectors q(v,1), ... q(v,M) are in turn linear combinations
   of the source packets P(1),...  P(k), the generated coded packet, can
   be expressed itself as a linear combination of these, yielding its
   global encoding vector.

   In practice, a special header containing the global coding vector of
   the transmitted code packet may be added as proposed by Chou et al.

A.2.  Random Linear Coding

   As shown above, when a node generates a coded packet with linear
   coding, an issue is how to select coefficients.  Whereas centralized
   deterministic methods exist, Ho and al.  [HKMKE03] presented a novel
   coding algorithm, which does not require any central coordination.
   The coding algorithm is random linear coding: when a node transmits a
   packet, it selects randomly the set of coefficients { g(i) }, which
   will be used to perform a linear combination of the vectors q(v,M) as
   indicated above.

A.3.  Decoding, Vector Space, and Rank

   A node v will recover the source packets P(1), ...  P(k) its the
   received packets q(v,1), ... q(v,M), considering the matrix of
   coefficients a(v,i,j) for i=1,...M and j=1,..k from Appendix A.
   Decoding amounts to inverting this matrix, for instance with Gaussian

   Thinking in terms of coding vectors, at any point of time, it is
   possible to associate with one node v, the vector space, Q(v) spawned
   by the coding vectors, and which is identified with the matrix.  The
   dimension of that vector space, denoted D(v), is also the rank of the
   matrix.  In the rest of this document, by abuse of language, we will
   call "rank of a node", that rank and dimension.

Adjih, et al.           Expires January 16, 2014               [Page 20]

Internet-Draft  Broadcast With Network Coding: DRAGONCAST      July 2013

   The rank of a node is a direct metric for the amount of useful
   received packets, and a received packet is called innovative when it
   increases the rank of the receiving node.  Ultimately a node can
   decode all source packets when its rank is equal to the the total
   number of source packets.

Appendix B.  Acknowledgements

   This document also stems from contributions of and from discussions
   with : Philippe Jacquet.

Authors' Addresses

   Cedric Adjih

   Phone: +33-136-635-215
   EMail: Cedric.Adjih@inria.fr

   Songyean Cho
   Samsung Electronics Co.,LTD.(*)
   (*) Author(Songyean Cho)'s contribution was done before
   joining Samsung Electronics.

   EMail: Songyean.Cho@gmail.com

   Emmanuel Baccelli

   Phone: +33-169-335-511
   EMail: Emmanuel.Baccelli@inria.fr
   URI:   http://www.emmanuelbaccelli.org/

Adjih, et al.           Expires January 16, 2014               [Page 21]

Html markup produced by rfcmarkup 1.124, available from https://tools.ietf.org/tools/rfcmarkup/