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

• Encoding Type and Parameters: in this version of the specification, the fields contains one of the constants ENCODING_GF_2, ENCODING_GF_4, ENCODING_GF_16 ENCODING_GF_256. 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.
• 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.
• 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 the concept of partitioning a flow into generations. In this version of the specification, each generation is considered as an independent "flow".

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

• 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:

• Flow Information Tuple
• F_flow_identifier: the identifier of the flow
• F_source_rate: the packet rate of the source
• F_generation_set: the Generation Information Set associated to the flow

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

• Generation Information Tuple
• G_generation_identifier: an integer (generations are numbered from 0)
• G_generation_size: number of coded packets in the generation
• G_encoding_window_size: the size of the sliding encoding window (for SEW)
• G_decoding: the Decoding Information Base associated to this generation
• G_neighbor_set: the Neighbor Information Set associated to this generation

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:

• Neighbor Tuple
• N_neighbor_address: address of the neighbor (heard) node
• N_neighbor_rank: the rank of the neighbor
• N_high_index: high index of the neighbor
• N_low_index: low index of the neighbor
• N_validity_time: the validity time of the tuple (after which it expires)

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

• D_coded_packet_set: a set of coded packets. For each, the node maintains:
  • 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 packets.

6. DRAGONCAST Protocol Functioning

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:

• It updates its Flow Information Base related to the associated flow. This includes rank and expiration time.
• It notifies SEW for real-time decoding. In turn, SEW will forward any decoded packets to the application.
• 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 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:

• D(v,t) denote the rank of a node v at time t
• N(v,t) denote the number of neighbors of one node
• 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:

• 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:

• if g(v,t) > 0 then: C(v,t) = A g(v,t) where A is some constant.
• 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:

• 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.
• 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 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) P(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 process.

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 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", Internet-Draft draft-baccelli-manet-multihop-communication-02, July 2013.
[CA08a]	Cho, S-Y.C. and C.A. Adjih, "Wireless Broadcast with Network Coding: Dynamic Rate Selection", Conference MedHocNet 2008, June 2008.
[CA08b]	Cho, S-Y.C. and C.A. Adjih, "Wireless Broadcast with Network Coding: DRAGONCAST", Inria Research Report RR-6569, July 2008.
[C08]	Cho, S-Y.C., "Efficient Information Dissemination in Wireless Multi-Hop Networks", Ecole Polytechnique PhD thesis, Sept 2008.
[HKMKE03]	Ho, T.H., Koetter, R.K., Medard, M.M., Karger, D.K. and M.E. Effros, "The Benefits of Coding over Routing in a Randomized Setting", International Symposium on Information Theory 2003, Jun 2003.
[CWJ03]	Chou, P.A.C., Wu, Y.W. and K.J. Jain, "Practical Network Coding", Forty-third Annual Allerton Conference on Communication, Control, and Computing 2003, Oct 2003.
[FWB06]	Fragouli, C.F., Widmer, J.W. and J.-Y. L. Le Boudec, "A Network Coding Approach to Energy Efficient Broadcasting", INFOCOM 2006, Apr 2006.
[SSMMB09]	Sundararajan, J.K.S., Shah, D.S., Medard, M.M., Mitzenmacher, M.M. and J.B. 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:

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 vector").

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. [CWJ03].

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 elimination.

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.

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