Internet DRAFT - draft-wang-roll-data-robustness
draft-wang-roll-data-robustness
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]
