一种最小代价组播树的快速算法

本文对KMB算法进行了改进,提出了一种快速的最小代价组播树算法,它只需使用一次PR IM算法,也不需要判断叶结点,从而快速地获得了最小代价组播树,减少了算法的运行时间。随机网络模型的仿真实验表明:该算法的计算时间远小于KMB算法,是一种快速、稳定、高效的算法。

基于主干树的最小代价组播路由算法

提出基于主干树的最小代价组播路由算法 ,该算法首先在网络中找出 K个代价最小的结点 ,然后以这K个结点形成一棵树 ,并称这棵为主干树 ,然后将不在主干树上的成员结点加入到树上 ,最后剪去非成员的叶结点。该算法的时间复杂度 O(n3)。该算法所构造的组播树代价略低于 MPH算法和 KMB算法。

IP编码网络及其优化算法

为了克服当前IP网络的带宽瓶颈问题,提出了一种基于网络编码的IP网络通信机制—IP编码网络。该文讨论了网络节点上包的代数运算与路由协议的结合方式,提出了IP编码网络中单、组播通信的实现方法。在此基础上,对应于现有最短路径、最小代价组播树的网络优化问题,提出了一种基于遗传算法的IP编码网络优化算法。该算法为单播和组播会话构造一个在最大流约束下通信代价优化的编码子网。算法的模拟实验结果表明对任意的单播和多源组播通信,都可以在有限的计算代价和计算时间内生成通信子网,有效减少了IP编码网络的编码开销和通信代价。该文的研究工作为网络编码的应用作了有益的实践探索。