网络拓扑聚合的带宽加权支配集算法研究

Research on MPLS Network Virtual Topology Aggregation Algorithm Based on Bandwidth Weighted Dominating Set

利用支配集可以将复杂的物理网络拓扑聚合成简单的虚拟拓扑,降低网络运行的开销.但是单纯考虑支配集合的大小并不能保证聚合后的拓扑具有最佳的性能.为此,本文对利用加权支配集的网络拓扑聚合方法进行了研究,构造了以带宽为权的支配集,使聚合后的网络在带宽方面具有更优的性能,并设计了一种计算复杂度为O(n),信息复杂度为O(Δn)的最小权支配集的并行近似算法.

Minimum dominating set can aggregate the complex network topologies into simple virtual topologies and reduce the cost of the networks. However, simply considering the size of dominating set can＇ t guarantee the performance of the networks after aggregation. So, a topology aggregation method based on weighted dominating set was considered which uses the bandwidth as the weight to satisfy the demand of bandwidth of the networks. Based on the research, a parallel approximation algorithm with O（n） computation complexity and O（△n） message complexity was designed.