多播路由算法MPH的时间复杂度研究

摘要

多播通信是从一个源点同时向网络中的多个成员发送分组的通信服务,一个最小代价的多播路由算法是NP完全的,在时间敏感的应用中其运行时间是一个关键问题.MPH(Minimum Path Cost Heuristic)算法是一个著名的启发式最小代价多播路由算法,本文对该算法进行了理论分析和证明,并做了广泛的仿真实验,结果表明其时间复杂度是O(m2n)而不是过去文献中所给出的O(m2n+e).