Research Of Subgraph Partition Multirate Multicast Algorithm Based On Network Coding

Network coding has changed traditional routing with only store-and-forward, and it allows relay nodes to code the data they have received. Network coding has been a hot subject of the research field as a result of its throughput improvement on layered multicast network.This paper focuses on the multirate multicast based on network coding and makes the advantage of network coding to improve the throughput of multirate multicast, namely total receiving rate of receivers. After reviewing existing layered multicast problems based on network coding, this paper analyzes the advantages and disadvantages of existing algorithms. Furthermore, a heuristic algorithm of subgraph partition layered multicast has been proposed for the problem where the rate of each layer is uncertain. This paper has also made experiments and performance analysis of the proposed algorithms. The main work of this paper is following.The multicast and network coding techniques are first introduced where the typical technology of multirate multicast is emphasized. Then an overview of network coding has been describled focusing on the theoretical basis of network coding and linear network coding techniques.According to the problems about layered multicast based on network coding, an overview of the principles and basic mode of the layered multicast is proposed. In this overview, the problems of layered multicast have been divided into two categories accoding to the rate of each layer. Afterwards, we decrible the problems in detail focusing on the solutions of the layered multicast based on network coding. Meanwhile, the advantages and disadvantages are also analysised in detail.When taking into account the variable layer rate, the problem of layered multicast is described as the nonlinear integer programming problem which is very difficult to solve for large-scale network.In order to maximize the totol receivvering rates of the receivering nodes, a polynomial-time heuristic subgraph partition algorithm is designed which is based on the idea of minimal coding network. By increasing the reuse degree of links within the same layer, this algorithm is to minimal the links in each layer subgraph and remain more links to transmit the following layers. The experiments show that this algorithm can achieve better network performance when the time complexity is not high.