Multi-batch Pipeline Coding with Adaptive Redundancy Control (ARC) 

Get Complete Project Material File(s) Now! »

Inter- ow network coding (Opportunistic Network Coding)

In this section, we introduce one popular and practical inter- ow network coding scheme called Opportunistic Network Coding (ONC). ONC is rst introduced in COPE [2] which is applied to unicast trac in wireless network. ONC is a technique which combines packets (i.e., XORs them together) from trac ows traversing in opposite ways at an intermediate node called encoder. Encoded packets are then acquired to retrieve the original packets at decoders. ONC is a practical inter- ow network coding system of which design is based on two key principles:
No point-to-point assumption and exploitation of the broadcast nature of wireless networks: In conventional wireless networks, nodes always discard the nonintended packets even though they can overhear them due to adapting the principle of point-to-point transmission from wired networks. However, ONC can exploit the broadcast nature of wireless environment to use the overheard packets in the term of network enhancement.
Inter- ow network coding for wireless unicast trac: ONC practically mixes and transformes data from multiple ows and gain an extra of network throughput. Consequently, an enhanced network system is proposed.
ONC systems are heavily based on a coding condition to decide which ows are codable together because there’s no point to code packets without ensuring their successful decoding. In ONC, the coding chances are gained more based on how the coding condition is dened (i.e., covering more network owing cases). We will detail these in the next subsections.

Coding Opportunistically (COPE)

Figure 2-4(a) and 2-4(b) show how COPE works in the basic scenario. The dashed lines imply that the related nodes are neighbors (i.e., within the transmission range) to each other and the arrows indicate the direction of trac ows. Both end-toend connections go through the intermediate node C which serves as a forwarding node. Suppose that node A and B want to send packet p1 and p2 to node B and A, respectively. Without network coding, node C simply forwards packets p1 and p2 to the destinations using two separate transmissions. Using network coding, node C can smartly combine these two native packets by XOR-ing them together and broadcast he coded packet (p1+p2) to nodes A and B in a single transmissions. Nodes A and B will decode the coded packet to get the desired packet by XOR-ing the coded packet with the packet they originate. As a result, node C can save one transmission and improve the network utilization. Node C is called the encoder and two nodes A and B serve as decoders.
More coding scenarios are possible if we consider one important feature introduced by COPE: the opportunistic listening in which each wireless node can overhear other transmissions and use the overheard packets for later use (e.g, for the decoding process). Consider the scenario presented in Figure 2-4(b) in which nodes A, B, D and E wish to send packets p1, p2, p3 and p4 to its opposite nodes B, A, E and D, respectively. Each extremity node (A, B, D and E) will perform the opportunistic listening because it is the neighbor of the other nodes except its opposite node. C intelligently encodes four native packets to broadcast pc = p1 + p2 + p3 + p4. All receivers are able to extract the desired packets because they have collected suciently other packets for decoding. For example, node A can decode the coded packet pc to get p2 successfully because p3 and p4 are obtained from opportunistic listening (p3 and p4 are overheard by transmissions (D ! C) and (E ! C) respectively) and p1 is its own packet. In summary, COPE exploits the broadcast nature of the wireless channel to perform the opportunistic listening and opportunistic encoding, reducing the number of forwarded packets and improving the network utilization. Indeed, the ONC system needs to check if the ows are codable or not based on a coding condition. The coding condition in ONC will dene which ow is codable to another and which node is the encoder or the decoder. There is no point in creating the coded packets if they are un-decodable. To check the coding condition, COPE needs to obtain the « neighbor state », or which packets the neighbors could receive. In the absence of deterministic information, COPE utilizes a link state routing protocol with the link-quality routing metric ETX [19] to guess the « neighbor state » intelligently. Certainly, the node can make a false decision, reducing the coding chances by not coding the codable native packets or producing un-decodable coded packets. How to guess the « neighbor state » intelligently is quite challenged. In the scope of this thesis, we leave this problem open as we focus on a more certain existing problem: extending the coding condition of COPE to gain more coding chances.

Distributed Coding-Aware Routing (DCAR)

COPE has two separate limitations: the routing path dependency and the strict two- hop coding pattern. The rst limitation is that the coding chances inevitably depend on the established route. The best routing path (e.g., the shortest path) may not be the best coding-aware one. Consider the example in Figs 2-5(a) and 2-5(b) with two trac ows. Without being aware of the potential coding chances, two separate routing paths shown in Fig 2-5(a) may be chosen. On the other hand, if a codingaware routing decision is made, a common routing path via node 1 is used. Node 1 becomes the encoder and has the coding chance to generate the coded packets (in Fig 2-5(b)). In  this example, coding-aware routing will provide the improved performance.

MAC-layer proactive mixing for Network Coding (BEND)

Concentrating trac through only one encoder which is also the intersecting node of two ows like COPE or DCAR can cause the performance problem. Considering a wireless mesh network with dense trac, concentrating trac via the encoders result in packet collisions and packet drops at the intersecting node. The problem can be worse if the dropped packets are the coded ones. BEND is a MAC layer solution to practical network coding in multi-hop wireless networks, which solves the problem. In contrast to COPE and DCAR which use a single node to encode packets, BEND deploys a group of neighboring nodes which can share the encoding process, called the encoder group. In fact, the transmission of a node is heard by its neighbors, which can be used to encode the packets. In BEND, any node can code and forward a packet even when this node is not on the routing path of the packet, as long as it ensures that the decoding process can be successfully performed at the decoders to obtain the original packets.

