Journal of Software:2017.28(7):1815-1834

(郑州航空工业管理学院 电子通信工程学院, 河南 郑州 450015;西北工业大学 电子信息学院, 陕西 西安 710072;中国人民解放军 32147 部队, 河南 商丘 476000)
Algorithm for Large Scale IP Network Multiple Link Congestion Inference
CHEN Yu,WEN Xin-Ling,DUAN Zhe-Min,LI Yu-Chong
(School of Electronics and Communication Engineering, Zhengzhou University of Aeronautics, Zhengzhou 450015, China;Institute of Electronic Information, Northwestern Polytechnical University, Xi'an 710072, China;Troop 32147, Chinese People's Liberation Army, Shangqiu 476000, China)
Chart / table
Similar Articles
Article :Browse 1565   Download 1062
Received:February 23, 2016    Revised:April 01, 2016
> 中文摘要: 基于最小集覆盖理论的拥塞链路推理算法,仅对共享瓶颈链路进行推理,当拥塞路径存在多条链路拥塞时,算法的推理性能急剧下降.针对该问题,提出一种基于贝叶斯最大后验(Bayesian maximum a-posterior,简称BMAP)改进的拉格朗日松弛次梯度推理算法(Lagrange relaxation sub-gradient algorithm based on BMAP,简称LRSBMAP).针对推理算法中链路覆盖范围对算法推理性能的影响,以及探针部署及额外E2E路径探测发包的开销问题,提出设置度阈值(degree threshold value,简称DTV)参数预选待测IP网络收发包路由器节点,通过引入优选系数ρ,在保证链路覆盖范围的基础上,兼顾开销问题,确保算法的推理性能.针对大规模IP网络多链路拥塞场景下,链路先验概率求解方程组系数矩阵的稀疏性,提出一种对称逐次超松弛(symmetry successive over-relaxation,简称SSOR)分裂预处理共轭梯度法(preconditioned conjugate gradient method based on SSOR,简称PCG_SSOR)求解链路先验概率近似唯一解的方法,防止算法求解失败.实验验证了所提算法的准确性及鲁棒性.
Abstract:Congested link inference algorithms only infer the set of share links based on methods of smallest set coverage. When some congested path contains more than one congested link, the inference performance is obviously descending. Aiming at this problem, a version of Lagrange relaxation sub-gradient algorithm based on Bayesian maximum a-posterior (LRSBMAP) is proposed. Aiming at the impacts of congested link inference performance in the different link coverage, and the cost problems of probe deployments and additional E2E active detection, the paper proposes a preliminary selection method for transceiver nodes by optimally selecting degree threshold value (DTV) parameter of IP networks. Through introducing the optimization coefficient ρ, problems of cost and link coverage can be both considered to ensure the performance of inference algorithm. In addition, according to the sparsity of coefficient matrix in link prior probability solution equations, a preconditioned conjugate gradient method based on symmetry successive over-relaxation (PCG_SSOR) is proposed to obtain approximate unique solutions, helping to avoid the solution failures in large scale IP networks under the scenarios of multiple link congestion. Experiments demonstrate that the algorithms proposed in this paper have higher accuracy and robustness.
文章编号:     中图分类号:    文献标志码:
基金项目:国家重点基础研究发展计划(973)(2012CB315901,2013CB329104);河南省高等学校重点科研项目(18A510019) 国家重点基础研究发展计划(973)(2012CB315901,2013CB329104);河南省高等学校重点科研项目(18A510019)
Foundation items:National Basic Research Program of China (973) (2012CB315901, 2013CB329104); Colleges and Universities Key Research Project of He’nan Province (18A510019)
Reference text:


CHEN Yu,WEN Xin-Ling,DUAN Zhe-Min,LI Yu-Chong.Algorithm for Large Scale IP Network Multiple Link Congestion Inference.Journal of Software,2017,28(7):1815-1834