VPLS中具有时延约束机制的组播问题研究

Study on the Delay-constrained Multicast Issue in VPLS Networks

VPLS作为一种革新的技术受到了广泛的关注和认可。但是,在用VPLS承载数据业务的时候还面临着一个复杂的难题:组播问题。传统的组播问题是具有NPC复杂度的Steiner问题。本文试图从应用和实现的角度出发,建立具有时延约束机制的组播转发机制。以建立最小时延树和最小开销树作为初始条件,运用循环迭代算法,求解满足时延约束的最小开销树。算法的复杂性为O(n2)。作为补充,还提出了组播树的剪枝机制。试验结果表明,文中的算法简单可行,易于实现,适合应用于VPLS网络中。

VPLS has gained world-wide recognition in recent years. However, deploying VPLS in Metro is confronted with one complicated issue： the muhicast problem. Instead of solving the NP-Complete Steiner tree problem, this paper emphasizes more on the experiential and implemental aspect of multicast in VPLS network. It begins with the construction of least cost tree（LCT） and least delay tree（LDT）, then an iterative algorithm is proposed to construct all the delay-constrained candidate trees, the one with least cost is chosen. To avoid unwanted traffic sent to PE devices, a pruning mechanism is also suggested. Compared with Steiner solutions, the algorithm is more suitable for implementation as the time complexity is only O（n^2 ）. Simulation result shows that the algorithm is feasible and suitable in building delay-constrained multicast trees over VPLS domain.