Project topics and materials
Get Complete Project Material File(s) Now! »
Linear Network coding
Most practical works on the subject make use of linear network coding. Linear coding uses linear algebra to achieve packet coding: packets are considered as vectors and the combinations of packets are linear combinations. It has been proven that linear coding is sufficient to achieve the optimal throughput in multicast situations [5].
The coefficients chosen to compute combinations can be obtained in two manners:
• Deterministic linear coding: coefficients are deterministic and derived from a known algorithm
• Random linear coding: coefficients are randomly or pseudo-randomly generated It has been demonstrated that random coefficients for linear network coding nearly allow to reach network capacity in broadcast transmission schemes like wireless networks using a decentralized algorithm, provided the field size is sufficiently large [6].
The larger the field size, the higher the probability for the receiver to obtain linearly independent combinations. In practice, a field of 28 elements is used most of the time since it is sufficient to achieve a good decoding probability, and it allows better performance. The enhanced performance comes from the fact that symbols in this field are actual bytes. This allows to manipulate packet data directly without bit masks, and eases their manipulation as most systems operate on byte basis and not bit basis.
Network coding approaches
Considering the flows from which the packets are coded together, we can distinguish two main categories of approaches: inter-flow coding and intra-flow coding.
Inter-flow coding
Inter-flow network coding aims at maximizing network capacity by combining packets from different unicast flows at relays.
Packets from different flows are combined together in order to send less packets and reduce wireless transmission time. The idea is to to transmit only the necessary information accross links. The spared transmission time is available for other flows. The result is an increased throughput for each flow, and increased network capacity. The butterfly network presented in the previous section (Fig. 2.1) shows a classic example of how the available throughput can be increased.
One of the pioneering works for inter-flow network coding in wireless networks is COPE [7]. Each node taking part in COPE opportunistically combines packets belonging to different unicast flows. Like most inter-flow coding schemes, packet combinations are performed with XOR operations. COPE infers coding opportunities, i.e., packets that can be coded together and sent only once, from the knowledge of packets heard by each neighbor. The information is gathered by listening transmissions from neighboring nodes.
Intra-flow coding
Intra-flow network coding enables to increase flow reliability by combining packets from a single flow together. The idea is to send combinations of outgoing packets from the same flow rather than sending the packets themselves. At destination, Gauss-Jordan elimination is performed and all packets can be recovered if enough independent linear combinations have been received. Depending on the coding implementation, intermediary nodes can either recode packets by mixing forwarded combinations, or just forward them.
To compensate losses, more combinations than original packets can be generated. At destination, original packets can be decoded, provided enough independent combinations are received.
Intra-flow coding and multicast traffic optimization
When a unique source use a multicast flow to reach multiple destinations, packets follow a multicast tree. If branches of the tree have common nodes, intra-flow coding can enhance the capacity along the tree in the same way inter-flow coding can enhance network capacity, therefore increasing the possible multicast flow throughput. To illustrate this benefit, let’s consider a source node multicasting in a butterfly-shaped network with three routes to two destination nodes (Fig. 2.2). Each destination node wants to receive the entire multicasted flow, and each link is assumed to have a capacity of one packet per time unit and no loss.
If only classic forwarding of packets is allowed (left), only one packet can be transmittedon each link per time unit. Therefore, the maximum throughput for the flow is 1.5 packets per time unit to each destination, i.e., 3 packets per time unit in total. With intra-flow network coding (right), similarly to the inter-flow butterfly topology case, the total throughput can be enhanced to 4 packets per time unit.
Table of contents :
1 Introduction
1.1 Context and objectives
1.2 Contributions
2 Background on network coding
2.1 Introduction to network coding
2.1.1 Definition and benefits
2.1.2 Linear Network coding
2.2 Network coding approaches
2.2.1 Inter-flow coding
2.2.2 Intra-flow coding
2.3 Intra-flow coding applications
2.3.1 Intra-flow coding and multicast traffic optimization
2.3.2 Intra-flow coding and unicast flow reliability
2.4 Intra-flow coding implementation methods
2.4.1 Network coding redundancy
2.4.2 Generation-based coding
2.4.3 Sliding-window coding
2.5 Network coding for opportunistic routing
2.5.1 Definition of opportunistic routing
2.6 Conclusion
3 Dynamic redundancy
3.1 Objective and Motivations
3.2 Redundancy control mechanisms
3.2.1 Static redundancy
3.2.2 Loss rate measurement
3.2.3 Explicit feedback
3.2.4 Conclusion
3.3 Redundancy estimation
3.3.1 Generation loss probability bound
3.3.2 Redundancy lower bound
3.3.3 Non-innovative combinations leading to intrinsic loss
3.4 Distributed adaptive redundancy control
3.4.1 Network model
3.4.2 Algorithm at relays
3.4.3 Redundancy at the source
3.4.4 On-the-fly recoding vs delayed recoding
3.5 Simulation results
3.5.1 Loss bound evaluation
3.5.2 Distributed adaptive redundancy evaluation
3.5.3 Resilience to coding/no coding nodes
3.5.4 Impact of delayed recoding
3.6 Conclusion
4 Taking constraints into account
4.1 Introduction
4.2 Taking constraints into account
4.3 State of the art
4.4 Constraint-aware Network Coding Model
4.4.1 General principle
4.4.2 Redundancy Selection Algorithm
4.4.3 Algorithm at relays
4.4.4 Special case of the source
4.4.5 Special case of neighbors of the destination
4.5 Simulation results
4.5.1 Effect of the contribution factor
4.5.2 Impact of nodes with lower contribution factors
4.6 Conclusion
5 Fairness and interaction between network coding and TCP
5.1 Objectives
5.2 TCP and fairness considerations
5.3 Sensitivity to losses and unfairness
5.3.1 Link and congestion losses
5.3.2 Case of competing flows
5.4 Measuring fairness
5.4.1 Jain’s fairness index
5.4.2 Fair allocation with coded and non-coded flows
5.4.3 Formalization
5.4.4 Modified fairness index
5.5 Conclusion
6 Increasing reliability of MPTCP over network coding
6.1 Objectives
6.2 Multi-path TCP over network coding
6.3 Emulated network setup
6.4 Performance evaluation
6.4.1 Influence of loss rate and redundancy
6.4.2 Influence of generation size
6.4.3 Influence of Round-Trip Time
6.5 Conclusion
7 Integration of network coding in the MPTCP protocol
7.1 Objectives
7.2 Network coding integration in MPTCP
7.3 Principle
7.3.1 Activation
7.3.2 Coding
7.3.3 Decoding
7.3.4 Feedback mechanism
7.4 Implementation details
7.4.1 Data Sequence Signal (DSS) option
7.4.2 Component size
7.5 Performance evaluation
7.5.1 Scenario
7.5.2 Results
7.6 Conclusion
8 Conclusion
