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

Xiaoqing XU; Hong TANG; Ke RUAN; Juan WU; Xiaojun LIU

doi:10.11959/j.issn.1000-0801.2021137

您当前的位置：

首页 >

文章列表页 >

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

Research and Development | 更新时间：2024-06-05

- Topology design and capacity planning of wide-area network based on delay constraint
- Telecommunications Science Vol. 37, Issue 6, Pages: 132-141(2021)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-0801.2021137
  CLC： TN915
- Published Online：2021-06，
  
  Published：20 June 2021
- 稿件说明：
移动端阅览
Xiaoqing XU, Hong TANG, Ke RUAN, et al. Topology design and capacity planning of wide-area network based on delay constraint[J]. Telecommunications science, 2021, 37(6): 132-141.
DOI：

Xiaoqing XU, Hong TANG, Ke RUAN, et al. Topology design and capacity planning of wide-area network based on delay constraint[J]. Telecommunications science, 2021, 37(6): 132-141. DOI： 10.11959/j.issn.1000-0801.2021137.

摘要

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

Abstract

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.

关键词

Keywords

references

PIÓRO M , MEDHI D . Overview [M ] // Routing,Flow,and Capacity Design in Communication and Computer Networks . Amsterdam : Elsevier , 2004 : 3 - 36 .

VUTUKURY S , GARCIA-LUNA-ACEVES J J , . A simple approximation to minimum-delay routing [R ] . Defense Technical Information Center , 1999 .

GILGUR A , ECK B . Sources of Traffic Demand Variability and Use of Monte Carlo for Network Capacity Planning [J ] . 2014 .

中国电信集团有限公司 . 低时延光网络技术白皮书 [R ] . 2016 .

China Telecommunications Group Co.,Ltd . White paper of low lantency optical network technology [R ] . 2016 .

MEDYA S , BOGDANOV P , SINGH A . Towards scalable network delay minimization [C ] // Proceedings of 2016 IEEE 16th International Conference on Data Mining (ICDM) . Piscataway:IEEE Press , 2016 : 1083 - 1088 .

MEDYA S , RANU S , VACHERY J , et al . Noticeable network delay minimization via node upgrades [J ] . Proceedings of the VLDB Endowment , 2018 , 11 ( 9 ): 988 - 1001 .

PAROTSIDIS N , PITOURA E , TSAPARAS P . Selecting shortcuts for a smaller world [C ] // Proceedings of the 2015 SIAMInternational Conference on Data Mining . Philadelphia,PA:Society for Industrial and Applied Mathematics , 2015 .

关怀庆 , 张毕西 , 欧江艳 . 贪婪取走启发式算法在离散网络选址中的研究 [J ] . 系统科学学报 , 2010 , 18 ( 3 ): 49 - 52 , 56 .

GUAN H Q , ZHANG B X , OU J Y . The study of greedy dropping heuristic algorithm in discrete network location [J ] . Chinese Journal of Systems Science , 2010 , 18 ( 3 ): 49 - 52 , 56 .

REESE J . Solution methods for the p-Median problem:an annotated bibliography [J ] . Networks , 2006 , 48 ( 3 ): 125 - 142 .

曹晓宏 , 徐思雅 , 周桂平 , 等 . 面向多层次、多指标的光网络规划与评估方法 [J ] . 电信科学 , 2019 , 35 ( 9 ): 58 - 68 .

CAO X H , XU S Y , ZHOU G P , et al . Multi-level and multi-index planning and evaluation method for optical network [J ] . Telecommunications Science , 2019 , 35 ( 9 ): 58 - 68 .

NACE D , PIORO M . Max-Min fairness and its applications to routing and load-balancing in communication networks:a tutorial [J ] . IEEE Communications Surveys ＆ Tutorials , 2008 , 10 ( 4 ): 5 - 17 .

JAIN S , KUMAR A , MANDAL S , et al . b4 [J ] . ACM SIGCOMM Computer Communication Review , 2013 , 43 ( 4 ): 3 - 14 .

Views

199

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Study on digital twins in network lifecycle management

Research on 5G base station radiation safety and corresponding network planning

Wireless network planning of typical SG-IoT

Multi-level and multi-index planning and evaluation method for optical network

A QoS-based network planning method for power fiber to the home

Related Author

Ye OUYANG

Aidong YANG

Guo CHEN

Jie SUN

Jianchao GUO

Xiaowen SUN

Tao SUN

Da WANG

Related Institution

AsiaInfo Technologies (China) Co., Ltd.

China Mobile Research Institute

China State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications

State Grid Liaoning Electric Power Co.,Ltd.

Beijing Guodiantong Network Technology Co.,Ltd.

⁰