基于时延约束的广域网络拓扑设计和容量规划

Topology design and capacity planning of wide-area network based on delay constraint

为了优化网络性能和降低建设成本,应用线性规划和启发式贪婪取走算法,基于时延约束对广域网络规划中拓扑设计和容量确定问题进行研究。首先,考虑需求的权重,采用线性规划求解给定路径下的最低时延和最低时延下的最低成本扩容问题。其次,采用贪婪取走算法,以全局归一化时延增量作为取走候选链路标准,从全拓扑网络的候选链路集中得到满足时延约束的新增链路。此外,提出可以结合线性规划和贪婪取走算法实现时延约束下最低成本的新增链路及扩容。结果表明,本文提出的方法可以有效解决针对时延优化的广域网络规划中拓扑设计和容量规划问题。

In order to optimize network performance and reduce construction cost,the topology design and dimensioning problems in wide-area network planning were investigated based on delay constraint with the use of linear programming(LP)and heuristic greedy-drop algorithm.Firstly,demands’weights were considered and LP was exploited with given paths to solve the capacity expansion problems of minimum delay and minimum delay with minimum cost.Secondly,greedy-drop algorithm was applied and candidate edges were removed from full mesh topology according to the global normalized delay increments.Thus,new added edges to satisfy the delay constraint were determined.Moreover,the combination of LP and greedy-drop algorithm was proposed to determine new added edges and capacity expansion of the delay-constraint scenario with minimum cost.The results turn out that the proposed algorithms are effective to solve the problems of topology design and capacity planning in wide-area network planning targeting delay optimization.