The Research On Performance Evaluation And Optimization Techniques For Network Coding Based Data Transmission

Network coding allows intermediate nodes in networks to encode several receivedpackets into a single coded packet by using linear or non-linear processing before send-ing them out. It fundamentally renovates the idea of store-and-forward technique, andcan achieve the theoretic maximum throughput in multi-cast networks. The concept ofnetwork coding was first introduced in 2000, and since then it has triggered enormousresearch in both computer community and communication community. After a decadeof development, based on the theoretical work on network codes design, network cod-ing has been gradually applied in various fields, such as P2P systems, wireless networks,distributed storage and network security, which now becomes one of the hot spots forboth the academe and the industry. However, the traffic burstiness and the stochastic na-ture in information processing and transmission complicate the packet's behavior undernetwork coding, thus, modeling and analyzing network coding mechanism turn out to bevery difficult. Nevertheless, To deploy network coding in real-world applications andto design new protocols for network coding are largely relies on a better understandingof its performance in stochastic networks. The above contradiction constraints the fur-ther development of network coding. Therefore, this thesis focuses on four unsolved butimportant topics related to the performance analysis and the optimization techniques fornetwork coding based data transmission.To deploy inter-flow network coding efficiently dependents on the understandingof its end to end performance. However, since the traffic burstiness and the stochasticnature in information processing and transmission bring complex correlations betweenpackets from different flows, existing mathematic tools (e.g. Markov queueing analysisand network calculus) can not work directly for analyzing the end-to-end performanceof inter-flow network coding. To address this problem, In this thesis, with the theory ofstochastic network calculus, we first model the behaviors of inter-flow network coding ina single node, and obtain the coding superposition property and the coding output charac-teristic to ensure the tightness of performance bounds in modeling. Then, we extend theresults of a single node into acyclic stochastic networks, and based on the concatenationproperty, we propose several theorems and an algorithm to calculate the end-to-end delayand the throughput. The experiment results show that our approach avoids the cumulative deviation brought by the hop-by-hop analysis, and obtains tight end-to-end performancebounds under various network topologies.During the subgraph selection in stochastic networks, to decide which nodes arecompetent for the inter-flow network coding largely relies on the understanding of eachqueueing behavior. However, in a single node with bounded maximum opportunistic de-lay, the number of packets which can be coded together is a random variable, and the cod-ing operation leads to complicate queueing behavior, Thus traditional queueing analysisapproaches turn out to be unsuitable for analyzing these situations. To address this prob-lem, this thesis first build queueing system with multiple input flows and multiple queues,which the inter-arrival times of the input flows and the service time all follow arbitrarydistributions. Then, proposes a coding opportunity based queue decomposition techniqueto reduce the analysis complexity. The basic idea of this approach is that the coding op-portunitiescouldcharacterizethecorrelationsbetweenanytwoinputflows, thenbasedonthe coding opportunity matrix, it regards the opportunistic delay as a virtual service, andtransforms the original queueing system into several independentG/G/1 sub-systems, bywhich we could easily compute the performance of interests. In experiments, throughthree cases with gradually increasing complexity, we validate our approach, which couldobtain performance of interests with high precision.To decide an optimal value of the segment granularity is important for random lin-ear network coding based data dissemination systems. However, the existing work oftenuse simulations or measurements to do so, which are time-consuming and waste a largeamount of resources. Due to the feedback control mechanism with breaking messages forthesuccessivesegmentsexchanging, theperformanceanalysisonthesegmentgranularityis not trivial. To handle this problem, this thesis utilizes the queueing theory to build abatch queues with multiple input flows and feedback controls, then propose an averageinter-segment block loss based approximation method to compute the distribution of theinter-departure time. By using the average inter-segment block loss, the post-departureepoch probability of the queue length can be transformed into the probability of the num-berofcodedblocksfedintothequeueduringtheservicetime. Thissimplifiestheanalysisofthecomplexqueueingsystem. Withthisapproach,weevaluatetheperformanceonseg-ment granularity through four aspects, including control overhead, computation complex-ity, block efficiency and inter-decoding delay. Finally, a P2P streaming system is used as an example to illustrate the optimal value of the segment granularity not only maximizesthe transmission efficiency, but also guarantees the playback QoS. Comprehensive simu-lation results shows that our approach precisely characterizes the performance metrics onsegmentgranularity,andtheoptimalvalueofthesegmentgranularityfurtherimprovesthetransmission efficiency for random linear network coding based P2P streaming systems.To minimize redundant paths needed is a vital problem for the inter-flow networkcoding based IP congestion control. One solution is to divide the input flows into severalcoding groups. However, the input flows fed into a router may have diverse rates, andmay belong to different transmission modes (e.g. unicast or multicast), therefore, how tofind a optimal solution within a large amount of feasible grouping results is an intricateproblem. To solve this problem, this thesis first formally define the redundant path build-ing problem, which is proved to be NP-hard. Then from the perspective of graph theory,we propose an algorithm called FlowGrouping to to find its approximate solution. Thisalgorithm transforms the original problem into a clique partition problem by adding edgeweights in a weighted undirected graph. Through four steps, including undirected graphtransform, minimum clique partition, stable clique selection and clique merging, Flow-Grouping can obtain a tight solution within O(n3) computation time. In order to supportFlowGrouping, wealsodesignanintegrateframeworkforIPcongestioncontrol, inwhichthe dynamic queue thresholds are used to detect congestion. The experiment results indi-cate that the FlowGrouping embedded IP congestion control mechanism groups the inputflowsefficientlyand largelyreduces the numberof redundantpathsneeded. Furthermore,it achieves a better packet loss rate compared with other existing mechanisms.