Research On Resource Optimization Multicast Routing Algorithm With QoS Constraints Based On Network Coding

Network coding, as a novel technology, proposed by R.Ahlswede and Robert Li et al in 2000, has proved that the theoretical max-flow of any multicast is achievable. However, coding operations will lead to a rise of computational complexity and processing delay, which increases the multicast cost. On the other hand, the end-to-end delay and delay variation among destinations, as significant characteristics in multicasting, have to be considered to guarantee the effectiveness of data transmission and the fairness of multiple multicast users. Therefore, minimizing network coding resources with desired multicast rate, end-to-end delay and delay variation constraints among destinations in a multicast tree becomes one of the most practical problems in the field of network coding.Coding resource optimization network-coding-based multicast routing problem is thoroughly investigated, where the QoS constraints like desired multicast rate, end-to-end delay and delay variation among destinations, have been taken into account at first time. This thesis constructed a methmetical optimization model for this problem and then proposed a novel genetic algorithm called REGA (Routing-based Encoding Genetic Algorithm, REGA) to solve it, where the chromosome enconding scheme is based on source-to-destination routing. On the other hand, a special case of REGA called SREGA (Simple Routing-based Encoding Genetic Algorithm, SREGA) is also well designed, which deals with the network coding optimization problem without the consideration of delay constraints. The routing-based encoding scheme of REGA has two evident benefits for the REGA's performance:1). The length of the chromosome only depends on the number of destinations. Compared to the traditional binary encoding scheme based on the states of auxiliary links of merging nodes, the length of each choromosome in REGA is shorter, which can decrease the computational amounts while running REGA.2). REGA takes the desired multicast rate and end-to-end delay constraints into consideration while chromosome encoding. Each choromosome represents a multicast tree which subjects to multicast rate and to some extent, meets the delay constraints. This distinguished encoding scheme leads to a reduced size of search space and can help REGA acquire the optimized solution more likely.Finally, experimental simulations over several network scenarios have been conducted, and the numerical results show that SREGA is characterized by high convergence speed and strong global search ability without the introduction of delay constraints; Further more, REGA is also superior over other algorithms in many aspects while considering delay constraints, which provides a solid demonstration that REGA is more suitable to sovle network coding resources optimization problem with QoS constraints in multicast network.