Network Working Group G. Wang Internet Draft G. Feng Intended status: Standards Track UESTC Expires: May 2014 November 29, 2013 Network Coding for Enhancing Data Robustness in Low-Power and Lossy Networks draft-wang-roll-data-robustness-00.txt 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 May 29, 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 carefully, as they describe your rights and restrictions with respect to this document. Abstract This document specifies a solution for improving the robustness of data transmission in multi-hop Low-Power and Lossy Networks (LLNs). It uses the network coding technique in conjunction with the Routing Protocol for LLNs (RPL) to increase the success rate of data Wang Expires May 29, 2014 [Page 1] Internet-Draft Network Coding in LLNs November 2013 collection at the sink node, with reasonable processing and traffic cost. Table of Contents 1. Introduction ................................................ 3 2. Terminology ................................................. 3 3. Protocol Overview ........................................... 5 4. Packet Format ............................................... 6 4.1. Coding Option .......................................... 6 4.2. Coding Control Messages ................................ 7 4.2.1. Degree Advertisement Message ...................... 7 4.2.2. Coding Period Start Message ....................... 8 4.2.3. Coding Procedure Pause Message .................... 8 5. Retrieve Information from Network ........................... 9 5.1. Sensor Nodes Number .................................... 9 5.2. Neighbor Nodes Number .................................. 9 5.3. Child Nodes Number .................................... 10 6. Coding Procedure Control ................................... 11 6.1. Coding Period ......................................... 11 6.2. Growth of Coding Degree ............................... 12 7. Coding Packet Processing ................................... 15 7.1. Coding Packet and Codewords ........................... 15 7.1.1. Codewords and Packets Transformation ............. 15 7.1.2. The Addition of Codewords ........................ 17 7.2. Receiving Packet ...................................... 18 7.3. Sending Packet ........................................ 19 7.4. Encoding and Decoding ................................. 21 8. Constants and Variables .................................... 21 9. Security Considerations .................................... 22 10. IANA Considerations........................................ 23 10.1. Additions to Hop-by-Hop Options ...................... 23 10.2. New Registry for Coding Option's Flags ............... 23 10.3. Coding Control Message ............................... 24 10.4. New Registry for Coding Control Codes ................ 24 10.5. Child Flag ........................................... 24 11. References ................................................ 25 11.1. Normative References ................................. 25 11.2. Informative References ............................... 25 12. Acknowledgments ........................................... 26 Appendix A. Encoding and Decoding Algorithm ................... 27 A.1. Decoding .............................................. 27 A.2. Manage Codewords in the Codeword Cache ................ 28 A.3. Choose Codewords for Encoding ......................... 29 Appendix B. The Growth of Coding Degree ....................... 31 B.1. Calculate the Degree Transition Sequence .............. 31 Wang Expires May 29, 2014 [Page 2] Internet-Draft Network Coding in LLNs November 2013 B.2. Update the Degree Transition Sequence ................. 32 1. Introduction RPL [RFC6550] is a distance vector IPv6 routing protocol designed for Low-Power and Lossy Networks (LLNs). Such networks are typically constrained in node's processing power and storage capacity, and the quality of the link between nodes is usually poor. Experiments have shown that RPL can work well in LLNs. However, data transmission in such networks is vulnerable to packet loss, delay and congestion. With network scaling up, the number of hops to the data collection node increases. It is difficult to deliver data to the destination, due to lack of data reliability mechanism. This document proposes a solution to the aforementioned problem. It uses a network coding scheme in conjunction with the Routing Protocol for LLNs (RPL) to increase the success rate of data collection at sink node with reasonable processing and traffic cost, and thus enhance the robustness of data transmission in LLNs. The network coding scheme used in this document is based on Growth Codes [Kamra06]. This document only discusses the case of multipoint- to-point UDP traffic. Discussions on point-to-multipoint or point-to- point traffic may be included in future documents. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119 [RFC2119]. In this document, these words will appear with that interpretation only when in ALL CAPS. Lower case uses of these words are not to be interpreted as carrying RFC-2119 significance. Additionally, this document uses terminology from [RFC2460] and [ROLL-TERMS], and introduces the following terminology: Symbol: a Symbol include the data generated by a node, which is to be transmitted to the sink, and the descriptive information about the data. Codeword: In the encoding procedure, multiple Symbols can be "XORed" together to generate a codeword. A codeword is constituted of data and its descriptive information. Wang Expires May 29, 2014 [Page 3] Internet-Draft Network Coding in LLNs November 2013 Coding Packet: the IPv6 packet which encapsulates a codeword. Codeword Cache: a part of memory allocated to temporarily store the codewords extracted from receiving Coding Packet. Coding Procedure: the functions a node performs to encode or decode data. When a node performs encoding, it uses codewords in the Codeword Cache and the codeword contained in the packet to be sent to generate a new codeword by using XOR operation. Subsequently, the new codeword is encapsulated in a Coding Packet and transmitted. When a node (usually the data sink) performs decoding, it extracts a new codeword from the receiving packet and executes the decoding function with this codeword and Codeword Cache as input, hopefully to generate new Symbols. Symbol Cache: a part of memory allocated to temporarily store the Symbols as output of the decoding function. Coding Complexity: the number of Symbols, which are "XORed" together to form the codeword. Coding Degree: the same with the Coding Complexity, Degree in short. Regular Packet: when a node receives a Coding Packet, if this packet's link layer destination is the receiver, this packet is called a Regular Packet. Overheard Packet: in contrast to the Regular Packet, if the received packet's link layer destination is not the receiver, but the receiver still accepts this packet, this packet is called an Overheard Packet. Neighbor Node: The neighbors of a node are the nodes that are located in the node's communication range. Child Node: The children of a specific node are the nodes which choose this node as the preferred parent in the RPL topology. Promiscuous Mode: in this mode, a node receives not only Regular Packets, but also Overheard Packets. DA: Degree Advertisement Message (see section 4.2.1). CPS: Coding Period Start Message (see section 4.2.2). CPP: Coding Procedure Pause Message (see section 4.2.3). Wang Expires May 29, 2014 [Page 4] Internet-Draft Network Coding in LLNs November 2013 3. Protocol Overview This document specifies a solution to enhance the robustness of data transmission in the networks which run IPv6 and RPL protocol. In the network, RPL constructs the topology called DODAG. This specification divides the data transmission procedure into multiple periods. In every period, sensors generate data, encapsulate it into Coding Packet and send it out. Sensors also encoding the packet received from other nodes and forward it towards the data sink. Meanwhile, the data sink receives Coding Packets from the nodes around it and decodes them to retrieve original data. Sensors perform the Coding Procedure to generate a new Coding Packet, then send the packet to the next hop determined by the RPL protocol. The Coding Procedure uses the "XOR" Operation, where multiple codewords are combined together in a bit-wise XOR manner. Such an operation's computational cost is relatively low, which meets the constraints of LLNs. A node may retransmit some of those packets it received to prevent packet loss due to poor link quality or channel collision. According to the Growth Codes' principle, the codeword's Coding Complexity grows gradually in a period, thus the amount of duplicate packets that the data sink receives is reduced. When a node sends out a packet, not only the next hop node will receive this packet, but all the neighbors of the sender will overhear and receive it. The neighbors which perform listening will re-code packets and send the Overheard Packets. In this way, the possibility that data reaches to the data sink is increased. The data sink calculates the Coding Complexity according to the quantity of original data it has retrieved. When the Coding Complexity increases, the sink broadcasts a DA message, and when a sensor sends a Coding Packet, the packet will carry the information of Coding Degree. When a sensor receives a DA message, it updates its Coding Degree. Sometimes, a sensor may firstly increase its Coding Complexity according to the number of packets it has sent. Considering that the packets far away from the sink will have a lower possibility to arrive at the sink, sensors take precedence to forward those packets. Data sink has a Symbol Cache and a Codeword Cache. The Symbol Cache is used for storing the original data of the contemporary period, and the Codeword Cache is for caching the codewords which could not be decoded immediately. Different from the sink node, sensors only need Codeword Cache for packets used in the Coding Procedure, including the packet sent out by the node itself and those packets received from other nodes. The size of these caches SHOULD be configured according to node's storage capacity. Wang Expires May 29, 2014 [Page 5] Internet-Draft Network Coding in LLNs November 2013 4. Packet Format This document defines a Hop-by-Hop option and a new kind of ICMPv6 Message. 4.1. Coding Option The coding option is used for depicting the network coding information in the packet. Coding option is encapsulated in the IPv6 Hop-by-Hop Options Header, so that the node on the packet's transmission path can properly process the packet. The format of the coding option is as follows: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Opt Data Len | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Flags |Version| Send Count | Degree | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | (Source Addresses...) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: Coding Option Option Type: TBD1. Opt Data Len: 8-bit field indicating the length of the option in octets, excluding the Option Type and Opt Data Len fields. Flags: 4-bit field. Currently the coding flags are defined as follows: Degree Update "U": 0x08. This flag is used for advertising that the receiver should update its Coding Degree to the value of Degree in this option. If a sending packet's degree is equal to the sender's Coding Degree, this flag SHOULD be set, otherwise this flag is cleared. Degree Advertisement "A": 0x04. This flag indicates that the receiver SHOULD update its Coding Degree to value (Degree- 1). If the sending packet's degree is greater than the sender's Coding Degree, this flag SHOULD be set, otherwise it should be cleared. This Code "T": 0x02. This flag indicates that the packet's sender requests the receiver to retransmit the data generated by Wang Expires May 29, 2014 [Page 6] Internet-Draft Network Coding in LLNs November 2013 the sender. When sending the next packet, the receiver SHOULD choose the sender's data to encode and send. Version: 4-bit sequence number used for distinguishing the packets of different period. Send Count: 8-bit fields representing the codeword's priority (see Appendix A.2). Degree: 8-bit fields representing the Coding Complexity of this codeword. Source Addresses: the coding coefficients, which are derived from the data sources' IP address. In this document, each coefficient which occupies 8 bits, represents the IP address's lowest byte. The number of coefficients is determined by the Coding Degree, thus this field is variable length. This option has no multi-byte field, so there is no alignment requirement. 4.2. Coding Control Messages 4.2.1. Degree Advertisement Message The sink node uses the Degree Advertisement Message to broadcast Coding Degree. This message is a type of ICMPv6 packet [RFC4443] and its format is shown 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type = TBD2 | Code = 0x00 | Check Sum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | InstanceID | DegreeAdv | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| Figure 2: Degree Advertisement Message Type: TBD2. Code: 0x00 indicates that this packet is used for advertising the Coding Degree. Check Sum: ICMPv6 packet's checksum. InstanceID: RPL instance identifier. Wang Expires May 29, 2014 [Page 7] Internet-Draft Network Coding in LLNs November 2013 DegreeAdv: the Coding Degree advertised by the sink node. Receiver SHOULD update its Coding Degree to the advertised degree. Reserved: this field is currently reserved and the sender should set it to zero. 4.2.2. Coding Period Start Message The Coding Period Start Message is carried by ICMPv6 packet, and its format is shown as follows. 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 = TBD2 | Code = 0x01 | Check Sum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| Figure 3: Coding Period Start Message Type: TBD2. Code: 0x01, this packet advertises that coding period starts. Check Sum: ICMPv6 packet's checksum. Version: 8-bit field representing the coding period's sequence number. Reserved: this field is reserved currently and the sender should set it to zero. 4.2.3. Coding Procedure Pause Message The Coding Procedure Pause Message is carried by ICMPv6 packet, and its format is shown as follows. 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 = TBD2 | Code | Check Sum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| Figure 4: Coding Period Pause Message Wang Expires May 29, 2014 [Page 8] Internet-Draft Network Coding in LLNs November 2013 Type: TBD2. Code: 0x02, this packet advertises that the Coding Procedure should be stopped temporarily. Check Sum: ICMPv6 packet's checksum. Version: 8-bit field representing the coding period's sequence number. Reserved: this field is reserved currently and the sender should set it to zero. 5. Retrieve Information from Network To guarantee that the protocol works properly, sensors and the data sink need some predefined configurations and information collected from the network. 5.1. Sensor Nodes Number It is difficult for every node to have the knowledge of the total number of nodes in the network. Before the network is deployed, the number of sensor nodes is hard-coded into every node. It is out of this document's discussion that the network's node number is variable. 5.2. Neighbor Nodes Number In order to facilitate calculation, the nodes treat themselves as a neighbor, and thus in the beginning, the number of a node's neighbor is 1. In this document, sensors need to count the number of neighbor nodes. Because sensors overhear all packets on the channel, they can record the source MAC address of the packet which identifies the neighbor. Nodes establish a table of neighbor information, whose entry includes the information listed below. neighbor_id: the neighbor's identifier derived from packet's source MAC address. alive_timer: the neighbor entry's lifetime, its initial value is set to NEIGHBOR_ENTRY_TIME. This field is decreased with time, when it reaches zero, the entry becomes invalid and should be removed from the table. flags: flags that indicate the neighbor's attributes. Currently defined flags are depicted below: Wang Expires May 29, 2014 [Page 9] Internet-Draft Network Coding in LLNs November 2013 Child "C": 0x80, indicating this neighbor is a child node. Next section will introduce this flag's usage. When a packet arrives, if its source MAC address is a unicast address, then the node searches the neighbor table to find if the corresponding neighbor entry is present. If not, then a new entry is added to the table and the entry's fields are initialized. Otherwise, the existing entry is updated, including the alive_timer field. A node determines the neighbor node number by the number of the neighbor entries. Note that the data sink should be excluded when collecting the neighbor information. Even if a node overhears to all packets on the link, the neighbor information may not be collected or will be removed due to the expiration of the alive_timer if there is no packet sent on the link. In this circumstance, this document provides a pair of Request/Response message to solve this problem. Before the neighbor entry is expired, the recording node sends a Request message. If the target neighbor is properly functioning, it will send back a Response message after receiving the Request message. The requesting node updates the target neighbor's entry when receiving the Response message. Since all sensors work under Promiscuous Mode, other nodes in the interactive nodes' communication range can also receive the Request/Response message, such that their neighbor information can be updated at the same time. An implementation MAY use the Neighbor Solicitation/Advertisement (NS/NA) in IPv6 Neighbor Discovery [RFC4861] to represent the Request/Response messages. 5.3. Child Nodes Number A child node must be a neighbor of a node, so the child node's information MAY also be saved in the neighbor information table. The child entry is distinguished from normal neighbor by the flags field of the entry. Specifically, the "C" flag (see section 5.2) is set in the child entry's flags field while it is cleared in the normal neighbor entry's flags field. Child entry's default lifetime which is used to initialize the alive_timer is CHILD_ENTRY_TIME. Under the Downward Routing Storing Mode of RPL, the RPL DAO message is always sent with link-local address, from child to parent node. Nodes can record the DAO message's source IP address to evaluate the child nodes number. In this document, it is assumed that a node's link-local IP address is derived from its MAC address, and thus it is equivalent to using the IP address or the MAC address to identify a node. Wang Expires May 29, 2014 [Page 10] Internet-Draft Network Coding in LLNs November 2013 The sending rate of DAO message gradually decreases due to the stabilization of the network. Thus in this specification, the reserved fields in DIO Message and NS/NA packet are utilized for facilitating the counting of child nodes number. The flags and reserved fields in DIO message are not used in the RPL specification. NS packet's reserved field has 4 bytes available and NA packet's flags and reserved fields have 29 bits available. This specification uses these available fields to carry child information. A child flag "C" is used in the three types of packets above. When the DIO's flags field is set with this "C" flag (see section 10.5), the reserved field of DIO represents the identifier of the sender's parent node, which is the lowest byte of the node's MAC address. If the DIO receiver is the target parent node that the reserved field stands for, the sender is added to the neighbor information table or it is updated as a child node. If the receiver is not the target parent, but the sender is recorded as the child of this node, the child entry is replaced with a neighbor entry of the sender. NS packet has no flags field. This document defines the first byte of the reserved field as flags field. When the flags field of NS is set with "C" flag, the sender is inquiring its child. The target NS receiver looks up the routing table to decide if the sender is the preferred parent. If the NS sender is the target receiver's parent, then the receiver sends a NA packet with the flags field set a "C" flag, acknowledging that the NA sender is the NS sender's child. When NS sender receives the NA packet, the NA sender is added to the neighbor information table as a child or the NA sender's child entry is updated. Nodes count the neighbor entries which set the child flag described in Section 5.2 to determine the child nodes number. 6. Coding Procedure Control 6.1. Coding Period In order to periodically transmit data, synchronization among all nodes is required, though it is not strict. This section introduces the mechanism to start and stop the Coding Procedure. The duration of the coding period is configured by the application and the Coding Procedure's start and stop are controlled by the coding module. Data sink sets T as the coding period, and broadcasts a Coding Period Start (CPS) message which will be flooded in the network. When a node receives a CPS message, it compares the message's Version field with its local record version which represents the node's coding period Wang Expires May 29, 2014 [Page 11] Internet-Draft Network Coding in LLNs November 2013 sequence number. If the message's version is higher, the node updates its local version, resets the Codeword Cache and enters a new coding period, and relays the start message. If the message's version is lower, the node does not update its local version but updates the message's Version field, then relays the message to notify the message's last sender. If the two versions are equal, then discards the message and does not do any more processing. If a node receives a Coding Procedure Pause (CPP) message, then it compares the versions like the CPS message. If the message's version matches the local version and the Coding Procedure is running, the Coding Procedure is stopped until next coding period starts and the CPP message is relayed. If the two versions are the same but the Coding Procedure has already stopped or the pause message's version is inconsistent with the local version, then this message should be ignored. If a node receives a Coding Packet when Coding Procedure is paused, then discards the packet and broadcasts a CPP message to notice the neighbors. When Coding Procedure is running and a node receives a Coding Packet, it compares the Version field of the packet's coding option to the local version. If the local version is lower than the coding option's Version, then local version is updated, the Codeword Cache is reset and the node reloads the Coding Procedure, and sends out a CPS message. If the local version is higher, which indicates the data is obsolete, the data sink or sensors should discard this packet, and send out a CPS message to inform the neighbors to get to the next coding period. When a sensor needs to send a Coding Control message (CPS, CPP), it MUST postpone the sending by a random range of time to avoid nodes sending packet synchronously, which causes collisions in the wireless channel. The data sink does not need back off when sending Coding Control message. 6.2. Growth of Coding Degree According to the number of packets it receives, the data sink decides the time when to increase and advertise the Coding Degree. The sensors propagate the degree information by piggybacking it in the Coding Packets. A node needs the following variables to maintain the Coding Degree: o N: the network's scale, i.e., the number of sensors in the network. The Data sink additionally needs the following data: Wang Expires May 29, 2014 [Page 12] Internet-Draft Network Coding in LLNs November 2013 o R: the degree transition sequence. o NsRecv: the number of different Symbols that the data sink has received. o DegExp: the Coding Degree of the packet that the data sink expects to receive. The data sink controls the growth of Coding Degree as follows: 1. The sink initiates the variables mentioned above: R is initialized according to N (see Appendix B.1). DegExp is set to 1 and NsRecv is set to 0. 2. If a Coding Packet Pr is received, and Pr's Coding Degree is less than DegExp, or Pr's Coding Degree equals to DegExp and the Coding Option's Flags field of Pr sets the "U" flag, the sink broadcasts DA message with Coding Degree DegExp to its neighbors. 3. If Pr is decoded successfully and a new Symbol is generated, the data sink updates NsRecv. If NsRecv is equal to or greater than R[DegExp], the sink increases DegExp until NsRecv is less than R[DegExp] or DegExp reaches MAX_DEGREE, and broadcasts DA message with the new Coding Degree to its neighbors. 4. Repeat Steps 2 and 3, until the Coding Procedure is paused or new coding period begins. The sensors additionally need the following data: o K: the degree transition sequence. o DegCur: the current Coding Degree. o BoolDegState: the current Coding Degree's state which is a Boolean value. When it is TRUE, DegCur has been updated by DA message or Coding Packet. When it is FALSE, DegCur has been updated by the increment of the number of sending packet. o NumRegular: the number of Regular Packets a sensor has sent. o NumOverhear: the number of Overheard Packets a sensor has sent. The sensors control the growth of Coding Degree as follows: Wang Expires May 29, 2014 [Page 13] Internet-Draft Network Coding in LLNs November 2013 1. The sensor initiates related variables: it calculates the sequence K according to N (see Appendix B.1), sets DegCur to 1, sets BoolDegState to TRUE, sets NumRegular and NumOverhear to 0. 2. A sensor receives a DA message, which broadcasts a Coding Degree DegAdv. If DegAdv is more than DegCur, the node updates DegCur to DegAdv, sets BoolDegState to TRUE, and updates the sequence K (see Appendix B.2). If DegAdv equals to DegCur and BoolDegState equals to FALSE, BoolDegState is set to TRUE and the sequence K is updated. 3. A sensor sends a Coding Packet Ps. If Ps's Coding Degree is equal to DegCur and BoolDegState is TRUE, the packet's Coding Option's Flags is set with the "U" flag. If Ps's Coding Degree equal to (D_now-1) and BoolDegState is TRUE, the packet's Coding Option's Flags is set with the "A" flag. In other cases, the "U" and "A" flag are cleared. 4. A sensor receives a Coding Packet Pr with degree DegAdv and Pr's Coding Option's Flags field is set with the "U" flag. If DegAdv is more than DegCur, the node updates DegCur to DegAdv, sets BoolDegState to TRUE, and updates K. If DegAdv equals to DegCur and BoolDegState is FALSE, then BoolDegState is set to TRUE, and the sequence K is updated. 5. A sensor receives a Coding Packet Pr with degree DegAdv and Pr's Coding Option's Flags field is set with the "A" flag. If (DegAdv-1) is more than DegCur, DegCur is updated to DegAdv, BoolDegState is set to TRUE, and the sequence K is updated. If (DegAdv-1) equals to DegCur and BoolDegState is FALSE, the node sets BoolDegState to TRUE, and updates the sequence K. 6. The sensor checks the number of packets it has sent. If ( NumRegular + NumOverhear ) > K[DegCur] Then DegCur is increased until the above expression is false or DegCur reaches its maximum value and sets BoolDegState to FALSE. 7. Repeat Steps 2 to 6, until the Coding Procedure is paused or new coding period begins. Since the nodes located in the network edge have fewer packets to send, it is difficult to encode high degree packet. But, it is possible to re-code high degree packets at intermediate nodes. Thus, those nodes in the edge of the network need not to use the same degree distribution, and the sensor's increment of degree (DegCur) is Wang Expires May 29, 2014 [Page 14] Internet-Draft Network Coding in LLNs November 2013 limited by the node's hop count. For example, the nodes whose hop count is 1 can reach a degree of MAX_DEGREE, hop count 2 nodes can reach (MAX_DEGREE-1)...hop count H nodes can reach MAX(MAX_DEGREE- H+1,2). When a sensor runs the above control procedure, this limit should be considered at first. 7. Coding Packet Processing Sensors run in Promiscuous Mode at data link layer, to receive packets including those whose destination is not this node. Sensors associate every packet with a variable, CodeFlags, to save flags. When CODES_FLAG_PROMISCUOUS is set, the associated packet is treated as an Overheard Packet whose destination is not the receive node. When the CODES_FLAG_PROMISCUOUS flag is cleared, the associated packet is a Regular Packet which should be sent to this node. Since sensors run in Promiscuous Mode, data can be disseminated more widely so that it can flow through multiple paths, increasing the possibility that the data reaches the data sink. By receiving the Overheard Packet, sensors can collect more data from other nodes. Thus there are more coding opportunities, which makes the diffusion of data more effectively. 7.1. Coding Packet and Codewords 7.1.1. Codewords and Packets Transformation Almost all nodes in LLNs are resource constrained including the storage. In order to cut down the requirement of memory, received packets are not directly added to the Codeword Cache, but the coding data and its related information are extracted from the packet and saved as codewords. In this way, redundant fields in the packet are elided. When decoding or encoding, reading data from codewords is more convenient than that from the original packets. An item of Codeword Cache SHOULD include the fields listed below: payload_length: indicating the length of the packet's data that is the IP packet excludes IP header and Hop-by-Hop Options Header. hop_limit: the Hop Limit field of the IP packet which is used by the router to decide if drop the packet. next_header: the Next Header field in the Hop-by-Hop Options Header. version: the Version field of the Coding Option. Wang Expires May 29, 2014 [Page 15] Internet-Draft Network Coding in LLNs November 2013 flags: saving flags for Coding Procedure. This field is initialized to zero. degree: the Coding Degree of the codeword, corresponding to the Degree field of the packet's Coding Option. The maximum Coding Degree defined in this document is MAX_DEGREE. src_ids: the codeword's coding coefficients extracted from the Coding Option's Source Address field. In order to facilitate encoding and decoding, the src_ids are sorted in ascending order. Original packets' source IP address which is utilized to calculate the checksum in the transmission layer, can be recovered according to the coding coefficients. data: the coded data, that is, the part of a packet represented by the payload_length, which is the payload after Hop-by-Hop Options Header. send_count: this field represents the sending priority of cached codewords corresponding to the Send Count field of the packet's Coding Option, and thus only used by sensors. The codewords in the Codeword Cache are sorted according to the degree and send_count. That is, firstly, the less the send_count, the more precedent the codeword is; and secondly, the higher the degree is, the prior the codeword is. Then minimum value by which send_count can be increased or decreased is PRI_UNIT. The following fields of a Coding Packet are not saved to the Codeword Cache, since they can be recovered from common knowledge or coding information. Because of IPv6, The Version field of all IP packet is set to 0x06. The Traffic Class and Flow Label fields in an IP packet that encapsulates the UDP data is set to zero. The Coding Packets which include a Coding Option must have a Hop-by-Hop Options Header, so the Next Header field in the IP Header is always set to 0x00. Source Address also does not need to be saved, since it can be recovered from the coding coefficients. Destination Address is elided in the cache because all the Coding Packet's destination should be the sink node. Any Coding Packet whose destination is not the sink node should be dropped quietly. Because only the sink node is the Coding Packets' destination, there is no problem with this processing method. Management of the Codeword Cache, such as replacement strategy of a codeword in the Codeword Cache, may influence the coding efficiency. It is out of this document's scope to determine an optimal method to Wang Expires May 29, 2014 [Page 16] Internet-Draft Network Coding in LLNs November 2013 manage the Codeword Cache. An implementation may refer to the method in the Appendix A.2. Besides the above rules, when transforming a codeword to a packet, if the codeword has degree one, the coding coefficient is used to recover the new packet's Source Address. If the codeword's degree is more than 1, the coding node's IP address is used as the new packet's Source Address. The RPL option [RFC6553] and Coding Option should be removed, since they are used in the link local scope and the information they carried has been read by the current node. Also, the Pad1 and PadN option should be removed because they carry no information. When converting a codeword to a packet, RPL option and Coding Option should be added to the Hop-by-Hop Options Header. To meet the alignment requirement of the extension header and options, the Pad1 and PadN option may be added into the header. The header's Length field is computed according to the total length of the options in the header. 7.1.2. The Addition of Codewords The addition of codewords is how to combine multiple codeword together to generate a new codeword. The codewords' data field is added in a bitwise "XOR" manner. If the codewords' payload_length is different, then the codewords which has smaller payload_length is padded with zero. Therefore, the addition also be called the "XOR" operation. The following text depicts how to perform addition on the other fields of the codeword. 1. The payload length of codewords may be different, since the corresponding Coding Packet may carry data with different length or have different extension headers. In this document, the codewords which have different payload_length can be coded together, and the packets that have smaller length are padded with zero bytes. In this way, the new codeword's payload_length field is set to the maximum value of payload_length among the packets participating in coding. Thanks to the length field of UDP packet [RFC768], it is easy to remove the padding and recover the original payload after transforming codewords to Coding Packet. 2. In order to keep the validity of hop_limit, the minimum value among the coding involved codewords is chosen as the new codeword's hop_limit. Wang Expires May 29, 2014 [Page 17] Internet-Draft Network Coding in LLNs November 2013 3. The next_header field of degree-one codeword indicates the next extension header type or the upper layer protocol type of the original packet. This field of degree-more codeword is the "XOR" result of multiple codewords' corresponding field. For example, if two degree-one codewords' next_header is 17(UDP), and another degree-one codeword's is 0(Hop-by-Hop Options Header), then the new codeword's this field is 0 (17 XOR 17 XOR 0). This field is used for identifying the next header and will not be read by the intermediate node, so coding this field is feasible. The decoding node will recover this field along with the coding data. 4. When encoding two codewords, the common coefficients of the two will be eliminated. Specifically, the new codeword's src_ids field is the combination of the two's excludes those common ones, thus the degree of the new codeword is calculated as follows: degree_new = degree_a + degree_b - common_degree; 5. Only the codewords which has the same version field can be coded together, and thus the new codeword's version field is the same with the old ones'. 6. When encoding two codewords, if one of the codewords' send_count equals to zero, the new codeword's send_count field is equal to another codeword's send_count. Otherwise, the send_count of the new codeword is a relatively small value of the two codewords' send_count. 7.2. Receiving Packet All packets are received at the link layer and the network coding module only needs to process those Coding Packet (and in this document, only UDP packet will be coded). Hence a packet filter should be added to drop those packets which need not to be processed, so as to reduce the processing cost of sensors. After IP header is handled at the network layer, the Hop-by-Hop Options Header of the packet will be checked. If no Hop-by-Hop Options Header or no Coding Option in the Hop-by-Hop Options Header presents, this packet is not a Coding Packet. If such a packet's CodeFlags is set with the flag CODES_FLAG_PROMISCUOUS, it should be quietly dropped, since it is an overheard non-Coding Packet, such as those UDP data which need not be coded or ICMP messages. If the flag CODES_FLAG_PROMISCUOUS is not set, the packet is a non-Coding Packet, and should be processed according to the regular IP routine. Wang Expires May 29, 2014 [Page 18] Internet-Draft Network Coding in LLNs November 2013 If a Coding Option exists there, this packet is a Coding Packet and needs to be re-coded and forwarded by the sensors or be decoded by the sink node. After re-coding or decoding, if a new packet is generated, the CODES_FLAG_PROMISCUOUS flag should be cleared from its CodeFlags field. This document sets the sink node as Coding Packet's destination, and thus all nodes only deal with the packets whose destination is the sink node, and other packets should be directly dropped with no more processing. If a Coding Packet is received, and its destination is the sink, the sensor reads the Coding Option, retrieves the packet's coding information, and adds the packet to the Codeword Cache. If the received packet is an Overheard Packet, the sensor does not forward the packet immediately but backs off a random time to encode and forward it. Otherwise, the received packet is re-coded and the new packet is forwarded at once. If re-coding is needed, the coding algorithm (see section 7.3) is performed to generate new codeword and Coding Option is added to it to generate a new Coding Packet. Before the new packet is sent out, RPL option should be added. If re-coding is not needed before forwarding, the RPL option of the received packet is updated. If the data sink receives a Coding Packet whose destination is the sink, then it tries to decode the packet (see section 7.3). If decoding succeeds, new Symbols are generated and transformed into a packet. The new packets are processed by the network layer like other non-Coding Packet, and delivered to the upper layer. The packet which cannot be decoded immediately is moved to the Codeword Cache. If multiple Symbols are produced in one decoding function, those Symbols should be processed successively. 7.3. Sending Packet In Promiscuous Mode, nodes will receive two type of Coding Packets, i.e., Regular Packet whose link layer destination is the receiver and Overheard Packet whose link layer destination is not the receiver. Obviously, a node cannot forward all the Overheard Packets. Otherwise, it is prone to produce broadcast storm when neighbors relay each other's packets in the dense node area. This document specifies a forwarding strategy which combines the sending of the two kinds of packets. Firstly, when receiving a Regular Packet, the sensor immediately re-codes and relays it, to minimize the delay of the packet. Secondly, to avoid the situation that too many Overheard Packets are sent out in the dense node area and guarantee that there are some Overheard Packets to be sent in the Wang Expires May 29, 2014 [Page 19] Internet-Draft Network Coding in LLNs November 2013 sparse node area, this document considers that the send count of Regular Packets and Overheard Packets is in proportion to the number of neighbors and the number of child nodes. Assuming that the number of neighbors of a node is denoted by NumNeighbor, and the number of child nodes is NumChild, then the number of non-child neighbors is (NumNeighbor - NumChild). Suppose that the number of Regular Packet which the node has sent is NumRegular, and NumOverhear is the number of Overheard Packet the node has sent, then a node can forward an Overheard Packet if the following condition is satisfied: NumOverhear/NumRegular <= (NumNeighbor-NumChild)/NumChild The procedure of sending packet is presented below: 1. If a Regular Packet Pr is received, and Pr has not been relayed, Pr is re-coded and sent. If Pr has been sent before, and NumOverhear/NumRegular >= (NumNeighbor-NumChild)/NumChild Pr is also re-coded and forwarded. 2. If an Overheard Packet Po is received, and NumOverhear/NumRegular < (NumNeighbor-NumChild)/NumChild back off a random time, and then the node encode and forward a new Coding Packet. 3. If Regular Packet is sent, NumRegular is increased. While overheard Coding Packet is sent, NumOverhear is increased. When one of these values is increased, the degree growth algorithm should be performed (see section 5.2). According to the settings specified in this document, only the UDP packets that sensors send to the sink node need the coding processing, while the sink node sends packets without coding. Besides, all the control messages should not be coded. The packet that does not contain Coding Option is treated as a non-Coding Packet, so if a packet needs not be coded, MUST not add a Coding Option to it. In order to enable the sensor to flexibly send Coding Packet and non- Coding Packet, an implementation SHOULD provide an interface for the upper layer. When sending Coding Packet, this interface sets the packet's associated variable CodeFlags with the flag CODES_FLAG_ENCODE to let the coding module know the packet need to be coded. When a sensor sends out its own coding data, it should save the codeword to Codeword Cache. To ensure the sensor's own data to be Wang Expires May 29, 2014 [Page 20] Internet-Draft Network Coding in LLNs November 2013 delivered to the data sink, this Codeword should be stored separately from other received codewords to avoid it be replaced by new codewords. 7.4. Encoding and Decoding The encoding function inputs one or more codewords, "XORs" them together and generates a new codeword. The operation and the output of the encoding function are determined, but the input, that is, how to choose the source codewords is not determined by this document. There may be many algorithm to choose codewords to gain high coding efficiency, and this document specifies one in the Appendix A.3. Given the coding information carried by the Coding Option, which provides the coding coefficients, decoding can be performed. This document illustrates the decoding algorithm in Appendix A.1. 8. Constants and Variables The following is a summary of constants and variables adopted by this document: T: the duration of coding period whose value is 120 seconds. NEIGHBOR_ENTRY_TIME: the lifetime of neighbor entry in the neighbor information table. Its default value is 15 seconds. CHILD_ENTRY_TIME: the lifetime of child entry in the neighbor information table. Its default value is 20 seconds. CODES_FLAG_PROMISCUOUS: this is a flag used for setting the variable CodeFlags. It indicates the associated packet is an Overheard Packet. Its value is 0x0001. CODES_FLAG_ENCODE: this is a flag used for setting the variable CodeFlags. It indicates the associated packet need to be coded. Its value is 0x0002. MAX_DEGREE: the Coding Degree's upper limit. Setting a limit for the Coding Degree is for limiting the packet's overhead and the computational complexity when degree grows. Its value is 16. PRI_UNIT: the unit of the codeword's priority. Its value is set to 4. Wang Expires May 29, 2014 [Page 21] Internet-Draft Network Coding in LLNs November 2013 9. Security Considerations This document mainly aims at the implementation of data transmission, and security schemes are not the goal, so this section only mentions some primary threat to this specification. Additionally, IPsec [RFC4301] has put forward a security architecture for the Internet layer, RPL [RFC6550] has given a framework for routing in LLNs, and other documents may propose new security solutions for this specification. Nodes in LLNs communicate on the wireless channel. This specification provides that a node can overhear all the packet on the wireless channel. So an attack node can easily eavesdrop in the same way. If active attack node is present, then the coding data may be tampered and injected into the network again, which will pollute a large amount of coding data in the network. Furthermore, if hostile nodes irregularly send the DA message, a node's Coding Degree may growth too quickly, resulting in efficiency degradation of the coding algorithm. If the hostile nodes send the Coding Control message (CPS, CPP) at the wrong time, it usually makes nodes pause the Coding Procedure and drop the packets from neighbors, result in denial of service. Since those fake nodes may not run according to the RPL protocol and this specification, they cannot be treated as neighbor nodes or child nodes. A node can hardly recognize a fake node, so there may be a deviation on the count of neighbors and child nodes, which can affect the protocol's performance. In order to ensure that the protocol is running properly, confidentiality must be provided, that is, the source of a packet must be credible and the packet must not be modified during the transmission. Generally, a data authentication scheme is needed to provide confidentiality. To protect packets from eavesdropping, an encryption mechanism should be adopted and both symmetric encryption and public key encryption can be an alternative method. However, the nodes in LLNs is resources limited, therefore, the security mechanism must be provided with relatively low cost. The solution like IPsec-AH and IPsec-ESP may not fit for the resources constrained nodes. Wang Expires May 29, 2014 [Page 22] Internet-Draft Network Coding in LLNs November 2013 10. IANA Considerations 10.1. Additions to Hop-by-Hop Options IANA has created a registry for the Hop-by-Hop Options. This document defines the Coding Option, which carries coding information including coding coefficients. The Option Type's value is as follows: Hex Value Binary Value act chg rest Description Reference --------- --- --- ------- -------------- --------------- TBD1 01 1 xxxxx Coding Option [This document] Figure 5: Details of the Option Type's value As specified in IPv6, the first two bits indicate that the IPv6 node MUST discard the packet if it doesn't recognize the option type. Because the packet including this option was coded, the node which do not realize the coding option can't further handle it. Since the packet needs to be re-coded during transmission, it may be modified by the intermediate node and the Type value's third bit is set to 1. IANA is requested to assign a new value for the Coding Option in the Hop-by-Hop Options registry to replace TBD1 before publication [RFC5226]. 10.2. New Registry for Coding Option's Flags IANA is requested to define a new registry for the Coding Option's Flags field. The flags can be set in the Flags field is depicted below: +-------+-----------------------------------+-------------------+ | Value | Meaning | Reference | +-------+-----------------------------------+-------------------+ | 0x08 | Degree Update | This document | +-------+-----------------------------------+-------------------+ | 0x04 | Degree Advertisement | This document | +-------+-----------------------------------+-------------------+ | 0x02 | This Code | This document | +-------+-----------------------------------+-------------------+ Figure 6: Coding Option's Flags The details of these flags are described in section 4.1. Wang Expires May 29, 2014 [Page 23] Internet-Draft Network Coding in LLNs November 2013 10.3. Coding Control Message Coding Control message is defined as a new type of ICMPv6 informational message, which is used for the control of Coding Procedure and the degree growth during the Coding Procedure. IANA has created a registry for the ICMPv6 Type number and IANA is requested to assign a number between 0x80~0xFF for the Coding Control message to replace the value TBD2 in this document before publication. 10.4. New Registry for Coding Control Codes IANA is requested to define a new registry for the Coding Control Message's Codes. The Codes' value and meaning are illustrated in the following figure: +-------+-----------------------------------+-------------------+ | Value | Meaning | Reference | +-------+-----------------------------------+-------------------+ | 0x00 | Degree Advertisement Message | This document | +-------+-----------------------------------+-------------------+ | 0x01 | Coding Period Start Message | This document | +-------+-----------------------------------+-------------------+ | 0x02 | Coding Procedure Pause Message | This document | +-------+-----------------------------------+-------------------+ Figure 7: Coding Control Message's Codes The details of the Codes field are described in section 4.2. 10.5. Child Flag IANA is requested to assign a new flag value used for the RPL DIO's Flags field. This new flag's value is TBD3, and should be replaced by the IANA assigned value before publication. IANA is requested to assigned a new flag value used for the NA's Flags field. This new flag's value is TBD4, and should be replaced by the IANA assign value before publication. Since NS has no flags field and this document defines the first byte of the reserved field as flags field, IANA is requested to create a new registry for the NS flags field. IANA is also requested to assign a value to the Child Flag (in section 6.3). The new entry should be tracked with the following properties: Wang Expires May 29, 2014 [Page 24] Internet-Draft Network Coding in LLNs November 2013 +-------+-----------------------------------+-------------------+ | Value | Meaning | Reference | +-------+-----------------------------------+-------------------+ | 0x80 | Child Flag | This document | +-------+-----------------------------------+-------------------+ Figure 8: new Flags registry for the NS packet 11. References 11.1. Normative References [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J.,Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, JP., and Alexander, R., "RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks", RFC 6550, March 2012. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC2460] Deering, S. and Hinden, R., "Internet Protocol, Version 6 (IPv6) Specification", RFC 2460, December 1998. [RFC4443] Conta, A., Deering, S., and Gupta, M., "Internet Control Message Protocol (ICMPv6) for the Internet Protocol Version 6 (IPv6) Specification", RFC 4443, March 2006. [RFC768] Postel, J., "User Datagram Protocol", RFC 768, August 1980. [RFC4861] Narten, T., Nordmark, E., Simpson, W., and Soliman, H., "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, September 2007. [RFC6553] Hui, J., and Vasseur, JP., "The Routing Protocol for Low- Power and Lossy Networks (RPL) Option for Carrying RPL Information in Data-Plane Datagrams", RFC 6553, March 2012. [RFC5226] Narten, T. and Alvestrand, H., "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 5226, May 2008. 11.2. Informative References [Kamra06] Kamra, A., Misra, V., Feldman, J., and Rubenstein, D., "Growth codes: Maximizing sensor network data persistence", ACM SIGCOMM Computer Communication Review, Vol. 36, No. 4, pp. 255-266, September 2006. Wang Expires May 29, 2014 [Page 25] Internet-Draft Network Coding in LLNs November 2013 [ROLL-TERMS] Vasseur, JP., "Terminology in Low power And Lossy Networks", Work in Progress, March 2013. 12. Acknowledgments This document was prepared using 2-Word-v2.0.template.dot. Wang Expires May 29, 2014 [Page 26] Internet-Draft Network Coding in LLNs November 2013 Appendix A. Encoding and Decoding Algorithm A.1. Decoding Data sink maintains a Codeword Cache and a Symbol Cache, which are denoted by CodeCache and SymbolCache respectively, to be used for decoding. When the sink receives a valid Coding Packet Pvc, it should conforms to the following rules to perform decoding: 1. If Pvc's Coding Degree is one, Pvc is transformed into a Symbol; if Pvc's degree is more than one, it is transformed into a codeword denoted by Cw. 2. Simplifying the codeword Cw by the SymbolCache, i.e., performing addition on Cw with the known Symbols in SymbolCache, if Cw contains them. The simplification removes the known data in Cw. After simplification, if Cw's degree reaches 1, then Cw is transformed into a Symbol. 3. Simplifying Cw by CodeCache, i.e., performing addition on Cw with the known codewords in CodeCache, if Cw contains them. After simplification, if Cw's degree reaches 1, then Cw is transformed into a Symbol. 4. Simplifying CodeCache by Cw, i.e., performing addition on codewords in CodeCache with Cw. If a codeword in CodeCache contains Cw, Cw is removed from the codewords. After simplification, the degree-1 codewords in CodeCache are transformed into Symbols. 5. In the above rules, if a Symbol is generated and it is not put in SymbolCache, it is denoted by S here. S is put into SymbolCache and CodeCache can also be simplified by S like the rule 4. 6. During the simplification, if Cw's degree reaches zero, that is to say, there is no new data carried by codeword Cw, the decoding function thus ends here. A codeword in the CodeCache should also be removed if its degree reaches zero or it is transformed into a Symbol. 7. Through the above rules, if Cw's Coding Degree is still more than one, Cw should be added to CodeCache for future decoding. When a new Symbol presents, it should be recovered as an IP packet to be delivered to the network layer for later processing. Wang Expires May 29, 2014 [Page 27] Internet-Draft Network Coding in LLNs November 2013 A.2. Manage Codewords in the Codeword Cache Codeword Cache size depends on the storage size of the node. However, usually the sensor's storage is constrained which limits the number of codewords in the Codeword Cache, and thus the coding opportunity is decreased. In order to reduce the influence of memory size, the sensor needs to manage the Codeword Cache. The codewords that no more need to be sent should not be put in the Codeword Cache; and some codewords in the Codeword Cache may become obsolete with the growth of Coding Degree and the increasing of their send_count, which should be removed when there is no more space to save new codeword in the Codeword Cache. In the Codeword Cache, codewords are sorted by the send_count and degree fields of each item. A node updates the value of send_count through receiving and sending Coding Packets. The larger the value of send_count is, the lower the codeword's priority is. When a sensor receives a codeword from the lower rank node, this codeword's send_count is increased by P1; when receiving a codeword from the equal rank node or sending a codeword, this codeword's send_count is increased by P2; when receiving a codeword from higher rank node, this codeword's send_count is increased by P3. To ensure the data which is further from the sink can reach the sink with a relatively high possibility, the following inequality should be satisfied: P1 > P2 > P3; Thus, let P1 = 32*PRI_UNIT, P2 = 4*PRI_UNIT, P3 = -2*PRI_UNIT. Let CodeCache denotes the Codeword Cache, DegCur denotes the current Coding Degree. If a sensor receives a codeword Cr, the following rules should be observed to decide how to store the codeword: 1. If Cr has been in the CodeCache, i.e., Cr equals to CodeCache[i] which denotes one of the codewords in the Codeword Cache, then Cr is discarded and the send_count of CodeCache[i] updated according to where Cr is received. 2. If Cr includes CodeCache[i], then Cr is simplified by CodeCache[i] (see Appendix A.1) and the send_count of CodeCache[i] is updated according to where Cr is received. 3. When CodeCache[i] includes Cr, if CodeCache is not full, then CodeCache[i] is simplified by Cr; and if CodeCache is full, and CodeCache[i]'s degree is less than DegCur, Cr is discarded; otherwise CodeCache[i] is replaced with Cr. Wang Expires May 29, 2014 [Page 28] Internet-Draft Network Coding in LLNs November 2013 4. If CodeCache is not full, Cr should be stored in CodeCache. 5. When CodeCache is full and Cr's degree is higher than DegCur, if the maximum degree of the codewords in CodeCache is lower than Cr's, then drops Cr; otherwise, the codeword whose send_count is the largest should be replaced with Cr. 6. If CodeCache is full and Cr's degree is lower than DegCur, the codeword whose send_count is the largest in the Codeword Cache, should be replaced with Cr. 7. If the content of the Codeword Cache is changed, it is necessary to sort the Codeword Cache again according to the degree and send_count. A.3. Choose Codewords for Encoding The following variables are defined at first to depict the encoding method: o DegCur: current Coding Degree of the sensor. o CodeCache: the Codeword Cache. o ThisCode: the codeword which is constructed from the data generated by the node itself. o BoolNewCode: a Boolean variable indicating if the method has chosen a codewords which has never been sent before. When the method starts, this variable is initialized to FALSE. o CodeNew: this is a memory block used for saving the new codeword. How to choose codewords to generate a new codeword whose degree is no more than DegCur is described as follows: 1. CodeNew is initialized as an empty codeword whose degree is zero. When a codeword is chosen for encoding, it should be added to the new codeword CodeNew. That is: CodeNew = CodeNew + CodeChosen ; 2. There may be a codeword designated to be encoded in CodeNew. It may be ThisCode or other codeword in the Codeword Cache. It should be encoded in CodeNew firstly. Wang Expires May 29, 2014 [Page 29] Internet-Draft Network Coding in LLNs November 2013 3. If a node has sent out its own data and it has never been acknowledged, the node may choose ThisCode to be encoded in CodeNew if it is not the designated codeword in the step 2. 4. Search for codeword which can be encoded in CodeNew from the Codeword Cache. The codeword with the highest priority is checked at first. The current checked codeword in the Codeword Cache is denoted as CodeCache[i]. If CodeCache[i], is the designated codeword in step 2, this codeword skipped. 5. If CodeCache[i]'s send_count is more than MAX_SEND_COUNT, it should not be sent any more. When a codeword's send_count reaches MAX_SEND_COUNT, it has been sent for many times or it has been acknowledged by the node which is close to the sink. The constant MAX_SEND_COUNT depends on the unit value of priority PRI_UNIT, in this document, it is set to (32*PRI_UNIT). Since the Codeword Cache is ascendingly sorted by the send_count value, when a codeword's send_count is greater than MAX_SEND_COUNT, the codewords after it should be ignored totally. 6. If a codeword that is never been sent is chosen for encoding, then sets BoolNewCode to TRUE. If BoolNewCode is TRUE and CodeCache[i]'s send_count field is 0, then this codeword is skipped. That is, in the encoding, only chooses one codeword that is never been sent by this node. 7. When CodeCache[i] is checked, evaluate the desired new code, which is the sum of CodeCache[i] and CodeNew. If the desired new code's degree is more than CodeNew and less than or equal to DegCur, then CodeCache[i] can be encoded into CodeNew. 8. When CodeCache[i] is chosen, accordingly change its priority, that is, the value of the send_count field of this codeword. Wang Expires May 29, 2014 [Page 30] Internet-Draft Network Coding in LLNs November 2013 Appendix B. The Growth of Coding Degree B.1. Calculate the Degree Transition Sequence According to Growth Codes, the data sink needs lower degree packet at first to retrieve original data, and higher and higher degree packet gradually to remove the redundancy of retransmission. Therefore, a degree transition sequence is needed to decide when to switch to higher Coding Degree. The degree transition sequence R of the sink is an integer array. The ith element of the sequence represents the number of different original Symbols that the sink needs to receive before expecting to receive a degree (i+1) packet. For example, if R[1]=5, R[2]=10, before expecting to receive degree-2 packets, the sensor needs to recover 5 original Symbols, and before expecting receive degree-3 packets, the sensor needs to recover 10 original Symbols. The elements of R are computed as follows according to Growth Codes: R[i] = ( i * N - 1 ) / ( i + 1 ); In which, i represent the current expecting Coding Degree. The degree transition sequence K of the sensors is an integer array, whose elements' value represent the number of packets a node need to send to switch to higher degree. For example, if K[1]=10 and a node wishes to send a degree-2 packet, it needs to send out 10 degree-1 packets at first. If K[2]=15, and a node wishes to send a degree-3 packet, it needs to send out 5 degree-2 packets firstly after switching from degree-1 to degree-2. The sequence K is computed as follows according to Growth Codes: 1. Create a sequence Rt which is the same to the sequence R of the data sink. Rt[0] is initialized to 0. 2. Create a sequence A, its elements are initialized by the following formula: A[j] = SUM{ C(N,j) / C(r,j-1) * (N-r) } R[j-1] <= r <= R[j]-1; In which, "SUM{*}" represents summation of the content. "C(n, k)" refers to the combination of taking k from n things. Wang Expires May 29, 2014 [Page 31] Internet-Draft Network Coding in LLNs November 2013 3. Initialize the sequence K by summarizing sequence A: K[i] = SUM{ A[j] } 1 <= j <= i; B.2. Update the Degree Transition Sequence The degree transition sequence is calculated by the network scale N. Since not every node can hear all the sensor nodes' data, the sequence is not precise enough for growth of degree. It is necessary to adjust the degree transition sequence during the Coding Procedure. To update the degree transition sequence, firstly compute a parameter ALPHA: ALPHA = ( NumRegular + NumOverhear ) / K[DegCur-1]; Then updates the sequence K as follows: K[i] = ALPHA * K[i]; Wang Expires May 29, 2014 [Page 32] Internet-Draft Network Coding in LLNs November 2013 Authors' Addresses Gang Wang UESTC (University of Electronic Science and Technology of China) No.2006, Xiyuan Ave, West Hi-Tech Zone Chengdu, Sichuan, P.R.China 611731 Phone: +86 151-8442-0373 Email: wanggang_uestc@163.com Gang Feng UESTC (University of Electronic Science and Technology of China) No.2006, Xiyuan Ave, West Hi-Tech Zone Chengdu, Sichuan, P.R.China 611731 Phone: +86 132-5825-6256 Email: fenggang@uestc.edu.cn Wang Expires May 29, 2014 [Page 33]