Multicast Technology In KOD And Steiner Tree Heuristic

The applications based on the multicast technology get more and more attention, while the technology progresses. The KOD (Kara OK on demand) system is suitable to apply the multicast technology because the content in KOD has more chance toshare among the terminals than other applications at the same time. Moreover, the network width among the terminals is wide. Considering the relation between the multicast routing and Steiner tree, the thesis points out the key points of the dissertation are the video multicast in KOD system, and the heuristics to Steiner tree. The thesis introduces the video multicast routing technology, Steiner tree definition, and several current widely-used heuristics.The thesis applies the Chaining multicast idea to the KOD system, designs and implement the heristic algorithm based on Chaining idea. According to the KOD system traits, it also analyzed the modules in the streaming server and client, as well as the rate control for the content produce. The advantages of the application layer multicast are also showed in KOD application. The RTSP communication operation processes are showed for both the direct service case and the redirect service case. It also introduces the Chaining multicast and its relation with current P2P technology. The heuristic algorithm based on Chaining is implemented in KOD system with the RTSP redirection. At last the experiments show it works well.The thesis generalizes the framework of heuristics. In order to re-use the edges in the selected path as many as possible, it designs several new heuristics, based on the number of hop and the number of vertex degree in the path respectively. Moreover, it designs the sample graph for every heurisitic where the modified heurisitic based on hop or vertex degree can get the optimal solution (the minium steiner tree), while the primary one can't achieve the optimal solution. The modified heuristics prove to be correct and better than the primary ones. The upper bounds of their worst-case performance ratios are also presented for the Steiner tree problem.The thesis investigates the combined heuristics and their worst-case performance ratios. The widely used heuristics need less running time and are easily implemented. Their performances are incomparable each other, so it is needed to investigate the performance of their combined heuristics from the academic view. The thesis points out the upper bound of...