摘要
未来应用场景对名字解析系统有着确定性时延保障的需求,如何有效选择测量节点,为确定时延名字解析提供支撑是本文着力解决的问题。本文将网络测量节点部署问题映射成为最小点覆盖问题,并基于传统的贪婪算法提出一种面向网络测量节点选取的改进贪婪算法,从优化贪婪算法迭代周期和针对实际场景特点改进排序算法2个方面进行优化。实验结果表明,基于改进贪婪算法的求解方式比传统贪婪算法的求解方式,平均耗时减少了90%以上。
In the future application scenarios,there is a need of deterministic delay guarantee for the name resolution system.How to effectively select measurement nodes and provide support for exact delay name resolution is the problem this article focuses on.This paper maps the network measurement scheduling deployment problem to the minimum vertex cover problem and proposes an improved greedy algorithm which mainly optimizes the greedy algorithm iteration cycle and improves the sorting algorithm in certain scenarios.The experimental results show that the improved greedy algorithm is more than 900%faster than traditional greedy algorithm.
作者
吴上
盛益强
邓浩江
WU Shang;SHENG Yi-qiang;DENG Hao-jiang(National Network New Media Engineering Research Center,Institute of Acoustics,Chinese Academy of Sciences,Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 100049,China)
出处
《计算机与现代化》
2021年第4期79-84,共6页
Computer and Modernization
基金
中国科学院战略性先导科技专项课题(XDC02070100)。
关键词
名字解析系统
信息中心网络
贪婪算法
最小点覆盖
name resolution system
information centric networking
greedy algorithm
minimum vertex cover