READ  Comparative psychology and cooperative cognition in animals

Source coding versus batch coding

Random linear network coding (RLNC) has been introduced almost at the same time since the idea of network coding emerged. As shown in Figs 2-1(b) and 2.2, RLNC is focusing on « coding the packets belonging to the same trac ows ». The nature of wireless network tends to be error-prone and exposed to interference and congestion. To provide a simple and eective transmission reliability, instead of transmitting native packets in order, native packets are coded to broadcast the random linear combinations.
At recipients, innovative coded packets are stored until they are suciently decoded for original data. In lossy environments like wireless networks, a redundancy control is also needed to mitigate losses. Automatic Repeat Query (ARQ) [22] and Forward Error Correction (FEC) [50] are two techniques which can be used:
ARQ is an error-control method for data transmission relying on acknowledgements and timeouts to ensure the transmission reliability.
FEC is an error-control method for data transmission which allows sending the information along with some redundant data to control errors over the lossy communication environment.
In this thesis, we focus on FEC-related coding schemes, such as source coding scheme [51] and batch coding scheme [1, 9]:
Source coding scheme: the source generated innovative coded packets, along with some redundant coded packets, and transmits them to the destination. Forwarders only forward the coded packets to the destination.
Batch coding scheme: the source generated innovative coded packets, along with some redundant coded packets, and transmits them to the destination.
Forwarders perform the re-encoding process over the input coded packets, generate and transmit new linear network coding combinations to the destination.
In this section, we would like to show the popular coding schemes of RLNC. We present Batch Coding (Section 2.6.3), Pipeline Coding (Section 2.6.4) and TCP/NC (Section 2.6.5), along with some frequently used terms in Table 2.1. Throughout the examples in Figs 2-8, 2-9, 2-10, the xed redundancy control used in Batch Coding, Pipeline Coding and TCP/NC coding scheme has the redundancy level R = 1:25 per one transmission, which means 1 redundant transmission every 4 transmissions.

Table of contents :

1 Introduction 
2 Related work 
2.1 Network Coding and its benets
2.2 Linear Network Coding versus Non-linear Network Coding
2.3 Linear Network Coding – Deterministic versus Random
2.4 Network coding approaches in the thesis
2.5 Interow network coding (Opportunistic Network Coding)
2.5.1 Coding Opportunistically (COPE)
2.5.2 Distributed Coding-Aware Routing (DCAR)
2.5.3 MAC-layer proactive mixing for Network Coding (BEND)
2.6 Intraow network coding (Random linear network coding)
2.6.1 Source coding versus batch coding
2.6.2 Generation
2.6.3 Batch Coding
2.6.4 Pipeline Coding
2.6.5 Transmission Control Protocol with Network Coding (TCP/NC)
2.7 Applications of network coding into current network systems
2.7.1 Wireless networks Multi-hop tracows in wireless networks Broadcast in wireless networks Coding-aware routing metric Opportunistic routing
2.7.2 Ad-hoc sensor networks
2.7.3 Peer to peer (P2P) le distribution
2.7.4 Network security
2.8 Problem statement
2.9 Chapter conclusion
3 Interow network coding 
3.1 Distributed and Diused Encoding (DODE)
3.1.1 Coding chance improvement
3.1.2 Generalized coding condition of DODE
3.2 Distributed and Diused Encoding with Multiple Decoders (DODEX)
3.2.1 Coding chance improvement
3.2.2 Generalized coding condition of DODEX
3.3 Distributed and Diused Encoding with Multiple Encoders and Multiple
Decoders (DODEX+)
3.3.1 Coding chance improvement
3.3.2 Generalized coding condition of DODEX+
3.4 Design
3.4.1 Node architecture Neighbor list and source routing list Decoder list Queuing system
3.4.2 Routing metric with coding chance discovery for DSDV protocol – SPENM
3.4.3 Modied DSDV packet format
3.4.4 Node behavior COPE and BEND DCAR and DODE DODEX and DODEX+
3.5 Simulation and results
3.5.1 DODE
3.5.2 DODEX
3.5.3 DODEX+
3.6 Chapter conclusion
4 Intraow network coding 
4.1 Multi-batch Pipeline Coding with Adaptive Redundancy Control (ARC)
4.1.1 Design
4.1.2 DRTT estimation
4.1.3 Adaptive redundancy scheme
4.1.4 Node behavior
4.1.5 Simulation and results
4.2 Dynamic Coding (DynCod)
4.2.1 Packet denition
4.2.2 Design
4.2.3 Dynamic information vector
4.2.4 Adaptive redundancy control
4.2.5 Simplied encoding vectors to reduce overhead
4.2.6 Multipath DynCod (MP-DynCod) Design Forwarding belt assignment Feedback of link quality Adaptive redundancy control Node behavior
4.2.7 Simulation and results DynCod MP-DynCod
4.3 Chapter conclusion
5 Conclusion and Future Work 
5.1 Conclusion
5.2 Future Work
List of Publications
A Mathematical Background 
A.1 Linear Framework F2s
A.1.1 Encoding
A.1.2 Decoding
A.2 Matrix and Gaussian elimination
A.3 Finite eld operations
B Practical Considerations 
B.1 Decoding matrix
B.2 Decoding delay
C Ad-hoc routing protocols 
C.1 Destination-Sequenced Distance Vector (DSDV)
C.2 Ad-hoc On-demand Distance Vector (AODV)


Related Posts