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

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

作　　者：马娅婕[1] 田翔川[2] 

机构地区：[1]武汉科技大学信息科学与工程学院,湖北武汉430081 [2]帝国理工学院计算机系

出　　处：《小型微型计算机系统》2007年第4期631-634,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60202005)资助.

摘　　要：利用支配集可以将复杂的物理网络拓扑聚合成简单的虚拟拓扑,降低网络运行的开销.但是单纯考虑支配集合的大小并不能保证聚合后的拓扑具有最佳的性能.为此,本文对利用加权支配集的网络拓扑聚合方法进行了研究,构造了以带宽为权的支配集,使聚合后的网络在带宽方面具有更优的性能,并设计了一种计算复杂度为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.

关 键 词：加权支配集 线性规划 带宽约束 拓扑聚合 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]