基于组播转发状态的聚合模型研究与算法分析

摘要

IP组播在IP网络中实现了多点通信模型，促进了视频点播、音视频会议和数据分发等多点通信业务在互联网上的发展。同时，新兴的IPv6技术更增强了对组播的支持；再加上组播技术相对于单播与广播技术的巨大优势，组播技术的应用越来越广泛，网络应用的要求也越来越强烈，人们日益认识到组播技术所带来的优点与好处，其研究价值也越来越凸现出来。 组播采用树型转发结构实现单点对多点通信的支持，每一个数据包只在分叉节点处被复制，每一条链路只转发一次。这种方法使得IP组播能有效的同时向多个组成员发送数据，并且能够同时支持多个组播组。IP组播这种多点通信机制使之成为互联网中视频会议等高带宽、共享性应用的重要基础。 然而，组播共享树要求所有树上节点处的路由器均保持每一个组的转发状态。因此，当多个组播组并存时，IP组播遇到一系列问题：路由器的转发状态数会随网络中的组播组数量线性增长，不但增加了路由器额外的存储和CPU处理开销，而且导致了更加缓慢的转发过程，当组播会话数很多时，会耗费大量的资源和控制开销来管理组播组，制约了组播会话的可扩展性。也就是说，组播转发状态问题成为影响IP组播大规模扩展应用的一个瓶颈。 组播聚合模型是针对大规模组播扩展性问题，结合当前网络拓扑特点提出来的新思想，最早由UCLA网络实验室提出，并给出了基于该种模型的贪婪算法。其主要思想是：适当牺牲带宽，使能够复合的组播组共享一棵组播分发树，通过这种方式，网络中组播树的数目会大大减少，组播转发状态也随之减少，最终提高了网络性能。 本文在对传统组播聚合模型深入研究的基础上，提出了优化组播转发状态问题的两个方案：基于叠加树算法的优化方案和基于遗传模拟退火算法的优化方案。 1.基于叠加树的聚合算法借鉴了图论中“相似”的概念，将符合特定QoS要求的原始组播树进行叠加合并，然后按照树的定义对叠加树进行剪枝，去环等操作以获取聚合树集合。 仿真实验表明，叠加树算法在时间、聚合度及转发状态降低率方面均优于传统的贪婪聚合算法。 2.基于遗传模拟算法的优化方案中，模拟退火算法在理论上，经过足够长的时间会收敛到全局最优解；而遗传思想强调的是两代之间的进化关系，但其交配有可能使最优解遗失而陷入局部最优解；由此，本文给出了遗传模拟退火算法的设计方案。 组播聚合问题的数学本质是最小集合覆盖问题（MSCP），这是一个NPC问题。本文将遗传模拟退火算法应用到求解MSCP，进而对组播聚合问题寻优，最终获得近似于全局最优的准最优解。 仿真实验通过与贪婪算法、拉格朗日松弛算法进行比较来表明该算法在优化聚合度、转发状态降低率两个方面的优势。