idnits 2.17.1 draft-adjih-dragoncast-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 381: '... packet MUST respect exactly one of ...' RFC 2119 keyword, line 383: '...th coded content): it MUST include the...' RFC 2119 keyword, line 387: '... (e.g. without coded content): it MUST...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 15, 2013) is 3930 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-04) exists of draft-baccelli-manet-multihop-communication-02 Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Coding Research Group (NCWCRG) C. Adjih 3 Internet-Draft Inria 4 Intended status: Informational SY. Cho 5 Expires: January 16, 2014 Samsung Electronics Co.,LTD.(*) 6 E. Baccelli 7 Inria 8 July 15, 2013 10 Broadcast With Network Coding: DRAGONCAST 11 draft-adjih-dragoncast-00 13 Abstract 15 This document describes a Network Coding (NC) based broadcast 16 protocol suitable mainly for wireless networks, including mobile ad 17 hoc networks (MANET). It provides data dissemination from a single 18 source, based on intra-flow network coding and for Internet Protocol 19 (IP). It is designed to minimize the assumptions over the working 20 environment and thus may operates over dynamically evolving 21 environments. 23 Status of This Memo 25 This Internet-Draft is submitted in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Internet-Drafts are working documents of the Internet Engineering 29 Task Force (IETF). Note that other groups may also distribute 30 working documents as Internet-Drafts. The list of current Internet- 31 Drafts is at http://datatracker.ietf.org/drafts/current/. 33 Internet-Drafts are draft documents valid for a maximum of six months 34 and may be updated, replaced, or obsoleted by other documents at any 35 time. It is inappropriate to use Internet-Drafts as reference 36 material or to cite them other than as "work in progress." 38 This Internet-Draft will expire on January 16, 2014. 40 Copyright Notice 42 Copyright (c) 2013 IETF Trust and the persons identified as the 43 document authors. All rights reserved. 45 This document is subject to BCP 78 and the IETF Trust's Legal 46 Provisions Relating to IETF Documents 47 (http://trustee.ietf.org/license-info) in effect on the date of 48 publication of this document. Please review these documents 49 carefully, as they describe your rights and restrictions with respect 50 to this document. Code Components extracted from this document must 51 include Simplified BSD License text as described in Section 4.e of 52 the Trust Legal Provisions and are provided without warranty as 53 described in the Simplified BSD License. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 5 60 3.1. General Functioning . . . . . . . . . . . . . . . . . . . 6 61 3.2. Protocol Principles and Definitions . . . . . . . . . . . 7 62 4. DRAS: DRAGONCAST Signaling . . . . . . . . . . . . . . . . . . 8 63 5. DRALIB: DRAGONCAST Local Information Base . . . . . . . . . . 11 64 6. DRAGONCAST Protocol Functioning . . . . . . . . . . . . . . . 13 65 6.1. Source Packet Generation . . . . . . . . . . . . . . . . . 14 66 6.2. Packet Processing . . . . . . . . . . . . . . . . . . . . 14 67 6.3. Packet Generation . . . . . . . . . . . . . . . . . . . . 14 68 7. DRAGON: Packet Rate Selection . . . . . . . . . . . . . . . . 14 69 7.1. DRAGON Rationale . . . . . . . . . . . . . . . . . . . . . 14 70 7.2. DRAGON (Dynamic Rate Adaptation from Gap with Other 71 Nodes) . . . . . . . . . . . . . . . . . . . . . . . . . . 15 72 8. Real-time Decoding: Sliding Encoding Window (SEW) . . . . . . 16 73 9. Security Considerations . . . . . . . . . . . . . . . . . . . 18 74 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 75 11. Informative References . . . . . . . . . . . . . . . . . . . . 18 76 Appendix A. Network Coding Fundamentals . . . . . . . . . . . . . 19 77 A.1. Linear Coding . . . . . . . . . . . . . . . . . . . . . . 19 78 A.2. Random Linear Coding . . . . . . . . . . . . . . . . . . . 20 79 A.3. Decoding, Vector Space, and Rank . . . . . . . . . . . . . 20 80 Appendix B. Acknowledgements . . . . . . . . . . . . . . . . . . 21 82 1. Introduction 84 The goal of this document is to describe a protocol for broadcast in 85 wireless networks with network coding. 87 It is best suited to multi-hop wireless networks. Compared to wired 88 networks, they have specific properties, see for instance 89 [I-D.baccelli-multihop], including: 91 - Wireless 'neighborcast': one wireless transmission by a node may 92 reach several receivers. This property may be used to optimize 93 broadcast. 95 - Time-variation: the visibility between two nodes may evolves 96 with time, due to node mobility, physical changes in the 97 propagation environment or other reasons. 99 - Unreliability of wireless communications: due to wireless 100 channel conditions or properties, transmissions losses (packet 101 erasures) potentially occur. 103 In wireless networks, applications sometimes require the 104 communication primitive of broadcasting information to the entire 105 network. As an example, in the context of MANETs, the Simplified 106 Multicast Forwarding (SMF) [RFC6621] has been proposed for this 107 purpose. 109 For applications where a single source sends a large volume of 110 information to the entire network, it will be split in several 111 packets, which will then be broadcast to the entire network. In this 112 case, network coding can provide two features: natural error 113 correction, and efficiency (in terms of the number of transmissions). 114 A large literature on this topic has evidenced the benefits of 115 network coding and explored design and implementation aspects. 117 In this document, we present DRAGONCAST (D.R.A.G.O.N., "Dynamic Rate 118 Adaptation from Gap with Other Nodes"), one such protocol for 119 broadcasting with network coding. 121 It is based on intra-flow coding. It attempts to maximize simplicity 122 and universality: it does not use explicitly or implicit knowledge 123 relative to the topology (such as the direction or distance to the 124 source, the loss rate of the links, ...), hence is perfectly suited 125 to the most dynamic wireless networks. 127 2. Terminology 129 +--------------+---------------------------------------------------+ 130 | Abbreviation | Definition | 131 +--------------+---------------------------------------------------+ 132 | MANET | Mobile Ad Hoc Network | 133 | NHDP | Neighborhood Discovery Protocol | 134 | OLSR | Optimized Link State Routing | 135 | SMF | Simplified Multicast Forwarding | 136 | TLV | Type-Length-Value encoding | 137 | DRAGON | Dynamic Rate Adaptation from Gap with Other Nodes | 138 | SEW | Sliding Encoding Window | 139 | PME | Protocol Message Element | 140 | F-PME | Flow Protocol Message Element | 141 | S-PME | State Protocol Message Element | 142 | ED-PME | Encoded Data Protocol Message Element | 143 +--------------+---------------------------------------------------+ 145 Table 1 147 The following table summarizes the definitions and notations related 148 to network coding in general and to DRAGONCAST. More details on 149 network coding can be found in Appendix A. 151 +----------------+--------------------------------------------------+ 152 | Name | Definition | 153 +----------------+--------------------------------------------------+ 154 | Coded Packet | Linear combination of source packets | 155 | Encoding | Coefficients in the linear combination of source | 156 | Vector | packets | 157 | Vector | abbrev. for "Information Vector", coded packet | 158 | Innovative | A coded packet that brings new information | 159 +----------------+--------------------------------------------------+ 161 Table 2 163 +-----------------------------+-------------------------------------+ 164 | Name | Notation | 165 +-----------------------------+-------------------------------------+ 166 | Source packets | P(1), ..., P(k) | 167 | Linear combination of | a(1) P(1) + ... + a(k) P(k) | 168 | packets | | 169 | Set of coded packets at a | q(v,i) = a(v,i,1) P(1) + ... + | 170 | node v | a(v,i,M) P(M) | 171 +-----------------------------+-------------------------------------+ 173 Table 3 175 3. Protocol Overview 177 DRAGONCAST is a protocol for broadcasting a set of packets from one 178 source to a entire network with network coding (various parts are 179 described in [CA08a], [CA08b], [C08]). The protocol is distributed 180 and requires minimal coordination. 182 The base functioning is simple: the broadcast is initiated by 183 transmissions for the source. Every node in the network retransmits 184 coded packets with a changing interval between transmissions. At the 185 same time, every node collects received coded packets, and performs 186 decoding as they are received. Finally, termination is automatically 187 detected when all the nodes have successfully received all data. 189 DRAGONCAST is based on several building blocks that are in two 190 categories. The first category concerns the protocol aspects 191 themselves: 193 o DRAS (DRAgoncast Signaling): the signaling for the control plane 194 for DRAGONCAST. The signaling is mostly present on a header to 195 each coded packet (e.g piggybacking). It includes with 196 information relative to the state of the node, in addition to the 197 packet encoding information. This allows each node to maintains 198 information about the state of its neighbors. 200 o DRALIB (DRAgoncast Local Information Base): this information base 201 maintains information about the flows, the decoding process, and 202 the state of the neighbors 204 o DRAGONCAST: the protocol itself with message generation and 205 message processing 207 The second category is relative to policy, that is building blocks 208 that define high level protocol behavior: 210 o DRAGON: a dynamic packet rate adjustment policy. Every node is 211 retransmitting coded packets with a certain packet rate; this rate 212 is adjusted dynamically. Essentially, the rate of the node 213 increases if it detects some nodes in the current neighborhood are 214 "falling behind" in the decoding process. This is called a 215 "dimension gap", and the proposed adaptation algorithm is a 216 Dynamic Rate Adjustment from Gap with Other Nodes (DRAGON), a 217 heuristic. 219 o SEW: a real-time decoding method denoted SEW (Sliding Encoding 220 Window). It does not requires the concept of generation; instead, 221 the knowledge of the state of neighbors is used to constrain the 222 content of generated coded packets and allow real-time decoding. 224 SEW maintains a buffer of the currently undecoded packets. 226 The Figure 1 represents the organization of the different building 227 blocks. 229 Application (source) 230 ................................................^.................. 231 V 232 +---------------------------+ +---------------------------+ 233 | | | | 234 | DRAGON | | SEW | 235 | | | | 236 | Packet Rate Selection | | Packet Encoding and | 237 | | | Real-time Packet Decoding | 238 +---------------------------+ +->| | 239 ^ | +---------------------------+ 240 Policy | +------+ ^ 241 ...............|.........|......................|.................. 242 Protocol V v v 243 +---------------------------+ +---------------------------+ 244 | | | | 245 | DRAGONCAST | | DRALIB | 246 | +<---> | 247 | Protocol | | Local Information Base | 248 | | | | 249 +---------------------------+ +---------------------------+ 250 ^ 251 | ............................. 252 v . Operating System 253 +--------------+------------+ . 254 | | . +--------------+ 255 | DRAS | . | | 256 | +<----------->+ IP Stack | 257 | Signaling | . | | 258 | | . +--------------+ 259 +---------------------------+ . 261 Figure 1: Organization of the DRAGONCAST Building Blocks 263 3.1. General Functioning 265 The source initiates broadcasting by sending its original data 266 packets with a format specified in Section 4. 268 When the source sends data packets, it produces packets of a 269 predefined, constant size, using padding if necessary. Other nodes 270 initiate transmission of encoded data upon receiving the first coded 271 packet, and stay in a transmission state where they will retransmit 272 coded packets with an interval decided by packet rate selection 273 algorithms. Precisely, when intermediate nodes receive a data packet 274 that is a source packet or a coded packet, they start scheduling 275 encoded data transmission. 277 The scheduling interval is decided by the policy DRAGON from 278 Section 7. Transmitted packets by intermediate nodes are coded 279 packets generated using random linear coding with a header specified 280 in Section 4. Data transmission continues until nodes detect the 281 termination condition, i.e. that themselves and all their neighbors 282 have successfully decoded the data stream. 284 General operations of the protocol are described in the following 285 algorithm: 287 1. Source data transmission scheduling: the source transmits 288 sequentially D vectors (packets) of a generation with rate C 290 2. Nodes' data transmission start condition: the nodes start 291 transmitting a vector when they receive the first vector. 293 3. Nodes' data storing condition: the nodes store a received vector 294 in their local buffer only if the received vector has new and 295 different information from the vectors that the nodes already 296 have. 298 4. Nodes' termination conditions: the nodes continue transmitting 299 until themselves and their current known neighbors in their local 300 information base have enough vectors to recover the D source 301 packets. 303 5. Nodes' data transmission scheduling: every node retransmits 304 linear combinations of the vectors in its local buffer after 305 waiting for a delay computed from the rate selection. 307 6. Nodes' data transmission restart condition: When one node 308 receives a notification indicating that one neighboring node 309 requires more vectors to recover the D source packets and it has 310 already stopped data transmission, the node re-enters in a 311 transmission state. 313 3.2. Protocol Principles and Definitions 315 DRAGONCAST uses the following concepts and definitions: 317 o Source: a source is a node that will broadcast information to the 318 network. This information is called a "flow". A source may have 319 an arbitrary number of flows, however each flow will be coded 320 independently (intra-flow coding). 322 o Flow: a flow is the unit of transmission of the protocol 323 DRAGONCAST. The flow represents a sequence of bytes at the source 324 that need to be broadcast. The source divides the flow in a 325 sequence of packets of equal size (padding may be used). The 326 packets are numbered, and can be identified by their packet index. 327 The packets of one flow may optionally divided in several 328 generations (one per default). 330 o Generation: a generation is a subset of a consecutive packets of 331 one flow. 333 4. DRAS: DRAGONCAST Signaling 335 DRAGONCAST uses one single packet format based on a sequence of Type- 336 Value including several protocol elements. The general packet format 337 is represented in Figure 2. 339 0 1 2 3 340 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 341 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 342 | Packet size | | 343 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 344 | | 345 | Protocol Message Element (PME) | 346 | +-+-+-+-+-+-+-+-+ 347 | | | 348 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 349 | | 350 : ... : 351 | | 352 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 353 | | | 354 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 355 | | 356 | Protocol Message Element (PME) | 357 | +-+-+-+-+-+-+-+-+ 358 | | 359 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 361 Figure 2 363 The following protocol elements are defined: 365 o The Flow Protocol Message Element (F-PME), Figure 3: it specifies 366 information identifying the flow and associated (constant) 367 parameters. 369 o The State Protocol Message Element (S-PME), Figure 4: it specifies 370 information relative to the state of the sender with respect to 371 the decoding process. 373 o The Encoded Data Protocol Message Element (ED-PME), Figure 5: it 374 specifies parameters of the encoding, along with the coding vector 375 and include the coded packet data. 377 They are used as the basis for DRAGONCAST Packets. Control 378 information is sent in-band, prepended to encoded packets. In the 379 normal flow of the protocol, the majority of transmitted packets are 380 "Data Packets". In the current version of the specification, the 381 packet MUST respect exactly one of the following formats: 383 o A regular data packet (with coded content): it MUST include the 384 three following elements, in this order exactly: F-PME, S-PME, ED- 385 PME 387 o A termination control packet (e.g. without coded content): it MUST 388 first include the two following elements, in this order exactly: 389 F-PME, S-PME. 391 0 1 2 3 392 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 393 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 394 | Type: FLOW | | 395 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 396 | Flow Identifier (64 bits) | 397 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 398 | | Generation Identifier | 399 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 400 | Source Packet Rate | Generation Number of Packets | 401 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 402 | Sliding Encoding Window Size | 403 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 405 Figure 3: Format of the Flow PME 407 The Flow PME includes the following fields: 409 o Flow Identifier (Flow-ID): an identifier of size 8 bytes for the 410 flow. Its semantics is opaque to DRAGONCAST. 412 o Generation Identifier: DRAGONCAST includes support for splitting a 413 flow (with a given Flow-ID), which allows flows with more than 414 65535 packets, and also allows to optionally operate with 415 generations. 417 o Source Packet Rate: expressed as the average inter-departure of 418 the coded packets in milliseconds (e.g. "10 packets per second" 419 yields the value 100). 421 o Generation Number of Packets: total number of packets in the 422 Generation with the given Generation ID. 424 o Sliding Encoding Window Size: the size of the encoding window, 425 when generating coded packets. 427 0 1 2 3 428 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 429 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 430 | Type: STATE | Rank of Transmitter | 431 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 432 | Lifetime | Number of Neighbors | 433 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 434 | High Index | Low Index | 435 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 436 | | 437 | Transmitter Address | 438 | | 439 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 441 Figure 4: Format of the State PME 443 The State PME specifies state information of transmitter with respect 444 to the generation identified by a preceding F-PME and includes: 446 o Rank of Transmitter: denotes the current amount of innovative data 447 of the transmitter for the generation. 449 o Lifetime: denotes duration during which the information in this 450 packet (that is, the rank and the fact that transmitter is a 451 neighbor of a node receiving this packet) is considered valid 452 (after this it will expire). 454 o Number of neighbors: denotes the number of neighbors heard, that 455 are not yet expired. 457 o High Index: specifies the highest index present in a undecoded 458 linear combination in the decoding table. 460 o Low Index: specifies the lowest index present in a undecoded 461 linear combination in the decoding table. Hence all source 462 packets with lower indices have been decoded. 464 o Transmitter Address: the IP address of the transmitter of the 465 message. 467 0 1 2 3 468 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 469 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 470 |Type: ENCODED_DATA | Encoding Type and Parameters | 471 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 472 | Encoding Vector Data Size | Coded Packet Data Size | 473 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 474 | Encoding Vector Index Offset | | 475 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 476 | Encoding Vector Data | 477 : ... : 478 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 479 | Coded Packet Data | 480 : ... : 481 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 483 Figure 5: Format of the Encoded Data PME 485 The Encoded Data PME holds actual coded packet content: 487 o Encoding Type and Parameters: in this version of the 488 specification, the fields contains one of the constants 489 ENCODING_GF_2, ENCODING_GF_4, ENCODING_GF_16 ENCODING_GF_256. 490 This represents the fact that the fields GF(2), GF(4), GF(16), or 491 GF(256) respectively are used as basis for the linear combination. 492 As a result, the coefficients are respectively coded on 1, 2, 4 or 493 8 bits. 495 o Encoding Vector Data Size: the size of the information 496 representing the encoding vector, in bytes. As indicated above, 497 one byte will hold an integral number of vector coefficients. 499 o Coded Packet Data Size: the size of data packets. 501 Constants: ENCODING_GF_2 = 0 ENCODING_GF_4 = 1 ENCODING_GF_16 = 2 502 ENCODING_GF_256 = 3 504 5. DRALIB: DRAGONCAST Local Information Base 506 A node maintains a Local Information Base that records information 507 about its decoding process, and the state of the neighbors. 509 The protocol state is maintained per flow: a flow is uniquely 510 identified by a flow identifier. In addition, DRAGONCAST supports 511 the concept of partitioning a flow into generations. In this version 512 of the specification, each generation is considered as an independent 513 "flow". 515 The different information bases of DRALIB are structured 516 hierarchically as follows: 518 o Flow Information Set. Each flow is independently associated a Flow 519 Information Tuple, which contains one or several generations. 520 Their state is maintained in a: 522 * Generation Information Set. Each generation contains the state 523 of the neighbors with respect to the propagation and the 524 decoding of the generation, stored in a: 526 + Neighbor Information Set, describing the neighbors. Such 527 information may also be provided by another protocol, such 528 as OLSR [RFC3626] or NHDP [RFC6130] 530 In addition, for decoding purposes, it includes the: 532 + Decoding Information Base 534 Each node maintains a Flow Information Set, which contains collected 535 information about current flows. Specifically, the Flow Information 536 Set consists of Flow Information Tuples each which records: 538 o Flow Information Tuple 540 o F_flow_identifier: the identifier of the flow 542 o F_source_rate: the packet rate of the source 544 o F_generation_set: the Generation Information Set associated to the 545 flow 547 Each node maintains, for each of its Flow Information Tuple, a 548 Generation Information Set, which contains information specific to a 549 generation: 551 o Generation Information Tuple 553 o G_generation_identifier: an integer (generations are numbered from 554 0) 556 o G_generation_size: number of coded packets in the generation 557 o G_encoding_window_size: the size of the sliding encoding window 558 (for SEW) 560 o G_decoding: the Decoding Information Base associated to this 561 generation 563 o G_neighbor_set: the Neighbor Information Set associated to this 564 generation 566 For each generation, a node maintains a Neighbor Information Set, 567 which contains its known neighbors (with an expiration time), and 568 information related to their state. 570 Specifically, the Neighbor Information Set consists of Neighbor 571 Tuples, each of which contain information about a single neighbor, 572 for a given flow and for a given generation, as follows: 574 o Neighbor Tuple 576 o N_neighbor_address: address of the neighbor (heard) node 578 o N_neighbor_rank: the rank of the neighbor 580 o N_high_index: high index of the neighbor 582 o N_low_index: low index of the neighbor 584 o N_validity_time: the validity time of the tuple (after which it 585 expires) 587 For each generation, a node maintains a Decoding Information Base 588 with the following content: 590 o D_coded_packet_set: a set of coded packets. For each, the node 591 maintains: 593 * Encoding vector 595 * Coded packet content 597 During the decoding process, the decoding module (SEW) performs real- 598 time decoding by performing Gaussian elimination on the list of coded 599 packets. 601 6. DRAGONCAST Protocol Functioning 602 6.1. Source Packet Generation 604 A node that acts as a data source for a flow, also runs a instance of 605 the DRAGONCAST protocol for that flow (e.g. has a Flow Tuple with all 606 associated information). 608 In addition, it adds periodically source packets in the associated 609 Flow Information Base respecting the source rate. 611 6.2. Packet Processing 613 Whenever a node receives an encoded packet: 615 o It updates its Flow Information Base related to the associated 616 flow. This includes rank and expiration time. 618 o It notifies SEW for real-time decoding. In turn, SEW will forward 619 any decoded packets to the application. 621 o It notifies DRAGON which may update the transmission packet rate 622 of the flow. 624 6.3. Packet Generation 626 For every "active" flow in its Flow Information Base, a node will 627 generate coded packets, with an interval between packets defined by 628 DRAGON (from the computed packet rate). 630 If for a given flow and generation, in the associated neighbor set, 631 no neighbor is known to require coded packets, the packet is 632 generated without encoded packet (without Encoded Data PME). 634 From information in its Local Information Base, every node is able to 635 determines if it needs to sends packets, as described in [C08]. 637 7. DRAGON: Packet Rate Selection 639 In this section, we describe one packet rate selection algorithms, 640 proposed for DRAGONCAST. 642 7.1. DRAGON Rationale 644 The heuristic DRAGON has been proposed and analyzed in [CA08a], and 645 is inspired by Fragouli et al. [FWB06]. We briefly summarize it in 646 this section for completeness. The starting point of our heuristic 647 DRAGON, is that the observation that, for real-time decoding, the 648 rank of nodes inside the network should be close to the index of the 649 last source packet, and that in any case, they should at least evolve 650 in parallel. 652 Thus, one would expect the rank of a node to grow at the same pace as 653 the source transmission, as in the example of optimal rate selections 654 for static networks. Decreasing the rates of intermediate nodes by a 655 too large factor, would not permit the proper propagation of source 656 packets in real time. On the contrary, increasing excessively their 657 rates, would not increase the rate of the decoded packets (naturally 658 bounded by the source rate) while it would decrease energy-efficiency 659 (by increasing the amount of redundant transmissions). 661 The idea of the proposed rate selection is to find a balance between 662 these two inefficient states. As we have seen, ideally the rank of a 663 node would be comparable to the lastly sent source packet. Since we 664 wish to have a simple decentralized algorithm, instead of comparing 665 with the source, we compare indirectly the rank of a node with the 666 rank of all its perceived neighbors. 668 The key idea is to perform a control so that the rank of neighbor 669 nodes would tend to be equalized: if a node detects that one neighbor 670 had a rank which is too low in comparison with its own, it would tend 671 to increase its rate. Conversely, if all its neighbors have greater 672 ranks than itself, the node need not to send packets in fact. 674 7.2. DRAGON (Dynamic Rate Adaptation from Gap with Other Nodes) 676 In this section, we describe the proposed heuristic, DRAGON, as a 677 packet rate selection. It is based on the following definitions. 678 Precisely, let: 680 o D(v,t) denote the rank of a node v at time t 682 o N(v,t) denote the number of neighbors of one node 684 o g(v,t) denote the maximum gap of rank with its neighbors, 685 normalized by the number of neighbors 687 Then g(v,t) is evaluated as: 689 o g(v,t) = maximum, for all neighbors u, of { (D(v,t) - D(u,t)) / 690 N(u,t) } 692 We propose the following rate selection, DRAGON (Dynamic Rate 693 Adaptation from Gap with Other Nodes), which adjusts the rates 694 dynamically, based on that gap of rank between one node and its 695 neighbors as follows: The packet rate of node v is set to C(v,t) at 696 time t as: 698 o if g(v,t) > 0 then: C(v,t) = A g(v,t) where A is some constant. 700 o Otherwise, the node stops sending encoded packets until g(v,t) 701 becomes larger than 0. 703 When computing the packet rate selection, DRAGONCAST Local 704 Information Base supplies the information necessary: for each 705 neighbor, the rank and the number of neighbors of the last packet 706 received, are maintained in the Neighbor Set. Although they might not 707 necessarily reflect the exact values at the computation time, they 708 are provide an estimate. 710 8. Real-time Decoding: Sliding Encoding Window (SEW) 712 In this section, we describe the method of DRAGONCAST for real-time 713 decoding, which allows recovery of some source packets without 714 requiring to decode all source packets at once. It is related to the 715 method from Sundararajan et al. [SSMMB09] described for TCP. 717 The real-time decoding method, Sliding Encoding Window (SEW) relies 718 on implicit cooperation between neighbor nodes, in order to ensure 719 the possibility of decoding. (Technically, as described in [CA08a], 720 it ensures the existence of a low triangle in global encoding vectors 721 saved in a node during the online Gauss elimination process). 723 The key of SEW, is to ensure the existence of an early decoding part; 724 to do so, every node in DRAGONCAST keeps track of the state of its 725 neighbors, in order to only send packets, The method SEW relies on 726 two principles: 728 o SEW coding rule: generates only coded packets that are linear 729 combinations of the first L source packets, where L is a quantity 730 that increases with time. 732 o SEW decoding rule: when decoding, performs a Gaussian elimination, 733 in such a way that one coded packet is only used to eliminate the 734 source packet with the highest possible index (i.e. the latest 735 source packet). 737 Before detailing the insights behind these rules, we first give 738 definition: the high index of a node, and the low index of a node. 739 As explained in Appendix A, a coded packet is a linear combination of 740 source packets. We define the highest and lowest index of a linear 741 combination, as the minimum and maximum of the coded packets 742 respectively. For instance, a packet Q = P(3) + P(5) + P(7) + P(8), 743 the highest index is 8 and the lowest index is 3. 745 Because all encoded packets have their own highest index and lowest 746 index, we can also compute the maximum of the highest index of all 747 not-yet decoded packets in a node, as well as the minimum of the 748 lowest index. We refer to the maximum and the minimum as high index 749 of a node and low index of a node. Notice that a node will generally 750 have decoded the source packets from 1 up to its low index. 752 The intent of the SEW coding rule is to use knowledge about the state 753 of neighbors of one node, namely their high and low index. A node 754 restricts the generated packets to a subset of the packets of the 755 source, until it is confirmed that perceived neighbors of the node 756 are able to decode nearly all of them, up to a margin K. Notice that 757 once all its neighbors may decode up to the first L-K packets, it is 758 unnecessary for the node to include packets P(1), ... P(L) in its 759 generated combinations. 761 Hence, the general idea of SEW is that it restricts the mixed 762 original packets within an encoded packet from a window of a fixed 763 size K. In other words, a node encodes only source packets inside a 764 fixed Encoding Window as: 766 i-th generated packet q(v,i) = a(v,i,k) P(k) + .... + a(v,i,k_K) 767 P(k+K) 769 where the { P(j) } is the set of packets generated by the source, The 770 sequence of coefficients for q(v,i) is the following global encoding 771 vector: [ 0, 0, ..., a(v,i,k), a(v,i,k+1), ..., a(v,i,k+K), ...,0,0]. 772 A node will repeat transmissions of new random combinations within 773 the same window, until its neighbors have progressed in the decoding 774 process. 776 The intent of the SEW decoding rule, is to guarantee proper 777 functioning of the Gaussian elimination. An example of SEW decoding 778 rule is the following: assume that node v has received packets q(1) 779 and q(2), for instance q(1) = P(1) + P(9) and q(2) = P(1) + P(2) + 780 P(3). Then q(1) would be used to eliminate P(9) for newly incoming 781 packets (the highest possible index is 9), and q(2) would be used to 782 eliminate P(3) from further incoming packets. On the contrary, if 783 the SEW decoding rule was not applied and if q(1) were used to 784 eliminate P(1), then it would be used to eliminate it in q(2), and 785 would result into the computation of q(2) - q(1) = P(2) + P(3) - 786 P(9); this quantity now requires elimination of P(9), an higher index 787 than the initial one in q(2). In contrast the SEW decoding rule 788 guarantees the following invariant: during the Gaussian elimination 789 process, the highest index of every currently non-decoded packet will 790 always stay identical or decrease. 792 Provided that neighbor state is properly exchanged and known, as a 793 result, the combination of the SEW coding rule and the SEW decoding 794 rule, guarantee that ultimately every node will be able to decode the 795 packets in the window starting from its lowest index; that is, they 796 guarantee early decoding. 798 Notice that improper knowledge of neighbor state might impact the 799 performance of the method but not its correctness: if a previously 800 unknown neighbor is detected (for instance due to mobility), the 801 receiving node will properly adjust its sending window. Conversely, 802 in DRAGONCAST, obsolete neighbor information, for instance about 803 disappeared neighbors, will ultimately expire. 805 9. Security Considerations 807 This document does not have any security considerations. 809 10. IANA Considerations 811 This document does not have any IANA actions. 813 11. Informative References 815 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link 816 State Routing Protocol (OLSR)", RFC 3626, 817 October 2003. 819 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, 820 "Mobile Ad Hoc Network (MANET) Neighborhood 821 Discovery Protocol (NHDP)", RFC 6130, 822 April 2011. 824 [RFC6621] Macker, J., "Simplified Multicast 825 Forwarding", RFC 6621, May 2012. 827 [I-D.baccelli-multihop] Baccelli, E. and C. Perkins, "Multi-hop Ad 828 Hoc Wireless Communication", draft-baccelli- 829 manet-multihop-communication-02 (work in 830 progress), July 2013. 832 [CA08a] Cho, S-Y. and C. Adjih, "Wireless Broadcast 833 with Network Coding: Dynamic Rate 834 Selection", Conference MedHocNet 2008, 835 June 2008. 837 [CA08b] Cho, S-Y. and C. Adjih, "Wireless Broadcast 838 with Network Coding: DRAGONCAST", Inria 839 Research Report RR-6569, July 2008. 841 [C08] Cho, S-Y., "Efficient Information 842 Dissemination in Wireless Multi-Hop 843 Networks", Ecole Polytechnique PhD thesis, 844 Sept 2008. 846 [HKMKE03] Ho, T., Koetter, R., Medard, M., Karger, D., 847 and M. Effros, "The Benefits of Coding over 848 Routing in a Randomized Setting", 849 International Symposium on Information 850 Theory 2003, Jun 2003. 852 [CWJ03] Chou, P., Wu, Y., and K. Jain, "Practical 853 Network Coding", Forty-third Annual Allerton 854 Conference on Communication, Control, and 855 Computing 2003, Oct 2003. 857 [FWB06] Fragouli, C., Widmer, J., and J. Le Boudec, 858 "A Network Coding Approach to Energy 859 Efficient Broadcasting", INFOCOM 2006, 860 Apr 2006. 862 [SSMMB09] Sundararajan, J., Shah, D., Medard, M., 863 Mitzenmacher, M., and J. Barros, "Network 864 Coding Meets TCP", INFOCOM 2009, Apr 2009. 866 Appendix A. Network Coding Fundamentals 868 This section introduces network coding concepts and terminology. 870 Network coding differs from classical routing by permitting coding at 871 intermediate nodes. One possible coding algorithm is linear coding 872 that performs only linear transformations through addition and 873 multiplication Precisely, linear coding assumes identically sized 874 packets and views the packets as vectors on a fixed Galois field. It 875 becomes then possible to perform linear combination of packets. 877 A.1. Linear Coding 879 In the case of single source broadcast, all packets initially 880 originate from one source: the source has k packets, which may be 881 seen equivalently as k vectors P(1), ..., P(k) from the vector space 882 over a Galois Field. 884 With network coding, any coded packet received by node, at any point 885 of time, is a linear combination of some source packets. The i-th 886 received coded packet at a node v is necessarily a linear combination 887 of the source packets P(1), .... P(k) and can be written as: 889 q(v,i) = a(v,i,1) P(1) + ... + a(v,i,k) P(k) 891 The sequence of coefficients for a coded packet q(v,i) (denoted 892 "information vector", or simply "vector") is itself a vector 893 [a(v,i,1), a(v,i,2), ..., a(v,i,n)] (denoted "global encoding 894 vector"). 896 With linear coding, when one node generates a coded packet, it 897 performs a linear combination of the packets that it possesses (the 898 set of received packets { q(v,i) }) with some set of coefficients 899 (g(1), ...., g(M)). It then transmits the result: 901 generated_coded_packet = g(1) q(v,1) + ... + g(M) q(v,M). 903 Since the vectors q(v,1), ... q(v,M) are in turn linear combinations 904 of the source packets P(1),... P(k), the generated coded packet, can 905 be expressed itself as a linear combination of these, yielding its 906 global encoding vector. 908 In practice, a special header containing the global coding vector of 909 the transmitted code packet may be added as proposed by Chou et al. 910 [CWJ03]. 912 A.2. Random Linear Coding 914 As shown above, when a node generates a coded packet with linear 915 coding, an issue is how to select coefficients. Whereas centralized 916 deterministic methods exist, Ho and al. [HKMKE03] presented a novel 917 coding algorithm, which does not require any central coordination. 918 The coding algorithm is random linear coding: when a node transmits a 919 packet, it selects randomly the set of coefficients { g(i) }, which 920 will be used to perform a linear combination of the vectors q(v,M) as 921 indicated above. 923 A.3. Decoding, Vector Space, and Rank 925 A node v will recover the source packets P(1), ... P(k) its the 926 received packets q(v,1), ... q(v,M), considering the matrix of 927 coefficients a(v,i,j) for i=1,...M and j=1,..k from Appendix A. 928 Decoding amounts to inverting this matrix, for instance with Gaussian 929 elimination. 931 Thinking in terms of coding vectors, at any point of time, it is 932 possible to associate with one node v, the vector space, Q(v) spawned 933 by the coding vectors, and which is identified with the matrix. The 934 dimension of that vector space, denoted D(v), is also the rank of the 935 matrix. In the rest of this document, by abuse of language, we will 936 call "rank of a node", that rank and dimension. 938 The rank of a node is a direct metric for the amount of useful 939 received packets, and a received packet is called innovative when it 940 increases the rank of the receiving node. Ultimately a node can 941 decode all source packets when its rank is equal to the the total 942 number of source packets. 944 Appendix B. Acknowledgements 946 This document also stems from contributions of and from discussions 947 with : Philippe Jacquet. 949 Authors' Addresses 951 Cedric Adjih 952 Inria 954 Phone: +33-136-635-215 955 EMail: Cedric.Adjih@inria.fr 957 Songyean Cho 958 Samsung Electronics Co.,LTD.(*) 959 (*) Author(Songyean Cho)'s contribution was done before 960 joining Samsung Electronics. 962 EMail: Songyean.Cho@gmail.com 964 Emmanuel Baccelli 965 Inria 967 Phone: +33-169-335-511 968 EMail: Emmanuel.Baccelli@inria.fr 969 URI: http://www.emmanuelbaccelli.org/