基于非线性规划的链路丢包率推理算法
顾然* 邱雪松 乔焰 李娟 孟洛明
北京邮电大学网络与交换技术国家重点实验室 北京 100876
Link Loss Inference Algorithm with Nonlinear Programming
Gu Ran Qiu Xue-song Qiao Yan Li Juan Meng Luo-ming
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
摘要 针对目前大多数链路丢包率推理算法不能兼顾精度和速度的问题，该文提出一种新的覆盖网链路丢包率推理算法，算法通过将链路丢包率推理问题转换为求解非线性规划的最优化解问题，从而较准确地计算出所有链路的丢包率。该算法仅需对每条端到端路径进行一次测量，且没有额外部署成本。通过软件模拟和Internet实验对算法性能进行了验证，实验结果证明了算法的可行性及优越性。
关键词 ：
网络测量 ,
网络层析成像 ,
单播 ,
链路丢包率 ,
非线性规划
Abstract ：To address the issue that most link loss rate inference algorithm can not take into account the accuracy and speed, a novel link loss rate inference algorithm of overlay network is proposed. This algorithm converts the link loss rate inference issue into solution of nonlinear programming issue in order to calculate the packet loss rate of all links more accurately and only needs to probe once for every path, with no extra deployment costs. Through software simulations and Internet experiments, the feasibility and superiority of this algorithm is proved.
Key words ：
Network measurement
Network tomography
Unicast
Link packet loss rate
Nonlinear programming
收稿日期: 2011-10-13
基金资助: 国家自然科学基金国家创新研究群体科学基金(61121061)，国家自然科学基金(60973108)，国家863计划项目(2011AA05A116)和国家973计划项目(2007CB310703)资助课题
通讯作者:
顾然
E-mail: guran@bupt.edu.cn
引用本文:
顾然, 邱雪松, 乔焰, 李娟, 孟洛明. 基于非线性规划的链路丢包率推理算法[J]. 电子与信息学报, 2012, 34(6): 1425-1431.
Gu Ran, Qiu Xue-Song, Qiao Yan, Li Juan, Meng Luo-Ming. Link Loss Inference Algorithm with Nonlinear Programming. , 2012, 34(6): 1425-1431.
链接本文:
http://jeit.ie.ac.cn/CN/10.3724/SP.J.1146.2011.01052 或 http://jeit.ie.ac.cn/CN/Y2012/V34/I6/1425
[1]
潘胜利,杨析儒,张志勇,钱峰,胡光岷. 单源多径路由网络拥塞链路识别
[2]
王晶,汪斌强,张校辉. 基于可重构测量模型的网络测量任务部署算法
[3]
伊鹏,钱坤,黄万伟,王晶,张震. 基于抽样流长与完全抽样阈值的异常流自适应抽样算法
[4]
侯颖, 黄海, 兰巨龙, 李鹏, 朱圣平. 基于自适应超时计数布鲁姆过滤器的流量测量算法
[5]
王聪, 张凤荔, 王瑞锦, 李敏, 杨晓翔. 一种网络时延矩阵分布式自适应重建算法
[6]
杨京礼, 孙超, 姜守达, 魏长安. 基于层次分解的网络链路时延分布快速推测算法
[7]
王聪, 张凤荔, 杨晓翔, 李敏, 王瑞锦. 支持入侵容忍的网络距离选举计算模型
[8]
周斌, 胡宏林. 提高蜂窝网络中数据分发效率的D2D协作转发算法
[9]
杨京礼, 许永辉, 姜守达. 基于最小覆盖集的高精度链路丢包率测量方法
[10]
费高雷, 胡光岷. 基于k 阶马尔可夫链的单播网络丢包层析成像
[11]
张志勇, 胡光岷. 一种新的故障链路识别算法RPI
[12]
张 震; 汪斌强; 陈庶樵; 朱 珂. 基于多维计数型布鲁姆过滤器的大流检测机制
[13]
费高雷; 胡光岷; 钱 峰. 一种非平稳网络链路丢包率层析成像方法
[14]
陈松,王珊,周明天. 一种新的物理网络拓扑发现算法
[15]
韦安明; 王洪波; 程时端. 基于分组抽样的P2P超级节点推测
2012, Vol. 34 
