随着多播技术的日渐成熟,多播技术的应用也受到广泛关注。由于KOD系统具有在单位时间内曲目被重复点播的频率较高、终端相互之间的网络带宽比较充裕等特点,因此应用多播技术比较适合。基于多播路由与Steiner树之间存在的对应关系,本文确定了KOD视频多播和Steiner树启发式算法作为本文的研究重点。文中介绍了多播视频路由技术;给出了Steiner树问题定义,并简要叙述了其精确求解算法、典型的启发式算法和贪心算法。本文将Chaining多播技术应用到KOD系统中,设计实现了相应的多播路由启发式算法。基于KOD系统的特点,分析了流服务器和客户端中各个模块的作用,以及内容制作中的码率控制。分析了应用层多播在KOD系统中的优势,并较为详细地叙述了流服务器直接提供客户端流服务和通过RTSP重定向技术实现间接服务两种情况下的通信流程。介绍了Chaining多播技术及其与P2P技术的关系,设计了基于Chaining多播思想的路由启发式算法,并将该算法和RTSP重定向技术相结合应用于KOD系统,试验证明取得了较好的效果。本文概括了典型启发式算法的框架,并在此基础上分别设计了基于路径中跳数和顶点度数的Steiner树的启发式算法,使每次添加的路径尽可能得到了重用。并针对每种算法,均举出图例说明了所设计的算法能求出最优解(最小Steiner树),而原来的算法得不到最优解,证明了所设计算法的正确性和优越性。并还简单分析了这些算法的最坏性能比的上界。本文完成了几种组合启发式算法的最坏性能比的分析。常用的启发式算法运行时间少、易于实现、求解质量较高,但不同启发式算法之间又具有不可比较性的特点,因此研究它们相互组合起来的性能具有一定的理论和实践意义。通过研究我们发现组合后启发式算法的性能上界是各个算法性能上界中最小的一个;组合启发式算法的上界是紧的;并且组合启发式算法确保了所求得的解是各个算法中最优的一个,保证了解的质量,弥补了仅用单个启发式算法求得的解的质量无法保证的不足。本文分别研究分析了相对贪心算法(RGA)和k-损失收缩贪心算法(k-LCA)的下